Gödel's First Incompleteness Theorem, Proof Sketch

Kurt Gödel rocked the mathematical world with his incompleteness theorems. With the halting problems, these proofs are made easy!

Created by: Cory Chang
Produced by: Vivian Liu
Script Editor: Justin Chen

—

Extra Resources:

[BelegaerTheGreat]

1:30 Yeah, imagine a system that proves only one statement, and that statement is false. This system is not sound, but neither does it lead to a contradiction, therefore it is consistent.

[LaureanoLuna]

Liked the video: clever way to tap Turing's theorem for proving Godel's;  but if soundness implies consistency, as you rightly say, then soundness is stronger, not weaker than consistency.

[GeorgWilde]

It is not math that is incomplete, but a formal system with axiom system sufficiently strong to encode natural numbers with both addition and multiplciation. (there is a formal system for natural numbers without multiplication which is complete and decidable) Mathematics is very different from formal systems. Formal systems are games with predetermined rules. If you are working withing fromal system, you are not discovering anything, you can only make more explicit what is already expressed by the axioms. Mathematics is creative and has to do with abstract ideas of space, count, structure etc. And these ideas are rewised and expanded all the time in mathematics. Axiomatic method is created only post hoc to make the communication of mathematics more explicit and convincing.

[allnamesaregiven]

Man, this is so good I'm sad I didn't come up with this kind of explanation myself. Also surprisingly I miss all the related formal puzzles. I did not really understand, until now, how much fun the "simulating machines in minimal arithmetic" stuff is to me.

[nissimlevy]

What does it mean to say a theorem is true? Godel Incompleteness makes a distinction between truth and provability. A provable theorem simply means that starting with one or more of the axioms and the rules of inference a theorem can be arrived at by simple string manipulation. It's like a system of dominoes, and a "domino" theorem says that a particular domino will fall if we give a push to the first few dominos (the axioms).

A true but unprovable theorem means that no amount of string manipulation can take you, step by step, from the axioms to the theorem, yet the theorem is nonetheless true. OK, but what does it mean to say the theorem is true? There isn't some set of truths which transcends all formal systems and whose members are the true theorems of all possible formal systems. So a true theorem only makes sense within the context of a formal system of axioms and string manipulation rules.

It appears that the truth of a theorem means that the theorem is a consequence of the axioms and string manipulation rules, but that for unprovable true theorems there is no amount of string manipulation steps that will get you from the axioms to the theorem. In the domino system, the analogy would be that a particular domino falls over at some point after we give a push to the first few dominos but that there is no step by step process that you can calculate ahead of time (without actually starting the dominos toppling chain reaction) that would show you (prove to you) that the target domino will fall.

This sounds absurd. However, the domino system would need to be nonlinear (contain self-reference/recursion) in order for this to happen. Any system of standing dominos that I've ever witnessed didn't contain recursion. So this analogy breaks down, but nonetheless, it illustrates what is meant by truth and provability. The statement that Incompleteness only happens if the system is sufficiently expressive simply means that the system must exhibit self-reference.

[LoganNagol]

So this is a proof that proves proofs cannot be proven

lol

[Mrjarnould]

Awesome! Always look forward to your videos :)

[linkmariofan]

But isn't eliminating the possibility that the program halts a proof in itself that it must loop? We suppose "n" is true, we show it can't so it must be that "not n" is true...or isn't it?

[McRaiged]

please keep posting these are amazing!

[jamestagge]

Can anyone critique my notions in this? I would appreciate it very a follow up to my recent posts on (Goedel’s incompleteness theorem) the architecture of materiality and that of the realm of abstraction, the two structurally linked, which prohibits for formulation of conceptual contradictions, I present the following for critique.

After watching several video presentations of Geodel’s incompleteness theorems 1 and 2, as presented in each I have been able to find, it was made clear that he admired Quine’s liar’s paradox to a measure which inspired him to formulate a means of translating mathematical statements into a system reflective of the structure of formal semantics, essentially a language by which he could intentionally introduce self-referencing (for some unfathomable reason). Given that it is claimed that this introduces paradoxical conditions into the foundations of mathematics, his theorems can only be considered as suspect, a corruption of mathematic’s logical structure. The self-reference is born of a conceptual contradiction, that which I have previously shown to be impossible within the bounds of material reality and the system of logic reflective of it. To demonstrate again, below is a previous critique of Quine’s liars paradox.

