On Thu, Apr 16, 2015 at 9:55 PM, David Wilson <davidwwilson@comcast.net> wrote:
Wikipedia states that
The Paris-Harrington theorem… is true, but unprovable, in Peano arithmetic.
The article goes on to intimate that PH can be proved in second-order arithmetic (the argument seems to be that second-order arithmetic can be used to prove PH from the “infinite Ramsey theorem”. A proof is given for the latter, which I assume uses Peano Arithmetic, am I right?)
I don't think you can even state the infinite Ramsey theorem in the language of Peano arithmetic.
At any rate, I would think that if PH were “true but unprovable” in PA, then either PH or ¬PH would be consistent with PA.
Correct
This would mean that we have two “flavors” of arithmetic: PA + PH, which is consistent with second-order arithmetic, and PA + ¬PH, which is not.
Correct, if by arithmetic you mean "a system in which the peano axioms are true". Incorrect if you mean "a system that models my intuitions about the integers", because my intuitions about the integers include more facts about them than just the Peano axioms and things that can be deduced from them.
So when the text says that PH is “true but unprovable in PA”, I’m hearing “true in second-order arithmetic but unprovable in PA”, with that tacit understanding that “arithmetic” subsumes second-order arithmetic?
Does this simply reveal a bias toward second-order arithmetic over other flavors of arithmetic such as PA + ¬PH?
(to keep things in ASCII, I'm using ~ for "not", and turning my upside-down A's and backwards E's right-side up). Depends on what you mean by "bias". I don't start from the Peano axioms and say "I'm equally interested in all of the systems that satisfy these axioms". I start with the integers, and say "I'm interested in what I can prove about this set of object". The Peano axioms are true of this set of objects, and so everything provable from these axioms is also true, but so are lots of other things about the integers, which I can prove from stronger axiom systems, such as the axioms of set theory. For every statement of Peano arithmetic, there is a corresponding statement in set theory, and everything provable in Peano arithmetic corresponds to a statement provable in set theory, but there are unprovable statements in Peano arithmetic that correspond to provable statements in set theory. The Paris Harrington theorem is one of them. The model of the nonnegative integers I am biased towards is the one that includes 0, S(0), S(S(0)), S(S(S(0))),... and *nothing else*. There are other models that have all of these elements, and a bunch more "infinite integers" that are greater than any of these. (S is the successor function; S(n) = n + 1). (I can't give a full description of any one of these models, for a reason I'll get to in a minute, but they exist). You might think this was impossible because of induction; The set of "numbers reachable from 0 via the successor function" includes 0, and if it includes x, it includes S(x) so doesn't induction guarantee that it includes all the nonnegative integers? Nope. You'd like it to say that, but it doesn't. The induction axiom schema doesn't talk about all sets of integers; it can't, because the language of Peano arithmetic only talks about integers, not sets of integers. For every first-order logic predicate P(x), we have an axiom that says (P(0) ^ Ax(P(x) -> P(x+1))) -> AxP(x). But this is only for the (countably many) properties definable by a predicate in Peano arithmetic, not for the (uncountably many) sets of integers. The non-standard models of the axioms, the ones I'm "biased against", have "infinite integers", and have very cleverly defined successor, +, and * on these infinite integers so that induction "just happens" to work for all first-order predicates, defeating the failed attempt by the induction axiom schema to say "there aren't any infinite integers" How clever do you have to be to define such a system of infinite integers? Cleverer than I, and cleverer than a computer. That is, if we try to define S, + and * on a countable set to make it into one of these nonstandard models of the integers, then either + or * is a noncomputable function. Another way to look at why I'm "biased against" PH + ~PA is that while it's consistent, it isn't "omega-consistent". That is, there are predicates P such that all of ~P(0), ~P(S(0)), ~P(S(S(0))), ~P(S(S(S(S(0)))))... are theorems, but so is Ex(P(x))! P(x) is true for one of those "infinite integers" that exist in the weird non-standard models of the integers, but not in the model Peano was thinking about when he invented the axioms.
Or is my argument above wrong? Is it somehow possible that PA + ¬PH is contradictory, yet PH is unprovable in PA?
Nope. The axioms of predicate calculus allow proof by contradiction. If you can prove a contradiction from PA + ~PH, then you can prove PH in PA, by the proof "assume not; then we get the following contraction..." Andy Latto alatto@pobox.com