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 [what?] that can [what?].
\( \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?