Quine’s liar’s paradox is in the form of the statement, “this statement is false”. Apparently, he was so impacted by this that he claimed it to be a crisis of thought. It is a crisis of nothing, but perhaps only of the diminishment of his reputation. “This statement is false” is a fraud for several reasons. The first is that the term “statement” as employed, which is the subject, a noun, is merely a place holder, an empty vessel, a term without meaning, perhaps a definition of a set of which there are no members. It refers to no previous utterance for were that the case, there would be no paradox. No information was conveyed which could be judged as true or false. It can be neither. The statement commands that its consideration be as such, if true, it is false, but if false, it is true, but again, if true, it is false, etc. The object of the statement, its falsity, cannot at once be both true and false which the consideration of the paradox demands, nor can it at once be the cause and the effect of the paradoxical function. This then breaks the law of logic, that of non-contradiction.

Neither the structure of materiality, the means of the “process of existence”, nor that of the realm of abstraction which is its direct reflection, permits such corruption of language or thought. One cannot claim that he can formulate a position by the appeal to truths, that denies truth, i.e., the employment of terms and concepts in a statement which in its very expression, they are denied. It is like saying “I think I am not thinking” and expecting that it could ever be true. How is it that such piffle could be offered as a proof of that possible by such a man as Quine, purportedly of such genius? How could it then be embraced by another such as Goedel to be employed in the foundational structure of his discipline, corrupting the assumptions and discoveries of the previous centuries? Something is very wrong. If I am I would appreciate being shown how and where.

All such paradoxes are easily shown to be sophistry, their resolutions obvious in most cases. What then are we left to conclude? To deliberately introduce the self-reference into mathematics to demonstrate by its inclusion that somehow reality will permit such conceptual contradictions is a grave indictment of Goedel. Consider;

As mentioned above, that he might introduce the self-reference into mathematics, he generated a kind of formal semantics, as shown in most lectures and videos, which ultimately translated numbers and mathematical symbols into language, producing the statement, “this statement cannot be proved”, it being paradoxical in that in mathematics, all statements which are true have a proof and a false statement has none. Thus if true, that it is cannot be proved, then it has a proof, but if false, there can be no proof, but if true it cannot be proved, etc., thus the paradox. If then this language could be created by the method of Goedel numbers (no need to go into this here), it logically and by definition could be “reverse engineered” back to the mathematical formulae from which it was derived. Thus, if logic can be shown to have been defied in this means of the introduction of the self-reference into mathematics via this “language” then should not these original mathematical formulae retain the effect of the contradiction of this self-reference? It is claimed that this is not the case, for the structure of mathematics does not permit such which was the impetus for its development and employment in the first place. I would venture then that the entire exercise has absolutely no purpose, no meaning and no effect. It is stated in all the lectures I have seen that these (original) mathematical formulae had to be translated into a semantic structure that the self-reference could be introduced at all. If then it could not be expressed in mathematical terms alone and if it is found when translated into semantic structures to be false, does that not make clear the deception? If Quine’s liar’s paradox can so easily be shown to be sophistry, how is Goedel’s scheme not equally so? If the conceptual contradiction created by Goedel’s statement “this statement has no proof” is so exposed, no less a defiance of logic than Quine’s liar’s paradox then how can all that rests upon it not be considered suspect, i.e., completeness, consistency, decidability, etc.?

I realize that I am no equal to Goedel, who himself was admired by Einstein, an intellect greater than that of anyone in the last couple of centuries. However, unless someone can refute my critique and show how Quine’s liar’s paradox and by extension, Goedel’s are actually valid, it’s only logical that the work which rests upon their acceptance be considered as invalid.

[jorgeromeu]

This video was extremely helpful. just subbed

[gabrielgiordanob]

Awesome!!!! Please keep making videos, this channel is gonna be amazing! =D

[madScientist]

So what if the proof of this incompleteness theorem is in itself incomplete or inconsistent ?

[procheese-tw]

how to prove the stronger form of the theorem(inconsistent instead of unsound)

[undefBehav]

How are we so sure that M(x) actually loops when the oracle program can't prove so? We say if M(x) halts, there should definitely be a proof that it does. But we are talking about incompleteness here, how are we so sure? That part of the video really confused me.

[AnandaKrsnaBBS]

Which program do you use to create your animations? thx

[MisterFanwank]

The way you describe soundness and consistency makes it sound like if a math system is unsound it must also be inconsistent. Is that not true?

[jttyler]

Question: at 5:54 you said we can't prove that it loops, but how isn't that exactly what you did in the preceding 30 seconds?

[GuadalupeGonzalez-dlxo]

The way you defined consistency, even in a mathematical sense, is not a definition I’ve been able to find.

[Ant-xzhe]

Great vid. Looking forward to the next!