Ep. 7 Gödel Made Easy: Explaining One of the Most Important Mathematical Demonstrations of All Time
Mathematician Kurt Gödel in 1931 published his two famous “incompleteness theorems,” which showed the principled limits on the knowledge we could generate from formal axiomatic systems. Loosely speaking, Gödel showed that there exist true statements about numbers that we will never be able to prove are true. His results have been cited not just in mathematics but also computer science and philosophy. In this episode, Bob details more precisely just what Gödel demonstrated, and gives an intuitive explanation of how Gödel did it.Gödel’s results are some of the most frequently-cited in the 20th century, and revolutionized how people think about truth and knowledge. Even if you have no formal mathematical background, rest assured that this episode will BLOW YOUR MIND.
Mentioned in the Episode:
- The Three Lads and the Lizard King, Bob’s story (written for his son) that we will review in January 2019.
- The Wikipedia entry on Gödel’s Incompleteness Theorems.
- “Numberphile”‘s YouTube episode on Gödel’s Theorems.
- The Paris-Harrington Theorem, the first “natural” mathematical proposition that is true but unprovable (in a well-defined sense).
- A conjecture on the ostensible loophole that Gödel discovered in the U.S. Constitution.
- BONUS (not mentioned in episode): Steve Landsburg’s riddle that relies on Gödel’s Incompleteness Theorems.
The sound engineer for this episode was Chris Williams. Learn more about his work at ChrisWilliamsAudio.com.
About the author, Robert
Christian and economist, Chief Economist at infineo, and Senior Fellow with the Mises Institute.
For those who actually want to go through the proof, the following book (in German) can be recommended: Dirk W. Hoffmann, Die Gödel’schen Unvollständigkeitssätze — Eine geführte Reise durch Kurt Gödels historischen Beweis, 2013, Springer Spektrum.
Great show Bob! I am glad that you are expanding the range of topics you discuss for the new podcast. It’s called the Bob Murphy Show so whatever Bob Murphy finds interesting should be fair game! I’m a software engineer and came to appreciate Gödel during my undergrad days as well. I would recommend Nagel & Newman’s short book “Gödel’s Proof” as a solid next step for ambitious laymen who want to read more of and deeper into the proof.
Steve Patterson has talked about this. I’m pretty sure that would be a good interview, for whatever that’s worth.
But isn’t this just a mathematical representation of the self-referential (or self recursive) being incoherent? I just don’t see the extra power of a mathematical representation of a linguistic incoherent statement.
I mean, you mentioned that it doesn’t take a genius to identify that the statement ‘95% of the universe is just invisible stuff” in reference to dark matter/energy, is idealogical. It could simply be their model is incorrect…
Numberphile is a good example of accepting nonsense, like scientism navelgazing “oh so counter-intuitive!” when they think the sum of all real numbers has a finite result:
https://www.youtube.com/watch?v=w-I6XTVZXww
infinities are the bane of current mathematics.
Todd, I am familiar with Steve’s stuff and I applaud his ambition (though I troll him a lot on Facebook). I am glad he exists; it’s worth pointing out that maybe the steps involving infinity are invalid.
However, two things about you saying this is the same thing here with Godel:
1) I don’t think there are any steps involving an infinite series of operations to generate the Godel sentence (but I could be mistaken).
2) It’s definitely more sophisticated than the words, “This sentence is false.” The proposition actually says something like, “The integers a, b, c do not evenly divide the integer n.” And then by the way Godel built up his system, you realize that either (a) your axiomatic system contains contradictions or (b) that statement about those particular integers is true, but you can’t prove it with your particular axiomatic framework. That is a lot more meaningful than someone saying, “I’m lying to you right now.”
Godel numbers proofs of statements about numbers, i.e. he defines a natural number corresponding to each proof of a statement about natural numbers within a particular formal system, PM (Russell’s Principia Mathematica). PM is a theory of the natural numbers (0, 1, 2, …) based upon Peano’s postulates.
Godel then constructs a predicate with one free variable, P(n). P(n) is either true or false depending upon the number n. P(n) is constructed so that if P(n) is true, then n corresponds to a proof of the proposition G. G says “not (there exists n satisfying P(n))”. The negation of G is “there exists n satisfying P(n)”.
If G is provable, then no number satisfying P(n) exists, but if this number does not exist, then no proof of G exists; therefore, G can have no proof if PM is consistent.
If not G is provable, then a number exists, and this number corresponds to a proof of G; therefore, not G can have no proof if PM is consistent.
P(n) is a finite formula in PM, but G asserts the non-existence of a number satisfying the predicate, so it is equivalent to an infinite sequence, namely
~P(0) & ~P(1) & ~P(2) & …
If PM is consistent, neither G nor ~G (not G) is provable within PM, so PM is either incomplete or inconsistent.
G is undecidable, or PM is inconsistent. This summary of the result is technically more accurate than “G is true but unprovable.”
A more familiar example of an undecidable proposition within a conventional theory of “number” (the “real” numbers) is
No number x satisfies x*x = -1. (A)
A “proof” of this proposition might be:
1) The square of every positive number is positive.
2) The square of every negative number is positive.
3) The square of zero is zero.
Therefore, no number satisfies (A).
But this proof assumes that positive numbers, negative numbers and zero exhaust the class of “numbers”. Mathematicians pondering general solutions of polynomial equations realized that an elegant, general solution of these equations exists only if we considers “numbers” not belonging to the “real number line” that we may intuitively associate with “number”. If we expand the idea of “number” to incorporate “complex numbers”, including a solution of x*x = -1, polynomial equations generally have solutions in this expanded class of numbers.
In his book “Godel, Escher, Bach”, Douglas Hofstaedter discusses a theory of “supernatural numbers” in which Godel’s undecidable proposition is similarly false by assumption, but the number satisfying P(n) is not among the “natural numbers” presumed by Godel’s numbering of proofs within PM.
Can’t decide if he looks like a mathematician or a Gulag kommisar.
Hofstaeder’s GEB cannot be allowed to go unmentioned in this context:
https://www.goodreads.com/book/show/24113.G_del_Escher_Bach
Bob,
Though there is nothing I totally disagree with in your explanation of what the theorem says, the way you explain it makes me think that we think differently about what math does exactly. For instance, when you describe axioms as “propositions no one would conceivably object to”, this makes math sound ultimately grounded in what we humans generally agree to be true statements about the world. The pursuit of mathematical truth, however, is of course not motivated by the world outside the mind at all. Logic is essentially just symbol shunting. The claim that the axioms are “true” or “obvious” or “unobjectionable” is meaningless to mathematics.
This way of talking mistakes the axioms for our ideas about what they represent. If an axiom seems obvious, it is not due to any relation between that axiom and an aspect of the outside world. The feeling stems from a strong analogy between the axiom and a relationship among some ideas we possess. Whether those mental objects represent anything in the world is irrelevant to the truth of whether their relations in our minds form a logical structure that is inconsistent or lacking in some critical attribute we would naturally like to add or some other statement strictly about those mental representations which is what the project of mathematics concerns itself with.
When you say “If it turned out math was inconsistent, it would be to a mathematician like a religious person finding out God didn’t exist”, you make it sound like any inconsistency in say, Peano Arithmetic, would imply some kind of contradiction in the fabric of the universe. If it were possible to prove a contradiction from the Peano axioms, in fact what that would mean is that our idea of an infinity of numbers is inconsistent- that imagining the properties of countable infinity is like musing about an omnipotent god making a stone heavier than he can lift, or a set of all sets that do not contain themselves. It would be a logical problem with the notion itself- a problem with our minds, not directly about the universe.
When you distinguish truth as something totally different than provability, you seem to imply that truth is necessarily about the outside world which math never quite embodies precisely. But clearly there is a truth to mathematical statements taken on their own. There is an unfeeling truth to a statement provable in mathematics which is given life by how we interpret the terms described by the axioms. The truth of a mathematical statement is a truth only directly about our ideas.
It is just this idea of truth where we differ. An axiom is devoid of truth. It only has a mathematical interpretation. A system is not inconsistent because it contains a “false axiom”. It is inconsistent because its axioms taken together generate contradictions because an idea represented by one or more of the axioms is not sound.
Agreed.
I found the chapter on Gödel in Stephen Hawking’s “God Created the Integers” to be especially enlightening on the incompleteness theorems.
Math statements do not exist by themselves as a current real time truth.
Negative one apple cannot be true in reality without reference to something other than the equation, other than the mathematical expression.
There can be an integer number of apples, doing nothing other than existing. There cannot be a negative number of apples existing in the same real world way. Negative apples means some process is occurring. So negative numbers would indicate the truth of the ‘environment’ of the statement in addition to the statement itself.
Maybe paradox always implies something specific about the conditions or the environment.
But math treats negative numbers as amounts of things that exist directly. Negative numbers should be called imaginary numbers.
Maybe that is why math cannot prove this and that, it violates ‘real world thingness’.
“There can be an integer number of apples, doing nothing other than existing. There cannot be a negative number of apples existing in the same real world way. Negative apples means some process is occurring.”
Specifically, negative numbers are merely expressing positive debts.
To say that there are negative one apples is to say that one apple is owed.
I don’t take this to mean that negative numbers should be called imaginary numbers, but rather that negative numbers are really just positive numbers in an accounting context.
Hey Bob, here is a topic for you:
If Ken Arrow’s theorem proved it’s not possible to have a fair election system, yet The Price System is the best voting system ever “invented”, what gives ?
I thought you’d enjoy.
I already follow several libertarian podcasts, so I didn’t jump on yours immediately, but this episode reveals a diversity of content appealing to me. Thanks.
Glad to hear it, thanks.
Unless there’s something about math that obligates Godel to assign the integer “123” to the Godel sentence, then the function of “123” is not an integer, but a label – a number formatted as text, if you will.
*Takes a bow*