Monday, 4 September 2006

lo.logic - Is any true sentence in the second-order Peano Axioms provable

If a theory has only one model, then of course it is complete, in the sense that any
statement or its negation is a consequence of the theory, because either it holds in the unique model or it doesn't.



As you mention, there is only one model of second-order PA, and this is the model of the natural numbers. Thus, second-order PA is complete for first order assertions.



One can easily extend this to second-order assertions by observing that any isomorphism of the first-order structures will extend to an isomorphism of the second order structures also, if one decrees that the second-order part of the structures should contain all subsets. Thus, there is up to isomorphism only one second-order structure of second-order PA, and so the theory is complete for second-order assertions.



BUT, there are interesting things still to say about incompleteness. And the reason is that the concept of second-order is a set-theoretic concept, and so the question of which statements are true in this unique second-order model of second-order PA will exhibit many set-theoretic independences. That is, ZFC proves that the theory of the natural numbers is a complete theory, but different models of ZFC will have their natural numbers satisfying different statements. This is true already in the first order theory, since some models of ZFC will have the arithmetic statement Con(ZFC) being true in their natural numbers, but others will have the negation of this being true in their natural numbers.



Because of this kind of issue, many logicians prefer to understand the second-order theory in a first-order way, by saying that one specifies a second-order model by giving first it's first order part, and then also specifying the collection of subsets that are to be used as the interpretation of the second-order part. Thus, a second-order model of PA consists of a first order structure (N,+,.,<,0,1) together with a collection S of subsets of N, to be used for interpreting the second-order quantifiers over subsets. In this weaker sense of second-order, one loses the categoricity, and there can be non-standard models again even in the first-order part.

No comments:

Post a Comment