Godel's 2nd Incompleteness Theorem Explained in Words of One Syllable | Hacker News Reader

Godel's 2nd Incompleteness Theorem Explained in Words of One Syllable

www2.kenyon.edu

A math professor was giving a talk and stated that "given a false premise one can prove anything is true". A member of the audience then interrupted with "Ok then, 1 + 1 = 3, now prove that you are the pope."

The professor thought for a moment and began, "If 1 + 1 = 3 then 1 = 2 and since the pope and I are two then the pope and I are one."

That is a clever professor.

See http://en.wikipedia.org/wiki/Principle_of_explosion for the usual lines of reasoning that get used.

Bertrand Russell is the Pope

"The story goes that Bertrand Russell, in a lecture on logic, mentioned that in the sense of material implication, a false proposition implies any proposition. ..."

http://www.nku.edu/~longa/classes/mat385_resources/docs/russ...

Russell's paradox?

Cute, but that's something different again.

My bad... This is new to me. What is the difference?

Russell's Paradox is the statement "Does the set of all sets that don't contain themselves contain itself?" (Parse that as "The set of (all sets that don't contain themselves)".)

Now, obviously, the set of all sets contains itself, and in naïve set theory that isn't a problem: In naïve set theory, a set is just an unordered collection of any objects you can define; a set that contains itself poses no logical problems in an of itself.

However, once you define the set of "all sets that don't contain themselves", you run into an immediate problem: If it does not contain itself, it must, in which case it cannot, and so on, in a neat infinite recursion.

This is a real paradox, also known as a falsidical paradox, and a real paradox indicates a deep problem with the set of axioms it was derived from. (Banach-Tarski is not a real paradox by my definition; it is merely called a paradox because it is a counter-intuitive result.) Russell's Paradox blew naïve set theory out of the water; later set theories, such as Zermelo-Fraenkel (more commonly just called ZF), were very careful to not allow sets to contain themselves.

In case anyone is interested, the non-witty answer would go like this: Clearly, 1+1=2, which is not 3, so ¬(1+1=3) (by usual rules of addition). But also 1+1=3 (by assumption). Since 1+1=3, then either I am the pope, or 1+1=3. But we know that ¬(1+1=3), which means that I must be the pope.

Eh, this doesn't really explain Godel's 2nd Incompleteness theorem; it only describes it in a roundabout way. The entire piece could be shortened down to: in math, all false statements are possible (i.e. their impossibility cannot be proved), and it doesn't go into any reasoning behind it.

I'm not sure about Godel's 2nd, but his 1st theorem can be described and explained with one simple sentence: this statement cannot be proven. If it is proven, then a false statement is proven. If it cannot be proven, then the proving system is flawed.

I like George Boolos' explanation because it plays with my paradoxic sensebrain, with something like poetry. Why not call it a poem?

But I like your explanations too.

However, I think that the Goedel card is counter-played well by the Schrodinger one. "This statement cannot be proven" is only a false statement because you inspect it with your system. It might otherwise be completely true.

Ah, but "true" and "proven true" are two different things!

I'm sensing an epistemology thread developing...

Not so fast!

I am taking issue with the so-called "falsity" of the "this statement is false". If you imagine that statement, and imagine that what you imagine is probable in the extreme, outside of your imagination, free, and unmolested by your probings, then "this statement is false" is always, only, incidental.

And don't come back saying saying "false" and "proven false" are different. I can compare strings!

That's the thing though... I interpreted it as being a true statement, but one that cannot be "proven" to be true. I merely possess the strong belief that it is true.

Is your argument that the statement could possibly be false? Otherwise we're already in agreement... Nobody is suggesting the statement is false (I think).

Edit: to clarify, the statement in question is "this statement cannot be proven," not "this statement is false."

You are right about the statement in question. I got mixed up, but I think the principal of "same difference" applies :D

He says, "If it [the statement] is proven, then a false statement is proven." (Proven true or false?)

I am not interpreting the statement "this statement cannot be proven" as true, as you do, or false.

What I argue is that one's interpretation has an effect, without which the statement is neither true nor false, but, as I claim, incidental. We can imagine the statement, but what we imagine is not the statement, even if it looks and smells like it.

Thus, the Schrodinger Card trumps the Goedel. The trick here is that I am standing outside of "the system", not permitting myself to enter paradox land. If you so much as look at me, I'll get sucked in.

> However, I think that the Goedel card is counter-played well by the Schrodinger one. "This statement cannot be proven" is only a false statement because you inspect it with your system. It might otherwise be completely true.

Gödel doesn't actually rely on any argument regarding the meaning of the statement "this statement cannot be proven"; he merely uses it as inspiration for an analogous entirely formal construction.

This statement is false. True or false?

Does the set of all sets that don't contain themselves contain itself?

What's even crazier to me is that there are statements that aren't self-referential that are both not true and not false at the same time. For instance the continuum hypothesis [1], or anything to do with the axiom of choice, like the trippy Banach-Tarski paradox [2].

[1] http://en.wikipedia.org/wiki/Continuum_hypothesis

[2] http://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox

The continuum hypothesis sort of fits your description, but Banach-Tarski does not. If you take the axiom of choice in your system, Banach-Tarski is simply true (in that the described construction will create two spheres out of one). If you do not take the axiom of choice, it is simply false (in that it can not be defined). (And I'm sure somebody somewhere has worked out some sort of in-between state there, but let's keep it simple.)

While it's a very interesting thing to think about, there is one sense in which the paradox is trivially resolvable; while the axiom of choice may make sense in mathematics, it almost certainly is never used by the real universe, and you certainly can not construct two real spherical shells made of atoms of the same size as one original spherical shell in the real world. (Whether the universe is continuous is an open problem, but we know matter isn't.) A great deal of the reason why the mind rebels at the Banach-Tarski paradox is that it is built on a thoroughly aphysical axiom; that the aphysical axiom permits aphysical (and therefore counterintuitive) results is not that surprising.

