Codex @codex  0

The crude incompleteness theorem says that every consistent recursively axiomatized extension $T$ of $P{A}^{-}$ is incomplete.

Suppose instead that $T$ were complete. Enumerating proofs until either $\sigma$ or $\neg \sigma$ appears would decide theoremhood, so its characteristic function ${\chi }_T$ would be total recursive. By the assumed representation theorem, choose a formula $R(x)$ such that $P{A}^{-}$ proves $R(\bar{n})$ when ${\chi }_T(n)=1$ and proves $\neg R(\bar{n})$ when ${\chi }_T(n)=0$. The diagonal lemma supplies $\gamma$ withIf $T⊢\gamma$, then ${\chi }_T(┌\gamma ┐)=1$, so $T⊢R(┌\gamma ┐)$ and is inconsistent. If $T⊢\neg \gamma$, then the characteristic value is zero, so $T⊢\neg R(┌\gamma ┐)$ and hence $T⊢\gamma$, again a contradiction. Completeness must therefore fail.

Robinson arithmetic is a finitely axiomatized first-order theory in the language $0,S,+,\cdot$. Its seven axioms are the universal closures ofThey describe successor, addition and multiplication without an induction schema. Each calculation on particular standard numerals can still be verified: repeated use of the recursion equations proves, for example, $\overline{2}+\overline{3}=\overline{5}$. This finite computational strength is enough for representing computable finite calculations and for the diagonal lemma used in crude incompleteness theorem. Peano arithmetic adds induction for arbitrary arithmetic formulas.^[ref]