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