By no means is that a criticism of BT, it is simply its nature. My personal position on constructivist vs platonic vs. blah blah blah is that in math, as long as you specify which axiom set you are using up front, there is nothing to be emotional about. (Except that I will reserve a special place of interest for whatever mathematics it turns out to be that precisely represents the real world. Alas, this is still a work in progress, though we can point to at least some characteristics of it.)

But it does fit the description. There is absolutely no statement that can be proven in standard math about the integers whose truth depends on the truth or falseness of Banach-Tarski. (More technically there is a theorem that any statement that can be proven about ZFC can be proven in ZF alone - this falls out of the construction that Goedel used to prove that ZFC is consistent if ZF is. The same construction and result falls out for many other axioms that you can add to ZF, including the closure of ZF is consistent, ZF + the consistency of ZF is consistent, ZF + the consistence of ZF plus the consistency of THAT is consistent, etc.)

Therefore the truth of Banach-Tarski has nothing to do with any statement you can readily make about the integers, which would include any statement that you can make about anything that can be done on a Turing machine.

Incidentally the whole debate about constructivism is much more subtle than you likely appreciate. For instance it is trivial to prove that almost all real numbers that exist, cannot be written down. (Proof, I can easily write out a countably infinite set of statements that could define real numbers. So the set of real numbers that can be written down is countable. But there are an uncountable number of real numbers, so almost all cannot be written down.) In what sense do said real numbers actually exist?

If our axioms say that numbers must exist, which have in a very real sense no actual existence, then are those axioms capturing what we want to mean by "exist"?

If you say it does not, then you're a constructivist who hasn't thought carefully enough yet. If you say it does make sense, then you've been brainwashed by decades of standard mathematical presentations into accepting a definition of "existence" that makes no sense to the average lay person. :-P

> If you do not take the axiom of choice, it is simply false

Nitpick: If you do not choose the axiom of choice, then Banach-Tarski is independent, not false. So you can't prove that it's true and you can't prove that it's false.

"If you take the axiom of choice in your system, Banach-Tarski is simply true"

- The exact same is true if you take the continuum hypothesis as an axiom. Both the axiom of choice and the continuum hypothesis are independent of the other standard ZF axioms

"If you do not take the axiom of choice, it is simply false"

- That is incorrect. It is only independent. To say it is false, another axiom(s) would need to contradict it.

"while the axiom of choice may make sense in mathematics, it almost certainly is never used by the real universe"

- neither are the real numbers. would you like to claim that pi, or the square root of 2, for that matter, also don't exist? How about the number 1?

Banach-Tarski is true if you accept the axiom of choice. Which is not especially interesting: Every theorem depends on the axioms used to prove it; axioms are, in fact, what separates math from the natural sciences, and why 'truth' is available to mathematicians as long as you stipulate that a theorem is only absolutely true if you accept the axioms as absolute.

