## A very basic take on Godel's Incompleteness Theorem

• 13.8k
Suppose a mathematical theory/system T.
G=This sentence is not provable in T

Either G is provable or not provable

1. G is provable. So G is unprovable
2. G is not provable

So, there is G in the theory T

Have I got it right?
• 65
All I see is the use of the boolean operator AND, which implies there are four possible states.
G_1: sentence is true but not provable <-- this was offered in the original post
G_2: sentence is true and provable
G_3: sentence is false but not provable
G_4: sentence is false and provable
• 14.1k
G=This math sentence is true AND not provable in T

Either G is true or false

1. G is true: Then T is incomplete
2. G is false: This math sentence is false AND provable in T. Inconsistent because this math sentence is true.

If G is false then "this math sentence is false or provable in T".
• 13.8k
I edited my OP. Please have a look again if you like.
• 2.6k
Have I got it right?

No.
• 13.8k
No

I know the real proof is very complex but it seems to rely on a modified form of the Liar's paradox. Can you explain where I went wrong. Thanks
• 2.6k
I know the real proof is very complex but it seems to rely on a modified form of the Liar's paradox. Can you explain where I went wrong. Thanks

G is not provable but it's true. But I'm not really an expert on the fine points so I probably shouldn't have jumped in earlier.
• 13.8k
No problem. I'm not sure too. Thanks anyway
• 53
Have I got it right?
Are you equating "true" with "provable"?
• 13.8k
Are you equating "true" with "provable"?

If you read the wikipedia article then this can't be done.
• 53
OK if not, why 1. can be done?
G is provable means it can be proven either true or false, how come "so G is unprovable"?
• 13.8k
OK if not, why 1. can be done?
G is provable means it can be proven either true or false, how come "so G is unprovable"?

I don't know.

G = This sentence is not provable

If you can prove G then G is not provable. If you can't prove G then G is not provable

Since, you can either prove or not prove G, it follows that G is not provable.

I think the logic works like that.
• 197

You forgot to add that: T is consistent and G is a sentence in the vocabulary of T.
• 13.8k
You forgot to add that: T is consistent and G is a sentence in the vocabulary of T.

Good to see you Nagase and thanks.
• 53
I now see what you meant is similar to Godel's introduction passage in his 1931 paper. It's just an example he stressed the contradiction within a formal system. But it's not all Godel's theorem (1st one) is about. If that answers the question?
1st one says a computerizable set of rules cannot prove all statements of itself. The 2nd is stronger, saying it cannot even prove itself as consistent.
Well that to me broke down any miracles maths had attained. Now if the plain arithmetic cannot be stated to be consistent then what can? nothing on earth. This is exactly a fatal blow to Hilbert as pioneer supporter of maths.
Finally if nothing is consistent then where should you place your trust on?
• 13.8k
Well that to me broke down any miracles maths had attained. Now if the plain arithmetic cannot be stated to be consistent then what can? nothing on earth. This is exactly a fatal blow to Hilbert as pioneer supporter of maths.
Finally if nothing is consistent then where should you place your trust on?

Don't give up on math. I think, as Galileo said(?), math is the language of the universe. Consistency may not be be so problematic. It could be that we can't prove every true mathematical statement BUT that may not be required.
• 731
Now if the plain arithmetic cannot be stated to be consistent then what can? nothing on earth. This is exactly a fatal blow to Hilbert as pioneer supporter of maths.
Finally if nothing is consistent then where should you place your trust on?

Yes it broke Hilbert's program, but it didn't prove that nothing is consistent in maths. For example, classical propositional logic is provably consistent (though we obviously want to use stronger logics than a propositional theory).

That said, you can work without consistency. After all, in response to Godel's Incompleteness Theorems, one can choose to go the inconsistent route and adopt a Paraconsistent Logic. This allows one to develop a mathematical theory on inconsistent foundations, yet because Paraconsistent logics lack the Law of explosion, theory is non-trivial.

This can result in an interesting mathematical theory which proves true (and simultaneously false) some of Frege's Logicism, as logicism becomes provable here and one can prove that the Continuum Hypothesis is false (in this formalism).
• 8.7k
I know the real proof is very complex but it seems to rely on a modified form of the Liar's paradox. Can you explain where I went wrong. Thanks

