# 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?