This is a summary of ch2 of Kaye. In the previous entry I considered models for all of $\Th\N$. Now I consider a subtheory $PA^-$, which are essentially the Peano axioms without induction. To be specific, the axioms consist of:
Axioms for a commutative semiring with operations $+$ and $\cdot$ (i.e. a commutative ring except additive inverses are not required)
Axioms for a linear order $<$
$<$ preserves $\cdot$ and $+$ : $\forall x,y,z(x<y\to x+z<y+z)$ and $\forall x,y,z(0<z\land x<y\to x\cdot z<y\cdot z)$
$<$ is a discrete order: $0<1$, $\forall x(x>0\to x\ge1)$ and $\forall x(x\ge 0)$
Smaller elements can be subtracted from larger elements: $\forall x,y(x<y\to \exists z(x+z=y))$. It can be proven using the other axioms that $z$ is unique.
Obviously $\N$ is a model. What is different from before is that now, we can construct lots of nonstandard models without appealing to compactness. Before I do so, let me point out a correspondence between models $M\vDash PA^-$ and discretely ordered commutative rings $R$ (with additive inverses). Given $M$, we can construct $R$ as the quotient $M^2/\sim$, where
$$(a,b)\sim(c,d) \iff a+d=b+c.$$
Think of $(a,b)$ as a formal representation of the difference $a-b$. We then define $+$, $\cdot$ and $<$ in the natural way and check that it forms a discretely ordered commutative ring. On the other hand, given a discretely ordered commutative ring $R$, the subset $\{x\in R\mid x\ge0\}$ forms a model of $PA^-$. This justifies calling $PA^-$ the theory of non-negative parts of discretely ordered rings. As we'll see, this correspondence is useful because it is often more convenient to construct both positive and negative elements at once, then restrict our attention to non-negative elements.
Also, one more remark: when defining $<$ on an ordered ring it suffices to specify the positive elements, because $x>y\iff x-y>0$.
Our first example involves the polynomial ring $\Z[X]$. I define a polynomial $p(X)$ to be positive iff its leading coefficient is positive. So $X^2-2X-1$ is positive, whereas $-X$ is not. Think of $X$ as an infinitely large element, so the 'positiveness' of $X^2$ outweighs the 'negativeness' of $-2X-1$. Anyway, we have a discrete order on $\Z[X]$, and we take the model to be the subset $\Z[X]^+$ of non-negative elements.
A few remarks. First, if we had used $\N[X]$ instead of $\Z[X]^+$, then the last axiom in the above list won't be satisfied: we have $1<X$ but there is no $z\in\N[X]$ satisfying $1+z=X$, Whereas in $\Z[X]^+$ we have $z=X-1$. This illustrates the importance of allowing polynomials with negative coefficients.
Second, $\Z[X]^+$ does not satisfy $\Th\N$ because we have $\Z[X]^+\nvDash \exists x\forall y(2y\neq x\land 2y+1\neq x)$. To see this, let $x=X$ and observe that either $y$ is a standard natural in which case $2y<2y+1<X$, or the coefficient of some power $X^k$ in $y$ is positive, in which case $2y+1>2y>X$. Therefore, $PA^-$ cannot prove all sentences in $\Th\N$.
Third, the earlier remark that $X$ is an 'infinitely large' element actually holds some weight. Given a nonstandard model $M\vDash\Th\N$ and $a\in M\setminus\N$, we can embed $\Z[X]^+$ as a substructure of $M$ by mapping $p(X)\mapsto p(a)$. If you're astute, you might notice this is not a valid definition: we can't just map $X-1$ to the element $a-1$ because $a-1$ is not even a valid $\cL_A$-term! A bit more work has to be done to make the definition work, which I do in the following proposition.
Proposition. $\Z[X]^+$ embeds as a substructure of $M$.
Proof. Let $p(X)\in\Z[X]^+$ and $a\in M\setminus\N$. I split $p(X)$ into two polynomials $q(X),r(X)$, where $q(X)$ contains the positive monomials and $r(X)$ contains the negative ones. For instance,
$$p(X)=X^3-4X^2-2X+1 \implies q(X)=X^3+1,\;r(X)=4X^2+2X.$$
If $p(X)$ has all positive coefficients then I set $q(x)=p(X)$ and $r(X)=0$. Now $q(a)$ and $r(a)$ are valid $\cL_A$-terms. Furthermore, we have $r(X)<q(X)$ which implies $r(a)<q(a)$; this follows from the inequality $a^k>s(a)$ for all polynomials $s$ with degree $<k$. Therefore, since $M\vDash PA^-$ there is a unique $z$ satisfying $r(a)+z=q(a)$. We map $p(X)$ to $z$.
It remains to check that this map respects $<$, $+$ and $\cdot$ for all polynomials. Note that respecting $<$ automatically implies it is an embedding. Suppose $p(X)=q(X)-r(X)<q'(X)-r'(X)=p'(X)$. Then we have
$$r(a)+z=q(a) \quad\text{and}\quad r'(a)+z'=q'(a)$$
where $p(X)\mapsto z$ and $p'(X)\mapsto z'$. Then
$$q(a)+r'(a)+z'=r(a)+r'(a)+z+z'=q'(a)+r(a)+z.$$
Observe that $q(X)+r'(X)<q'(X)+r(X) \implies q(a)+r'(a)<q'(a)+r(a)$, so we are forced to have $z'>z$, and order is preserved. Next, we have
$$(r+r')(a)+(z+z')=(q+q')(a)$$
where $p(x)+p'(X)=(q+q')(X)-(r+r')(X)$, so addition is preserved. Lastly, by multiplying both equations and adding $r(a)r'(a)$ we get
$$\begin{align*} q(a)q'(a)+r(a)r'(a) &= r(a)r'(a)+r(a)r'(a)+r(a)z'+r'(a)z+zz' \\ &= r(a)(r'(a)+z')+r'(a)(r(a)+z)+zz' \\ &= r(a)q'(a)+r'(a)q(a)+zz', \end{align*}$$
which matches up with the fact that
$$\bigl(q(a)-r(a)\bigr)\bigl(q'(a)-r'(a)\bigr)=q(a)q'(a)+r(a)r'(a)-\bigl(q(a)r'(a)+q'(a)r(a)\bigr),$$
so multiplication is preserved. $\qed$
The second example is a general template for constructing models of $PA^-$ not satisfying certain sentences in $\Th\N$, which involves taking quotients of polynomial rings over $\Z$.
We construct a discrete order on $R=\Z[X,Y]/(X^2-2Y^2)$ so that the non-negative elements form a model of $PA^-$ satisfying $\exists x\exists y(x^2=2y^2)$, which is not in $\Th\N$.
Let $P$ be the subset of $R$ consisting of polynomials with constant coefficient 0, along with 0. It is a rng (ring without 1). There is a rng homomorphism $P\to\R$ which maps $X\mapsto\sqrt2$ and $Y\mapsto1$. By an analogue of the first isomorphism theorem, we have an embedding $P/(X^2-2Y^2)\to\R$. The order on $\R$ induces an order on $P/(X^2-2Y^2)$ which is dense.
Then, we replace each point in $P/(X^2-2Y^2)$ with an ordered $\Z$-chain corresponding to some coset $\overline{p(X,Y)}+\Z$ with $\overline{p(X,Y)}\in P/(X^2-2Y^2)$, and this gives us a discrete order. Note that each coset can be identified with a subset of $R$, and they form a partition.
This construction illustrates the general idea: we take any ordered ring satisfying some property that is not satisfied in $\N$, then 'expand' each point into a $\Z$-chain in order to turn it into a discrete order.
This time let $R=\Z[X,Y,Z]/(XZ-Y^2)$. The significance of this ring is that $Y$ is irreducible but not prime, implying that the two formulas
$$\text{prime}(x) = x>1\land \forall y,z,w(xw=yz\to \exists v(xv=y\lor xv=z))$$
and
$$\text{irred}(x) = x>1\land \forall u,v(uv=x\to u=x\lor v=x)$$
are not equivalent in $PA^-$.
Define $P$ in the same manner as above, and define a rng homomorphism $\varphi:P\to\R$ mapping $x\mapsto e$, $y\mapsto\sqrt{e\pi}$ and $z\mapsto\pi$. It is crucial that there are no algebraic relations between the images apart from $\varphi(x)\varphi(z)=\varphi(y)^2$; also note that $\varphi(x)<\varphi(y)<\varphi(z)$. So we have an embedding $P/(XZ-Y^2)\to\R$ and the rest follows as above. Note that we might have different orders on $R$ depending on the choice of images of $\varphi$.
Recall that if $M\vDash\Th\N$ then $\N$ is an initial segment of $M$ (denoted $\N\subseteq_c M$). The same is true if $M\vDash PA^-$. The proof relies on showing for each $k\in\N$ that
$$PA^-\vdash \forall x(x\le\underline{k}\to x=\underline0\lor x=\underline1\lor \ldots\lor x=\underline{k-1}).$$
I'll omit the details of because it's boring and tedious. Analogously, every model $M\vDash PA^-$ has an end extension $N\vDash PA^-$, i.e. $M\subseteq_c N$. Namely, we take $N=R[X]^+$ where $R=M^2/\sim$ is the discrete ordered ring induced by $M$, and there is a natural embedding $M\to R\to R[X]^+$. Note the special case $M=\N$ and $R=\Z$.
Initial segments are related to a certain class of formulas called $\Delta_0$ formulas. They have the form $\exists x(x<t\land \varphi(x))$ (abbreviated $\exists x<t(\varphi(x))$) or $\forall x(x<t\to \varphi(x))$ (abbreviated similarly), where $t$ is an $\cL_A$-term and $\varphi$ is quantifier-free. Such formulas are said to have bounded quantifiers, and their truth and falsity can be computed by simply checking all numbers up to $t$. The notion of $\Delta_0$ formulas being computable will be made precise in the following entry.
If $M\subseteq N$ are $\cL_A$-structures, then there is a notion of $M$ being a $\Delta_0$-elementary substructure, denoted $M\prec_{\Delta_0} N$. There is also a variant of the Tarski-Vaught criterion but for $\Delta_0$ formulas. The reader can easily give a definition and prove the variant. Now this is where initial segments come in:
Proposition. If $M\subseteq_c N$ are $\cL_A$-structures, then $M\prec_{\Delta_0} N$. In particular we can take $M=\N$.
Proof. We verify the Tarski-Vaught criterion. Let $a_1,\ldots,a_n\in M$ and $t(a_1,\ldots,a_n)$ be an $\cL_A$-term, and suppose there is some $b\in N$ such that $N\vDash b<t(a_1,\ldots,a_n)\land \phi(b,a_1,\ldots,a_n)$. Then $b\in M$ because $M$ is an initial segment and so
$$\{y\in N \mid y < t(a_1,\ldots,a_n)\} = \{y\in M \mid y < t(a_1,\ldots,a_n)\}.$$
Thus $M$ also satisfies that formula as desired. $\qed$
One level up from $\Delta_0$, we have $\Sigma_1$ and $\Pi_1$ formulas, which are formulas of the form $\exists\overline{x}\,\phi(\overline{x},\overline{y})$ and $\forall\overline{x}\,\phi(\overline{x},\overline{y})$ where $\phi$ is $\Delta_0$. In other words, $\Sigma_1$ formulas start with a sequence of unbounded existential formulas followed by a $\Delta_0$-formula, and similarly for $\Pi_1$. By convention, $\Delta_0$ formulas are considered to be also $\Sigma_1$ and $\Pi_1$.
It is easily verified that $\Sigma_1$ and $\Pi_1$ are closed under conjunction and disjunction, the negation of $\Sigma_1$ is $\Pi_1$ and vice versa. In fact, $\Delta_0$, $\Sigma_1$ and $\Pi_1$ are part of a larger hierarchy called the arithmetic hierarchy. The reader might notice huge parallels with the Borel hierarchy.
I will also use $\Sigma_1$ to denote the set of $\Sigma_1$ formulas, and similarly for the other types.
Corollary. $PA^-\vdash \Sigma_1\cap\Th\N$.
Proof. If $M\vDash PA^-$ then $\N\subseteq_c M$. Suppose $\N\vDash\exists x\,\theta(x)$ where $\theta\in\Delta_0\cap\Th\N$. So there is some $a\in\N$ such that $\N\vDash\theta(a)$. Clearly $a$ also lies in $M$, and by the proposition we have $M\vDash\theta(a)$, so $M\vDash\exists x\,\theta(x)$ as desired. $\qed$
So $PA^-$ can prove as a substantial amount of true sentences in $\N$, but not all of them as seen in the above examples. In fact, no reasonable extension of $PA^-$ can prove all of $\Th\N$ by Gödel's first incompleteness theorem, which is the subject of the next entry.