We define the equational theory $\mathrm{PRA}$ (Primitive Recursive Arithmetic) to be initial among Lawvere theories whose generator $1$ is a parametrized natural numbers object. The set of morphisms $0\to 1$ in $\mathrm{PRA}$ is the set of equivalence classes of closed terms, and is identified with the set of numerals $\mathbb{N}$. (This $\mathbb{N}$ will serve double duty in a moment, as being also the set of objects of the Lawvere theory.)
The first-order theory of Peano Arithmetic, PA for short, can be presented as a Boolean hyperdoctrine
taking $j\in \mathrm{Ob}(\mathrm{PRA})=\mathbb{N}$ to the set $T(j)$ consisting of $j$-ary predicates in the language of PA, modulo provable equivalence in PA. If $f:j\to k$ is a morphism of $\mathrm{PRA}$ and $R\in T(k)$, we let ${f}^{*}(R)$ denote $T(f)(R)\in T(j)$; it can be described as the result of substituting or pulling back $R$ along $f$. There is a corresponding “action” of $\mathrm{PRA}$ on $T$,
which allows us to regard $T$ as a $\mathrm{PRA}$-module.
Let $\mathrm{Form}(\mathrm{PA})$ be the set of all formulas of PA, with $\Phi (j)$ the set of formulas with $j$ free variables. There is an equivalence relation on $\Phi (j)$, where two formulas $F,F\prime $ belong to the same equivalence class $[F]$ if they are provably equivalent in PA. Thus $[-]:\Phi (j)\to T(j)$ is the corresponding quotient map. Let $\mathrm{Term}(0)$ denote the set of closed terms in the logical theory $\mathrm{PRA}$; morphisms $0\to 1$ in the Lawvere theory $\mathrm{PRA}$ are equivalence classes of terms, and we let $\mathrm{ev}:\mathrm{Term}(0)\to \mathrm{PRA}(0,1)$ be the corresponding quotient map. The map $\mathrm{ev}$ has a section $\mathrm{num}:\mathrm{PRA}(0,1)\to \mathrm{Term}(0)$ which sends each morphism $0\stackrel{\prime n\prime}{\to}1$ to the corresponding numeral term (the $n$-fold successor of the zero term). Finally, we have a substitution map
that substitutes a closed term $\tau $ in for the free variable of $F\in \Phi (1)$, giving a closed formula $\mathrm{sub}(\tau ,F)\in \Phi (0)$.
There is a standard Gödel coding taking formulas to numerals,
and we define an application pairing $\cdot $ to be the composite along the top of the following commutative diagram:
In other words, for all formulas $F\in \mathrm{Form}(\mathrm{PA})$ and $R\in \Phi (1)$, we define the pairing $F\cdot R\u2254\mathrm{sub}(\mathrm{num}(\mathrm{code}(F)),R)$, and according to the commutative diagram, we have the equation
which will be used in our diagonalization result.
The following result is routine from general recursive-arithmetic properties of Gödel coding:
There is a primitive recursive function (i.e., a morphism $d:1\to 1$ in $\mathrm{PRA}$) such that for all $t\in \Phi (1)$, we have $d\circ \mathrm{code}(t)=\mathrm{code}(t\cdot t)$.^{1}
For every $R\in \Phi (1)$ there is a fixed point in \Phi(0), i.e., a closed formula $s\in \Phi (0)$ such that $[s]=[s\cdot R]$ ($s$ is provably equivalent to $s\cdot R$).
Pick a formula $t\in \Phi (1)$ such that $[t]={d}^{*}[R]$, and then put $s=t\cdot t$. We have
as required.
Recall there is also a Gödel coding of PA proofs (certain sequences of PA formulas), $\mathrm{code}:\mathrm{Proof}(\mathrm{PA})\to \mathrm{PRA}(0,1)$.
There is a binary primitive recursive predicate $\mathrm{Pf}$ such that $\mathrm{Pf}(p,x)$ is true in $\mathbb{N}$ if $p$ is the code of a proof of a sentence (a closed formula) with code $x$. Thus there is an unary recursive predicate $\mathrm{Prov}\u2254{\exists}_{p}\mathrm{Pf}(p,x)\in T(1)$. Similarly, there is an unary recursive predicate $R=\neg \mathrm{Prov}\in T(1)$.
(Gödel’s First Incompleteness Theorem) There exists a sentence $s$ in the language of PA such that $s$ is logically equivalent to the PA-sentence $\mathrm{code}(s{)}^{*}(\neg \mathrm{Prov})$ (whose interpretation in the model $\mathbb{N}$ is that $s$ has no PA proof).
Thus, if $s$ is false in $\mathbb{N}$, then $s$ has a PA proof (so that PA proves a false statement in a model: is inconsistent). In classical logic, the only other alternative is that $s$ is true in $\mathbb{N}$, but then this true sentence (in the language of PA) has no PA proof.
Indeed, let $R$ be a formula that represents the unary predicate $\neg \mathrm{Prov}$, and let $s$ be a fixed point in the sense $[s]=[s\cdot R]$. The equality here is logical equivalence, and $[s\cdot R]=\mathrm{code}(s{)}^{*}(\neg \mathrm{Prov})$ by equation (1).
The proof of theorem 1 was written to lay bare its provenance as a special case of Lawvere’s fixed point theorem, and its essential kinship with the structure of the standard fixpoint combinator in combinatory algebra. See Yanofsky’s article below.
This and the next lemma demonstrate the essential truth of Paul Taylor’s quip (Practical Foundations of Mathematics, p. 192): “Lemmas do the work in mathematics: Theorems, like management, just take the credit. A good lemma also survives a philosophical or technological revolution.” ↩