Arithmetic definability

The value of a term is a primitive recursive function of its variables, by induction on the term, since successor, addition and multiplication are primitive recursive. The relations $=$ and $<$ are primitive recursive, and primitive recursive relations are closed under Boolean operations and bounded quantifiers whose bound is a primitive recursive function of the free variables (Corollary 5.10 of “Primitive recursive functions”). The result follows by induction on the formula.

For conjunction and disjunction, rename the bound variables apart and move the existential quantifiers to the front: $\exists \vec y\ \theta \wedge \exists \vec z\ \eta$ is equivalent to $\exists \vec y\, \exists \vec z\, (\theta \wedge \eta)$. Existential quantification is immediate, and $\exists z < t\ \exists \vec y\ \theta$ is equivalent to $\exists z\, \exists \vec y\, (z < t \wedge \theta)$. For bounded universal quantification, the collection principle holds in $\nat$:

where $\exists \vec y < b$ abbreviates $\exists y_1 < b \cdots \exists y_m < b$. From left to right, choose witnesses for each of the finitely many values of $z$ and let $b$ exceed all of them. The right-hand side is a $\Sigma_1$ formula.

By induction on the definition of $f$ as a primitive recursive function. The basic functions have the bounded definitions $y = 0$, $y = S(x)$ and $y = x_i$.

Composition. If $f(\vec x) = h(g_1(\vec x), \dots, g_m(\vec x))$ and the graphs of $h$ and of the $g_i$ are defined by $\Sigma_1$ formulas $\psi_h$ and $\psi_{g_i}$, then

which is $\Sigma_1$-definable by Lemma 4.4.

Primitive recursion. Let $f(\vec x, 0) = g(\vec x)$ and $f(\vec x, n + 1) = h(\vec x, n, f(\vec x, n))$. A computation of $f(\vec x, n)$ is the finite sequence of values $f(\vec x, 0), \dots, f(\vec x, n)$, which by Gödel’s lemma (Gödel) is represented by two integers $c, d$ through the β-function $\beta(c, d, i) = c \bmod (1 + (i + 1) d)$ (Definition 6.5 of “Coding finite sequences”). The graph of $\beta$ is defined by the bounded formula

Then $f(\vec x, n) = y$ if and only if there are $c$ and $d$ such that $\beta(c, d, 0) = g(\vec x)$, such that $\beta(c, d, i + 1) = h(\vec x, i, \beta(c, d, i))$ for every $i < n$, and such that $\beta(c, d, n) = y$. Indeed, if these conditions hold, the values $\beta(c, d, i)$ are $f(\vec x, i)$ by induction on $i \leq n$; conversely, Gödel’s lemma provides $c$ and $d$ encoding the sequence $f(\vec x, 0), \dots, f(\vec x, n)$. Written with the formulas for the graphs of $g$, $h$ and $\beta$, each condition is $\Sigma_1$-definable, the second one by bounded universal quantification over a $\Sigma_1$-definable relation. By Lemma 4.4, the graph of $f$ is $\Sigma_1$-definable.

A $\Sigma_1$-definable relation is the projection of a relation defined by a bounded formula, which is computable by Lemma 4.3; so it is c.e. Conversely, by Kleene's normal form, $x \in W_e$ if and only if $\exists s\ T_1(e, x, s)$, with $T_1$ primitive recursive. If $\chi$ is the characteristic function of $T_1$, then $T_1(e, x, s) \iff \chi(e, x, s) = 1$, and the graph of $\chi$ is $\Sigma_1$-definable by Theorem 4.5; so $W_e$ is $\Sigma_1$-definable. For a c.e. relation of arity $k$, the same argument applies with $T_k$, since a c.e. relation is the domain of a partial computable function of $k$ arguments. A computable relation and its complement are c.e., which gives the second statement.

If $A$ is $\Sigma^0_n$, then $\vec x \in A \iff \exists y_1\, \forall y_2 \cdots Q y_n\ R(\vec x, \vec y)$ with $R$ computable, and $R$ is defined both by a $\Sigma_1$ formula and by the negation of one (Corollary 4.6); choosing the first when $Q$ is $\exists$ ($n$ odd) and the second when $Q$ is $\forall$ ($n$ even) gives a definition of the stated form. Conversely, in a formula of the stated form, $\varphi$ defines a $\Sigma^0_1$ relation when $n$ is odd and a $\Pi^0_1$ relation when $n$ is even (Corollary 4.6). Then $Q y_n\ \varphi$ defines a relation of the same class, by Proposition 1.4, and each of the $n - 1$ remaining quantifiers, of the kind opposite to the one after it, raises the level by one: $\forall y$ in front of a $\Sigma^0_k$ relation gives a $\Pi^0_{k+1}$ relation, and $\exists y$ in front of a $\Pi^0_k$ relation a $\Sigma^0_{k+1}$ relation. The relation defined is therefore $\Sigma^0_n$.

For the first statement, it remains to show that every definable relation is arithmetic, by induction on formulas. Atomic formulas define computable relations. The arithmetic relations are closed under complement, since $\Sigma^0_n$ and $\Pi^0_n$ are complements of each other and $\Pi^0_n \subseteq \Sigma^0_{n+1}$; under finite unions and intersections, since a $\Sigma^0_m$ and a $\Sigma^0_n$ relation are both $\Sigma^0_{\max(m, n)}$; and under quantification, since $\exists y$ applied to a $\Sigma^0_n$ relation gives a $\Sigma^0_n$ relation, and $\forall y$ applied to a $\Sigma^0_n$ relation gives a $\Pi^0_{n+1}$ relation (Proposition 1.4).

Every arithmetic set $A$ is many-one reducible to $\mathrm{True}$: by Theorem 4.7, some formula $\varphi(x)$ defines $A$, and $n \in A \iff \ulcorner \varphi(\bar n) \urcorner \in \mathrm{True}$, and $n \mapsto \ulcorner \varphi(\bar n) \urcorner$ is computable. Suppose $\mathrm{True}$ is $\Sigma^0_n$. The set $\emptyset^{(n+1)}$ is arithmetic, so it reduces to $\mathrm{True}$, and it would be $\Sigma^0_n$ by Proposition 1.6. But $\Sigma^0_n \subseteq \Pi^0_{n+1}$, and $\emptyset^{(n+1)}$ is not $\Pi^0_{n+1}$ (Corollary 2.3). The second statement follows by Theorem 4.7.

The set of theorems of $T$ is c.e., hence $\Sigma^0_1$, and it is contained in $\mathrm{True}$, since the theorems of a set of true sentences are true. If it were equal to $\mathrm{True}$, then $\mathrm{True}$ would be $\Sigma^0_1$, contradicting Theorem 4.8.