The Gödel incompleteness phenomenon

Joel David Hamkins, Professor of Logic, Oxford University
This lecture is based on chapter 7 of my book, Lectures on the Philosophy of Mathematics, published with MIT Press, mitpress.mit.edu/books/lectur....
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 :)

[@bac2154]

the expert and the popularizer ;)

[@SpencerTwiddy]

omg it's Jade! I've been a sub for years and watch all your videos!

[@joeldavidhamkins5484]

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.

[@Saurabh-illumina]

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 etc......

[@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.

[@joeldavidhamkins5484]

One could easily formulate a suitable notion of "most" by which meaningful statements like "most assertions in arithmetic have the property that..." But my expectation would be that the conclusions one makes this way would be extremely sensitive to the syntactic details concerning exactly how one is counting the sentences. This is what happens in the computability case, where whether a problem counts as having a black hole or not depends on how one is measuring asymptotic density.

[@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?

[@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.

[@ralfille7840]

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?

[@joeldavidhamkins5484]

Yes, you are right.

[@namelastname2449]

Why so few views? This is gold

[@erincarmody8562]

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

[@joeldavidhamkins5484]

Yes, that is right. Tarski defined the inductive satisfaction relation, defining what it means to say that a statement phi is true in a model M for a given valuation of the free variables to objects of M. This is the mathematical instantiation of the disquotational theory of truth, by which a propositon "S" is true just in case S. At the same time, Tarski proved that arithmetic truth is not arithmetically definable, in the sense that there is no arithmetically expressible predicate that holds of all and only the numbers that are the Gödel codes of true arithmetic assertions. So Tarski both defined truth and proved that truth is not definable.

[@erincarmody8562]

@@joeldavidhamkins5484 Haha! So good!

[@Achrononmaster]

@@erincarmody8562 Tarski defined truth only relative to a model. He did not define absolute truth. If you comprehend this, then you realize there is nothing weird about the result that a model or formal system cannot internally define it's notion of truth.

[@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?

[@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 KZbin comments are too narrow for me to provide this proof here 😜 p.s. No, I'm not a crazy Fermatist

[@schmetterling4477]

Of course there are formal systems that are complete... but they are also completely trivial. That's not the stuff most mathematicians are concerning themselves with. It's like saying that chess on a two by two board is always winnable. ;-)

[@Achrononmaster]

How to you formulate Fermat's Theorem without multiplication or exponentiation to an arbitrary whole number _n_ ?

[@jurgenblick5491]

So you are saying that math is mechanical?

[@JamesColeman1]

Let’s call this lecture the Value Paradox

[@deannecarpenter6659]

Is this video an online course?

[@joeldavidhamkins5484]

These videos are part of my lecture series at Oxford on the Philosophy of Mathematics. See more information at: jdh.hamkins.org/lectures-on-the-philosophy-of-mathematics-oxford-mt20/

[@deannecarpenter6659]

thanks～

[@pmcate2]

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?

[@joeldavidhamkins5484]

Ultimately, it will be difficult to establish the incompleteness phenomenon using geometry, since Tarski proved that the elementary theory of geometry (extending Euclid's with axioms of betweeness, incidence and continuity) is both complete and decidable. Whether incompleteness is a blessing or not, I believe that we should seek out the truth. Our desires for the what the truth might be don't matter.

[@pmcate2]

@@joeldavidhamkins5484 I meant that incompleteness may be a blessing because it guarantees that mathematicians will always have a job (Although now that I remember, Tarksi's geometry is complete yet mathematicians are still needed so my point feels moot). Also, I think you missed the third point in my original post

[@joeldavidhamkins5484]

@@pmcate2 Logicians are usually careful to state the incompleteness theorem correctly, and I don't usually see people stating it loosely as "math cannot prove its own consistency." Indeed, I find your formulation a bit vague, referring to "math" as though this is one thing, but the theorem makes separate claims about all the various possible theories T that we might have. So the theorem states that any computably axiomatizable consistent theory of arithmetic T admits of true but unprovable statements and more specifically, does not prove the assertion that T is consistent.

[@zemm9003]

​@@joeldavidhamkins5484 there is no such thing as a truth that is unprovable. Truth has no meaning outside of provability. We can create a Master Theory (and we did it's called Set Theory) that can meta mathematically prove that something is true or false outside what is provable by the axioms of the smaller theory but truth will have no meaning outside of what is provable in the big theory.

[@jamestagge3429]

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

[@jamestagge3429]

I cannot thank you enough for having taken the time to read my comment (it was lengthy) and then to write such a complete response. Unfortunately, I could not get from it that which would have resolved my confusion. This is no indictment of you but rather of my lack of education in this area. I am dyslexic and thus could never continue in math beyond a very elementary level, I always transposing numbers, etc., and getting more lost with each step. Anyway, my self-taught compensating measure was to consider such things in a kind of “material” context. What I don’t see is what Goedel started with and what each step was to end with this statement, “this statement has no proof”, or some version of it. I don’t see the link. Of what is that statement composed? How is it linked with mathematics at all? I also don’t see the point of the Goedel numbers “because” I don’t see this relationship. He expressed a concept, i.e., that “this statement…”, suggesting that it was in some way reflective of something in mathematics which is a language which on its own cannot express such a concept. Yet, as a concept on its own, it is as big a fraud as Quine’s liar’s paradox. I would think that if there are mathematical statements which are true but cannot be proved as such and this statement, “this statement cannot be proved” was representative of that very condition (in math), there would be a direct linking of the meaning of this statement and the mathematical statement of which it is reflective. 1. Mathematical statement or construction which is true but no provable  Goedel numbers  semantic statement which is self-referencing that states what the math couldn’t, i.e., that the statement translated cannot be proved? It is probably very difficult for someone with your obvious expertise to dumb down such matters for someone with my lacking of that ability. There must be a sort of “mechanical” or “material” linking of the math to which his statement “this statement cannot be proved” connects. This is driving me crazy.

[@schmetterling4477]

Yes, that was total bullshit. ;-)

[@jamestagge3429]

@@schmetterling4477 I believe your comment to me was an insult, saying that what “I” posted was all bullshit. Why be a smart ass? Why not demonstrate for me where I am wrong? I would really like some help understanding this incompleteness business. I have a significant problem with dyslexia and so I never progressed sufficiently in math to be able to understand what it was Goedell did from the comment explanations. I think (think) I understand more clearly what Turing did, though perhaps I don’t because it makes no sense to me, as I will demonstrate. First, were there a program (A) called Halt which could determine whether a program (B) would halt or continue, it would by that very definition (as per the video) in actuality only be required of program (A) to determine whether a program (B) output fed to it would halt. Logically, it would not have to analyze if program (B) would continue on for that is the only possibility left if program (A) determined that the program (B) would NOT halt or whether it was unable to determine that program (B) would halt. If one were to deny this, he would by that be also denying that the program (A) had any ability to ever determine if program (B) would halt and of course, the instruction to us in the video was to assume that it could. The goal as stated was to determine whether a program (B) would halt or continue as per program (A) which would output that answer. Then for some reason we are instructed that a program (C) would be required to take the output of program (A) as to whether program (B) would halt or not and do the opposite. Why? The goal was defined and achieved before program (C’s) introduction. This makes no sense. So program (B) performs its function, is judged by program (A) as to whether it will halt or continue on and program (C), as per the video is required to look at the output of program (A) and do the opposite. So the input of program (C) is the output of program (A) as per the function of program (B). That is the way at least three of the videos on the topic stated the problem. Claiming then that the program (C) would be input to itself and by that, create a contradiction for if it halted, it would continue on and if it continued on, it would halt, is the same fraud promoted in the liar paradox by Quine. In the liar paradox, “this statement is false”, self-reference is employed to generate the paradoxical function, i.e., if “this statement is false” is true that it is false, then it is false and thus NOT true, but then it is in fact false and by that true, etc., thus the paradox. The liar paradox is complete sophistry and defies logic. The term “statement” in “this statement is false” is a set definition as well as a subject noun. But it is empty, i.e., it has no members. There is no reference object which might be judged as true or false. The adjective false (within the statement “this statement is false” is the means of its judgment), connected to the term “statement” by the linking verb “is”, is denied its function because the set definition/subject noun is empty. Here the term “statement” is not a noun like rabbit whose definition is self-contained so to speak. Additionally, this piffle breaks the law of non-contradiction as well as other logical rules. So, it seems that the halting problem is employing kind of self-referencing, i.e., if program (C) COULD run itself, which itself makes no sense, then the same kind of contradiction would be generated, i.e., that if it halted, it didn’t and if it didn’t halt, it did. How is this functional, logical or meaningful? To me it seems that Turing did not discover a contradiction in mathematics, he introduced one from outside, created one by the manipulation of the logic of the problem originally defined. Can ANYONE show me if I am wrong and how? Tell me exactly where, because I think this is a fraud. Also, could you tell me how Goedell got from the mathematical statements to the proposition that there could be a true mathematical statement for which there was no proof? What was the point of the Goedell numbers if the end product was to be the statement in propositional calculus (what it was called when I was in college) that “this statement cannot be proved”? If translated backwards from that statement to where the process originated, what were the connections? Remember, I have NO math background. I just want to understand the logic and structure of the process. Thanks.

[@schmetterling4477]

@@jamestagge3429 How much are you going to pay me to read that bullshit now? ;-)

[@atol71]

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.

[@atol71]

I do hope you do not declare empiric example (empiric example of cut board and knife) void like the last one I talked about it. If you do all your Academic mathematics is VOID.

[@glebpolevoy278]

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

[@joeldavidhamkins5484]

I guess you are inquiring about the Feferman theory, which is interesting because it is a theory that proves its own consistency, which would seem to contradict the incompleteness theorem, except that it isn't a computably axiomatizable theory. So it doesn't actually contradict the incompleteness theorem.

[@glebpolevoy278]

The question is why the Feferman theory isn't computably axiomatizable, if PA* = PA. Isn't PA computable axiomatizable?

[@joeldavidhamkins5484]

@@glebpolevoy278 We can't prove in PA that PA* and PA are the same theory. We can only do so in PA+Con(PA). We believe this stronger theory is true, and this is why we believe PA* and PA have the same axioms, but the definition of PA* is to include the next axioms of PA only if this remains consistent, and this in general is not a computably enumerable criterion.

[@glebpolevoy278]

@@joeldavidhamkins5484, thanks!

[@MarleneWalker-su8ku]

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.

[@davidwilkie9551]

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.

[@Mizar88]

wtf you talking about