Appendix: Some Basic Facts and Notation
We list here some elementary definitions and results, primarily to establish notation.
App 1 N = {0, 1is the set of natural numbers and N = NN is the Baire space of all unary functions on N. This carries the natural product topology with N discrete, generated by the basic neighborhoods
and the product spaces Nn x Nm carry the corresponding product topologies.
In general, lower case Latin letters vary over N and Greek letters а, в,... vary over N.
App 2 A partial function f : X ^ Y is a function f : Df ^ Y, where Df с X is the domain of convergence of f. We write
Partial functions compose strictly, e.g.,
It is sometimes convenient to identify f : X ^ Y with its graph
App 3 xA : X ^ N is the characteristic function of A с X (= 1 on A and 0 on Ac = X A).
App 4 Sequence coding in N. The following functions and relations are recursive, with pi the (i + 1)’th prime number:
(u0,...,un-1> = pu0+1 ••• pu-1+1 = the code of (u0,...,un -1);
Seq(u) & u is the code of some sequence, and if it is, then lh(u) is its length and for i < lh(u), (u)i = ui;
u c v & u codes an initial segment of the sequence coded by v; u C v & u c v & u = v;
u | v & u and v are codes of incompatible sequences &^(u C v v v c u); u * v = the code of the concatenation of the sequences coded by u and v; a(t) = (a(0),... ,a(t - 1)> (= 1 if t = 0).
App 5 Kleene’s Normal Form and Enumeration Theorem: Every recursive partial function(al) f : Nn x Nm ^ N is (pn'm for some e, where
with (primitive) recursive Tn and U, and we will skip some or all of the superscripts n, m when they are clear from the context or irrelevant. Moreover, there are (primitive) recursive injections Sln,m (e, y1yl) such that
We call e a code of pne'm and we use both pe and {e} interchangeably, as the desire for neat typography dictates.
To avoid (implausible) confusion, we use [1] for the singleton set whose only member is e.
App 6 Relativization. It is sometimes useful to fix some of the function arguments in the Normal Form Theorem and treat them as parameters. We write
and we say that the partial function (x, a) ^ {e}e (x, a) is recursive in в or relative to в. For recursion relative to a set B, we write
It is often—almost always—the case that a result about (absolutely) recursive partial functions can be easily seen to be true about partial functions recursive in some в, by relativization, i.e., basically adding the superscript в to all functions in the proof; it is a simple but very useful method of proof.
App 7 Recursively enumerable sets. A set A c N is r.e. in B c N if
and (absolutely) r.e. if it is r.e. in the empty set.
App 8 Total recursive functions into N. A (total) function f : Nn x Nm ^ N is recursive if
for some recursive partial f : N1+n x Nm ^ N. Useful examples include the tupling and projection functions:
so that for i < k, ({a0,.ak-1))j = a.
The class of total recursive functions into N or N is closed under composition— which is not true for recursive partial functions with values in N.
App 9 The rank of a strict, well founded relation. A binary relation x on a set F is well founded if there is no infinite descending chain x0 > x1 x ••• or, equivalently, if there is a function p : X ^ Ordinals such that
the (pointwise) least such function px is the rank function of x and
When we apply this to the strict part x of a wellordering x, we get a (unique) similarity
of x with an ordinal.
App 10 Monotone inductive definitions. An operator Ф : P (X) ^ P (X) on the subsets of a space X is monotone if
The set
defined inductively (or built up) by Ф is the least fixed point of Ф, and
(with the usual convention that U 0 = 0). Moreover,
and since these iterates cannot increase forever, there is a least ordinal к = к(Ф), the closure ordinal of Ф such that
An operator Ф is operative on X to W if its domain is P (X x W) and
When this holds, then Ф : X ^ W is (the graph of) the least partial function fixed by the operator Ф.
- [1] t
