Goldbach's Conjecture (Theorem?)

[johnny_boy]

An attractive thought, but it doesn't work out.

The most obvious problem is that "Goldbach's conjecture is undecidable in PA" means that "PA + Goldbach's Conjecture is false" is a consistent theory!

I know this is super old school, but in case someone else finds this thread, I thought it might be worth clarifying this highly interesting discussion.

It's true that if GC is independent of PA then it's true. It's also true that PA + ~GC is consistent, but that's irrelevant to the previous fact. Consider a usual Godel sentence G, saying of itself that it's not provable. Well clearly G is both independent of PA and true (!) even though PA + ~G is consistent. Of course, any model for PA + ~G must be non-standard since there can be no standard witness to ~G (which is equivalent to a Sigma_1 formula).

EDIT: I thought it might be helpful to give an informal proof of why GC is true if independent. Suppose GC is independent and, for reductio, false. Then there's an n that is a counterexample to GC. Note that GC is Sigma_2, having the form ExAyAzF(n), so AyAzF(n/x) is true. But given F, obviously the universal quantifiers Ay and Az can be bound by n, and clearly Ay<nAz<nF(n/x) is decidable, whence PA-provable.

 

[Hurkyl]

It's true that if GC is independent of PA then it's true.

... for the finite ordinals, or some other isomorphic model. (in the set theory we've used to prove it)

It always bothers me when someone says "it's true" in a situation that could be interpreted as "it's true for the formal theory under consideration".

But given F, obviously the universal quantifiers Ay and Az can be bound by n, and clearly Ay<nAz<nF(n/x) is decidable, whence PA-provable.

I think your plan is basically to, by external induction on n, internally prove that

Ay<n: P(y)​

is equivalent to

$$\bigwedge_{y = 0}^{n-1} P(y)$$​

(both of which make sense because n is a finite ordinal and our formal logic allows up-to-some-finite-ordinal-indexed operations)

And so the claim "n is a counterexample to Goldbach's conjecture" can be proven equivalent to an (externally) finite conjunction of arithmetic equations involving only finite ordinals, which can then be straightforwardly proven true.

And so we have the (external) theorem "If a finite ordinal n is a counterexample to Goldbach's conjecture, then there is a proof in PA of that fact".

I think I'm happy with the argument...


(P.S. I've had no luck finding an internet reference on the properties of Sigma_n sentences. Do you know of one?)

 

[TylerH]

[English] Re: Goldbach's Conjecture (Theorem??)

not enough (I don't know if the correct word in english is this...)

"enough" makes sense, but "sufficient" is more often used. For example, if $a \Rightarrow b$, then you could say "a is necessary, but not sufficient for b."

I'm not picky. What you used was fine. I just like to help non-native speakers (and native speakers who didn't pay attention in language class). :)

 

[johnny_boy]

... for the finite ordinals, or some other isomorphic model. (in the set theory we've used to prove it)

It always bothers me when someone says "it's true" in a situation that could be interpreted as "it's true for the formal theory under consideration".

In the case of arithmetic "it's true" means "it's true in the standard model". I don't know anyone else who uses it differently. Likewise, for any theory that has a standard model, whenever someone says it's true relative to that theory, they almost always mean true in the standard model of the theory.

(P.S. I've had no luck finding an internet reference on the properties of Sigma_n sentences. Do you know of one?)

Look http://en.wikipedia.org/wiki/Arithmetical_hierarchy" .