[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