Section 3.3: Problem 1 Solution »

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.
  1. (S1) .
  2. (S2) .
  3. (L1) .
  4. (L2) .
  5. (L3) .
  6. (A1) .
  7. (A2) .
  8. (M1) .
  9. (M2) .
  10. (E1) .
  11. (E2) .
Note, that , as not all previous axioms for and are in .
  1. (-) (S3) .
  2. (?) (S4) For every , , .
  3. (?) (L4) .
  4. (?) (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

  1. For every , .
  2. For every term not containing variables, there is a unique such that .
  3. For every quantifier-free or existential ( ) sentence true in , .
    1. 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 .
  1. A relation is representable iff its characteristic function is representable, where if , and otherwise.
  2. If are representable, then , i.e. iff , is representable.
    1. For example, is representable, as iff . See also the next catalog item.
  3. If is representable, then so are and .
    iff .
  4. The divisibility relation is representable.
    iff , and is representable.
  5. The set of primes is representable.
    (there are other forms to express , but we need one to use catalog item 0).
  6. The set of pairs of adjacent primes is representable.
  7. , the st prime, is representable.
    iff (informally) .
  8. The encoding function , , , is representable.
  9. The decoding function where is representable.
    1. Note, that, formally, is defined for all natural numbers as the least such that either or .
  10. The set of sequence numbers such that for some is representable.
  11. The length function where is representable.
    1. Note, that, formally, is defined for all natural numbers as the least such that either or .
  12. The restriction of to where is representable.
    1. Note, that, formally, is defined for all natural numbers as the least such that either or both and for every , , implies .
  13. (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 , ”, .
  14. If is representable, so are and .
  15. The concatenation of and , , i.e. , 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).
  16. is representable.