\( \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 Answer
\( \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 [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?