Math 557 Nov 3

End Extensions

The standard model can be embedded into every model $\mathcal{M}$ of $\mathsf{PA}$ as an initial segment. It turns out this already holds for models of the theory $\mathsf{PA}^-$.

Definition 1
Let $L$ be a language containing a 2-ary symbol $<$, and let $\mathcal{M}$ and $\mathcal{N}$ be $L$-structures with $\mathcal{M} \subseteq \mathcal{N}$. Then $\mathcal{N}$ is called an end extension of $\mathcal{M}$ (and correspondingly $\mathcal{M}$ is an initial segment of $\mathcal{N}$) if and only if the larger set $N$ does not add any further elements below an element of $M$: \[ \mathcal{M} \subseteq_{end} \mathcal{N}: \iff \text{for all} \; x \in M,y \in N: (y<^N x \Rightarrow y \in M). \]

Each natural number $n$ is represented in the standard model, which we also simply denote by $\mathbb{N}$ here, by the constant term \[ \underline{n} = 1+ \ldots + 1 \quad \text{($n$ times)} \] where $\underline{0}$ is the constant $0$.

Theorem 1
Let $\mathcal{M} \models \mathsf{PA}^-$. Then the map \[n \mapsto \underline{n}^{\mathcal{M}}\] defines an embedding of the standard model $\mathbb{N}$ onto an initial segment of $\mathcal{M}$.

In particular, every model of $\mathsf{PA}^-$ is isomorphic to an end extension of the standard model $\mathbb{N}$.*

Proof. By simple induction (in the meta-theory), one shows for all natural numbers $n,k,l$: \[ \begin{aligned} n = k+l & \quad \Longrightarrow \quad \mathsf{PA}^- \vdash \underline{n}= \underline{k}+ \underline{l} \\ n = k \cdot l & \quad \Longrightarrow \quad \mathsf{PA}^- \vdash \underline{n}= \underline{k} \cdot \underline{l} \\ n < k& \quad \Longrightarrow \quad \mathsf{PA}^- \vdash \underline{n} < \underline{k}\\ \end{aligned} \] and \[ \mathsf{PA}^- \vdash \forall x \:(x \le \underline{k} \to (x = \underline{0} \; \vee \ldots \vee \; x = \underline{k}) \]

The first three statements will later be generalized to all recursive functions and relations; they imply that the map $n \mapsto \underline{n}^{\mathcal{M}}$ is a homomorphism, and, due to the last statement, the map is also an embedding onto an initial segment of $\mathcal{M}$.

Remark

The standard model has no proper initial segment, and $\mathbb{Z}[X]^+$ has $\mathbb{N}$ as its only proper initial segment. On the other hand, every model $\mathcal{M} \models \mathsf{PA}^-$ has a proper end extension that is also a model of $\mathsf{PA}^-$, namely the non-negative part of the polynomial ring $R[X]$, where $R$ is the discretely ordered ring associated with the model $\mathcal{M}$.

Preservation Properties of End Extensions

In the previous lecture, we introduced arithmetical formulas. $\Delta_0$-formulas are at the bottom of the arithmetical hierarchy. We already saw that relations defined by such formulas are primitive recursive. Next, we will show that those formulas mean the same thing in a structure as in all end extensions. This will be crucial later on.

Theorem 2
Let $\mathcal{N}, \mathcal{M}$ be structures of the language $\mathcal{L}_A$ of $\mathsf{PA}^-$, with $\mathcal{N} \subseteq_{end} \mathcal{M}$, and let $\vec{a} \in N$. Then:

Every $\Delta_0$-formula $\varphi(\vec{v})$ is absolute: \[ \mathcal{N}\models \varphi[\vec{a}] \iff \mathcal{M}\models \varphi[\vec{a}], \]
Every $\Sigma_1$-formula $\varphi(\vec{v})$ is upward-persistent: \[ \mathcal{N}\models \varphi[\vec{a}] \Longrightarrow \mathcal{M}\models \varphi[\vec{a}], \]
Every $\Pi_1$-formula $\varphi(\vec{v})$ is downward-persistent: \[ \mathcal{M}\models \varphi[\vec{a}] \Longrightarrow \mathcal{N}\models \varphi[\vec{a}], \]
Every $\Delta_1$-formula $\varphi(\vec{v})$ is absolute: \[ \mathcal{N}\models \varphi[\vec{a}] \iff \mathcal{M}\models \varphi[\vec{a}]. \]

Proof. Part (i) is proved by induction on the formula structure of $\varphi(\vec{v})$. Most cases are straightforward (using that $\mathcal{N}$ is a substructure of $\mathcal{M}$). In the case of a bounded quantifier, one argues that, since $\mathcal{M}$ is an end extension of $\mathcal{N}$, $M$ does not insert any new elements below an element of $N$, so that a bounded quantifier means the same thing in both structures.

The other parts follow easily from the definition of the satisfaction relation $\models$ and the $\Delta_0$ case.

Let $\Sigma_1$-$\operatorname{Th}(\mathbb{N}):= \{\sigma \mid \sigma \text{ is a } \Sigma_1\text{-sentence with } \mathbb{N} \models \sigma \}$. Then we have:

Corollary 1 \[ \mathsf{PA}^- \models \Sigma_1\text{-}\operatorname{Th}(\mathbb{N}) \]

Proof. Let $\mathcal{N} \models \mathsf{PA}^-$. By Theorem 1, we may assume that $\mathbb{N} \subseteq_{end} \mathcal{N}$, and the claim then follows from part (ii) above.

Thus one can prove in the theory $\mathsf{PA}^-$ all $\Sigma_1$-sentences that hold in the standard model. This is no longer true for $\Pi_1$-sentences. For instance, the $\Pi_1$-sentence stating that every number is even or odd: \[ (*) \quad \forall x \; \exists y \le x \; (x = 2 \cdot y \vee x = 2 \cdot y +1) \] is true in the standard model, but not in the $\mathsf{PA}^-$-model $\mathbb{Z}[X]^+$.

Even true $\forall$-sentences (i.e., sentences of the form $\forall \vec{x} \; \psi$ with quantifier-free $\psi$) that hold in the standard model need not be provable in $\mathsf{PA}^-$. For example, the $\forall$-sentence \[ \forall x,y (x^2 \ne 2 \cdot y^2) \] is true in the standard model, but not provable in $\mathsf{PA}^-$ ($\mathbb{Z}/(X^2 - 2Y^2)$ is a counterexample).

Thus the above sentence (*) is an example of a $\Pi_1$-sentence that is not a $\forall$-sentence, where one cannot omit the bounded quantifier! (By the way, one can show that $\mathbb{Z}[X]^+$ is at least a model of all $\forall$-sentences that hold in the standard model.)