\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \newcommand{\E} {\mathrm{E}} \)
deepdream of a sidewalk
Show Question
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \newcommand{\groupMul}[1] { \cdot_{\small{#1}}} \newcommand{\groupAdd}[1] { +_{\small{#1}}} \newcommand{\inv}[1] {#1^{-1} } \newcommand{\bm}[1] { \boldsymbol{#1} } \require{physics} \require{ams} \require{mathtools} \)
Math and science::Theory of Computation

Number theory is undecidable 

Mathematical model

An alphabet \( \land, \lor, \lnot, (,), \forall, \exists, x_1, x_2, ..., R_1, ... R_k \) has a model which is a tuple \( (U, P_1, ... P_k) \) where \( U \) is the universe from which variables may take values and \( P_1, ... P_k \) are the relations assigned to the symbols \( R_1 ... R_k \).

A formula is recursively defined starting from atomic formula and building from here with the \( \land, \lor, \lnot, \forall\) and \( \exists \) symbols.

The language of a model is the collection of formulas but restricted to those that only use the relations listed in the model.

The theory of a model is the collection of true sentences in the language of that model.

Decidable theory

For a model, \( \mathcal{M} \), its theory \( \operatorname{Th}(\mathcal{M}) \) is said to be a decidable theory iff there exists an algorithm (Turing machine) that can decide if a statement constructed according to the model is true or false.

\( \operatorname{Th}(\mathbb{N}, +) \) is decidable

The model constructed from the logic symbols along with the natural numbers and the addition relation—the theory for this model is decidable.

\( \operatorname{Th}(\mathbb{N}, +, \times) \) is undecidable

The model constructed from the logic symbols along with the natural numbers and the addition and multiplication relation—the theory for this model is not decidable.

The proof idea of the undecidability of number theory is on the reverse side. Can you remember the rough idea?


\( \operatorname{Th}(\mathbb{N}, +, \times) \) is undecidable. Proof idea.

The idea is to show that if the theory was decidable, we could determine whether an arbitrary Turing machine accepts some arbitrary input!

For a given Turing machine and input, it's possible to construct a statement according to the model such that the statement is true iff the machine accepts the input. Now a fact: we can enumerate all proofs possible in the model. With this we will eventually find a proof for the statement and thus determine whether the machine accepts the input. But this is impossible! We would have just created an algorithm to determine if a Turing machine accepts an input! The catch is that we assumed that there was a proof for the statement to be either true or false. The line of reasoning in the detailed proof implies that there are statements in the model that have no proof for either truth or falsity.