Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

non-standard models of arithmetic in second order arithmetic?

Background: According to Godel's theorem, if we have, in a given consistent system S, a non-provable wff. A, then we can extend the system to either S1 or S2 by including A or ~A as a new axiom, respectively. Both S1 and S2, according to Godel, will be consistent. If S is a first order system, then both S1 and S2 have at least a model, (let us call them M1 and M2) and the two models are essentially different because in M1 A is true, but in M2 ~A is true. If S is PA (peano arithmetic), then that means that there are infinitely many unintended models in addition to the natural numbers, each one obtained by extending PA with a new axiom which is not true for the model of the natural numbers. These unintended interpretations are named non-standard models of arithmetic.

The question(s): The above conclusions refer to first order systems. However, it is unclear to why this argument is restricted to first order systems, as Godel's proof is also valid for second order systems: Any extension of second order PA can be consistently extended into two different systems by including any non-provable wff. A or ~A as a new axiom, respectively. These two systems should in turn describe two essentially different models, and so there should also be non-standard models of arithmetic in second order arithmetic.

The problem is, that it is often stated that second order PA determine the set of natural numbers uniquely, and so there should be not room for non-standard models of arithmetic in second order arithmetic, which contradicts what .

Metaquestion: I am sure there is something wrong in my reasoning leading to this contradiction. But I cannot find any errors, can anybody help me, please!!!!

share|improve this question
1  
The Incompleteness Theorem cannot be proved for a second-order system, unless one cheats and formalizes the underlying informal set theory in a first-order way. The downside of second-order PA is that there is no useful formal notion of proof. –  André Nicolas Sep 27 '12 at 6:23
1  
Second order arithmetic is still a first order theory. You can think of having two distinguished unary relations. One tell you if an element is is a "number" and the other tells you if an element is a "set". So all the logical theorem of arbitrary first order theories like the completeness and incompleteness theorems holds for second order arithmetics. –  William Sep 27 '12 at 6:50
1  
@William: That is not my understanding of the meaning of the term second-order arithmetic. –  André Nicolas Sep 27 '12 at 7:05
    
@AndréNicolas My statement is not entirely correct. It is the view often used Reverse Math. Wikipedia said the following: "Although second-order arithmetic was originally studied using full second-order semantics, the vast majority of current research treats second-order arithmetic in first-order predicate calculus. This is because the model theory of subsystems of second-order arithmetic is more interesting in the setting of first-order logic." –  William Sep 27 '12 at 7:25
    
@AndréNicolas. You said "The Incompleteness Theorem cannot be proved for a second-order system". I was unaware of that, can you please give a reference to investigate in further? thanks –  julian fernandez Oct 7 '12 at 23:28
show 1 more comment

3 Answers

up vote 6 down vote accepted

The distinction between "first-order semantics" and "full second-order semantics" for arithmetic is somewhat muddy in much of the literature, and the overuse of the terms "first-order" and "second-order" to mean many different things only confuses the issue more (the same is true for "completeness").

In plain terms, the only difference between formalizing arithmetic in first-order semantics and formalizing it in full second-order semantics is that in the former case we look at all models (in the usual sense) for the theory, while in the latter case we only look at the standard model. This is not the way full second-order semantics is usually defined, but when we combine the usual definition with the well-known categoricity results, we see that this restriction is exactly the effect of full second-order semantics for arithmetic.

But nothing else changes. The syntax and the deductive systems for "second-order arithmetic" are exactly the same regardless of which semantics is used. Because the incompleteness theorems are proved syntactically, they continue to apply in their syntactical sense regardless of which semantics we use.

What does change is that the completeness theorem fails when we move to full second-order semantics, because we have excluded by fiat many of the models required for every syntactically consistent theory to have a model. Thus the semantic consequences of the incompleteness theorems, such as the existence of nonstandard models, do not go through in full second-order semantics, because we have already eliminated all nonstandard models from discussion. This is a side effect of full second-order semantics - because the completeness theorem fails, it becomes necessary to carefully distinguish between syntactic and semantic definitions for concepts such as (logical) implication and consistency.

When we use first-order semantics for second-order arithmetic, which is what is typically done in the literature these days, there are indeed many nonstandard models. These models vary from the standard model in two ways. First, the set of "numbers" may be different from the standard set of natural numbers. Second, the collection of "sets of numbers" may be a proper subcollection of the true powerset of the set of "numbers". There are many of these nonstandard models, and we know quite a bit about their properties from research in the field of Reverse Mathematics.

The fact that moving to full second-order semantics is no different than just working with the standard model is one reason that these semantics are not so useful. Anything we could do with full second-order semantics, we could do in our usual first-order semantics by just talking about the standard model explicitly. Any question that we cannot answer about the standard model when working in ZFC will be equally unanswerable when we work with full second-order semantics.

share|improve this answer
    
"The only difference between formalizing arithmetic in first-order semantics and formalizing it in full second-order semantics is that in the former case we look at all models (in the usual sense) for the theory, while in the latter case we only look at the standard model" I suspect that this way of putting things really begs the question against the second-orderist like Shapiro. For such a theorist the second-order quantifiers are logical devices. Their interpretation as running over the full powerset of the first-order domain must stay as fixed from model to model. [continued] –  Peter Smith Sep 27 '12 at 12:28
    
