Skip to content

Instantly share code, notes, and snippets.

@luqui
Created August 29, 2010 15:23
Show Gist options
  • Save luqui/556375 to your computer and use it in GitHub Desktop.
Save luqui/556375 to your computer and use it in GitHub Desktop.
@spencertipping says "Similarly, the Twin Prime conjecture will never be proven independent;
it will only remain an unsolved problem. Independent -> true."
Let me try to paint a picture of the Twin Prime Conjecture (TPC) having been proven independent
of, let's say, ZFC. That means "ZFC + TPC" is consistent, and so is "ZFC + ~TPC". Since both
of these are consistent, neither of them is concretely falsifiable. Let's see how:
ZFC+TPC: there are infinitely many twin primes. "Pick any number, you will find a twin prime
above it."
Imagine this: Pick an insanely huge number, and start checking for twin primes above it. What
if one never comes? You will just keep checking for eternity, knowing that "the next one is
it." This is a situation in which TPC is false despite being assumed true, and no contradiction
arises.
ZFC+~TPC: there are not infinitely many twin primes.
Imagine this: this means that there is an upper bound on all twin primes. So you run a program
to find it and the same thing happens: "found one, found one, found one, found one". You will
keep finding new ones for eternity, knowing that eventually you will stop. This is a situation
in which TPC is true despite being assumed false, and no contradiction arises.
So, in this world with an independent TPC, is it true or false?
@md2perpe
Copy link

md2perpe commented Jul 3, 2011

It still sounds like a contradiction for me...

Thinking...

Maybe I get it now... If TPC is a case of Gödel's incompleteness theorem under ZFC, then it's neither provable nor provable in ZFC, and ZFC+TPC would be consistent. Yet TPC could have an actual truth value of being false.

Hmm... I really need to think this over... Are we understanding Gödel's incompleteness theorem correctly...?

@md2perpe
Copy link

md2perpe commented Jul 6, 2011

I found a good explanation of Gödel's incompleteness theorem at a Swedish forum:
https://www.flashback.org/sp31523789

Here's a Google translate of it (without any corrections):

It is significant that the English said "arithmetical statements". They believe claims about the natural numbers.

The thing is here that the natural numbers is, by definition, something that meets the Peano arithmetic. The problem is that the Peano axioms can not be expressed in first order logic. However, one can specify a weaker axiom, "Peano arithmetic", which can be written in first order logic. This, however, is weaker, and does not specify the natural numbers uniquely, but there are other models that satisfy all axioms of "Peano arithmetic", but not the natural numbers (in the sense that they do not satisfy Peano axioms.) Read more on Peano axioms .

Gödel's incompleteness theorem about first order logic. It says that if a theory containing Peano arithmetic type, there is a claim about the natural numbers that are

a) true, in the sense that they apply to the natural numbers, or in other words can be proved from the Peano axioms,

b) but not provably (in first order logic), in the sense that they can not be proved from the weaker axioms of Peano arithmetic (which, according to Gödel's completeness theorem, is equivalent to the existence of models of Peano arithmetic ("nonstandard models" in the wiki page) in which the claim in question is not true)

One can see Gödel's (first), incomplete kit as a claim of inherent limitations in first order logic.

Just noticed one word in the last sentence: "kit" should the "theorem".

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment