The Recursion Theorem and Infinite Sequences

Arnold W. Miller ^{1}

Abstract

In this paper we use the Recursion Theorem to show the existence of various infinite sequences and sets. Our first result is that there is an increasing sequence e_{0} < e_{1} < ⋯ such that W_{e_{n}} = {e_{n+1}} for every n. Similarly, we prove that there exists an increasing sequence such that W_{e_{n}} = {e_{n+1}, e_{n+2}, …} for every n. We call a nonempty computably enumerable set A self-constructing if W_{e} = A for every e ∈ A. We show that every nonempty computably enumerable set which is disjoint from an infinite computable set is one-one equivalent to a self-constructing set.

Kleene’s Recursion Theorem says the following:

For any computable function f there exists an e with ψ_{e} = ψ_{f(e)}.

In this Theorem ⟨ψ_{e} : e ∈ ω⟩ is a standard computable numbering of all partial computable functions. For example, ψ_{e} might be the partial function computed by the e^{th} Turing machine. The number e is referred to as a fixed point for f and this theorem is also called the Fixed Point Theorem.

For a proof of Kleene’s Theorem see any of the standard references, Cooper [1], Odifreddi [3], Rogers [4], or Soare [6]. See especially Smullyan [5] for many variants and generalizations of the fixed point theorem. The Recursion Theorem applies to all acceptable numberings (in the sense of Rogers, see Odifreddi [3] p.215-221). All natural enumerations are acceptable. We use W_{e} to denote the domain of ψ_{e} and hence ⟨W_{e} : e ∈ ω⟩ is a uniform computable listing of all computably enumerable sets.

The proof of the Recursion Theorem is short but tricky. It can be uniformized to yield what is called the Recursion Theorem with Parameters. The proof also yields an infinite computable set of fixed points by using the Padding Lemma. See Soare [6] pages 36-37.

We will use the following version of the Recursion Theorem with Parameters which includes a uniform use of the Padding Lemma:

1Mathematics Subject Classification 2000: 03D25; 03D99

Keywords: Recursion Theorem, fixed points.

Lemma 1 For any computable function f : ω ×ω → ω there is a computable function h : ω → ω such that W_{h(x)} is an infinite computable set for every x and for every y ∈ W_{h(x)} we have that ψ_{f(x,y)} = ψ_{y}.

The proof is left to the reader.

It is an exercise (see Miller [2] section 13) to show (using Smullyan’s double recursion theorem or more particularly its n-ary generalization, see [5] Chapter IX) that for any n > 0 there is a sequence

e_{0} < e_{1} < ⋯ < e_{n}

such that W_{e_{i}} = {e_{i+1}} for i < n and W_{e_{n}} = {e_{0}}. It occurred to us to ask if it would be possible to have an infinite sequence like this. We show that it is.

Theorem 1 There is a strictly increasing sequence:

e_{0} < e_{1} < ⋯ < e_{n} < ⋯

such that

W_{e_{n}} = {e_{n+1}} for every n.

Proof

We use W_{e,s} to denote the set of all y < s such that ψ_{e}(y) converges in less than s-steps. We use ⟨x, y⟩ to denote a pairing function, a computable bijection from ω^{2} to ω, e.g., ⟨x, y⟩ = 2^{x}(2y + 1) − 1.

Let q(e, x) be a computable function such that for all x and e:

