On Tue, Jul 14, 2009 at 11:20 AM, Dan Asimov <dasimov@earthlink.net> wrote:

Now suppose that TWP is really of this kind -- that it can neither be proved nor disproved (with a conventional finite proof in number theory).

Then we have the right to choose to add either TWP or its negation to the existing axioms and the resulting system will be consistent*. And so there exists a model for this new system. And so it (apparently) "exists".

BUT -- what if a hypothetical infinite check of all possible twin primes shows that TWP is true . . . yet we choose to add as an additional axiom its negation ~TWP. Then there is a model of this system, despite the fact that it is WRONG.

Would that system really exist?

Let me first answer not this question, but the opposite one. That is, "BUT -- what if a hypothetical infinite check of all possible twin primes shows that TWP is false . . . yet we choose to add as an additional axiom its negation TWP. Then there is a model of this system, despite the fact that it is WRONG." I'm answering a different question than the one you asked because it's a little simpler; I'll get to your original question later. The integers we know and love form a model that satisfies the peano axioms. But it is not the only model. There are other, 'nonstandard' models, that include not only the familiar integers, but other objects, which you can think of as "infinite integers". There are rules for how to add and multiply regular integers and infinite integers, and infinite integers and other infinite integers, and these extended multiplication and addition operations continue to satisfy associativity, distributivity, and all the rest of the Peano axioms. You might think that this is impossible because of the axiom of induction. Given that we have axioms (one for each proprety P) that say that if P(0), and P(n) -> P(n+1), then P(x) for all x, doesn't that guarantee that our model contains 0, 1, 1+1, 1+1+1, 1+1+1+1, and *nothing else*? Well, no. That's what this axiom schema is trying to say, but it's not able to actually say that. That's because the axiom scheme of induction only makes this statement about the countably many properties P expressible in first order logic, not the uncountably many properties that correspond to all the subsets of the integers. Addition and multiplication on the "infinite integers" in the nonstandard model can be very cleverly defined in such a way that the induction axiom "just happens" to hold for every first-order property P. And the property S(x) = "S is a standard integer" is not one expressible in first order logic. Now the answer to my modified version of the twin prime conjecture is clearer. TWP is false for the standard model of the integers, where there are no twin primes greater than 10^10^10^10^10^10. But in some nonstandard models in which there are pairs of nonstandard integers that are prime; infinitely many pairs in some models. So since you have a set of axioms that doesn't distinguish between the standard model and these nonstandard models, so you can't prove anything that is true in one of these models and false in another, so you can't prove TWP true or false. To answer the original question instead of my modification of it, you have to realize that the language of formal number theory doesn't let you say "there are infinitely many prime pairs". Instead, it lets you say "For any N, there exists a P such that P > N, P is prime, and P+2 is prime". If there are infinitely many prime pairs in the standard integers, but there are models with more, nonstandard, "infinite" integers, none of which are twin primes, then TWP is true in the standard model, but false in the nonstandard model. Not(TWP) is true in the particular model of the axioms you are thinking about, but the axioms are not "categorical", so there are other, different, models of those same axioms where TWP is false. Anticipating a few questions about this: 1. Q. What if you don't use the Peano axoms for the natural numbers, but instead use the axioms of set theory, ZFC, and consider TWP as a statement in ZFC about finite ordinals? A. The same thing happens; it's just more confusing and complicated to think about. There are other models of ZFC, in which the finite ordinals behave differently. In particular, the finite ordinals in some of these models are not isomorphic to the standard model of the natural numbers, but include "infinite integers". How can the finite ordinals include infinite integers? Because you can't really express "this set is infinite" in ZFC; all you can say is "This set has a bijection with a proper subset". There can be sets you think of as infinite that are "finite" within the model, because the bijections that would show them to be infinite aren't "sets" in these models. The fact that there are countable models of ZFC shows that the axioms do not succeed in characterizing the sets as the only model. The "uncountable sets" in these countable models are actually countable, because the whole model is countable. The bijections between these "uncountable sets" and the finite ordinals just aren't "sets" in these models. Q. OK, if there are other, nonstandard, countable models of the Peano axioms, there are models with N as the set. Show me addition and multiplication axioms on N that satisfy all the axioms, but aren't isomorphic to the standard model, but have other integers in addition to 0, 1, 1+1, 1+1+1, ... A. Sorry. While I can prove that such models exist, I can also prove that I can't show you one. That is, in any nonstandard model, either the + function or the * function or both is a nonrecursive function. So if I exhibited a model, and you asked me 'what is 2 "+" 3 in your model', I wouldn't be able to say "Yes" or "No"; I'd have to say "Yes if the following Turing machine halts", and you won't be able to add and multiply any pair of numbers unless you can solve the halting problem, which you can't. Q. Well if the standard axioms for number theory are satisfied not only by the "real" integers, but by these screwy nonstandard models that include these stupid infinite integers, we're using the wrong axiom system! Why don't we add enough axioms so that the only model that satisfies them all is the "real" integers? A. Can't do that. Or more precisely, if you want the set of axioms to be recursive (so you can write an algorithm that takes a statement as input, and always halts with the statement "Yes, that's an axiom" or "No, that's not an axiom") then it will have nonstandard models. That's just another way of restating Goedel's theorem. In thinking about this, it might help to think about axioms for some simpler system, where Goedel's theorem does not apply. Suppose we want to use our formal theorem prover to prove things about S10, the permutation group on N objects. We use as axioms the standard group theory axioms, and axioms that say that there are exactly 10! distinct objects. This lets us prove lots of theorems about S10, but not all true facts about S10, because there are other groups with 10! elements. So if we take one of the statements P about S10 that we can't prove from our axioms, we can add not-P as an axiom, and no contradiction will result, even though not-P is WRONG. Not-P is wrong in our intended model, S10, but not in one of the other groups of order 10!. In this case, we can fix the problem by adding finitely many additional axioms, producing a set of axioms only satisfied by S10 and no other groups. In the case of the natural numbers, or the sets, what Goedel showed is that we can't do that; for any finite or recursive set of axioms, there will still be other nonisomrphic models, in addition to our intended model, that satisfy the axioms. So there will always be statements that are true in our intended model, but false in other models, and we can't prove those statements.

I.e., spiritually, it's inconsistent, but we could not prove it thus with a conventional finite proof.

It's not inconsistent; you won't get a contradiction. It's just that it doesn't happen to be true in the particular model of the axioms you are thinking of. andy.latto@pobox.com