Section 3.3: A Subtheory of Number Theory

Consider $\mathfrak{N}=(\mathbb{N};0,S,<,+,\cdot,E)$ .

In $(\mathbb{N};E)$ we can define relations $\cdot$ , $\{0\}$ , $S$ , $<$ and $+$ .
In $(\mathbb{N};+,\cdot)$ we can define relations $\{0\}$ , $S$ , $<$ and $E$ .

It will be shown that $\mathfrak{N}$ is neither decidable, nor axiomatizable (effectively enumerable).

𝔑_E

Axiomatization

Let $A_{E}$ be the following finite set of axioms.

(S1) $\forall x\mathbb{S}x\neq0$ .
(S2) $\forall x\forall y(\mathbb{S}x=\mathbb{S}y\rightarrow x=y)$ .
(L1) $\forall x\forall y(x<\mathbb{S}y\leftrightarrow x\le y)$ .
(L2) $\forall xx\nless0$ .
(L3) $\forall x\forall y(x<y\vee x=y\vee y<x)$ .
(A1) $\forall xx+0=x$ .
(A2) $\forall x\forall yx+\mathbb{S}y=\mathbb{S}(x+y)$ .
(M1) $\forall xx\cdot0=0$ .
(M2) $\forall x\forall yx\cdot\mathbb{S}y=x\cdot y+x$ .
(E1) $\forall xx\mathbb{E}0=\mathbb{S}0$ .
(E2) $\forall x\forall yx\mathbb{E}\mathbb{S}y=x\mathbb{E}y\cdot y$ .

Note, that $\mbox{Cn}A_{E}\subsetneq\mbox{Th}\mathfrak{N}$ , as not all previous axioms for $\mathfrak{N}_{S}$ and $\mathfrak{N}_{L}$ are in $\mbox{Cn}A_{E}$ .

(-) (S3) $A_{E}\nvdash\forall y(y\neq0\rightarrow\exists xy=\mathbb{S}x)$ .
(?) (S4) For every $n\in\mathbb{N}$ , $n\ge1$ , $\forall x\mathbb{S}^{n}x\neq x$ .
(?) (L4) $\forall x\forall y(x<y\rightarrow y\nless x)$ .
(?) (L5) $\forall x\forall y\forall z(x<y\rightarrow y<z\rightarrow x<z)$ .

A theory $T$ (in a language with $0$ and $\mathbb{S}$ ) is called $\omega$ -complete theory iff for any formula $\phi$ and variable $x$ , if $\phi_{\mathbb{S}^{n}0}^{x}$ belongs to $T$ for every $n\in\mathbb{N}$ , then $\forall x\phi$ belongs to $T$ . $A_{E}\subseteq T=\mbox{Th}\mathfrak{N}$ iff $T$ is a consistent $\omega$ -complete theory (in the language of $\mathfrak{N}$ ).

Consequences of the axioms

For every $n\in\mathbb{N}$ , $A_{E}\vdash\forall xx<\mathbb{S}^{n}0\leftrightarrow x=0\vee\ldots\vee x=\mathbb{S}^{n-1}0$ .
For every term $t$ not containing variables, there is a unique $n\in\mathbb{N}$ such that $A_{E}\vdash t=\mathbb{S}^{n}0$ .
For every quantifier-free or existential ( $\exists_{1}$ ) sentence $\tau$ true in $\mathfrak{N}$ , $A_{E}\vdash\tau$ .
1. It is known that there are universal ( $\forall_{1}$ ) sentences $\tau$ true in $\mathfrak{N}$ such that $A_{E}\nvdash\tau$ .

Representable Relations

Let $T$ be a theory in a language containing $0$ and $\mathbb{S}$ . A formula $\rho$ represents an $m$ -ary relation $R$ in $T$ iff for every $n_{1},\ldots,n_{m}\in\mathbb{N}$ , $\begin{eqnarray*} <n_{1},\ldots,n_{m}>\in R & \Rightarrow & \rho(\mathbb{S}^{n_{1}}0,\ldots,\mathbb{S}^{n_{m}}0)\in T,\\ <n_{1},\ldots,n_{m}>\notin R & \Rightarrow & \neg\rho(\mathbb{S}^{n_{1}}0,\ldots,\mathbb{S}^{n_{m}}0)\in T. \end{eqnarray*}$