W_{q(e,x)} = \{ \begin{matrix}\{y\} & if (∃s∃y ∈ W_{e,s} y > x) and ⟨s, y⟩ is the least such pair \\ ∅ & otherwise. \end{matrix}

Such a q is constructed by a standard argument using the s-m-n or Parameterization Theorem. To see this, one defines a partial computable function θ as follows:

θ(e, x, y) = \{ \begin{matrix}0 & if (∃s∃y ∈ W_{e,s} y > x) and ⟨s, y⟩ is the least such pair \\ ↑ & otherwise. \end{matrix}

The uparrow stands for a computation that diverges, i.e, does not halt. By the s-m-n Theorem there is a computable q such that

ψ_{q(e,x)}(y) = θ(e, x, y) for all e, x, y.

Using Lemma 1 let h be a computable function such that for every e, the set W_{h(e)} is an infinite set of fixed points for q(e, ·), i.e., W_{x} = W_{q(e,x)} for all x ∈ W_{h(e)}. Let e be a fixed point for h, so W_{e} = W_{h(e)}.

Let x be any element of W_{e}. Then x ∈ W_{h(e)} so W_{x} = W_{q(e,x)} = {y} where y > x and y ∈ W_{e}. Hence, starting with any e_{0} ∈ W_{e} we get an infinite increasing sequence as required. QED

Note that to obtain a sequence with W_{e_{n+1}} = {e_{n}} is trivial. Also note that the sequence in Theorem 1 must be computable. This is not necessarily true for our next result:

Theorem 2 There exists a computable strictly increasing sequence ⟨e_{n} : n < ω⟩ such that for every n

W_{e_{n}} = {e_{m} : m > n}.

Proof Using the s-m-n Theorem find q a computable function such that for every x and e:

W_{q(e,x)} = {max(W_{e,s}) : s ∈ ω} \ {0, 1, …, x}.

As in the above proof, let h be a computable function such that for every e, the set W_{h(e)} is an infinite set of fixed points for q(e, ·), i.e., W_{x} = W_{q(e,x)} for all x ∈ W_{h(e)}. Let e be a fixed point for h, so W_{e} = W_{h(e)}.

Note that W_{e} is infinite and let

{e_{0} < e_{1} < e_{2} < …} = {max(W_{e,s}) : s ∈ ω}.

For any x ∈ W_{e} = W_{h(e)} we have that

W_{x} = W_{q(e,x)} = {max(W_{e,s}) : s ∈ ω} \ {0, 1, …, x}.

Hence for any n we have that

W_{e_{n}} = {e_{m} : m > n}.

QED

A variation on this theorem would be to get a computable strictly increasing sequence e_{0} < e_{1} < ⋯ such that

ψ_{e_{n}}(m) = e_{n+m+1} for every n, m < ω.

The proof of this is left as an exercise for the reader.

Usually the first example given of an application of the Recursion Theorem is to prove that there exists an e such that W_{e} = {e}. We say that a nonempty computably enumerable set A is self-constructing iff for all e ∈ A we have that W_{e} = A. So W_{e} = {e} is an example of a self-constructing set. Our next result shows there are many self-constructing sets.

Theorem 3 For any nonempty computably enumerable set B the following are equivalent:

1. B is disjoint from an infinite computable set.

2. There is a computable permutation π of ω such that A = π(B) and A is self-constructing.

Proof (2) → (1) Let E be an infinite computable set such that for every e ∈ E we have

that W_{e} = ∅. Any self-constructing set is disjoint from E.

(1) → (2)

Given any e consider the following computably enumerable set Q_{e}. Let

{c_{0} < c_{1} < c_{2} < …} = {max(W_{e,s}) : s ∈ ω}

which may be finite or even empty. Then put

Q_{e} = {c_{n} : n ∈ B}.

By the s-m-n Theorem we can find a computable q such that for every e:

W_{q(e)} = Q_{e}.

By the Padding Lemma there is a computable h such that for every e the set W_{h(e)} is infinite and for all x ∈ W_{h(e)} we have that W_{x} = W_{q(e)}. Now let e be a fixed point for h so that W_{h(e)} = W_{e}. Let A = Q_{e}. Then for all x ∈ A we have that W_{x} = A. So A is self-constructing.

To get π let D and E be two infinite pairwise disjoint computable sets disjoint from B. Take one-one computable enumerations of them:

D = {d_{n} : n < ω} and E = {e_{n} : n < ω}.

Note that W_{e} = W_{h(e)} is infinite and let C be the infinite computable set:

C = {c_{0} < c_{1} < c_{2} < …} = {max(W_{e,s}) : s ∈ ω}.

Since W_{e} = W_{h(e)} is a set of fixed points, it is coinfinite and hence C ⊆ W_{e} is coinfinite. Take a one-one computable enumeration of the complement \overline{C} of C:

\overline{C} = \{\overline{c}_{n} : n < ω\}.

Now we can define π:

π(c_{n}) = \{ \begin{matrix}d_{2n} & if n ∈ D \\ d_{2n+1} & if n ∈ E \\ n & otherwise \end{matrix}

π(\overline{c}_{n}) = e_{n}.

Note that π bijectively maps C to \overline{E} and \overline{C} to E. Furthermore if n ∈ B then π(c_{n}) = n, and since A = {c_{n} : n ∈ B} we have that π(A) = B. QED

As a corollary we get that there are self-constructing sets of each finite cardinality and there is a self-constructing set which is not computable, in fact, there is a creative self-constructing set.

It is not hard to show that

S = {e : W_{e} is self-constructing}

is Π_{2}^{0}-complete. To see this first note that it is easy to show that S is Π_{2}^{0}. We can get a many-one reduction f of

Tot =^{def} {e : W_{e} = ω}

to S as follows. Fix an infinite self-constructing set A with one-to-one computable enumeration A = {a_{n} : n ∈ ω}. By the s-m-n Theorem construct a computable f so that for every e:

W_{f(e)} = {a_{n} : n ∈ W_{e}}.

Hence, e ∈ Tot iff f(e) ∈ S. Since Tot is Π_{2}^{0}-complete (see Soare [6] page 66), S is too.

An anonymous referee came up with this very nice proof of Theorem 1:

Define a total computable function f(j, n) as follows:

W_{f(j,n)} = \{ \begin{matrix}\{ψ_{j}(n + 1)\} & if ψ_{j}(n + 1) ↓ \\ ∅ & otherwise. \end{matrix}

By using the padding lemma, we may construct f so that f(j, n+1) > f(j, n) for every j, n. By the fixed point theorem there exist a j such that for every n we have that ψ_{j}(n) = f(j, n). Hence ψ_{j} is total and ψ_{j}(n + 1) > ψ_{j}(n) all n. Furthermore,

W_{ψ_{j}(n)} = W_{f(j,n)} = {ψ_{j}(n + 1)}

for every n.

On the otherhand perhaps we would not have thought of Theorem 3 if we had not been thinking about using a computable set of fixed points.

It is traditional for our qualifying exam in Logic to always have a problem which uses the recursion theorem (Kleene was the first logician in Madison). After over twenty years of exams it is hard for us to think of another original problem using the recursion theorem.

Some other examples of the use of the recursion theorem are the following:

1. The set {e : W_{e} = {1, …, e}} is m-complete for the class of differences of computabily enumerable sets.

2. Suppose A is a simple set and A = {a_{n} : n ∈ ω} is a 1-1 computable enumeration of A. Then there exist infinitely many n such that

W_{a_{n}} = {a_{m} : m > n}.

This last problem was our motivation for the proof of Theorem 1.

References

[1] Cooper, S. Barry Computability theory. Chapman & Hall/CRC, Boca Raton, FL, 2004. x+409 pp. ISBN: 1-58488-237-9

[2] Miller, Arnold W. Lecture Notes in Computability Theory. eprint Jan 08: http://www.math.wisc.edu/∼miller/res [3] Odifreddi, Piergiorgio Classical recursion theory. The theory of

functions and sets of natural numbers. With a foreword by G. E. Sacks. Studies in Logic and the Foundations of Mathematics, 125. North-Holland Publishing Co., Amsterdam, 1989. xviii+668 pp. ISBN: 0-444-87295-7

[4] Rogers, Hartley, Jr. Theory of recursive functions and effective computability. McGraw-Hill Book Co., New York-Toronto, Ont.- London 1967 xx+482 pp.

[5] Smullyan, Raymond M. Recursion theory for metamathematics. Oxford Logic Guides, 22. The Clarendon Press, Oxford University Press, New York, 1993. xvi+163 pp. ISBN: 0-19-508232-X

[6] Soare, Robert I. Recursively enumerable sets and degrees. A study of computable functions and computably generated sets. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. xviii+437 pp. ISBN: 3-540-15299-7

Arnold W. Miller miller@math.wisc.edu http://www.math.wisc.edu/∼miller University of Wisconsin-Madison Department of Mathematics, Van Vleck Hall 480 Lincoln Drive Madison, Wisconsin 53706-1388

Appendix

The appendix is not intended for final publication but for the on-line electronic version only.

Theorem 1 There exists an infinite strictly increasing sequence ⟨e_{n} : n < ω⟩ such that for every n

W_{e_{n}} = {e_{m} : m > n}

and the sequence is not computable.

Proof This is a combination of the proof of Theorem 2 and Theorem 3. Fix B a computably enumerable but not computable set. For any e let

{c_{0} < c_{1} < c_{2} < …} = {max(W_{e,s}) : s ∈ ω}

By the s-m-n Theorem find computable q such that for any x and e

W_{q(e,x)} = {c_{n} : n ∈ B and c_{n} > x}.

Take h computable so that for every e, W_{h(e)} is an infinite set of fixed points for q(e, ·), i.e., x ∈ W_{h(e)} implies W_{x} = W_{q(e,x)}. Take e to be a fixed point for h, so W_{h(e)} = W_{e}.

For this e as above define c_{n}:

{c_{0} < c_{1} < c_{2} < …} = {max(W_{e,s}) : s ∈ ω}.

Let {e_{n} : n < ω} list the set {c_{n} : n ∈ B} in strictly increasing order. Clearly the set {e_{n} : n < ω} is computably enumerable but not computable since the sequence of c_{n}’s is a strictly increasing computable sequence and B is computably enumerable but not computable.

Fix any c_{m} for m ∈ B. Then c_{m} ∈ W_{e} = W_{h(e)} and so

W_{c_{m}} = W_{q(e,c_{m})} = {c_{n} : n ∈ B and c_{n} > c_{m}}.

If e_{k} = c_{m} this means that

W_{e_{k}} = {e_{l} : l > k}.

QED Theorem 2 There is a computable strictly increasing sequence e_{0} < e_{1} < ⋯ such that

ψ_{e_{n}}(m) = e_{n+m+1} for every n, m < ω.

Proof As in the proof of Theorem 2 given any e let

{e_{0} < e_{1} < e_{2} < …} = {max(W_{e,s}) : s ∈ ω}

and using the s-m-n Theorem find q a computable function such that for every x, m, and e:

ψ_{q(e,x)}(m) = e_{n+m+1} where n is minimal so that e_{n} ≥ x}.

Let h be a computable function such that for every e, the set W_{h(e)} is an infinite set of fixed points for q(e, ·), i.e., ψ_{x} = ψ_{q(e,x)} for all x ∈ W_{h(e)}. Let e be a fixed point for h, so W_{e} = W_{h(e)}.

Now for any n we have that e_{n} ∈ W_{e} = W_{h(e)} and so ψ_{e_{n}} = ψ_{q(e,e_{n})} and hence for every m:

ψ_{e_{n}}(m) = e_{n+m+1}.

QED