For any two models of PA, is one model a cut of the other?

133 Views Asked by At

For two models of arithmetic $M_1=(S_1, 0_1, 1_1, +_1, \times_1, <_1)$, $M_2(S_2, 0_2, 1_2, +_2, \times_2, <_2)$, we say that the $M_1$ is a cut of the $M_2$ if there is a $S \subseteq S_2$ such that if $x \in S$, $y \in M_2$, and $y <_2 x$, then $y \in S$, and $M_1 \cong (S, 0_2, 1_2, +_2, \times_2, <_2)$.

My question is, for two models $M_1$ and $M_2$ of PA, is true that one of them is a cut of the other? If not, what is a counter example?

2

There are 2 best solutions below

4
On

Hint: every countable non-standard model of PA has a proper cofinal elementary extension: that is, an elementary extension such that every new element is below some old element.

Take a non-standard prime model $M$ (that is, a prime model of a completion of PA besides TA) and a proper cofinal elementary extension $N$. One can show that $M$ is not isomorphic to a proper cut of $N$.

5
On

No.

This is a nice analogy to models of set theory, where being an initial segment is replaced by being a transitive model.

Suppose that $M$ and $N$ are models of $\sf PA$, and $M$ is an initial segment of $N$. Then every $\Sigma_1$ sentence true in $M$ is true in $N$. First we prove this for $\Sigma_0$ formulas, by induction on the complexity of the formula $\varphi$: the only nontrivial part is bounded quantifiers, but since you can only bound quantifiers with either numerals or add new free variables which are again taken from $M$, this holds.

The upwards absoluteness of $\Sigma_1$ sentences is now fairly easy to obtain.


Finally, if $M$ is a countable model satisfying $\lnot\operatorname{Con}\sf (PA)$, any end-extension of $M$ will satisfy this as well, being a $\Sigma_1$ sentence. However, it is not hard to show that there are uncountable models of $\sf PA$ which satisfy $\operatorname{Con}\sf (PA)$, and therefore these models are neither initial segments of $M$ nor end-extensions of it.