Just as the interpretation of the first-order quantifiers is fixed as running over the full first-order domain. For such a second-orderist, (i) moving to a two-sorted first-order theory is changing the meaning of the quantifiers, and (ii) the second-order quantifiers construed as necessarily running over the full powerset are the regimentation of the quantifiers we find in various bits of informal mathematical reasoning. (I'm not necessarily endorsing that view, just noting that there is a real issue for debate here.) –  Peter Smith Sep 27 '12 at 12:31
    
@Peter Smith: This is why I attempted to qualify my statement specifically to arithmetic rather than second-order logic generally. It is certainly true that changing the semantics changes the formal meaning of quantifiers. But even someone who thinks that full second-order semantics is implicit in the natural-language meaning of set quantification should be willing to accept that the mathematical effect of changing from Henkin to full semantics is to reduce the collection of acceptable models. ... –  Carl Mummert Sep 27 '12 at 12:41
    
Of course the second-orderist thinks the non-full models shouldn't be called "models" at all, but that's exactly the point. And non-second-orderists should all agree that non-full Henkin models are not the intended models for set quantification, but they are familiar with many other non-intended models. So the philosphical debate concerns the status of these non-intended Henkin models. But in the particular context of arithmetic, using full semantics has exactly the same mathematical effect as working in Henkin semantics but only studying the standard model, which is a common thing to do. –  Carl Mummert Sep 27 '12 at 12:44
    
Yes, that's right: we are not in substantive disagreement then. I was just worrying a bit that your headline way of putting it could possibly mislead someone not up to speed on these issues. –  Peter Smith Sep 27 '12 at 13:02
add comment

Let $\mathsf{PA_2}$ be a standard recursively axiomatized second-order Peano Arithmetic (e.g. the theory which Hilbert and Bernays call $\mathsf{Z}_2$). And interpret the wffs of $\mathsf{PA_2}$'s language with the 'full' semantics, where the second-order quantifiers are constrained to run over the full collection of sets of numbers.

Then (i) Gödel's theorem applies, of course, to $\mathsf{PA_2}$, so (assuming consistency) there will be a true canonical Gödel sentence $\mathsf{G}$ such that $\mathsf{PA_2} \nvdash \mathsf{G}$.

However, (ii) $\mathsf{PA_2}$, with the full semantics, is categorical by Dedekind's argument, so has only one model (up to isomorphism). In that one model, $\mathsf{G}$ is true, so $\mathsf{PA_2} \vDash \mathsf{G}$.

This shows that syntactic provability $\vdash$ falls short of semantic entailment $\vDash$ in the scecond-order case (there is no complete deductive system for second-order consequence, assuming the full semantics).

In summary, then, while the claim "$\mathsf{PA}$ settles all arithmetical truths" is false however we interpret it (where $\mathsf{PA}$ is first-order Peano Arithmetic), the situation with the corresponding claim "$\mathsf{PA_{2}}$ settles all arithmetical truths" is more complex. It depends whether you mean "semantically entails" or "deductively implies".

For vividness, it may well help to put that symbolically. We'll use $\{\mathsf{PA}, \vdash\}$ to denote the set of theorems that follow in $\mathsf{PA}$'s formal proof system, and $\{\mathsf{PA}, \vDash\}$ to mean the set of sentences semantically entailed by $\mathsf{PA}$'s axioms (given the standard semantics for first-order arithmetic). Similarly, we'll use $\{\mathsf{PA_{2}}, \vdash_2\}$ to mean the set of theorems that follow in $\mathsf{PA_{2}}$'s formal proof system, and $\{\mathsf{PA_{2}}, \vDash_{2}\}$ to mean the set of sentences semantically entailed by $\mathsf{PA_{2}}$'s axioms (given the "full" semantics for the quantifiers). Finally we'll use $\mathcal{T}_{A}$ to denote the set of truths of first order arithmetic (often called, simply, True Arithmetic); and we'll now use $\mathcal{T}_{2A}$, the set of truths of the language of second-order arithmetic (True Second-Order Arithmetic). Then we can very perspicuously display the relations between these sets as follows, using `$\subset$' to indicate strict containment:

$\{\mathsf{PA}, \vdash\} \;=\; \{\mathsf{PA}, \vDash\} \;\subset\; \mathcal{T}_{A}$

$\{\mathsf{PA_{2}}, \vdash_2\} \;\subset\; \{\mathsf{PA_{2}}, \vDash_{2}\} \;=\; \mathcal{T}_{2A}$.

The completeness of first-order logic which yields $\{\mathsf{PA}, \vdash\} = \{\mathsf{PA}, \vDash\}$ is, though so familiar, a remarkable mathematical fact which is enormously useful in understanding $\mathsf{PA}$ and its models. This has led some people to think the strict containment $\{\mathsf{PA_{2}}, \vdash_2\} \subset \{\mathsf{PA_{2}}, \vDash_{2}\}$ is a sufficient reason to be unhappy with second-order logic. Others think that the categoricity of theories like second-order arithmetic, and the second-order definability of key mathematical notions like finiteness, suffices to make second-order logic the natural logic for mathematics. Stewart Shapiro's Foundations without Foundationalism is a classic defence of the second position.

The issue here is discussed at some length in Ch. 29 (or Ch. 22 of the 1st edition) of my Gödel book, if you want more!

share|improve this answer
add comment

In Second Order Logic , PA2+not (G), where G is the first sentence of GÖdel, is consistent. But we know that G is true in the standard model and the unique model of PA2 is the standard model. What is the solution to this? PA2+not (G) is consistent, you never prove a contradiction from it, but it has no model. In second order a theory can be sintacticaully consistent, but have no models. In first order it don´t matter. If a sentence S is undecidable in a first order theory T1, you have 2 models ( at lest) for it, it is said: if theory T1 is consistent , like is in first order it has a model, and T1+S and T1+ not(S) will be consistent both of them, everyone with his models

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.