Goldbach's Conjecture (Theorem?)

[CRGreathouse]

Thanks for your comments. Why choose s arbitraily. S is half the even number, the object for the primes are sought.

Choosing s arbitrarily is the right way, no problem there. But your proof does not show that either p or p' is prime. Now it's easy to show that one of p or p' can be chosen to be prime for s >= 1, by the infinitude of the primes and the fact that 2 is prime, respectively. But there's no reason to think that they can be chosen so that both are prime, and your proof does not even attempt to show that they are prime.

 

[namus]

Hi Dragonfall,

What al-mahed means is that for a question like goldbach conjecture proving undecidability is as hard as proving the theorem itself. Well, that is a bit erroneous, in fact proving it is undecidable is in fact fallacious. For if the conjecture is false there exists a proof (the very number that is not sum of two primes, together with the list of primes upto it and their pairwise sums, and pair-by-pair verification that neither of the sums is the number, establishes a (possibly very long) proof of its falsity. So when you prove that it is undecidable, you consequently prove that is it is true, and thereby contradict your own theorem.

And the above is a proof that it cannot be proven undecidable. Is this too confusing?

However, there exists a faint possibility of the following (let us go into terms more concrete that "undecidable" which can mean "neither can it be proven true, nor untrue", and just consider statements like "xyz can be proven true"):

Consider the theorems P_0, P_1, P_2, ...

where P_0 = the goldbach conjecture.

and P_{i+1} = "The statement P_{i} cannot be proven true".

Now there is a possibility that all the statements P_0, P_1, ... are true, but therefore, none of them can be established.

The morale of the story is that if you want to enter into any investigation around goldbach conjecture, you better invest your time for the conjecture itself, no questions on its decidability, and decidability thereof in higher order, can be attained-- if true. :)

 

[namus]

I am terribly sorry. I seem to have posted a comment into the wrong thread... multitab parallel processing... :) sorry guys.

 

[namus]

Hi Dragonfall,

What al-mahed means is that for a question like goldbach conjecture proving undecidability is as hard as proving the theorem itself. Well, that is a bit erroneous, in fact proving it is undecidable is in fact fallacious. For if the conjecture is false there exists a proof (the very number that is not sum of two primes, together with the list of primes upto it and their pairwise sums, and pair-by-pair verification that neither of the sums is the number, establishes a (possibly very long) proof of its falsity. So when you prove that it is undecidable, you consequently prove that is it is true, and thereby contradict your own theorem.

And the above is a proof that it cannot be proven undecidable. Is this too confusing?

However, there exists a faint possibility of the following (let us go into terms more concrete that "undecidable" which can mean "neither can it be proven true, nor untrue", and just consider statements like "xyz can be proven true"):

Consider the theorems P_0, P_1, P_2, ...

where P_0 = the goldbach conjecture.

and P_{i+1} = "The statement P_{i} cannot be proven true".

Now there is a possibility that all the statements P_0, P_1, ... are true, but therefore, none of them can be established.

The morale of the story is that if you want to enter into any investigation around goldbach conjecture, you better invest your time for the conjecture itself, no questions on its decidability, and decidability thereof in higher order, can be attained-- if true. :)

 

[ramsey2879]

sorry, my mistake, the correct is gcd(3a',5b') = gcd(3a'', 5b'') = 1, it is a necessary condition to both expression represents both prime numbers, but obviously it is not sufficient

Sorry but not all primes can be expressed in the form 3a+5b, in particular 7 can not be put into that form and (5+7 = 12) is not the sum of primes according to this form.

 

[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" .