% LaTeX2e
% The recursion theorem and infinite sequences
% A. Miller Nov 2007 last revised Aug 08
\documentclass[12pt]{article}
\usepackage{amssymb,xspace}
\pagestyle{myheadings}
\def\header{A.Miller\hfill Recursion Theorem \hfill}
\markboth\header\header
%\pagestyle{myheadings} \def\header{\today} \markboth\header\header
\def\la{\langle}
\def\om{\omega}
\def\proof{\par\noindent Proof\par\noindent}
\def\qed{\par\noindent QED\par\bigskip}
\def\ra{\rangle}
\def\rmand{\mbox{ and }}
\def\self{self-constructing\xspace}
\def\smn{s-m-n\xspace}
\def\st{\;:\;} % such that
\def\su{\subseteq}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\begin{document}
\begin{center}
{\large The Recursion Theorem and Infinite Sequences}
\end{center}
\begin{flushright}
Arnold W. Miller
\footnote{
Mathematics Subject Classification 2000: 03D25; 03D99
\par Keywords: Recursion Theorem, fixed points. }
\end{flushright}
\def\address{\begin{flushleft}
Arnold W. Miller \\
miller@math.wisc.edu \\
http://www.math.wisc.edu/$\sim$miller\\
University of Wisconsin-Madison \\
Department of Mathematics, Van Vleck Hall \\
480 Lincoln Drive \\
Madison, Wisconsin 53706-1388 \\
\end{flushleft}}
\begin{center} Abstract \end{center}
\begin{quote}
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_00$ there is a sequence
$$e_0x) \mbox{ and
$\la s,y\ra$ is the least such pair} \\
\emptyset & \mbox{ otherwise. }
\end{array}\right.$$
Such a $q$ is constructed by a standard argument
using the \smn or Parameterization Theorem.
To see this, one defines a partial computable function $\theta$
as follows:
$$\theta(e,x,y)=\left\{
\begin{array}{ll}
0 & \mbox{ if } (\exists s \exists y\in W_{e,s} \;\; y>x) \mbox{ and
$\la s,y\ra$ is the least such pair} \\
\uparrow & \mbox{ otherwise. }
\end{array}\right.$$
The uparrow stands for a computation that diverges, i.e, does not halt.
By the \smn Theorem there is a computable $q$ such that
$$\psi_{q(e,x)}(y)=\theta(e,x,y)\mbox{ for all } e,x,y.$$
Using Lemma \ref{lem1} 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,\cdot)$, i.e., $W_x=W_{q(e,x)}$ for all $x\in 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\in W_{h(e)}$ so
$W_x=W_{q(e,x)}=\{y\}$ where $y>x$ and $y\in W_e$. Hence, starting
with any $e_0\in 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 \ref{main} must be
computable. This is not necessarily true
for our next result:
\begin{theorem} \label{two}
There exists a computable strictly increasing sequence
$\la e_n:n<\om\ra$ such that for every $n$
$$W_{e_n}=\{e_m\st m>n\}.$$
\end{theorem}
\proof
Using the \smn Theorem find $q$ a computable function
such that for every $x$ and $e$:
$$W_{q(e,x)}=\{\max(W_{e,s})\st s\in \om\}\setminus\{0,1,\ldots,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,\cdot)$, i.e., $W_x=W_{q(e,x)}$ for all $x\in 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_0n\}.$$
\qed
A variation on this theorem would be to get a computable
strictly increasing sequence
$e_0f(j,n)$ for
every $j,n$. By the fixed point theorem there exist a $j$ such
that for every $n$ we have that $\psi_j(n)=f(j,n)$. Hence
$\psi_j$ is total and $\psi_j(n+1)>\psi_j(n)$ all $n$.
Furthermore,
$$W_{\psi_j(n)}=W_{f(j,n)}=\{\psi_j(n+1)\}$$
for every $n$.
\medskip
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:
\begin{enumerate}
\item The set $\{e\st W_e=\{1,\ldots, e\}\}$ is m-complete for
the class of differences of computabily enumerable sets.
\item Suppose $A$ is a simple set and $A=\{a_n\st n\in\om\}$ is a 1-1
computable enumeration of $A$. Then there exist infinitely many
$n$ such that $$W_{a_n}=\{a_m\st m>n\}.$$
\end{enumerate}
This last problem was our motivation for the proof of Theorem 1.
\begin{thebibliography}{99}
\bibitem{cooper} Cooper, S. Barry {\bf Computability theory}. Chapman \&
Hall/CRC, Boca Raton, FL, 2004. x+409 pp. ISBN: 1-58488-237-9
\bibitem{miller} Miller, Arnold W. {\bf Lecture Notes in Computability Theory}.
eprint Jan 08:
http://www.math.wisc.edu/$\sim$miller/res
\bibitem{odifreddi} Odifreddi, Piergiorgio { \bf 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
\bibitem{rogers} Rogers, Hartley, Jr. {\bf Theory of recursive functions and
effective computability.} McGraw-Hill Book Co., New York-Toronto, Ont.-London
1967 xx+482 pp.
\bibitem{smullyan} Smullyan, Raymond M. {\bf 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
% \bibitem{smullyan2}
% Smullyan, Raymond M. {\bf Diagonalization and
% self-reference.} Oxford Logic Guides, 27. Oxford Science Publications. The
% Clarendon Press, Oxford University Press, New York, 1994. xx+396 pp. ISBN:
% 0-19-853450-7
\bibitem{soare}
Soare, Robert I. {\bf 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
\end{thebibliography}
\address
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\def\header{ Appendix \hfill Electronic on-line version only\hfill }
\markboth\header\header
\setcounter{page}{1}
\setcounter{theorem}{0}
\begin{center}
Appendix
\end{center}
\bigskip
The appendix is not intended for final publication but for
the on-line electronic version only.
\bigskip
\begin{theorem}
There exists an infinite strictly increasing sequence
$\la e_n:n<\om\ra$ such that for every $n$
$$W_{e_n}=\{e_m\st m>n\}$$
and the sequence is not computable.
\end{theorem}
\proof
This is a combination of the proof of Theorem \ref{two} and
Theorem \ref{self}.
Fix $B$ a computably enumerable but not computable set.
For any $e$ let
$$\{c_0x\}.$$
Take $h$ computable so that for every $e$, $W_{h(e)}$ is an
infinite set of fixed points for $q(e,\cdot)$, i.e.,
$x\in 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_0c_m\}.$$
If $e_k=c_m$ this means that
$$W_{e_k}=\{e_l: l>k \}.$$
\qed
\begin{theorem}
There is a computable
strictly increasing sequence
$e_0