Larry_D'Anna comments on The Cartoon Guide to Löb's Theorem - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (90)
J Thomas:
Once more through the mill. If PA proves that 6 is a prime number, then 6 is really a prime number. Can you prove that if PA proved 6 was a prime number then 6 would be a prime number? How would you do it?
If PA |- "forall x y . x * y = 6 => |x|=1 || |y|=1" then N |= "forall x y . x * y = 6 => |x|=1 || |y|=1" (N = the natural numbers equiped with + and *) so for all x and y in N, N |= ",x * ,y = 6 => |,x|=1 || |,y|=1" (where ,x means a constant symbol for x) if x*y = 6 then N |= ",x * ,y = 6" so therefore N |= "|,x|=1 || |,y|=1" thus either N |= "|,x| = 1" or N |= "|,y| = 1" thus either |x|=1 or |y|=1 therefore we have that if x*y = 6 then either |x| = 1 or |y| = 1 therefore 6 is prime therefore if PA |- "6 is prime" then 6 is actually prime
Of course it is also a meta-theorem that for any sentence phi in the language of PA that
ZF |- "PA |- phi => phi_omega"
where phi_omega is phi relativeized to the finite ordinals.