None of this involves the kind of actual (or falsidical) paradoxes the incompleteness theorems do. (Note that the Banach-Tarski Paradox is a viridical paradox, as it is a true result that is only thought paradoxical because it contradicts naïve intuition. A falsidical paradox is one that shows a true flaw or limit in a logical system, such as Russell's Paradox is to naïve set theory. This terminology is due to Quine.)

not all axioms are created equally. some axioms are simple, like that the empty set exists. to think that we should have all these simple axioms, and then out of left field accept the continuum hypothesis as an axiom is a bit weird don't you think? also weird is that we can build up all this mathematical machinery from the ZF axioms, but still can't answer some seemingly innocuous questions.

that's a good distinction you make in the second paragraph. to me though, the viridical paradoxes are more interesting :-)

>to think that we should have all these simple axioms, and then out of left field accept the continuum hypothesis as an axiom is a bit weird don't you think?

It's like the parallel postulate - famously much more awkward and complicated than the other axioms of geometry, and you can do most of geometry the same with or without it. But even so, most of us choose to use standard euclidean geometry and accept the parallel postulate.

>also weird is that we can build up all this mathematical machinery from the ZF axioms, but still can't answer some seemingly innocuous questions.

I think of it like this: "the language of mathematics is expressive enough that we can formulate nonsense questions". If you look at it that way the incompleteness theorem isn't terribly surprising; in natural language any five year old can ask unanswerable questions.

This sentence is true. True or false?

I took two classes by George Boolos at MIT. They were a lot of fun, and Prof. Boolos was a rather strange fellow.

The Department of Linguistics and Philosophy has a memorial display case filled with some of Boolos's favorite puzzles. You should check it out if you're in the area.

Consider superposition, where it is both true and false at the same time (and has been proven)

Russell's Paradox :-)

The axioms of Zermelo-Fraenkel set theory don't admit the construction of a "set of all sets that don't contain themelves".

So...

  If it can be proved that it can't be proved that two plus two
  is five, then it can be proved as well that two plus two is
  five, and math is a lot of bunk.

Then:

  p: it can't be proved that 2 + 2 = 5
  q: it can be proved that it can't be proved that 2 + 2 = 5

  q → ¬p

Thus if it can be proved that it can't be proved that 2 + 2 = 5 then it can be proved that 2 + 2 = 5. (i.e. when q is true, p cannot be true)

Sorry, had to do this for myself because I'm just starting a course in discrete mathematics!

I like the way this explanation considers it a first class possibility that "math is a lot of bunk".

This is a bit ingenious, it should actually be "the theory in which we are working is a lot of bunk" (theory refers to a set of axioms), and maths is a lot broader than one specific theory.

That is, if one proves Peano arithmetic[1] is inconsistent (which would really suck), this would not effect the consistency or otherwise of other independent theories, like, for example, Presburger arithmetic[2] which has actually been proved to be consistent.

[1]: https://en.wikipedia.org/wiki/Peano_arithmetic [2]: https://en.wikipedia.org/wiki/Presburger_arithmetic

Peano arithmetic has also been proved consistent (by Gödel himself, Gentzen, and others) but all of the proofs necessarily use methods slightly beyond Peano arithmetic. Gentzen proved the consistency of PA from primitive recursive arithmetic (a much weaker theory than PA, lacking quantifiers) combined with transfinite induction up to a particular ordinal. Gentzen also proved that this is more-or-less the best possible.

Similarly, since Presburger arithmetic can't even express its own consistency, never mind attempt to prove it, any proof of the consistency of Presburger arithmetic must use methods beyond Presburger arithmetic, which will probably subsume Presburger Arithmetic itself.

While formal consistency results have some meaningful technical consequences, from afar they often give off an aire of preaching to the converted. Anyone who accepts transfinite induction up to the ordinal in Gentzen's proof will probably have no problem accepting PA itself.

Reminds me of this classic: http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html

2 + 2 = 5; for large values of 2.

Or Python evil. (https://gist.github.com/1208215)

Or Haskell.

  let 2+2=5 in 2 + 2

(Significantly less mind-blowing though.)

interesting and funny though for somebody who doesn't know Haskell

Or small values of 5.

So to compensate for large values of 2, provide a small value of 5?

I suddenly have a very strong urge to read Alice in Wonderland.

Ahh but can it be proved that language can prove anything?

Well... the article attempts to "explain" rather than to "prove".

Unfortunately, this write-up is a load of irresponsible crap, because it can be proven that it can't be proven that two plus two equals five.

This is a load of ivory-tower hogwash, precisely why people get turned away from math and philosophy.

>because it can be proven that it can't be proven that two plus two equals five

Really? What does that even mean? In what number system it can it be proven? Does it hold for all?

>This is a load of ivory-tower hogwash, precisely why people get turned away from math and philosophy.

If people get "turned away from math and philosophy" then it's the peoples' problem, not math and philosophy's problem.

Can you supply us the proof that it can't be proven that two plus two equals five? Even a citation would be fine. Thanks!

The Math 101 'proof':

Assume it can be proven that 2 + 2 = 5.

Then 2 + 2 = 5.

It can be proven that 2 + 2 = 4.

The closure axiom of addition states that the expression 2 + 2 is a unique number.

4 != 5.

Therefore it can't be proven that 2 + 2 = 5.

-----

I'm sure it can't be that simple, but logically I can't see a reason why not.

You haven't proven that it can't be proven that 2 + 2 = 5. All you have proven is that if 2 + 2 = 5, then mathematics are inconsistent. Which they could be; you can't just assume math and logic are consistent.

> you can't just assume math and logic are consistent.

What a bunch of bollocks.

Precisely my point. Wow, that guy really stepped in it.

Claiming that logic isn't valid is worse than a logical contradiction, because if logic isn't valid, you can't claim anything.

Nobody ever said logic isn't valid. We're talking about consistency.

If logic isn't consistent, then logic isn't valid.

I'm not assuming specialized definitions of "consistency" and "validity" here, just your normal everyday layman's usage.

Well, you were responding to someone who was using the correct formal terms. You, after all, don't dispute the second theorem - but given it uses the term "consistent" you can hardly complain when someone makes their argument using the same terminology as the theorem you agree with!

Interested in what you define "consistent" and "valid" as in laymans terms though.

Take two objects. Take two more objects. How many do you have? Four. Could you ever have five? No. Thus, two plus two does equal four, and it does not equal five.

Can you ever prove something to be true, that is not true? No; your proof would simply be incorrect. By definition of "proof" and "truth."

Thus, it can't be proven that two plus two equals five.

I would like to hear your response to this. I don't understand how mathematicians can justify referencing some kind of mathematical formalism and just skipping reality altogether, and then not mentioning that they had done so.

To be clear, I am not contesting Godel's Second Incompleteness Theorem; I'm criticizing the writeup posted here, which uses everyday language to blatantly contradict what is obvious in reality.

For someone who said that someone who pointed out that you can't assume math and logic are consistent "really stepped in it", you have a funny way of proving you don't contest Godel's second incompleteness theorem, which is:

For any formal effectively generated theory T including basic arithmetical truths and also certain truths about formal provability, if T includes a statement of its own consistency then T is inconsistent.

A formalism (layman's definition of "formalism") need not include a statement of its own consistency in order to be valid (including, in order to be consistent).

For example, I know that basic addition and subtraction are valid by observing individual concrete objects in reality, rather than because of some kind of formalism stating that.

I am not very familiar with the kind of "math and philosophy" that went into Godel's theorems, but what I'm saying is that either (a) actual math and logic as such (as opposed to something made up, like a false math where 2 + 2 can equal 5) are ruled out by the giant disclaimer that takes up most of the 2nd theorem (i.e., they are not "formally effectively generated theories..."), or (b) they are, but simply "do not include a statement of their own consistency."

Perhaps do some reading up before making a fool of yourself.

Wow. I've actually done a lot of reading in epistemology and done a lot of thinking about these issues. I would have really appreciated a serious response from you.

For example, I would have liked to hear whether you agree that 2 + 2 = 4 (for example) can be proven from looking at actual concrete objects in reality (e.g., I take 2 pens from the left side of the table, two pens from the right, put them all in the middle, and count them... and then you can, of course, abstract away to get a concept of "unit"... etc).

Try reading up on Hilbert's second problem. Wikipedia does a good job [1]. Then read about Peano axioms [2]. Finally try to understand what is meant by the term "consistency" [3]

1. http://en.wikipedia.org/wiki/Hilbert%27s_second_problem

2. http://en.wikipedia.org/wiki/Peano_axioms

3. http://en.wikipedia.org/wiki/Consistency#Consistency_and_com...

Reply on news.ycombinator.com