Godel's incompleteness theorems and implications
I understand that Godel's theorems put in place restrictions on any axiomatic system trying to derive mathematics, in the sense that for the simplest example, not all the truths about natural numbers can be discovered within one axiomatic system.
My question is that do they also put in restrictions on mathematics itself?
Can all the truths which can be established under an axiomatic system be discovered by mathematics?
I always thought that we had some preexisting fundamental truths, and mathematics attempts to map these truths to formal statements.
So, can all the truths about natural numbers be discovered within mathematics?
If by discovering we also mean proving them, then is it possible that mathematics itself is an incomplete language? Since, the theorems also imply that we cannot prove all the true statements within an axiomatic system.
We definitely would need some axiomatic system or the other to derive mathematics.
Why was the onus of failure which resulted from these theorems put on logicism and not mathematics?
My question is that do they also put in restrictions on mathematics itself?
Can all the truths which can be established under an axiomatic system be discovered by mathematics?
I always thought that we had some preexisting fundamental truths, and mathematics attempts to map these truths to formal statements.
So, can all the truths about natural numbers be discovered within mathematics?
If by discovering we also mean proving them, then is it possible that mathematics itself is an incomplete language? Since, the theorems also imply that we cannot prove all the true statements within an axiomatic system.
We definitely would need some axiomatic system or the other to derive mathematics.
Why was the onus of failure which resulted from these theorems put on logicism and not mathematics?
Comments (84)
I had a similar problem. In fact there are formal systems in which every true arithmetical statement can be proved. But there are unprovable true sentences in that stronger formal system of course.
I dont think these problems can't be solved within mathematics since math is based on axiomatic systems.
Will read the link you sent.
Quoting guptanishank
Quite the reverse: there cannot be an axiomatic system from which we could derive all of mathematics.
But, my point is that how do we even know if a mathematical statement is true or not without an axiomatic system?
I think I just understood that the theorems have to be formed from the axioms themselves. As such, all of them can be found through mathematics?
I think my understanding of the theorems is quite naive to be honest.
How can something unprovable be true?
Earlier you said "I always thought that we had some preexisting fundamental truths, and mathematics attempts to map these truths to formal statements."
Could you clarify what you mean by this? Are you accepting that there are unproven truths, but arguing that true statements are statements that are proven to "map" these "preexisting fundamental truths"?
That there might be unproven truths, but we try and map all the truths to statements in mathematics which can be proved or unproved.
Basically that there are some pre existing fundamental truths. Mathematics represents them in formal language.
I wanted to know if it could completely represent them, besides other things.
In math however if a statement is unproven, we cannot "know", if it was one of these fundamental preexisting truths or not.
Sure, but it might still be true. For example, if we take the current number system, and assume that we hadn't yet measured the value of Pi, would it not be the case that "the first three digits of Pi are 3.14" would be true, even if we didn't know it? A lucky guess can be true, can't it?
In fact one could prove a statement to be true, even outside the axioms I guess.
The question however is if all the truths about mathematics, say for example arithmetic can be discovered? Would discovery imply provability as well? Because certainly you would need to prove them one way or the other to establish them to be true.
In this way, we can go on. And now, the question arises if mathematics itself is an imperfect, incomplete language. Because all the statements have to be based on axioms. No perfect set of axioms can ever be obtained. Therefore all the true statements which math attempts to map to, cannot be discovered.
Godel sentences are not "true but unprovable" for this reason. For to assume that they are true is to beg the question of consistency, an assumption without which it is impossible to assign any meaning to godel sentences, for they are no longer necessarily non-derivable.
When reading popular accounts of Godel's theorem, there is always this whiff of a shady magical trick being pulled before the reader's eyes. And this magical trick is when authors like Douglas Hofstadter attempt to sell mystery to the reader by saying to the effect "forget about this boring and logically impossible-to-verify disclaimer about logical consistency that we cannot meaningfully assert, or the related fact that completed infinity doesn't really exist - *cough* look at this weird "self-referencing" Escher picture!"
I have a hazy understanding of Godel's theorems, and there are two incompleteness theorems. The first one states, roughly:
(1) Consider a consistent formal system F that allows the expression of arithmetic truths, then there is a statement in F which cannot be proved or disproved (ie F is incomplete)
And the second one:
(2) Consider a consistent formal system F that allows the expression of arithmetic truths, then F cannot (syntactically, using elements and rules in F) imply F's consistency.
Theorem 1 is done through construction. Godel figured out a way to uniquely encode every element of the formal system F (mathematical entities) with a number. Many steps in the proof later, he assigned such a number to the statement [math]G_F[/math] "This statement is unproveable in F". Then if F allows derivation of [math]G_F[/math], F derived something unproveable, so F is inconsistent. If F does not derive [math]G_F[/math], then [math]G_F[/math] is true. To establish [math]G_F[/math]'s truth I think he had to go to a bigger system than F (think 'more arithmetical truths' than 'simple arithmetic'). This kind of makes sense, since he's trying to prove something about the system as a whole - specifically whether a statement of F's consistency implies [math]G_F[/math].
Theorem 2 precisely concerns the aforementioned idea of 'having to go beyond the system to establish the system's overall properties'. Specifically, 'having to go beyond the system to prove the system's consistency', since the second theorem is 'A consistent formal system F (that contains simple arithmetic) does not allow the derivation of F's consistency within F'. But I don't have any intuitions about its proof since my model theory is pretty weak.
What are the implications of Godel's theorems for mathematics? Well, when they came out they were a massive 'fuck you' to the Hilbert Program, which was a desire to axiomatize all mathematics. As collateral damage, it screwed over the idea of formalism in philosophy of math - since there are now mathematical truths which cannot be ascertained through string manipulation rules of very general axiomatic systems (like ZFC).
What does it mean for the actual practice of mathematics? Well that depends on the discipline. It has little to no consequences for applied mathematics, it has big consequences in proof theory and mathematical logic. The interesting thing about the theorem for me is that the practice of mathematics, what it means to reason mathematically about mathematical entities, was largely unperturbed - though it did rain on the parade of having a 'complete axiomatic system of all mathematics', and was in essence a no go theorem for that aspiration.
I think this is because the desire for axiomatisation isn't removed by Godel's theorems, you still want to be as precise as you can about mathematical entities. But when you're familiar with the entities in a problem class in mathematics, you don't think in terms of syntactic operations in that class. This is evinced further by the majority of papers with proofs in them not providing a formally valid proof - just 'enough' of the proof that a skilled reader can construct it in their head.
Also, the role of conjecture and heuristics in mathematics wasn't changed by Godel's theorem. People still publish conjectures and heuristics - statements of interesting problems and informal ways of thinking about them.
The idea that Godel's theorem destroys mathematics in some sense is largely due to poor outreach about it. It's in the same ball park as 'quantum weirdness' for generating misapprehensions about a science. I think if it was presented in its philosophical and historical context, and these presentations contained assessment of the impact of the theorems on subfields outside of proof theory and model theory, it wouldn't be seen as a cataclysmic event for mathematics.
I actually like it. For me it gives some kind of internal evidence within mathematics that mathematical progress takes on a quasi-empirical character, like Lakatos and others have argued.
Just one last thing:
Where does the law of excluded middle fit into all this?
A statement must be either true or false.
So if it is unprovable, within a formal axiomatic system, and you cannot decide it's truth value even by going outside the system, what value do you assign to that statement?
How does this fit within the context of Godel's theorems?
@sime: I don't understand why that would be nonsensical.
Are you implying that every statement in mathematics can be shown to be either true or false?
LEM is irrelevant, since Godel's Incompleteness theorems don't use it, that is to say, his proof is entirely constructive and syntactic without invoking ~~P -> P.
Recall that Godels results weren't at all surprising to Intuitionists who rejected LEM twenty years in advance of the publication of his incompleteness theorems precisely because they rejected the the assumption that logic has transcendental significance beyond the step-wise empirical construction of its formulas in accordance with intuition. Why on the basis of this intuition ought it be expected that for any well-formed formula P in the language of an axiomatic system that we must derive P or ~P?
Indeed, historians have recently discovered a cache of previously unpublished letters between Gödel and Hilbert. I take the liberty of summarizing them here.
Godel: Fick dich!
Hilbert: Oh no mein freund. Fick DICH!!
Gödel: Fick dich to the n-th power!
Hilbert: Und deine Mutter auch!
etc.
Godel's theorem does not say that we cannot prove the statement by going outside the system. Indeed, for the unprovable statements often considered in this context, they can be proved by moving to a meta-system that is larger than the original one and consistent with it. The problem is that there will then be new statements in that meta-system that cannot be proved or disproved (are 'undecidable') in that system. So we need to move to a meta-meta-system to decide those. No matter how many times we do this, the system we end up with will contain new undecidable statements.
Hahahaha
I don't know how the law of excluded middle relates to Godel's theorem, or how rejecting it relates to Godel's theorem. One way to find out how it relates would be to study Godel's incompleteness theorems in the context of intuitionist interpretations of mathematics. Here is a starting place, but I can't guide you any more.
But I got the essentials here.
I don't really care about the law of excluded middle.
But I just came to know about the assumption that Godel made and it's made me a little happier.
I thought Gödel's theorem only applied to non-negative integers. Why would it have anything to say about mathematics in general or anything else?
It applies to any system that contains arithmetic. This is why it's so important. If you want a system to do maths in, it should definitely contain some kind of arithmetic, so Godel's theorems - or analogues of them - will apply.
Is there a transcendental-logical or arithmetic system that could account for everything or is this just stating the set of all sets that is also a self-containing set paradox?
No Posty, if the system contained enough arithmetic it would still be subject to Godel's theorems.
Yes, but, my understanding is that a theorem that can't be proved within a system can be proved by a meta-system as mentioned. So, can this process go on forever or is Godel's Incompleteness just a proof of a hard limit to this process, thus giving rise to some asymptotic behavior of the ability to prove arithmetic truths?
A la, Penrose, if one believes in mathematical Platonism and such, then there seems to be a final system that could account for all proofs in it, no?
Such a language would be incomprehensible to we mere humans, or any other finite beings, but one can fantasise about possible infinite mega-beings or deities that might be able to reason in such an alphabet, and hence potentially even 'know everything'.
So, Hilbert was right, just not as we have come to understand it or are even able to within our current framework...
It seems intuitively obvious if you consider QM in infinite Hilbert Space or anything in infinite Hilbert Space. Degrees of freedom fly out the window, etc. etc. etc.
?Gödel was in fact a Platonist. He believed in mathematical truth. His incompleteness theorems show the limits of formal systems in finding that truth.
Quoting Posty McPostface
Not sure what that means. Hilbert space is easily modeled within standard set theory. Infinite dimensional spaces aren't very mysterious. The set of all polynomials has basis {1, x, x^2, x^3, ...} That's an infinite dimensional space that's accessible to the understanding of a high school student. Hilbert space in general is just a function space; that is, a collection of functions with pointwise addition and scalar multiplication. There is no mathematical mystery to Hilbert space.
Yes, I understand that much. But, having objects that can only exist in infinite Hilbert space isn't a mystery to you? Like, say, the very unprovable mathematical truths according to Godel?
No, why? Perhaps you can explain your point of view to me. I didn't study much physics but I've studied functional analysis. Hilbert spaces aren't very mysterious at all. In fact when I learned that the mysterious bra-ket notation is nothing more than a linear functional acting on a vector, I felt enlightened, as if perhaps QM isn't that far beyond me. If you can explain to me what you're thinking I'm sure I'd learn something. Maybe there's a mystery I'm not appreciating.
Well, I just edited that post to include Godelian unprovable truths that can exist in such a 'logical space' of sorts. I'm not entirely sure they exist in the domain of infinite Hilbert space. I may be wrong; but, reading some works by Max Tegmark was enlightening to say the least, to present the notion that there are different domains of where mathematical truths can exist but are still unprovable in lower domains of (what I call) state space's or 'logical space'.
Maybe not prove everything perfectly?
Say we have a language which says that this statement "currently points to being true".
In the sense a language where you lose accuracy and precision a little, but it points to everything being true or not.
I think such a language can exist.
One of these days I'll read Tegmark. I only know about his mathematical universe hypothesis and can't really respond to the point you are making about domains of mathematical truth.
The way I understand all this is by example. Say we take Zermelo-Fraenkel set theory, or ZF. We know that the Axiom of Choice (AC) is formally independent of ZF. So we can then adjoin Choice to ZF and study the resulting system (called ZFC) or we can adjoin the negation of ZF and study that resulting system.
A Platonist is someone who thinks that "out there" in the Platonic world there are sets, and that in that world of sets, Choice is either true or else it's false. There's a definite answer. Formalists think neither system is true, we're just describing different conceptions of what sets might be.
Viewed that way, I think this is all much less mysterious than it's sometimes made to seem. It's more of a syntactic problem. Sufficiently complex formal systems will always have well-formed statements that can neither be proved nor disproved by the system. There's less than meets the eye. It's not any kind of cosmic mystery. It's just a limitation of formal symbolic systems.
But the world is every changing. How do they account for that?
What if Choice being true or Choice being false shifted in value. That could very well be true as well.
In that case you would only be able to say that "Choice so far points to True".
Not being a Platonist, I couldn't say. I can't imagine that there are mathematical sets that actually exist anywhere except as abstract ideas that behave whichever way the axioms say they do. That's just my personal sense of things. I don't think there's any actual truth about sets beyond trivial observations about finite collections.
I don't know enough to say. As I mentioned, Gödel was a Platonist and he was pretty smart. There's a lot I don't know about Platonism.
This conversation made me look up this article https://plato.stanford.edu/entries/platonism-mathematics/. I'll give it a read when I get a chance.
I did not know that about Godel.
These conversations always make me look things up.
This is from his SEP entry.
In his philosophical work Gödel formulated and defended mathematical Platonism, the view that mathematics is a descriptive science, or alternatively the view that the concept of mathematical truth is objective. On the basis of that viewpoint he laid the foundation for the program of conceptual analysis within set theory (see below). He adhered to Hilbert's “original rationalistic conception” in mathematics (as he called it); and he was prophetic in anticipating and emphasizing the importance of large cardinals in set theory before their importance became clear.
Later in the article in section 3.2, "?Gödel's Realism," they quote this passage from his writings. These are Gödel's own words.
[i]Classes and concepts may, however, also be conceived as real objects, namely classes as “pluralities of things,” or as structures consisting of a plurality of things and concepts as the properties and relations of things existing independently of our definitions and constructions.
It seems to me that the assumption of such objects is quite as legitimate as the assumption of physical bodies and there is quite as much reason to believe in their existence. They are in the same sense necessary to obtain a satisfactory system of mathematics as physical bodies are necessary for a satisfactory theory of our sense perceptions and in both cases it is impossible to interpret the propositions one wants to assert about these entities as propositions about the “data,” i.e., in the latter case the actually occurring sense perceptions.[/i]
That's a pretty good description of Platonism. I'm struck by his comment that these objective structures are "necessary to obtain a satisfactory system of mathematics ..." That's a fantastic claim. That the existence of abstract entities is actually necessary to the enterprise of math. You can't dismiss them as a mere formalism.
There's a lot more in that SEP article about all this and more.
To me, ?Gödel's Platonism is a clue to the meaning of incompleteness. He's not saying that we can't know mathematical truth. He's saying that formal systems are too weak to know mathematical truth. But like they used to say on the X-Files, The truth is out there.
The next question is, if formal systems can't get at the truth, what can? I don't know anything about what philosophers think about that.
Wouldn't it have to be something like intuition? Or perhaps, on the other hand, new formalizations that are truer to intuition?
For me the finite and the computational are just nakedly "real" or "true." They are more persuasive than the philosophy that might try to ground them. You'll probably agree that it's the infinite that gives us trouble. Tentatively this trouble seems to involve the gap between a fuzzy, linguistic concept and a mechanizable concept. There are limits to mechanization (halting problem, for instance), and yet mechanization is as Platonic as it gets?
Yes, the work of modern set theory has consisted largely in trying out new axioms that might solve the Continuum hypothesis. I suppose you could say that this is the vision of Gödel. To find better axioms that are natural in the sense of being intuitively right.
As one example, Gödel proposed a model of set theory called L. [Technical definition not important]. In this model, the Axiom of Choice and the Continuum hypothesis are both true. That proves that these statements are at the very least consistent with ZF [Zermelo-Fraenkel set theory].
Now you might think this would be enough. We'd say, we have a model of set theory and AC and CH are both true, so let's all work in L forever and be happy.
However!! It turns out that Gödel himself did not believe that L was the entire universe of sets. We don't work in L, we work in a much more generous model of set theory.
If we call the entire universe of sets V, then the claim that L is the entire universe can be notated as V = L and nobody thinks it's true.
This is perhaps what Gödel is getting at. We can use pure symbolic manipulation to learn more about our axioms. But there is always an "intended" or "real" interpretation out there, and we are not content with a purely symbolic or formal interpretation.
The point is that modern set theory is the search for new axioms that are plausible and seem natural for the world of sets we have in our minds. In our intuition. Yes, it's ultimately driven by intuition. By our intuition about what the Platonic sets must be. Even if we're formalists in the end we must be part Platonist.
Quoting t0m
I would say that the infinite is what makes math interesting! Otherwise it's just combinatorics. Balls in bins. Finite sets are boring. Also you need infinity to come up with a satisfactory theory of the real numbers. Which themselves are a philosophical mystery.
It's true that once we allow infinite sets we have paradoxes and strange and counterintuitive results. But that's the fun part! Because when we're doing math, we should think like formalists. That means we just push the symbols and see how much we can prove and if we prove some crazy stuff, well that's fun too. It's a game played with symbols. We do it because it's fun and interesting.
I think that deep down, we're all Platonists. Math is telling us something about the world. But when we DO math, we are formalists. Push the symbols, don't worry too much about what it might mean.
Quoting t0m
Yes. Something that I find interesting is that even though we have all these crazy theories about humongous infinite sets; all of our reasoning is finitistic. Proofs are finite strings. The axioms and theorems are finite strings. The rules of inference are described with finite strings. You could program a computer to check if a proof is valid. This is a huge area of active research these days, they're doing amazing things.
So all we're really doing is playing around with finite strings of symbols. We tell ourselves it's "about infinity," but it really isn't. We are only pretending to be able to deal with infinity. That's one way to look at things.
The strings of symbols that represent recursion are finite. The simplest example is the intuition of the natural numbers 1, 2, 3, ...
Those dots are finite. I used 9 symbols above, not counting spaces. 9. I "represented" infinity but ... what does that mean? It's clever of us humans to have worked out a system of symbols to discuss infinity. But the symbology is finite.
Gödel's theorems are about the properties of certain collections of finite strings of symbols. That's why you can do mathematical proofs on a computer. There's no infinity in the computer but we can use a computer to reason symbolically about infinite sets.
No, computations are required to finish after a finite number of steps. That's part of Turing's definition of computation and it's fundamental to computer science. It's just as proof in math is required to consist of a finite number of steps.
I agree with there's a Platonist or intuitionist motive involved. I suppose I experience it in terms of a virtue intersubjective reality. I don't know or even care much how sets or numbers may exist apart from human cognition. It's the aesthetic experience of exact imagination that does it for me. So indeed I'm not just writing symbols down at the end of a proof. The theorem is a revealed truth about a potentially shared world.
Quoting fishfry
You have a point, but you may be underselling the charms of the finite. I especially like Turing machines and other models of computation. This theorem really moved me: https://en.wikipedia.org/wiki/Cook–Levin_theorem Of course lots of models allow for infinite tape or memory, but in practice computation is utterly finite. I love the cold, perfect mechanization. It's an engineering-scultpure in a material that never rusts or bends ('imaginary titanium').
The reals are beautiful but troubling. "Almost all" of them are incomputable, utterly untouchable. They are elusive ideal entities. We stuff geometrical intuitions into a formal system that seems to work. Perhaps the passionate analysts are Platonist of the continuum and they just use the symbols as part of a "normal" discourse or to discipline their intuition. I've heard an analyst say that for analysts the world is continuous (metaphysically he meant).
Quoting fishfry
Yes, these "finite stings" are what especially interest me. But we do indeed handle them in terms of an intuition of the infinite. It reminds me of Heidegger. There's a framework that "opens" the meaning of the strings for us, but we can't put this dimly visible framework itself in a string. I liked Kleene's book on logic. I know what you mean about proofs being finite strings. Getting Turing machines to search through the countable set of all strings for proofs is a pretty great idea.
I'd say that not all of our reasoning is finitistic. On the other hand, the non-finitistic stuff is therefore problematic. It's a fuzziness that may be the condition of possibility for what is crystal clear.
One thing:
I think Math IS an incomplete language.
How do we know that the statement we are proving outside the axioms is the same statement as inside the axioms?
A statement is comprised of all the axioms above it. So in a way we are proving different statements to be true, even though they may look the same.
Any thoughts?
It seems very counter intuitive to me to use two different axiomatic systems for two different proofs of the same statement.
Could it not be that a statement is True under one axiomatic system and False under another then?
I don't know what that means. Can you give an example?
Quoting guptanishank
That doesn't correspond with my understanding of what a statement is. A statement in a formal system is simply a well-formed formula that may be true or false. For example "2 + 2 = 5" is a statement. "2 + 2 =" isn't.
Quoting guptanishank
Don't know what you mean. Example?
Quoting guptanishank
Of course. In Euclidean geometry there's exactly 1 line through a given point parallel to another given line. In non-Euclidean geometry there may be zero or many.
Well, we discussed that if a statement is unprovable, then we go outside the ambit of the axiomatic system to establish a larger meta system which can prove or disprove that statement, in the above discussion.
Quoting fishfry
Of course 2+2 = isn't a statement, but 2+2 = 4, comprises of all the axioms needed to define 2, +, = and 4
Quoting fishfry
Let's say under ZFC we could not prove 2+2 = 4, as true. Then to prove Godel's theorems we would still need to establish that statement as true or false eventually. The thing is that truth or falsehood of the statement will vary according to the axiomatic framework we consider.
The provability of a statement is a function of the axioms.
The truth of a given statement is a function of which model, or interpretation of the axioms we choose.
But now that you've clarified your ideas I still don't understand your question.
How would you know if a statement is true without the proof?
What do you do with a statement unprovable within the axioms? Do you say that it is neither true nor false?
Yes, different. Provability is a syntactic notion. Given some axioms and some inference rules, a given statement either has a proof or its negation has a proof or neither. There is no meaning attached to the symbols.
Truth is a semantic notion. Given an axiomatic system, we choose some interpretation of the symbols, and then we see if the statement is true or false under that interpretation.
Gödel's completeness theorem says that in first-order predicate logic, a statement is true in every model of the system if and only if it has a proof in that system.
Quoting guptanishank
You look at the model in question and see if it's true. If I tell you it's raining, you look outside and see if it's raining.
This distinction between truth and provability is at the heart of ?Gödel's Platonism. Even though he can't prove the Continuum hypothesis within ZFC, he is certain that "out there" in the actual world of sets, CH has a definite truth value.
How do you "see" this without proving? Mathematical statements can be notoriously hard to "see" if true or false.
Now we're back to formalism versus Platonism. To a formalist, there is no truth, just provability. To a Platonist, there's truth and then there's what you can prove. We can't solve that here. It's enough to note that syntax and semantics are two different things.
A simple example is basic propositional logic. If I have propositions P and Q, then I can define an operator ^ (and) and say that P ^ Q is true just when P is true and Q is true. But that's just syntax. I haven't assigned any meaning to P and Q.
If I say that P is the proposition, "It's raining outside right at this moment," I can look outside and see if it's true or not. I agree with you that when it comes to math, the question of "how do we look outside?" is a tricky matter of philosophy.
So to recap, if I am understanding this right.
1) Every statement has a definite truth value (under every model of the system). This is a semantic notion.
2) Provability is syntactical. We have a set of assumptions assigned as true, some operators defined on some symbols, and say that every statement within it can be proved or not proved?
3) Under Godel's theorems not all true statements within an axiomatic system can be proven, but we know they are true by going "outside" the system, and imposing a larger meta framework, and proving them in there?
Have I understood it correctly so far?
That's a bit muddled.
No statement has any truth value by itself. It's just a string of symbols. 2 + 2 = 4 doesn't mean anything until we say what are '2', '+', '=', and '4'.
Statements are syntax. A statement is a string of symbols manipulated according to formal rules. No meaning.
A model is an interpretation of some statements. An interpretation is a domain, or universe, in which the statements are to be interpreted. Then you map each symbol to some object in the domain. Like '2' refers to the number 2, where the number 2 is "out there" in Platonic land. But it's hard to argue that the number 2 doesn't have (abstract) existence so we'll just say it exists. And '2' is a symbol that refers to it, as are '1+1' and so forth.
Now some statements are true in some models and not in others. For example the statement "Every number has an additive inverse" is false in the natural numbers but true in the integers.
Now if a statement is true in EVERY model, then it has a proof. That's Gödel's completeness theorem.
But of course we would hope that if a statement is true in some models but not in others, there would NOT be a proof. Because proofs are syntactic. They apply to every model. So the only statement that can have a proof is a statement that's true in every model. [Unless our axiomatic system is badly behaved].
Statements are syntactic. Models are semantic. "All numbers are even" is a statement that's neither true nor false. It's true in the model consistent of the set of even numbers. It's false in the model consisting of all the whole numbers. We would HOPE that there's no proof of "all numbers are even" because it is NOT true in all models.
This is all a huge area of mathematical logic. I can't really hope to do any of this justice. If you are interested, there are a lot of courses on formal logic on EdX and Coursera and other MOOC providers. I definitely recommend a course in elementary logic, it will clarify a lot of things for you.
Quoting guptanishank
Yes.
Quoting guptanishank
Well maybe every statement or its negation can be proved. If so, the system is called complete. If not, it's incomplete. Some systems are complete and others are incomplete. The modern formulation of Euclidean geometry, for example, is complete. Every statement is either provable or not.
Quoting guptanishank
A little muddled. There are no true statements by themselves. Incompleteness just says there are statements that can't be proven nor disproven. There is no reference to truth.
Quoting guptanishank
You can disprove them that way too. Take the Continuum hypothesis, CH. We know that it's independent of ZFC. So we can now work in ZFC plus CH, or ZFC plus not-CH. Math doesn't care. They're both equally valid. You can choose whichever you like.
The quest is to find out WHICH is "true," CH or not-CH. And what we mean by "true" is that there is some preferred or intended model of set theory; and we want to know if CH is true in that model. Or in the Platonic world if we believe in such a thing. This is all very nebulous and I'm very far from being an expert.
The point here is that we can make a larger system in which CH can be proved; and another system in which not-CH can be proved. The question of what the "true" answer is, starts with trying to explain what that would even mean, and then trying to answer it. Very smart people have been working on all this for over a century. We won't be able to nail it down here.
Quoting guptanishank
I've tried to place into context some of your thoughts, to the limit of my own understanding and ability to explain it. You'll have to tell me if I've been successful.
Does the notion of truth then pertain to consistency?(I guess that's what you meant when you said "Every") That the model under which I am trying to say if the statement is true is consistent with all my other models out there, and so on recursively.
What's at the end of the recursion?
There must have been something very basic model, which was chosen first and said that the proof has to be true in at least this model.
I think I understood you, but can't explain it in words yet. Have a diagram in my head.
Thank you for this. I will study this in more detail.
That's a very good question.
In set theory, which is regarded as the foundation of math, we think of the axioms as statements accepted without proof in order to get our formal system off the ground. The axioms are chosen on the basis of naturalness and general agreement that they represent what we think about sets.
On the other hand, in non-foundational areas of math, axioms really are used more as definitions. As an example, in abstract algebra we talk about groups, rings, and fields. In real analysis we talk about metric spaces and topological spaces. In each case we list a set of "axioms," which are taken to be the defining property of the object in question.
So we're not saying the axioms are true. We are saying that anything that satisfies the axioms deserves the name we're giving it. Anything that satisfied the axioms for a toplogical space will from now on be known as a topologica space.
It's not about truth. It's about classification.
Now we can take this point of view and retrofit it to set theory. A "system of set theory" is any collection of mathematical objects that satisfies the axioms of set theory.
In this sense we can in fact view even the axioms of set theory as being definitional rather than foundational. The axioms of set theory are simply the defining properties of the things we call sets.
Quoting guptanishank
No. Consistency is syntax. Truth is semantics.
A formal system is consistent if it does not have a proof of both P and not-P for some statement P. Syntax. It's about the existence or nonexistence of proof, which are just sequences of statements derived according to inference rules. A computer could crank out a proof.
Truth is about meaning. You assign meaning to your symbols to see whether it's true. "It is raining outside." A string of meaningless letters and punctuation. Onece you define "raining", "outside," and "It", and "is", and so forth, then you can look out your window and determine if it's raining outside.
If by raining you mean sunny and by outside you mean inside, then the meaning of the statement changes. Meaning is semantics.
Symbols are syntax. Meaning is semantics.
Quoting guptanishank
Not clear what you're referring to.
Quoting guptanishank
That diesn't make sense to me. There's no recursion. You're overthinking this.
Formal manipulation of strings is syntax. Proofs. Consistency. Completeness. Assignment of meaning is semantics. Truth.
Quoting guptanishank
There's no recursion.
Quoting guptanishank
Oh yes. This is the concept of the "intended model." Given a set of axioms, it often has many models. Mathematicians are thinking of a particular model and not the weird models. Again this is about the intuition of what the axioms are about.
Quoting guptanishank
There are a lot of good explanations around the Internet, lots of Wiki pages, etc. There's too much content being covered in this conversation to be summarized easily. Don't rely too much on just what I've said, I'm not an expert.
I realize that in mathematics, the notion is entirely different and totally based on semantics, which is why I am still having a hard time wrapping my head around this.
Thank you so much though!. Please allow me to analyze and read carefully all that you have written and come back for more questions if any.
Is there a definition for truth as well? Non-circular?
That doesn't preclude you from learning what the logicians think about it. I might be a vegetarian but I could still go to butcher school and learn how to cut meat. I just wouldn't eat it. I'm only explaining a point of view in response to your questions. I'm not demanding that you agree with any of it.
Quoting guptanishank
Ah. Well, no. In mathematical logic we spend a lot of time worrying about these things. Working mathematicians generally don't spend any time thinking about them at all. A group theorist proves theorems about groups, investigates the different types of groups. attempts to classify all the possible groups, and so forth. It's not part of their discipline to define truth or think about syntax and semantics. It doesn't come up. [To be accurate, there are some questions in group theory that depend on mathematical logic, and to that extent, group theorists are interested in logic. But only to solve problems in group theory, not because they care about mathematical logic].
We're talking about mathematical logic. We are not talking about math in general. You can get an undergrad math degree without ever spending five minutes thinking about syntax versus semantics. Probably a Ph.D. too in most mathematical disciplines.
Quoting guptanishank
Ah yes well in the 1930's, Alfred Tarski defined truth.
https://en.wikipedia.org/wiki/Semantic_theory_of_truth
This stuff is way over my head. A standard example is:
'Snow is white' is true just in case snow is white.
I have never taken the trouble to learn the presumably deep theory underlying this idea. They talk about the object language (the language you care about) and the metalanguage, which is the language you use to talk about the object language.
That's literally everything I know about it. But Tarski is the guy who gets credit for defining truth.
It is circular.
For what it's worth, that is not the mainstream view. But I'm not familiar with the subject so I can't really say.
Could you give me a link to more resources then?
It looks so obviously circular. Something depending on itself is circular.
Oh, you mean the one where it is based on formulae that you can write in the language?
Yup, that is circular as well, I think.
Tarski's work is taken seriously. You are dismissing it. Clearly logicians don't dismiss it. As I say I'm not in a position to discuss the issue in detail. I'm only pointing out that Wikipedia doesn't say, "Tarski's idea is circular and not taken seriously by anyone." On the contrary, Tarski's name comes up whenever anyone discusses the definition of truth in logic. His work in that area is regarded as important.
The thing is that truth can ONLY be defined circularly.
Tarski was brilliant and recognized that and still gave a meaningful definition.
As far as I know it.
If he was indeed able to give a non circular definition, then hats off to him for achieving that.
The google result circular definition of truth, brings up tarski on the first 2-3 results.
I meant nothing emotional when I made those statements about Tarski. Just, what seemed like a matter of fact to me.
I see your point. Googling around shows many people asking if Tarski's definition is circular. You know more about this than I do.
And now you see why this "semantic" notion confuses me such.
It is not a definition as far as I know, but just a notion.
It's not well defined.
You were being sarcastic right? :P (when you said I knew more about this)
Please do not take offense.
So a sentence in the object language, which one wants to show or define as true, has to hold in the metalanguage as well.
So there is no concept of truth in the metalanguage?
I am currently reading all that I can about this. Please allow me to come back with more intelligent questions.
Sorry if you took offense, over my comments on Tarski.
We wish to prove the truth of a sentence in the object language ( L ), but we use a metalanguage (M) to do so, the definition is based around terms used in the sentence of M, but without the notion of "truth".
The whole thing seems circular. I mean not the definition of truth, but the usage of the words in the object language and the metalanguage. Because, now the words in L are dependent on truth, and truth is now dependent on the same words M.
This is the paper I had found, and thought that it was widely known that Tarski's definition is circular.
http://www.sa-logic.org/sajl-v1-i1/06-Greimann-SAJL.pdf
https://philosophy.stackexchange.com/questions/47018/how-do-you-define-truth?
Also, asking the same question here.
Hopefully, I understand it better!
I don't know anything about the subject and can't respond to any of your questions. Hopefully you'll get some insight on Stackexchange.
Alright. Thank you for answering all my other questions.
It's been a ton of help really!
Do you mean the axiom of infinity? I would be curious to see a reference for this relationship. I know some set theory but I have never heard of any relation between the axiom of infinity and Tarski's definition of truth. That doesn't mean there isn't one, just that I wonder if you could provide some context and/or references.
Truth in the object language depends on the metalanguage. And for truth in metalanguage, you form a bigger metalanguage and so on... at least as far as I was able to understand it.
Do you have a reference for this? Or is the infinite tower of meta's something you are bringing to the discussion that's not in the primary literature?
https://plato.stanford.edu/entries/tarski/
Perhaps it points to the same thing. Will give it a better read later.