If $T$ is complete and satisfiable ( $\neg\sigma\in T\Leftrightarrow\sigma\notin T$ ), then $\rho$ represents $R$ in $T$ iff $\rho$ defines $R$ in a model of $T$ .
- $\rho$ represents $R$ in $\mbox{Th}\mathfrak{N}$ iff $\rho$ defines $R$ in $\mathfrak{N}$ .
If $T$ is satisfiable but not complete ( $\neg\sigma\in T\Rightarrow\sigma\in T$ ), then if $\rho$ represents $R$ in $T$ , then $\rho$ defines $R$ in a model of $T$ , but not necessarily vice versa. A relation is representable in $T$ iff some formula represents it in $T$ .
- $\rho$ represents $R$ in $\mbox{Cn}A_{E}$ iff for every $n_{1},\ldots,n_{m}\in\mathbb{N}$ , $\begin{eqnarray*} <n_{1},\ldots,n_{m}>\in R & \Rightarrow & A_{E}\vdash\rho(\mathbb{S}^{n_{1}}0,\ldots,\mathbb{S}^{n_{m}}0),\\ <n_{1},\ldots,n_{m}>\notin R & \Rightarrow & A_{E}\vdash\neg\rho(\mathbb{S}^{n_{1}}0,\ldots,\mathbb{S}^{n_{m}}0). \end{eqnarray*}$
- $\rho$ is called numeralwise determined by $A_{E}$ iff for every $n_{1},\ldots,n_{m}\in\mathbb{N}$ , $\begin{eqnarray*} A_{E} & \vdash & \rho(\mathbb{S}^{n_{1}}0,\ldots,\mathbb{S}^{n_{m}}0)\\ & \mbox{or}\\ A_{E} & \vdash & \neg\rho(\mathbb{S}^{n_{1}}0,\ldots,\mathbb{S}^{n_{m}}0). \end{eqnarray*}$ Then, $\rho$ represents $R$ in $\mbox{Cn}A_{E}$ iff $\rho$ is numeralwise determined by $A_{E}$ and $\rho$ defines $R$ in $\mathfrak{N}$ .

Any atomic formula is numeralwise determined by $A_{E}$ . If $\phi$ and $\psi$ are numeralwise determined by $A_{E}$ , so are $\neg\phi$ , $\phi\rightarrow\psi$ , $\exists x(x<y\wedge\phi)$ and $\forall x(x<y\rightarrow\phi)$ (bounded quantification).

Church’s Thesis

A relation representable in a consistent axiomatizable theory is decidable.

A relation representable in a consistent finitely axiomatizable theory is decidable.

The corollary itself does not add any value to the theorem. It is its converse that is of interest.

We cannot really hope to prove the converse on the basis of our informal notion of decidability... It is nevertheless possible to make plausibility arguments in support of the converse... The assertion that both the above corollary and its converse are correct is generally known as Church’s thesis. This assertion is not really a mathematical statement susceptible to proof or disproof; rather it is a judgment that the correct formalization of the informal notion of decidability is by means of representability in consistent and finitely axiomatizable theories.

A relation $R$ on $\mathbb{N}$ is recursive iff it is representable in a consistent finitely axiomatizable theory in a language with $0$ and $\mathbb{S}$ .

A relation is recursive iff it is representable in $\mbox{Cn}A_{E}$ (see below).

(Church’s Thesis) A relation is decidable iff it is recursive.

Representable Functions

A function $f:\mathbb{N}^{m}\rightarrow\mathbb{N}$ is said to be computable iff there is an effective procedure that, given $a_{1},\ldots,a_{m}\in\mathbb{N}$ , outputs $f(a_{1},\ldots,a_{m})$ .

$f$ is computable iff $f$ as a relation is decidable iff $f$ as a relation is effectively enumerable iff $f$ as a relation is recursive.

A formula $\phi$ functionally represents function $f$ in $\mbox{Cn}A_{E}$ iff for every $a_{1},\ldots,a_{m}\in\mathbb{N}$ and $a_{m+1}=f(a_{1},\ldots,a_{m})$ , $A_{E}\vdash\forall v_{m+1}(\phi(\mathbb{S}^{a_{1}}0,\ldots,\mathbb{S}^{a_{m}}0)\leftrightarrow v_{m+1}=\mathbb{S}^{a_{m+1}}0)$ .

$f$ is functionally representable in $\mbox{Cn}A_{E}$ iff $f$ as a relation is representable in $\mbox{Cn}A_{E}$ .

