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.

Richard Shore, in his 2010 paper in the Bulletin of Symbolic Logic, 'Reverse Mathematics: The Playground of Logic', writes that

Obviously, if an $\omega$-model $\mathcal{M}$ (those with $M = \mathbb{N}$) is a model of one of the systems above, such as $\Pi^1_1\text{-}\mathsf{CA}_0$, then it is also a model of the analogous system, such as $\Pi^1_1\text{-}\mathsf{CA}$.

Unfortunately, it is not obvious to me, although I'm sure I'll kick myself once someone explains.

Thanks in advance!

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

An $\omega$-model $M$ has for its first-order part the standard natural numbers from the metatheory (think: some model of ZFC containing $M$ as a set). Since the standard numbers satisfy induction for all properties definable in the metatheory, in particular they satisfy induction for all properties definable in the model $M$, because any property definable in $M$ by an $L_2(M)$ formula is definable in the metatheory by a formula of set theory with parameters.

A similar thing happens even if we start with a model $N$ of $\mathsf{ACA}_0$ which may not have satisfy the full induction scheme. If $M$ is a countable coded $\omega$-submodel of $N$, meaning it has the same numbers as $N$, then $N$ will think that $M$ satisfies full induction. This is because $M$ is coded in $N$ using a single sequence of sets, so set quantification over $M$ can be simulated by arithmetical quantification in $N$ using $M$ as a set parameter. Because $\mathsf{ACA}_0$ includes the induction scheme for arithmetical formulas with parameters, $N$ believes that $M$ satisfies full induction.

One thing to watch out for is that some people, including Shore, use $\mathbb{N}$ to refer to the set $\omega = \{0, 1, 2, \ldots\}$ from the metatheory, while others, including Simpson, use $\mathbb{N}$ to refer to the first order part of any given model of arithmetic, which may not be $\omega$.

share|improve this answer
    
Thanks Carl, that clarifies things substantially. The point about countable coded $\omega$-submodels is also really interesting. –  Benedict Eastaugh Feb 24 '12 at 13:52
1  
Thanks. The two situations are completely parallel: even if $V$ is a nonstandard, non-well-founded model of set theory, if it satisfies ZFC then it will think of itself as well founded, and so it will think that any $\omega$-model it contains must satisfy full induction. –  Carl Mummert Feb 24 '12 at 14:23
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.