Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

These days, Peano Arithmetic ($PA$) refers to the first-order version of the axioms, where induction is only over formulas referring to natural number variables. Peano's original version of the induction axiom was actually second-order, allowing reference to sets-of-natural-numbers variables. This latter version corresponds to what a category theorist (like me) would call a natural number object. Call this 'second-order $PA$' or $PA_2$.

However, we also have second-order arithmetic $Z_2$ (wikipedia), which up to some redundant axioms, looks like $PA_2$ plus a comprehension axiom schema (details of the schema). We know that $PA_2$ has a unique model up to isomorphism, and so does $Z_2$. My first question is then

What, if anything, separates a model of $PA_2$ from a model of $Z_2$?

I imagine that there are sets of naturals in $Z_2$ that cannot be proved to exist in $PA2$, but where is the boundary?

From the Wikipedia page I see that $ACA_0$, a subsystem of $Z_2$ with restricted induction, is a conservative extension of $PA$ (and equiconsistent with $PA$), and I infer that $ACA$, the same subsystem plus unrestricted induction, would be a conservative extension of $PA_2$.

Is this true? Is $ACA$ equiconsistent with $PA_2$?

One reason I am interested in this is that McLarty has proved that the machinery of derived functor cohomology, in the setting appropriate for arithmetic geometry, is do-able in $Z_2$ (more precisely, derived functor cohomology over a Noetherian scheme, with coefficients in an arbitrary sheaf of modules on the Zariski site, only requires a system equiconsistent with second-order arithmetic). If one can get from working in $Z_2$ down to $ACA$, then these tools of algebraic geometry are available as soon as one accepts the existence of natural number objects (and, presumably, classical logic).

share|improve this question
add comment

2 Answers 2

$Z_2$ as it is usually viewed is a first-order theory with two sorts, and as such is not categorical. The difference (apart from terminological issues) is entirely in the semantics that are used. In "full" second-order semantics, the set variables quantify over all subsets of the domain, while in first-order "Henkin" semantics each model has a domain for number variables and a second domain for set quantifiers to range over.

There are two things that you might mean by $PA_2$ (I realized this after writing the answer, so I have expanded it). The first option is to have $PA_2$ include the entire second-order induction scheme; let's call that $PA^s_2$. $PA^s_2$ and $ACA$ are indeed equiconsistent. Every model of $ACA$ is already a model of $PA^s_2$, and every model of $PA^2_2$ extends to a model of $ACA$ by just throwing in the definable sets. In fact, this extends any model of $PA^s_2$ to a model of $Z_2$, so these theories are equiconsistent. There is an issue that this could mean "equiconsistent in full second order semantics" or "equiconsistent in first-order semantics", but either way they are pairwise equiconsistent as long as the same semantics is used for both theories.

The other option is that $PA_2$ might just have the single second-order induction axiom $$ (\forall x)[0 \in X \land (\forall n)[n \in X \to n+1\in X] \to (\forall n) n \in X]. $$ Let's call that version $PA^i_2$. Now the semantics matters. In full second-order semantics, any model of $PA^i_2$ is a model of $PA^s_2$, so it extends to a model of $Z_2$. In first-order semantics, $PA^i_2$ is very weak, because without any comprehension axioms the single second-order induction axiom is not very strong in first-order semantics. $PA^i_2$ is (syntactically) a subtheory of $\mathsf{RCA}_0$, one of the weak systems of arithmetic considered in reverse mathematics, and so $PA^i_2$ has a much lower consistency strength than $Z_2$ in the first-order setting.

share|improve this answer
    
Thanks, Carl! I really didn't expect $PA_2$ and $Z_2$ to be equiconsistent, once I starting thinking about the question. –  David Roberts May 16 '12 at 2:51
    
@David Roberts: I realized I might have misunderstood the question, so I expanded my answer just now. –  Carl Mummert May 16 '12 at 3:05
    
Actually I think that I care about $PA_2^s$, since this seems to be the version that corresponds to a NNO - thanks for clarifying. It's interesting that $PA_2^i$ is as weak as (or weaker) than $RCA_0$... –  David Roberts May 16 '12 at 3:11
add comment

Regarding the first question: The second order theory $PA_2$ is usually defined relative to an ambient universe $V$ of Zermelo-Fraenkel set theory, and as such it only has one model up to isomorphism. In other words, $PA_2$ is a categorical theory from the point of view of any model $V$ of $ZF$ since all of its models are isomorphic to $(\Bbb{N},\mathcal{P}(\omega))$, where $\Bbb{N}$ is the standard model of $PA$ and $\mathcal{P}(\omega)$ is the collection of all subsets of natural numbers (from the point of view of $V$).

On the other hand, $Z_2$ is a first-order approximation of $PA_2$, and by some standard theorems of model theory, it has many $2^\kappa$ nonisomorphic models of cardinality $\kappa$ for each infinite cardinal $\kappa$. In particular, there are continuum-many nonisomorphic countable models of $Z_2$. Each such countable model of $Z_2$ is of the form $(\Bbb{M},\mathcal{F})$, where $\Bbb{M}$ is a standard or nonstandard model of $PA$, and $\mathcal{F}$ is a countable family of subsets of the universe of discourse $M$ of $\Bbb{M}$

Regarding the second question: $ACA$ is much stronger than first order Peano Arithmetic $PA$ since it proves Con($PA$) (the formal consistency of $PA$) and much more (itertions of consistency statements) .

However, $ACA$ is, in turn, much weaker than $Z_2$ since already the fragment known as $\Pi^1_1$-$CA$ of $Z_2$ can prove Con($ACA$).

One way to see this is based on an old result (noticed by a number of people, including Takeuti and Feferman) that $ACA$ is equiconsistent with an extension $PA(T)$ of $PA$ with a distinguished predicate $T$ that codes up the full truth predicate for the ambient model of arithmetic. Note that $PA(T)$ includes induction in the extended language of arithmetic augmented by the predicate $T$.

P.S. The subsystem $ATR_0$ of $\Pi^1_1$-$CA$ already proves Con($ACA$).

share|improve this answer
    
"Regarding the second question..." I was asking about $PA_2$ :-) I know $PA$ is weaker than $ACA$. –  David Roberts May 16 '12 at 3:30
    
@David: In my answer to question 2, I mentioned $PA$ in order to highlight the fact that for the same Godelian reasons that $PA$ is weaker than $ACA$, $ACA$ is in turn weaker than $Z_2$. @Carl, $ACA$, being an axiomatizable theory, has many non-$\omega$ models, so your model-theoretic argument for conservativity will not work for such models. –  Ali Enayat May 16 '12 at 11:09
    
Ah, I see. Thanks for clarifying. –  David Roberts May 16 '12 at 22:45
1  
I know $ATR_0$ proves the consistency of $ACA_0$, I didn't know it proves the consistency of $ACA$. –  David Roberts May 18 '12 at 4:13
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.