Mathematician explains Gödel's Incompleteness Theorem | Edward Frenkel and Lex Fridman

Please support this podcast by checking out our sponsors:

GUEST BIO:
Edward Frenkel is a mathematician at UC Berkeley working on the interface of mathematics and quantum physics. He is the author of Love and Math: The Heart of Hidden Reality.

PODCAST INFO:

SOCIAL:

[LexClips]

Guest bio: Edward Frenkel is a mathematician at UC Berkeley working on the interface of mathematics and quantum physics. He is the author of Love and Math: The Heart of Hidden Reality.

[baTonkaTruck]

I love that he mentioned Alan Watts, who had the best description of Goedel’s Theorem: “No system can define all of its own axioms.”

[jacksmith]

This guy might be the best guest you have had on Lex I love this dude

[TobyZobell]

This is the first time I've been introduced to this guy. I like how he seems to be more of a "unification of knowledge" type of person, rather than just a mathematician. He draws from examples everything from math, to pop-culture, to eastern and western philosophy, and so on. Thanks again Lex!

[arsartium]

Here are brief statements of the theorems for those interested:

Gödel's First Incompleteness Theorem states that "Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true, but not provable within that theory."

Gödel's Second Incompleteness Theorem states that "For any effectively generated formal theory T including basic arithmetical truths and certain truths about formal provability, T includes a statement of its own consistency if and only if T is inconsistent."

Just prior to publication of his incompleteness results in 1931, Gödel already had proved the completeness of the First Order logical calculus; but a number-theoretic system consists of both logic plus number-theoretic axioms, so the completeness of PM and the goal of Hilbert's Programme (Die Grundlagen der Mathematik) remained open questions. Gödel proved (1) If the logic is complete, but the whole is incomplete, then the number-theoretic axioms must be incomplete; and (2) It is impossible to prove the consistency of any number-theoretic system within that system. In the context of Mr. Dean's discussion, Gödel's Incompleteness results show that any formal system obtained by combining Peano's axioms for the natural numbers with the logic of PM is incomplete, and that no consistent system so constructed can prove its own consistency.

What led Gödel to his Incompleteness theorems is fascinating. Gödel was a mathematical realist (Platonist) who regarded the axioms of set theory as obvious in that they "force themselves upon us as being true." During his study of Hilbert's problem to prove the consistency of Analysis by finitist means, Gödel attempted to "divide the difficulties" by proving the consistency of Number Theory using finitist means, and to then prove the consistency of Analysis by Number Theory, assuming not only the consistency but also the truth of Number Theory.

According to Wang (1981):
"[Gödel] represented real numbers by formulas...of number theory and found he had to use the concept of truth for sentences in number theory in order to verify the comprehension axiom for analysis. He quickly ran into the paradoxes (in particular, the Liar and Richard's) connected with truth and definability. He realized that truth in number theory cannot be defined in number theory, and therefore his plan...did not work."

As a mathematical realist, Gödel already doubted the underlying premise of Hilbert's Formalism, and after discovering that truth could not be defined within number theory using finitist means, Gödel realized the existence of undecidable propositions within sufficiently strong systems. Thereafter, he took great pains to remove the concept of truth from his 1931 results in order to expose the flaw in the Formalist project using only methods to which the Formalist could not object.

Gödel writes:
“I may add that my objectivist conception of mathematics and metamathematics in general, and of transfinite reasoning in particular, was fundamental also to my work in logic. How indeed could one think of expressing metamathematics in the mathematical systems themselves, if the latter are considered to consist of meaningless symbols which acquire some substitute of meaning only through metamathematics...It should be noted that the heuristic principle of my construction of undecidable number theoretical propositions in the formal systems of mathematics is the highly transfinite concept of 'objective mathematical truth' as opposed to that of demonstrability...” Wang (1974)

In an unpublished letter to a graduate student, Gödel writes:
“However, in consequence of the philosophical prejudices of our times, 1. nobody was looking for a relative consistency proof because [it] was considered that a consistency proof must be finitary in order to make sense, 2. a concept of objective mathematical truth as opposed to demonstrability was viewed with greatest suspicion and widely rejected as meaningless.”

Clearly, despite Gödel's ontological commitment to mathematical truth, he justifiably feared rejection by the formalist establishment dominated by Hilbert's perspective of any results that assumed foundationalist concepts. In so doing, he was led to a result even he did not anticipate - his second Incompleteness theorem -- which established that no sufficiently strong formal system can demonstrate its own consistency.

