All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Paradoxes
Provably unprovable? (Posted on 2004-08-22) Difficulty: 4 of 5
Gödel proved that there are true sentences that cannot be proved.

Suppose I told you that the Goldbach conjecture is one of those. (The Goldbach conjecture supposes that every even integer number can be expressed as the sum of two odd primes.)

Is that logically possible? (And, no, I haven't proved it!)

See The Solution Submitted by Federico Kereki    
Rating: 3.2727 (11 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Problem Stated Wrong - GC Can't Be FALSE (has counterexample) & Unrefutable Comment 36 of 36 |

This puzzle is stated wrong. It is possible for Goldbach's Conjecture GC to be true and unprovable. We'll never find a counter-example but will never know if one exists.  It cannot be that GC is FALSE and we cannot prove that fact.  This is the miswording of this puzzle.  If FALSE there is a counter-example and we can find it.<o:p></o:p>

Just like Godel's 2nd Incompleteness Theorem says we may be consistent but then will be unable to prove it. Consistent means no proof of a contradictory sentence P&~P can be found but we'll never prove that - Goldbach is saying no proof of a counter-example number can be found but likewise perhaps we'll never prove it.<o:p></o:p>

The solution says if GC is true then the program doesn't stop so it's true and we just proved it. No! We only said that if we are given that GC is true, then "GC is true!!" is true so GC is true. We didn't prove it - we just repeated our given assumption.  We didn’t show that we can actually prove it.<o:p></o:p>

GC can't be FALSE and not provably false. If false, there is a counter-example and we can find it and showing it gives a proof that GC is FALSE. It is not possible for ~GC but ~ |- ~GC. GC can't be FALSE and undecidable, not resolvable, not provably so. If FALSE we can prove it is FALSE!<o:p></o:p>

Formally we say that GC being FALSE is recursively enumerable. (exists x)P(x) where P() is recursive means if P(N) then |- P(N) we can prove it and ~|-~P(N) we cannot refute P(N). (exists x) is "a counter-example x exists" and P(N) is "N if even is the sum of 2 primes". That is easy to check so it is recursive, so when it is FALSE it is provably false.<o:p></o:p>

The basic conclusion comes from Marvin Minsky's Computation: Finite and Infinite Machines.<o:p></o:p>


  Posted by Charlie on 2012-04-26 12:10:45
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information