4
1. INTRODUCTION
the 1-3-1 lattice, the one of the two basic nondistributive lattices which includes
a critical triple, is embeddable in the r.e. degrees. We show that this construction
uses finiteness in an essential way; it can only be performed in the a-v.e. degrees
(here a is any admissible ordinal) if a is countable in some effective sense. All of
the work taken together shows that no lZa is elementarily equivalent to 1Z.
Notation and Terminology. Rather than give a long list of definitions of the
concepts used in this work and of the notation associate with them, we prefer to
place each definition in its natural context as it comes up in the work. Many of these
definitions make sense only together with facts concerning the objects involved; in
the appendices we develop much of the theory which is needed to make most of the
definitions comprehensible.
The basics of admissible recursion theory are developed in appendix A. It is
there where we define our "playing ground", namely Jensen's Ja hierarchy, describe
the notions of amenability and admissibility, discuss a-recursive enumerations and
ce-reductions, and in that context it makes sense to define nice functionals, which
are not used in the standard texts of the field (Sacks [Sac90] and Chong [Cho84].)
We also define there effective versions of cofinality, such as the S
n
cofinality of a
and the recursive cofinality of a degree.
Further notions of a-recursion theory include the jump operator (and the notion
of lowness which accompanies it), described in appendix B, and the projectum £™,
which is discussed in appendix C.
Notions from classical recursion theory, often more algebraic in nature (such as
the lattices we try to embed in the degrees, or the coding of models of arithmetic
in the degrees), are defined in the body of the text as they appear.
The notation used follows modern set-theoretic standards (see, for example,
Jech [Jec03]). Thus for example we use f"X to denote the pointwise image of X
under the function / . C means inclusion, whether proper or not (when we want to
stress proper inclusion we will use C). Club means closed and unbounded (usually
in the fixed admissible ordinal a).
For recursion theory we use the functional notation which has become standard
in recent years. The meaning of this notation in the context of admissible recursion
theory is explained in appendix A. During effective constructions or enumerations
we use Lachlan's notation ([Lac79]) of modifying objects and whole expressions
by [s] to denote they are viewed in stage s of the construction or enumeration. In
general notation will be similar to the one used in [Soa87, XIV s.4].
1. The Results
In this thesis we show how the proximity of an admissible ordinal a to u is
reflected in the structure of the a-recursively enumerable degrees (which we denote
by Ka).
1.1. Lattice Embeddings.
THEOREM
1.1. There is a sentence ip (in the language of partially ordered sets)
such that for every admissible ordinal a, 7Za \= ip iff
Q2a
= w and cfs2(jQ)(a) = UJ.
The sentence ip states the existence of an embedding of the 1-3-1 lattice (also
known as M5; see [Soa87, IX 2.7] and figure 6.1) into 1Z& with an incomplete top.
The class of ordinals a such that lZa (= ip is exactly the class of admissible ordinals
Previous Page Next Page