See also,
Gödel, Kurt "On Formally Undecidable Propositions of Principia Mathematica and Related Systems I" Jean van Heijenoort (trans.), From Frege to Gödel: A Sourcebook in Mathematical Logic, 1879-1931 (Harvard 1931)

[johnstebbins]

Great show. I really love Frenkel. He is so clear and his enthusiasm and sense of wonder is infectious!

[kaibe]

This was one of my favourite shows from Lex. Edward is a truly remarkable human being, and it's always beautiful to see so much love and compassion in one's heart.

[DumblyDorr]

I think it's valuable to also go a bit into the whole "completeness & consistency" thing.

One could start with definitions and explaining why they're important things we want from formal systems.

Then one could proceed to a little history of how "cracks" in set-theory based formal systems began to be discovered by Frege and Russel almost as soon as those systems arose.

The story continues with a quick overview of the various approaches to these issues, like ZF(C), NBG, "New Foundations" and type theory (with Russell for a while, then dormant for a long time, then getting a big comeback with Per-Martin Löf and lots more interest recently with Homotopy Type Theory).

This brings us to a classification and analysis of the underlying issue - that of predicativity and impredicativity - one might briefly explain what that is and why it's problematic - using various examples of paradoxa of (direct or indirect) self-referentiality.

We can then explain how these developments and the predominant research institutions in Germany and Eastern Europe lead to Gentzen's proof of the consistency of (Peano) arithmetic - and how that was a process of formalization which took us around 2.5 millennia from basic arithmetic and logic to Gentzen's proof. The importance could hardly be overstated.

The "victory march" of formalization and the power of formal systems seemed assured.

... and then came Gödel.

[BerenddeBoer]

Edward Frenkel is so extremely lucid, just extraordinary.

[eamonnsiocain]

In another paper, Gödel developed an axiomatic system containing the self-referential statement, “This statement is false.” He then proved — within the same system —that “This statement is false” is true. All he needed was the countable numbers (the set N) and a few very simple rules.

On “Emergence:” Taking simple rules then applying them to a simple structure to produce complex “behaviour, ” is also a subjective process. In what axiomatic system can you consistently define both “simple” and “complex, ” then show that there are no self-referential contradictions?

[markcarey]

Ed Frenkel is one of my favourite people. His book is fantastic.

[jeremias]

Great video, people take calculus and algebra classes for years and no one explains to them the fundations of what you are studying as clear as this guy does

[cryptic]

Gödel's theorems challenged the notion of completeness and consistency within formal systems and had a profound impact on the philosophy of mathematics. They demonstrate inherent limitations of formal systems and suggest that there will always be truths that lie beyond the reach of any particular system. These theorems have also influenced the field of computer science, particularly in the areas of artificial intelligence and algorithmic complexity theory.

[risenloudly]

A full 14 minute in depth explanation of goedel's impossibility theorems, and then lex goes "so every why has a definite answer"

[arontesfay]

I love his comment on the findings of Godel and Turing being "life affirming". Very well said.

[sanjitdaniel]

Wow!! Great explanation of incompleteness! The best I have seen so far!

[elindauer]

I love this stuff. This channel never seems to disappoint.

[guntherschabus]

What a great an inspiring guy Mr. Frankel is. It’s simply great learning from his talks.

[brainxyz]

Great explanation!
Regarding the perception problem at 14:52, the top down perception in the brain can provide a trivial explanation. Just like Lex mentioned for neural networks, the bottom up sensory features leads two activated outputs: 0.5 Rabbit and 0.5 Duck. However, the top down awareness in the human brain can only attend to one output at time. So if you attend to the duck output, the duck neuron will be activated. Now because the information comes from top to bottom, all the related neurons to Duck will activate (none will activate for the Rabbit). And that is why you suddenly perceive it as 100% Duck or 100% Rabbit if your top down awareness attend to the Duck or vice versa.

[koraamis]

There are some nice ideas about emergence of complexity. As nothing is the same, there is an incremental effect by repetition, similar to what our memory in the brain does with the episodic memory, each time we see a cat for example, the cat experience adds meaning to our definition of cat, even if it is the same cat at the same place. A bit like Peircean semiotics thirdness, when we interpret a sign it can generate a new one, even more if instead of just one triadic relationship there is a whole network of it, by aggregation and interconnection, at some point it generates more complexity of evolving meaning, because it cannot be the same, different than in mathematics. In mathematics if we add 1 + 1 it is always 2, but in reality that is impossible, and the 2 will be always slightly different each time we add 1+1. In short, complexity has to emerge because repetition is impossible.