Believe it or not, Godel's original paper is very readable and worth reading. You just have to find it. And it will require some work on your part. But in my opinion it's the easiest way in. Caveat: there are some subtleties you're not going to get, But for acquaintance's sake, it doesn't matter.
• 13.8k
Thanks.

I watched a video on it and the reasoning was...

Assume a consistent theory T
G is a statement in T
G = This sentence isn't provable from the axioms of T

Either G is true or false

Assume G is false. That means ''this sentence is provable from the axioms''. But only true statements are provable. That means G is true. But G is false (assumed). A contradiction.

But T is consistent. So it can't be that G is false.

What are we left with? G is true. In other words ther IS a sentence that can't be proved from the axioms.

Have I brushed against the truth or is this the real import of Godel's theorems?
• 8.7k
Assume a consistent theory T
Because otherwise, every theorem is provable in T.
G is a statement in T
Ok, but now you have to be careful about exactly what G says.
G = This sentence isn't provable from the axioms of T
As you have it, G isn't a meaningful expression in T. The problem is with "This sentence." It has to be well defined. Absent that, it's just a variation of the Liar Paradox in English - English isn't math, and Godel's theorem is interesting because it is itself a variation of the Liar Paradox, but expressed in mathematical-logical terms, which the English sentence is not.

Let's assume your G is the sentence "2+2=4 is not provable in T." (T also has to be specified with some care, but for present purpose let's just call it arithmetic.) Well, 2+2=4 is provable in T, so G is false. And the negation of G is provable. But for the Godelian sentence G, neither it nor its negation is provable in T. Crafting the Godelian G is the trick!

It works, roughly, like this: Godel created/discovered a method by which every proposition and every sequence of propositions in T can be assigned a unique number. His sentence (a number - a pretty big number) then (when translated appropriately), becomes (roughly), "The proposition with the Godel number G is not provable (in T)." And you might ask, so what? Well, the number of this proposition is just G itself! (How did he do that? Read the paper, or research Godel numbering. He did it his way, and subsequently other people found different ways.)

If G is provable (i.e., the negation of G), then G is not provable.
If G is not provable, then G is true, and you have a true proposition not provable in T.
Neither G nor its negation is provable in T. What does Godel's G look like? in his paper it's represented as 17Genr.

The proof is constructive in this sense: if you add G as an axiom to T, giving (say) T', then you can construct G' with the same effect in T', and so on into the transfinite.

And there's a bonus in his paper: the consistency of T cannot be proved in T. To say that T is consistent is equivalent to saying there are unprovable propositions in T (else, as above, if T is inconsistent then every proposition is provable.)

Let's let the expression "T is consistent" be represented by w. G is unprovable; we can write, w => unprovable G. However, G asserts its own unprovability(!) We can therefore write, w=>G. The expression w=>G is provable. But, that means that if w were itself provable, then G would be provable. G is not provable, therefore w is not provable. Some trick, and very slippery!
• 53
Thanks, I need to learn more to understand the extent you introduced but the reason I said so was due to my subscription to Godel's own view:
So the following disjunctive conclusion is inevitable: Either mathematics is incompletable in this sense, that its evident axioms can never be comprised in a finite rule, that is to say, the human mind (even within the realm of pure mathematics) infinitely surpasses the powers of any finite machine, or else there exist absolutely unsolvable diophantine problems of the type specified . . . (Gödel 1995: 310).

i.e I am against the scientific trend to treat human as a classical moving machine, especially what inside the brain or thoughts.
• 13.8k
Thank you for the explanation. I'm not sure if I understand all that but I feel much closer to the truth than before.

T = consistent mathematical theory
G = The mathematical proposition P is not provable from the axioms of T

G is either provable or not provable

1. G is provable. In other words ''the mathematical proposition P is not provable from the axioms'' is true. G is true

2. G is unprovable. G is true
• 80
How do you prove G to be true in T? You can't for then you'd prove G and contradict to its content. So G is true or false in T but we cannot know it (within T). We also have no position beyond T for T does already contain logic & arithmetic. Therefore I think we cannot conclude that G is true, but its truth is unprovable and that's not a proof of G's truth.
• 14
I think this shows that mathematics is both intuitive and formal at the same time. We shouldn't forget that mathematics is a creation of more than one brain function and, as such, can appear contradictory in the same way as someone can hold two or more positions in their head simultaneously.
• 400
Suppose a mathematical theory/system T.
G=This sentence is not provable in T

