The Gödel incompleteness phenomenon

Joel David Hamkins, Professor of Logic, Oxford University

Chapter 7. Incompleteness

David Hilbert sought to secure the consistency of higher mathematics by finitary reasoning about the formalism underlying it, but his program was dashed by Gödel’s incompleteness theorems, which show that no consistent formal system can prove even its own consistency, let alone the consistency of a higher system. We shall describe several proofs of the first incompleteness theorem, via the halting problem, self-reference, and definability, showing senses in which we cannot complete mathematics. After this, we shall discuss the second incompleteness theorem, the Rosser variation, and Tarski’s theorem on the nondefinability of truth. Ultimately, one is led to the inherent hierarchy of consistency strength rising above every foundational mathematical theory.

[upandatom]

Thank you so much for this! Been trying to learn this for three years and this really helped. Bought your book too :)

[joeldavidhamkins]

In the discussion beginning 1:15:32, I mention that the first incompleteness theorem can be seen as a consequence of Tarski's theorem on the non-definability of truth. This can be seen from the fact that provability is first-order expressible, and Tarski proved that truth is not expressible. Therefore, provability does not align with truth. So there must be true but unprovable statements.

[SaurabhMotalkar]

Love from India to people like you, Because it's rare to find intellectuals who not only understand but they enlighten others. & Arm society with powerful tools such as logic or mathematics or

[calmander]

Thank you for the excellent lectures. I will be getting the book.

[jackhurwitz]

Is there a similar "black hole" phenomenon in provability to the one for the Halting Problem which you described in the computability lecture? Namely, is there a notion of asymptotic probability for measuring sets of mathematical statements, and do we know what that asymptotic probability is for decidable statements? Thank you for the wonderful lecture.

[Achrononmaster]

@1:18:00 you got to my last question, but stopped too short! The thing about CH is that it enriches the conception of ℝ. We could not claim to have realized a conception of ℝ at all before. (And philosophically certainly still no one knows what a true continuum means! You can always squeeze in hyperreals or surreals between the reals.) In some sense the metaphysical continuum is the core issue, and that's just way beyond all of axiomatizable mathematics. What am I trying to say? I think that it is fine to add CH to ZFC as a _provisional theory._ Many logicians might balk at that, but this is the way mathematics is inexorably going. If ZFC+CH cannot force any inconsistency not already in ZFC of course, but more mildly could allow some very obviously stupidly wrong statement to be provable, then so much the worse for CH, but the mathematical exploration is the thing worth pursuing, not the final rejection/acceptance of CH.
The thing is, what on earth could be "very obviously stupidly wrong" but not disprovable in ZFC? (Do not tell me Banach-Tarski dissections, since they are beautiful "true" results imho. Showing the richness of sets like ℝ .) To find some such statement surely would require a helluva intuition at the ω-Ramanujan level, and so it'd be only one geniuses intuition, to the rest of us it'd be unfathomable, most likely, unless she could explain it to us children.

[ralfille]

Great lecture. I have in the fixed-point lemma some difficulties to distinguish the syntactic and the semantic level. In the proof there was n = Gödelcode(Theta(x)) and n is a natural number. After this Phi was defined with Phi = Theta(n). I think this is exactly only correct with Phi = Theta(n*) where n* = 1+1...+1 n times. Was this just not done to keep the notation readable?

[Achrononmaster]

@1:16:00 and @51:20 --- is it fair (correct?) to say Tarski gave a criterion for a truth predicate, and showed the predicate is not definable in any formal system? The criterion for a predicate is not a definition _of the predicate_ in a formal system, right? So it's not as paradoxical as you make out?

[MarleneWalker-suku]

Never trust the dreams of a man who wears a silly hat.He dreamt of a time when his own skills would be redundant.I admire his honesty though as I would shirk from such a depressing thought even if my intuition led me to believe it's truth.

[erincarmody]

