Section 3.3: A Subtheory of Number Theory
Consider
.
 In we can define relations , , , and .
 In we can define relations , , and .
It will be shown that
is neither decidable, nor axiomatizable (effectively enumerable).
𝔑_{E}
Axiomatization
Let
be the following finite set of axioms.
 (S1) .
 (S2) .
 (L1) .
 (L2) .
 (L3) .
 (A1) .
 (A2) .
 (M1) .
 (M2) .
 (E1) .
 (E2) .
Note, that
, as not all previous axioms for
and
are in
.
 () (S3) .
 (?) (S4) For every , , .
 (?) (L4) .
 (?) (L5) .
A theory
(in a language with
and
) is called
complete theory iff for any formula
and variable
, if
belongs to
for every
, then
belongs to
.
iff
is a consistent
complete theory (in the language of
).
Consequences of the axioms
 For every , .
 For every term not containing variables, there is a unique such that .

For every quantifierfree or existential (
) sentence
true in
,
.
 It is known that there are universal ( ) sentences true in such that .
Representable Relations
Let
be a theory in a language containing
and
. A formula
represents an
ary relation
in
iff for every
,

If
is complete and satisfiable (
), then
represents
in
iff
defines
in a model of
.
 represents in iff defines in .

If
is satisfiable but not complete (
), then if
represents
in
, then
defines
in a model of
, but not necessarily vice versa. A relation is representable in
iff some formula represents it in
.
 represents in iff for every ,
 is called numeralwise determined by iff for every , Then, represents in iff is numeralwise determined by and defines in .
Any atomic formula is numeralwise determined by
. If
and
are numeralwise determined by
, so are
,
,
and
(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
on
is recursive iff it is representable in a consistent finitely axiomatizable theory in a language with
and
.
 A relation is recursive iff it is representable in (see below).
(Church’s Thesis) A relation is decidable iff it is recursive.
Representable Functions
A function
is said to be computable iff there is an effective procedure that, given
, outputs
.
 is computable iff as a relation is decidable iff as a relation is effectively enumerable iff as a relation is recursive.
A formula
functionally represents function
in
iff for every
and
,
.
is functionally representable in
iff
as a relation is representable in
.
 For every that functionally represents in , represents as a relation in .

If some
represents
as a relation in
, then some
functionally represents
in
.
 Take to be .
Examples and catalog
In this subsection “representable” means “representable in
”. We also use
for
(where the value of
should be clear from the context).
Every equation
, where
is a term containing
as (free) variables, (functionally) represents the function that it defines.

Examples:
 : .
 : .
 : .
 : where .
Let
and
, for
, be representable, then
is representable.
Let
be a representable function such that for every
, there is
such that
. Then
such that
is representable (here
stands for the
operator, i.e. the least number satisfying the equation in the brackets).
Let
be a representable relation such that for every
there is some
such that
. Then “the least
such that
”, i.e.
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
a quantifier free definition is representable, b) the class of representable relations is closed under unions, intersections, and complements, and c) if
is representable, so are
and
.
 A relation is representable iff its characteristic function is representable, where if , and otherwise.

If
are representable, then
, i.e.
iff
, is representable.
 For example, is representable, as iff . See also the next catalog item.

If
is representable, then so are
and
.iff .

The divisibility relation
is representable.iff , and is representable.

The set
of primes is representable.(there are other forms to express , but we need one to use catalog item 0).
 The set of pairs of adjacent primes is representable.

, the
st prime, is representable.iff (informally) .
 The encoding function , , , is representable.

The decoding function
where
is representable.
 Note, that, formally, is defined for all natural numbers as the least such that either or .
 The set of sequence numbers such that for some is representable.

The length function
where
is representable.
 Note, that, formally, is defined for all natural numbers as the least such that either or .

The restriction of
to
where
is representable.
 Note, that, formally, is defined for all natural numbers as the least such that either or both and for every , , implies .

(Primitive recursion) Let
. Then, for a function
, there exists unique
, and if
is representable, then so is
.is the least number such that “ is a sequence number of length , and for , ”, .
 If is representable, so are and .

The concatenation of
and
,
, i.e.
, is representable.
 Note, that, formally, the concatenation is defined by the formula for all natural numbers.
 However, the operation, as defined, is associative on sequence numbers only (see Exercise 6).
 is representable.