Either G is provable or not provable

1. G is provable. So G is unprovable
2. G is not provable

So, there is G in the theory T

Have I got it right?

For me the problem starts with 'This sentence is not provable'. This is meaningless. It does not state what is not provable. It would make no more sense to say 'This sentence is provable'.'This sentence' is not a statement and is not even a sentence. It is not provable or unprovable.

I wish someone would explain incompleteness in a way that it seems plausible to non-mathematicians. But explanations always it seems to depend on taking the liar paradox seriously, which try as I might I cannot do. , . . .
• 8.7k
For me the problem starts with 'This sentence is not provable'.
And it has nothing to do with Godel's G.

G is a number constructed following explicit rules. And it is susceptible of translation into, e.g., English.

But any imprecision in the translation is an artifact of translation, not of G or its construction or the reasoning behind it. In Godel's paper G is represented by 17Genr. I will try to unpack that. "Proof," btw, is rigorously defined.

Godel numbering is a method of giving symbols, variables, propositions, and sequences of propositions each a unique number, such that they could be listed. Godel apparently discovered the idea and developed his own method; other methods have since been developed.

17 is just the name/number of a free variable - for convenience let's call it here x. "Gen" stands for generalization, here translated as "for all." r is the number of a proposition.

So far, then, we have, "For all x, r." To learn just what, exactly, r is, I refer you to Godel's paper, here, on text p.188, #12. the paper itself starts on p. 173. :
https://monoskop.org/images/9/93/Kurt_G%C3%B6del_On_Formally_Undecidable_Propositions_of_Principia_Mathematica_and_Related_Systems_1992.pdf

It looks formidable, but it isn't, at least at first. That is, this is by far the easiest way to go. And the paper itself is a pleasure to read.

So in an expanded translation of 17Genr, it reads, "For all x, that is, for anything found on the listing, r holds." And you might like to know what "holds" means here, but for that, again, back to the reference.

Taken altogether, it says that 17Genr (aka G) is not decidable, which means that neither G nor its negation are provable. But 17Genr just is G! So it says of itself it is not decidable! And you can work out the implications of that, and as well see the resemblance to the liar paradox, but a resemblance is all it is.
• 553
Sadly, the whole thing seems beyond me. I've tried different books and sites, but just don't have any idea what he's doing. I get lost at the very first step.
• 3.6k
Don't feel badly. I was a professor of mathematics for many years and never encountered a theorem in my area of study that was not provable in PA. Most of us don't. But there are some.
• 553

Thanks. But at least you understand what we're talking about. I need to find a professor of mathematics to sit down with me and help me understand it. But they aren't easy to come by.
• 400
Thanks. I tried to read the linked article but it goes over my head. It seems it is impossible to explain this issue to non-mathematicians.
• 8.7k
You don't need to know everything about automotive engineering to drive and even more-or-less appreciate a car. Same with Godel's paper. But you do have to work with it for a while and at least a little bit. And even being interested, you already know more than you think you know.

Possibly the simplest way - maybe you've seen this - take a piece of paper and write on one side, "The statement on the other side is false." and on the other, "The statement on the other side is true." Then try reading it. Is one side true and the other false, or the other way 'round? Both? Neither?

Godel substituted "provable" for true, and he devised a system that could encompass and include all statements. All of these statements can be imagined to be ordered on a great long list of statements. His statement G, then, can be read as, "The statement on the list at location G is not provable." And if we consult the list and look at the statement at location G, we would see that it read, "The statement on the list at location G is not provable." So, if G were provable, then it would not be provable, and if not provable, then true but not provable, thus undecidable (QED).

Giving it some thought, you'd recognize that G is not too hard to describe - we just did it - but also that it is not-so-easy to actually construct and write out in rigorous terms, which is what Godel did. And seen this way, it does not seem so remarkable. But then you remember it is just a straightforward if somewhat complicated expression in arithmetic, and it's undecidable!

If I may, I suggest returning to the paper and reading the first section, that starts with, "It is well known...". Section 2 starts with, "We pass now to the rigorous execution of the proof...". An invitation hard to resist.
bold
italic
underline
strike
code
quote
ulist
image
url
mention
reveal