Herarchy of Formulas

${\Delta }_0$ Formula

A formula $\phi$ is a ${\Delta }_0$-formula if

1. $\phi$ is atomic, or
2. $\phi$ is $\neg \psi$ where $\psi$ is ${\Delta }_0$, or
3. $\phi$ is $\psi \wedge \chi$ where $\psi$ and $\chi$ are ${\Delta }_0$, or
4. $\phi$ is $\exists x(x\le t\wedge \psi )$ where $t$ is a term not containing $x$ and $\psi$ is ${\Delta }_0$, or
5. $\phi$ is $\forall x(x\le t\to \psi )$ where $t$ is a term not containing $x$ and $\psi$ is ${\Delta }_0$. It follows that $\psi \vee \chi$ and $\psi \to \chi$ are ${\Delta }_0$ if both $\psi$ and $\chi$ are ${\Delta }_0$.

So ${\Delta }_0$-formulas are those formulas built up using connectives and bounded quantifiers, that is $\neg ,\wedge ,\vee ,\to ,⟺,=,(,)\text{and quantifiers of form}$ $\phi (y):=\exists x(x\le y\wedge \psi (x)),\phi (y):=\forall x(x\le y\to \psi (x))$

${\Delta }_0$ Formulas: Validity and End Extensions

Suppose $\mathfrak{N}$ is the standard model for arithmetic and $\phi (x_1,\dots ,x_n)$ is a ${\Delta }_0$-formula with free variables $x_1,\dots ,x_n$. Then it is a “mechanical” procedure to check if $\mathfrak{N}\models \phi (a_1,\dots ,a_n)$, where $(a_1,\dots ,a_n)\in {\mathbb{N}}^n$ ($\mathbb{N}$ the universe of $\mathfrak{N}$). In particular, $\{(a_1,\dots ,a_n)\in {\mathbb{N}}^n\mid \mathfrak{N}\models \phi (a_1,\dots ,a_n)\}$ is primitive recursive. If $\mathfrak{A}=⟨A;S,+,\cdot ,<,0⟩$ is an end-extension of $\mathfrak{N}$ with $\mathbb{N}\subset A$ , then for $(a_1,\dots ,a_n)\in {\mathbb{N}}^n$, $\mathfrak{N}\models \phi (a_1,\dots ,a_n)\text{iff}\mathfrak{A}\models \phi (a_1,\dots ,a_n).$

(${\Delta }_0$ implies Primitive Recursive). The mechanical procedure discussed in the previous theorem is primitive recursive, as it can be carried out by a software program using no unbounded search.

${\Sigma }_1$ Formula

A formula $\phi$ is a ${\Sigma }_1$-formula if it is of the form $\exists x_1\exists x_2\dots \exists x_n\psi ,$ where $\psi$ is ${\Delta }_0$.

${\Pi }_1$ Formula

A formula $\phi$ is a ${\Pi }_1$-formula if it is of the form $\forall x_1\forall x_2\dots \forall x_n\psi ,$ where $\psi$ is ${\Delta }_0$.

(${\Delta }_0\subset {\Sigma }_1,{\Delta }_0\subset {\Pi }_1$). We include the case $n=0$ in Definition 6.48, by which we mean there are no quantifiers. So if a formula is ${\Delta }_0$ then it is also ${\Sigma }_1$ and ${\Pi }_1$.

Validity for ${\Sigma }_1/{\Pi }_1$ formulas

Suppose $\mathfrak{N}$ is the standard model for arithmetic, $\phi (x_1,\dots ,x_n)$ is a formula with free variables $x_1,\dots ,x_n$, and $(a_1,\dots ,a_n)\in {\mathbb{N}}^n$. If $\mathfrak{A}$ is an end extension of $\mathfrak{N}$, then