For every $\phi$ that functionally represents $f$ in $\mbox{Cn}A_{E}$ , $\phi$ represents $f$ as a relation in $\mbox{Cn}A_{E}$ .
If some $\phi$ represents $f$ as a relation in $\mbox{Cn}A_{E}$ , then some $\psi$ functionally represents $f$ in $\mbox{Cn}A_{E}$ .
- Take $\psi$ to be $\phi\wedge\forall x(x<v_{2}\rightarrow\neg\phi(v_{1},x))$ .

Examples and catalog

In this subsection “representable” means “representable in $\mbox{Cn}A_{E}$ ”. We also use $\vec{a}$ for $a_{1},\ldots,a_{k}$ (where the value of $k$ should be clear from the context).

Every equation $v_{m+1}=t$ , where $t$ is a term containing $v_{1},\ldots,v_{m}$ as (free) variables, (functionally) represents the function that it defines.

Examples:
- $S$ : $v_{2}=\mathbb{S}v_{1}$ .
- $n$ : $v_{m+1}=\mathbb{S}^{n}0$ .
- $I_{i}^{m}$ : $v_{m+1}=v_{i}$ .
- $+,\cdot,E$ : $v_{3}=v_{1}*v_{2}$ where $*\in\{+,\cdot,E\}$ .

Let $g:\mathbb{N}^{n}\rightarrow\mathbb{N}$ and $h_{i}:\mathbb{N}^{m}\rightarrow\mathbb{N}$ , for $i=1,\ldots,n$ , be representable, then $f=g(h_{1},\ldots,h_{n}):\mathbb{N}^{m}\rightarrow\mathbb{N}$ is representable.

Let $g:\mathbb{N}^{m+1}\rightarrow\mathbb{N}$ be a representable function such that for every $a_{1},\ldots,a_{m}\in\mathbb{N}$ , there is $a_{m+1}\in\mathbb{N}$ such that $g(\vec{a})=0$ . Then $f:\mathbb{N}^{m}\rightarrow\mathbb{N}$ such that $f(\vec{a})=\mu a[g(\vec{a},a)=0]$ is representable (here $\mu b[]$ stands for the $\mu$ -operator, i.e. the least number satisfying the equation in the brackets).

Let $R$ be a representable relation such that for every $\vec{a}$ there is some $n$ such that $<\vec{a},n>\in R$ . Then “the least $n$ such that $R$ ”, i.e. $f(\vec{a})=\mu n[<\vec{a},n>\in R]$ $=\mu n[K_{R}(\vec{a},n)=1]=\mu n[K_{\overline{R}}(\vec{a},n)=0]$ is representable (see catalog item 1 below).

Catalog.

0. We already know (see the theorem in Representable Relations) that a) every relation that has in $\mathfrak{N}$ a quantifier free definition is representable, b) the class of representable relations is closed under unions, intersections, and complements, and c) if $R$ is representable, so are $R_{\forall}=\{<\vec{a},b>|\mbox{for all }c<b,<\vec{a},c>\in R\}$ and $R_{\exists}=\{<\vec{a},b>|\mbox{exists }c<b,<\vec{a},c>\in R\}$ .