My favorite part is that Tarski defined truth, while proving that truth is not definable! Did I get that right?

[atol]

Instead of going into higher levels of mathematics one should ponder: If you have nothing on cut board (0) and you try to divide ( / ) the nothing (0) with your one knife (1). How many peaces of bread you have in cut board? AKA 0/1==? Before going forward in academic curriculum of mathematics.

[Achrononmaster]

@1:17:00 one thing I've never been totally clear about is whether "Set Theory" (or any other axiomatization of the notion of arithmetic or the like) is a lot like Euclidean geometry: If you cannot prove a nice conjecture like the CH, and you really want to prove it, not take it as an axiom, then you are looking at maybe an analogue of non-Euclidean geometries which turned out to "be a _thing!"_ (Who knew?!! We were all flat-earthers before Gauss, Lobachevsky and Bolyai, haha.) So the deeper question is what are non-standard set theories? And can we realize them concretely in a similar way to the way a sphere gives elliptical geometry or Poincaré disk gives hyperbolic geometry?, and the real mind-bender --- the set theoretic or number theoretic analogue of Riemann geometry! To my knowledge we are still "Flat Setters" in this respect.
I note that Woodin's V=Ultimate- L conjecture, if true, would establish the CH, and the way he speaks makes it more a set theoretic Universe rather than Multiverse. But surely that is only gauged to CH. I imagine there really should be other varieties of set theory that would not destroy the CH, and so "secure" the finite part of Peano arithmetic relative to ZFC+CH, but still allow for different conceptions of the transfinite, analogous to how Riemann geometry warps Euclid. Thoughts?

[davidwilkie]

All is vibration, positioning point-line-circle time-timing in log-antilog No-thing=> Eternity-now real-time relative-timing sum-of-all-histories quantization Entanglement.
Yes the Halting Problem is equivalent to positioning Absolute Zero Kelvin Singularity-point Entanglement in/on the reciprocation-recirculation axis of trivial zero-infinitesimal coordination-identification, here-now-forever, ie x, y, z etc and i-reflection containment @.dt instantaneously vanishing-into-no-thing, => reiterative reintegration POV that is Computational = made-of-making "thermodynamical" Perspective.

Math-Physics interpretation is absolutely unavoidable.. be-cause-effect in/of inherent Disproof Methodology in/of pure-math imagined i-reflection containment-> 1-0-infinity potential elimination at vanishing point density-intensity real-numberness, possibilities of infinitesimal-infinite reciprocation-recirculation point of Exhaustion.

[jurgenblick]

So you are saying that math is mechanical?

[glebpolevoy]

If PA* = PA, why solve the Entscheidungsproblem to enumerate PA*? Just enumerate PA. This part in unclear to me

[vitalysarmaev]

Gödel's theorem is a statement of the impossibility of solving a recursive object in the form of a direct solution.

In arithmetic where there is no recursion, such as arithmetic without multiplication, all propositions are provable. From here, one more small step and you can prove Fermat's theorem in the way that he kept silent about in his diary: most likely Fermat understood the meaning of recursion - this is a function whose domain of definition is the product of the set of values ​​​​of the function itself by the set of the domain of definition of its predecessors. And after a couple of manipulations, you can come to Fermat's conclusion. But the boundaries of YouTube comments are too narrow for me to provide this proof here 😜

p.s. No, I'm not a crazy Fermatist

[JamesColeman]

Let’s call this lecture the Value Paradox

[jamestagge]

could someone critique the 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.

[pmcate]

1) Why was incompleteness such a surprise when the independence of the parallel postulate was already known?

2) So incompleteness is actually a blessing in disguise?

3) I get confused why the second incompleteness theorem gets stated as "math cannot prove it's own consistency". Shouldn't we just be saying "we cannot prove (in some agreed metalanguage that) math is consistent"? Certainly there are other ways to show some axiomatic theory is consistent or inconsistent other than turning the language on itself correct?