• if $\phi$ is ${\Sigma }_1$,$\mathfrak{N}\models \phi (a_1,\dots ,a_n)⟹\mathfrak{A}\models \phi (a_1,\dots ,a_n),$
• if $\phi$ is ${\Pi }_1,\mathfrak{A}\models \phi (a_1,\dots ,a_n)⟹\mathfrak{N}\models \phi (a_1,\dots ,a_n).$

Corollary

If $\phi (x_1,\dots ,x_n)$ is ${\Sigma }_1$ and $\mathfrak{N}\models \phi (a_1,\dots ,a_n)$ then $PA⊢\phi (a_1,\dots ,a_n)$.

If $\mathfrak{N}\models \phi (a_1,\dots ,a_n)$ then $\mathfrak{A}\models \phi (a_1,\dots ,a_n)$ for every end extension $\mathfrak{A}$. But every model of $PA$ is an end extension.

${\Delta }_0$, ${\Sigma }_1$, ${\Pi }_1$, ${\Delta }_1$ Sets

A set $A\subseteq {\mathbb{N}}^k$ is ${\Delta }_0$ if it is defined by a ${\Delta }_0$-formula, ${\Sigma }_1$ if defined by a ${\Sigma }_1$-formula, ${\Pi }_1$ if defined by a ${\Pi }_1$-formula, and ${\Delta }_1$ if defined by both a ${\Sigma }_1$-formula and by a ${\Pi }_1$-formula.

Similarly we can define ${\Sigma }_2$, ${\Pi }_2$ and ${\Delta }_2={\Sigma }_2\cap {\Pi }_2$.

${\Sigma }_n$, ${\Pi }_n$ Formulas

A formula $\phi$ is ${\Sigma }_n$ or ${\Pi }_n$ if it is in the form

• $\exists x_1\dots \exists x_n\forall y_1\dots \forall y_m\exists z_1\dots \exists z_k\dots \psi \text{or}$
• $\forall x_1\dots \forall x_n\exists y_1\dots \exists y_m\forall z_1\dots \forall z_k\dots \psi ,$ respectively, where $n\ge 1$ is the number of alternating blocks of quantifiers and $\psi$ is ${\Delta }_0$.

\ddots & & & & \mathinner{\cdot^{\cdot^{\cdot}}} \ & & \Delta_3 & & \ & \nearrow & & \nwarrow & \ \Sigma_2 & & & & \Pi_2 \ & \nwarrow & & \nearrow & \ & & \Delta_2 & & \ & \nearrow & & \nwarrow & \ \Sigma_1 & & & & \Pi_1 \ & \nwarrow & & \nearrow & \ & & \Delta_1 & & \ & & \uparrow & & \ & & \Delta_0 & & \end{array}$$

With $\mathcal{N}$ a standard model of arithmetic, $\Omega$ a non-standard model of Peano arithmetic. We have standard model $\mathcal{N}$ and $\mathcal{N}⊢PA$ by a non-standard model here we have $\Omega ⊢PA$ and $\mathcal{N}\subset \Omega$. $\psi$ is a ${\Sigma }_1$ sentence, then $\mathcal{N}\models \psi ⟹\Omega \models \psi$ $\Omega \models \psi /⟹\mathcal{N}\models \psi$ $\psi$ is a ${\Pi }_1$ sentence $\Omega \models \psi ⟹\mathcal{N}\models \psi$ $\mathcal{N}\models \psi /⟹\Omega \models \psi$

First order logic can’t tell the difference between the standard model and the non-standard extension.

Theorem

Every premitive recursive function $f$ and relation $r$ as representable in PA by $\psi ,\phi$ $R(a_1\cdots a_n)⟹PA⊢\phi (a_1\cdots a_n)$ $\text{not}R(a_1\cdots a_n)⟹PA⊢\neg \phi (a_1\cdots a_n)$ $f(a_1,\cdots a_n)=a_{n+1}⟹PA⊢\psi (a_1\cdots a_{n+1})$ $f(a_1,\cdots a_n)\ne a_{n+1}⟹PA⊢\neg \psi (a_1\cdots a_{n+1})$