A relation $R$ is representable iff its characteristic function $K_{R}$ is representable, where $K_{R}(\vec{a})=1$ if $\vec{a}\in R$ , and $K_{R}(\vec{a})=0$ otherwise.
If $R,f_{1},\ldots,f_{m}$ are representable, then $Q=\{\vec{a}|<f_{1}(\vec{a}),\ldots,f_{m}(\vec{a})>\in R\}$ , i.e. $\vec{a}\in Q$ iff $<f_{1}(\vec{a}),\ldots,f_{m}(\vec{a})>\in R$ , is representable.
1. For example, $Q=\{<x,y>|<y,x,x>\in R\}$ is representable, as $<x,y>\in Q$ iff $<I_{2}^{2}(x,y),I_{1}^{2}(x,y),I_{1}^{2}(x,y)>\in R$ . See also the next catalog item.
If $R$ is representable, then so are $R_{\forall}'=\{<\vec{a},b>|\mbox{for all }c\le b,<\vec{a},c>\in R\}$ and .
$<\vec{a},b>\in R_{\forall}'(R_{\exists}')$ iff $<I_{1}^{m+1}(\vec{a},b),\ldots,I_{m}^{m+1}(\vec{a},b),S(I_{m+1}^{m+1}(\vec{a},b))>\in R_{\forall}(R_{\exists})$ .
The divisibility relation $\mathcal{D}=\{<a,b>|a\mbox{ divides }b\}$ is representable.
$<a,b>\in D$ iff $<I_{1}^{2}(a,b),I_{2}^{2}(a,b),I_{2}^{2}(a,b)>\in\{<a,b,c>|\mbox{ for some }x\le c,a\cdot x=b\}$ , and $\{<a,b,c>|a\cdot c=b\}$ is representable.
The set $\mathcal{P}$ of primes is representable.
$\mathcal{P}=\{p|\mathbb{S}0<p\wedge\forall x(x<p\rightarrow\forall y(y<p\rightarrow x\cdot y\neq p))\}$ (there are other forms to express $\mathcal{P}$ , but we need one to use catalog item 0).
The set $\mathcal{P}_{2}$ of pairs of adjacent primes is representable.
$f(k)=p_{k}$ , the $(k+1)$ st prime, is representable.
$p_{a}=b$ iff (informally) $b\in\mathcal{P}\wedge\exists c\le b^{a^{2}}(<2,c>\notin D$ $\wedge<b^{a},c>\in D\wedge<b^{a+1},c>\notin D\wedge\forall q<b\forall r\le b$ $(<q,r>\in\mathcal{P}_{2}\Rightarrow\forall j<c(<q^{j},c>\in D\Leftrightarrow<r^{j+1},c>\in D)))$ .
The encoding function $\langle\rangle$ , $\langle a_{0},a_{1},\ldots,a_{m}\rangle=\prod_{i=0}^{m}p_{i}^{a_{i}+1}$ , $\langle\rangle=1$ , is representable.
The decoding function $(b)_{c}=a_{c}$ where $b=\langle a_{1},\ldots,a_{m}\rangle$ is representable.
1. Note, that, formally, $(b)_{c}$ is defined for all natural numbers as the least $n\in\mathbb{N}$ such that either $b=0$ or $<p_{c}^{n+2},b>\notin\mathcal{D}$ .
The set of sequence numbers $b$ such that $b=\langle\vec{a}\rangle$ for some $\vec{a}$ is representable.
The length function $\mbox{lh}b=m+1$ where $b=\langle a_{0},\ldots,a_{m}\rangle$ is representable.
1. Note, that, formally, $\mbox{lh}b$ is defined for all natural numbers as the least $n\in\mathbb{N}$ such that either $b=0$ or $<p_{n},b>\notin\mathcal{D}$ .
The restriction of $b$ to $c$ $b\upharpoonright c=\langle a_{0},\ldots,a_{c-1}\rangle$ where $b=\langle a_{0},\ldots,a_{m}\rangle$ is representable.
1. Note, that, formally, $b\upharpoonright c$ is defined for all natural numbers as the least $n\in\mathbb{N}$ such that either $b=0$ or both $n\neq0$ and for every $j<c$ , $k<b$ , $<p_{j}^{k},b>\in\mathcal{D}$ implies $<p_{j}^{k},n>\in\mathcal{D}$ .
(Primitive recursion) Let $\overline{f}(a,\vec{b})=\langle f(0,\vec{b}),\ldots,f(a-1,\vec{b})\rangle$ . Then, for a function $g(x,a,\vec{b})$ , there exists unique $f(a,\vec{b})=g(\overline{f}(a,\vec{b}),a,\vec{b})$ , and if $g$ is representable, then so is $f$ .
$\overline{f}(a,\vec{b})$ is the least number $b$ such that “ $b$ is a sequence number of length $a$ , and for $i<a$ , $(b)_{i}=g(b\upharpoonright i,i,\vec{b})$ ”, $f=g(\overline{f},I_{1}^{m+1},\ldots,I_{m+1}^{m+1})$ .
If $f$ is representable, so are $\prod_{i<a}f(a,\vec{b})$ and $\sum_{i<a}f(a,\vec{b})$ .
The concatenation of $a$ and $b$ , $a\ast b=a\cdot\prod_{i<\mbox{lh}b}p_{i+\mbox{lh}a}^{(b)_{i}+1}$ , i.e. $\langle a_{0},\ldots,a_{m}\rangle\ast\langle b_{o},\ldots,b_{n}\rangle=\langle a_{0},\ldots,a_{m},b_{0},\ldots,b_{n}\rangle$ , is representable.
1. Note, that, formally, the concatenation is defined by the formula for all natural numbers.
2. However, the operation, as defined, is associative on sequence numbers only (see Exercise 6).
$\ast_{i<a}f(i,\vec{b})$ is representable.

Subpages

Section 3.3: A Subtheory of Number Theory

Section 3.3: A Subtheory of Number Theory

𝔑E

Axiomatization

Consequences of the axioms

Representable Relations

Church’s Thesis

Representable Functions

Examples and catalog

𝔑_E