[FOM] CH and mathematics

Vaughan Pratt pratt at cs.stanford.edu
Mon Jan 21 15:57:38 EST 2008


joeshipman at aol.com wrote:
> How about "we'll never know whether busy-beaver(googol), expressed as a 
> base=10 integer, has an even or odd number of digits?"
> 
> (By this I mean the number of 1's output by the 
> longest-running-but-still-halting-on-blank-input TM in a 2-letter 
> alphabet and 10^100 states has an even or odd number of digits.)
> 
> That's probably unknowable even if 10^100 is replaced by a feasible 
> number like 10^5.

Why not Goldbach's Conjecture (GC), or Twin Primes?  These are definite 
questions that may turn out not to be knowable at all.

While on this topic, does Peano Arithmetic admit any notion of forcing 
analogous to that for ZFC?  Assuming it does, then unlike CH and ZFC, GC 
can't be forced true in some relatively consistent extension of say 
Peano arithmetic without actually proving GC, since if GC were false 
there would be a proof in ZFC of this, namely a witness counterexample, 
whence such an extension could not be consistent.

Is there an argument showing that GC can't be forced false in PA without 
settling GC?  A consistent extension of PA that forces not-GC would 
establish the unprovability of GC, but wouldn't it leave open whether GC 
is false or true-but-unprovably-so?  If so then this would seem an 
easier goal than trying to decide GC.

Vaughan Pratt


More information about the FOM mailing list