Abstract Theorems of hyperarithmetic analysis (THAs) occupy an unusual neighborhood in the realms of reverse mathematics and recursion theoretic complexity. They lie above all the fixed (recursive) iterations of the Turing Jump but below ATR $_{0}$ (and so $\Pi _{1}^{1}$ -CA $_{0}$ or the hyperjump). There is a long history of proof theoretic principles which are THAs. Until Barnes, Goh, and Shore [ta] revealed an array of theorems in graph theory living in this neighborhood, there was only one mathematical denizen. In this paper we introduce a new neighborhood of theorems which are almost theorems of hyperarithmetic analysis (ATHAs). When combined with ACA $_{0}$ they are THAs but on their own they are very weak. We generalize several conservativity classes ( $\Pi _{1}^{1}$ , r- $\Pi _{2}^{1}$ , and Tanaka) and show that all our examples (and many others) are conservative over RCA $_{0}$ in all these senses and weak in other recursion theoretic ways as well. We provide denizens, both mathematical and logical. These results answer a question raised by Hirschfeldt and reported in Montalbán [2011] by providing a long list of pairs of principles one of which is very weak over RCA $_{0}$ but over ACA $_{0}$ is equivalent to the other which may be strong (THA) or very strong going up a standard hierarchy and at the end being stronger than full second order arithmetic.

Abstract We extend the usual language of second order arithmetic to one in which we can discuss an ultrafilter over of the sets of a given model. The semantics are based on fixing a subclass of the sets in a structure for the basic language that corresponds to the intended ultrafilter. In this language we state axioms that express the notion that the subclass is an ultrafilter and additional ones that say it is idempotent or Ramsey. The axioms for idempotent ultrafilters prove, for example, Hindman’s theorem and its generalizations such as the Galvin--Glazer theorem and iterated versions of these theorems (IHT and IGG). We prove that adding these axioms to IHT produce conservative extensions of ACA0+IHT, ${\rm{ACA}}_{\rm{0}}^ +$ , ATR0, ${\rm{\Pi }}_2^1$ -CA0, and ${\rm{\Pi }}_2^1$ -CA0for all sentences of second order arithmetic and for full Z2for the class of ${\rm{\Pi }}_4^1$ sentences. We also generalize and strengthen a metamathematical result of Wang (1984) to show, for example, that any ${\rm{\Pi }}_2^1$ theorem ∀X∃YΘ(X,Y) provable in ACA0or ${\rm{ACA}}_{\rm{0}}^ +$ there aree,k∈ ℕ such that ACA0or ${\rm{ACA}}_{\rm{0}}^ +$ proves that ∀X(Θ(X, Φe(J(k)(X))) where Φeis theeth Turing reduction andJ(k)is thekth iterate of the Turing or Arithmetic jump, respectively. (A similar result is derived for ${\rm{\Pi }}_3^1$ theorems of ${\rm{\Pi }}_1^1$ -CA0and the hyperjump.)

Abstract If X0and X1are both generic, the theories of the degrees below X0and X1are the same. The same is true if both are random. We show that then-genericity orn-randomness of X do not suffice to guarantee that the degrees below X have these common theories. We also show that these two theories (for generics and randoms) are different. These results answer questions of Jockusch as well as Barmpalias, Day and Lewis.

Abstract We study low level nondefinability in the Turing degrees. We prove a variety of results, including, for example, that being array nonrecursive is not definable by a Σ1 or Π1 formula in the language (≤, REA) where REA stands for the “r.e. in and above” predicate. In contrast, this property is definable by a Π2 formula in this language. We also show that the Σ1-theory of ( , ≤, REA) is decidable.

Abstract We present some abstract theorems showing how domination properties equivalent to being or array nonrecursive can be used to construct sets generic for different notions of forcing. These theorems are then applied to give simple proofs of some known results. We also give a direct uniform proof of a recent result of Ambos-Spies, Ding, Wang, and Yu [2009] that every degree above any in is recursively enumerable in a 1-generic degree strictly below it. Our major new result is that every array nonrecursive degree is r.e. in some degree strictly below it. Our analysis of array nonrecursiveness and construction of generic sequences below ANR degrees also reveal a new level of uniformity in these types of results.

Abstract We affirm a conjecture of Sacks [1972] by showing that every countable distributive lattice is isomorphic to an initial segment of the hyperdegrees, . In fact, we prove that every sublattice of any hyperarithmetic lattice (and so, in particular, every countable, locally finite lattice) is isomorphic to an initial segment of . Corollaries include the decidability of the two quantifier theory of , and the undecidability of its three quantifier theory. The key tool in the proof is a new lattice representation theorem that provides a notion of forcing for which we can prove a version of the fusion lemma in the hyperarithmetic setting and so the preservation of ω1ck. Somewhat surprisingly, the set theoretic analog of this forcing does not preserve ω1. On the other hand, we construct countable lattices that are not isomorphic to any initial segment of .

Abstract To each computable enumerable (c.e.) setAwith a particular enumeration {As}s∈ωthere is associated a settling functionmA(x), wheremA(x) is the last stage when a number less than or equal toxwas enumerated intoA. One c.e. setAis settling time dominated by another setB(B>stA) if for every computable functionf, for all but finitely manyx, mB(x) >f(mA(x)). This settling-time ordering, which is a natural extension to an ordering of the idea of domination, was first introduced by Nabutovsky and Weinberger in [3] and Soare [6]. They desired a sequence of sets descending in this relationship to give results in differential geometry. In this paper we examine properties of the <stordering. We show that it is not invariant under computable isomorphism, that any countable partial ordering embeds into it. that there are maximal and minimal sets, and that two c.e. sets need not have an inf or sup in the ordering. We also examine a related ordering, the strong settling-time ordering where we require for all computablefandg, for almost allx, mB(x) >f(mA(g(x))).

Abstract We investigate the complexity of various combinatorial theorems about linear and partial orders, from the points of view of computability theory and reverse mathematics. We focus in particular on the principles ADS (Ascending or Descending Sequence), which states that every infinite linear order has either an infinite descending sequence or an infinite ascending sequence, and CAC (Chain-AntiChain), which states that every infinite partial order has either an infinite chain or an infinite antichain. It is wellknown that Ramsey's Theorem for pairs ( ) splits into a stable version ( ) and a cohesive principle (COH). We show that the same is true of ADS and CAC, and that in their cases the stable versions are strictly weaker than the full ones (which is not known to be the case for and ). We also analyze the relationships between these principles and other systems and principles previously studied by reverse mathematics, such as WKL0, DNR, and BΣ2. We show, for instance, that WKL0 is incomparable with all of the systems we study. We also prove computability-theoretic and conservation results for them. Among these results are a strengthening of the fact, proved by Cholak, Jockusch, and Slaman, that COH is -conservative over the base system RCA0. We also prove that CAC does not imply DNR which, combined with a recent result of Hirschfeldt, Jockusch. Kjos-Hanssen, Lempp, and Slaman, shows that CAC does not imply (and so does not imply ). This answers a question of Cholak, Jockusch, and Slaman. Our proofs suggest that the essential distinction between ADS and CAC on the one hand and on the other is that the colorings needed for our analysis are in some way transitive. We formalize this intuition as the notions of transitive and semitransitive colorings and show that the existence of homogeneous sets for such colorings is equivalent to ADS and CAC, respectively. We finish with several open questions.

When bounds on complexity of some aspect of a structure are preserved under isomorphism, we refer to them as intrinsic. Here, building on work of Soskov [34], [33], we give syntactical conditions necessary and sufficient for a relation to be intrinsically on a structure. We consider some examples of computable structures and intrinsically relations R. We also consider a general family of examples of intrinsically relations arising in computable structures of maximum Scott rank. For three of the examples, the maximal well-ordered initial segment in a Harrison ordering, the superatomic part of a Harrison Boolean algebra, and the height-possessing part of a Harrison p-group, we show that the Turing degrees of images of the relation in computable copies of the structure are the same as the Turing degrees of paths through Kleene's . With this as motivation, we investigate the possible degrees of these paths. We show that there is a path in which ∅′ is not computable. In fact, there is one in which no noncomputable hyperarithmetical set is computable. There are paths that are Turing incomparable, or Turing incomparable over a given hyperarithmetical set. There is a pair of paths whose degrees form a minimal pair. However, there is no path of minimal degree.

Abstract. We show that if d ∈ GH1 then (≤ d) has the complementation property, i.e., for all a < d there is some b < d such that a ∧ b = 0 and a ∨ b = d.

Abstract Given two incomparable c.e. Turing degrees a and b, we show that there exists a c.e. degree c such that c = (a ∪ c) ∩ (b ∪ c), a ∪ c ∣ b ∪ c, and c < a ∪ b.

Abstract Cholak, Goncharov, Khoussainov, and Shore [1] showed that for each k > 0 there is a computably categorical structure whose expansion by a constant has computable dimension k. We show that the same is true with k replaced by ω. Our proof uses a version of Goncharov's method of left and right operations.

Complete axiomatizations and exponential-time decision procedures are provided for reasoning about knowledge and common knowledge when there are infinitely many agents. The results show that reasoning about knowledge and common knowledge with infinitely many agents is no harder than when there are finitely many agents, provided that we can check the cardinality of certain set differences G G' where G and G' are sets of agents. Since our complexity results are independent of the cardinality of the sets G involved, they represent improvements over the previous results even with the sets of agents involved are finite. Moreover, our results make clear the extent to which issues of complexity and completeness depend on how the sets of agents involved are represented.

Effective model theory is the subject that analyzes the typical notions and results of model theory to determine their effective content and counterparts. The subject has been developed both in the former Soviet Union and in the west with various names (recursive model theory, constructive model theory, etc.) and divergent terminology. (We use “effective model theory” as the most general and descriptive designation. Harizanov [6] is an excellent introduction to the subject as is Millar [13].) The basic subjects of model theory include languages, structures, theories, models and various types of maps between these objects. There are many ways to introduce considerations of effectiveness into the area. The two most prominent derive from starting, on the one hand, with the notion of a theory and its models or, on the other, with just structures. If one begins with theories, then a natural version of effectiveness is to consider decidable theories (i.e., ones with a decidable (equivalently, computable or recursive) set of theorems). When one moves to models and wants them to be effective, one might start with the requirement that the model (of any theory) have a decidable theory (i.e., Th ( ), the set of sentences true in , is decidable). Typically, however, one wants to be able to talk about the elements of the model as well as its theory in the given language. Thus one naturally considers the model as a structure for the language expanded by adding a constant ai, for each element ai of . Of course, one requires that the mapping from the constants to the corresponding elements of be effective (computable). We are thus lead to the following basic definition: A structure or model is decidable if there is a computable enumeration ai of A, the domain of , such that Th( , ai,) is decidable. (Of course, ai, is interpreted as ai, for each i Є ω.)

We investigate the relationship of (jumps of) the degrees of splittings of a computably enumerable set and the degree of the set. We prove that there is a high computably enumerable set whose only proper splittings are low2.

The spectrum of a relation R on a computable structure is the set of Turing degrees of the image of R under all isomorphisms between A and any other computable structure B. The relation R is intrinsically computably enumerable (c.e.) if its image under all such isomorphisms is c.e. We prove that any computable partially ordered set is isomorphic to the spectrum of an intrinsically c.e. relation on a computable structure. Moreover, the isomorphism can be constructed in such a way that the image of the minimum element (if it exists) of the partially ordered set is computable. This solves the spectrum problem. The theorem and modifications of its proof produce computably categorical structures whose expansions by finite number of constants are not computably categorical and, indeed, ones whose expansions can have any finite number of computable isomorphism types. They also provide examples of computably categorical structures that remain computably categorical under expansions by constants but have no Scott family.

We provide three new results about interpolating 2-r.e. (i.e. d-r.e.) or 2-REA (recursively enumerable in and above) degrees between given r.e. degrees: Proposition 1.13. If c < h are r.e., c is low and h is high, then there is an a < h which is REA in c but not r.e. Theorem 2.1. For all high r.e. degrees h < g there is a properly d-r.e. degree a such that h < a < g and a is r.e. in h. Theorem 3.1. There is an incomplete nonrecursive r.e. A such that every set REA in A and recursive in 0′ is of r. e. degree. The first proof is a variation on the construction of Soare and Stob (1982). The second combines highness with a modified version of the proof strategy of Cooper et al. (1989). The third theorem is a rather surprising result with a somewhat unusual proof strategy. Its proof is a 0‴ argument that at times moves left in the tree so that the accessible nodes are not linearly ordered at each stage. Thus the construction lacks a true path in the usual sense. Two substitute notions fill this role: The true nodes are the leftmost ones accessible infinitely often; the semitrue nodes are the leftmost ones such that there are infinitely many stages at which some extension is accessible. Another unusual feature of the construction is that it involves using distinct priority orderings to control the interactions of different parts of the construction.

We show that the elementary theory of the recursively enumerable tt-degrees has the same computational complexity as true first-order arithmetic. As auxiliary results, we prove theorems about exact pairs and initial segments in the tt-degrees.

The primary relation studied in recursion theory is that of relative complexity: A set or function A (of natural numbers) is reducible to one B if, given access to information about B, we can compute A. The primary reducibility is that of Turing, A ≤TB, where arbitrary (Turing) machines, φe, can be used; access to information about (the oracle) B is unlimited and the lengths of computations are potentially unbounded. Many other interesting reducibilities result from restricitng one or more of these facets of the procedure. Thus, for example, the strongest notion considered is one-one reducibility on sets: A ≤1B iff there is a one-one recursive (= effective) function f such that x Є A ⇔ f(x) Є B. Many-one (≤m) reducibility simply allows f to be many-one. Other intermediate reducibilities include truth-table (≤tt) and weak truth-table (≤wtt). The latter imposes a recursive bound f(x) on the information about B that can be used to compute A(x). The former also bounds the length of computations by requiring that the computation of A(x) from B halt in at most f(x) many steps. Each such reducibility r defines a notion of degree, degr(A) = {B : A ≤rB ∧ B ≤rA}, and a corresponding structure of the r-degrees ordered by r-reducibility. (We typically denote the degree of A by a.) A major theme in recursion theory has been the investigation of the relation between a set's place in these orderings (the algebraic properties of its degree) and other algorithmic, set-theoretic or definability type notions of complexity. Important examples of such other notions include rates of growth of functions, the types of approximation procedures which converge to the given function or set and the (syntactic) complexity of defining the set (or function) in arithmetic or analysis.

In recent work, Cooper [3, 1990] has extended results of Jockusch and Shore [6, 1984] to show that the Turing jump is definable in the structure given by the Turing degrees and the ordering of Turing reducibility. In his definition of x′ from x, Cooper identifies an order-theoretic property shared by all of the degrees that are recursively enumerable in x and above x. He then shows that x′ is the least upper bound of all the degrees with this property. Thus, the jump of x is identified by comparing the recursively enumerable degrees with other degrees which are not recursively enumerable. Of course, once the jump operator is known to be definable, the relation of jump equivalence x′ = y′ is also known to be a definable relation on x and y. If we consider how much of the global theory of the Turing degrees is sufficient for Cooper's methods, it is immediately clear that his methods can be implemented to show that the jump operator and its weakening to the relation of jump equivalence are definable in any ideal closed under the Turing jump. However, his methods do not localize to , the degrees, or to the recursively enumerable degrees. This paper fits, as do Shore and Slaman [16, 1990] and [17, to appear], within the general project to develop an understanding of the relationship between the local degree-theoretic properties of a recursively enumerable set A and its jump class. For an analysis of the possibility of defining jump equivalence in , consult Shore [15, to appear] who shows that the relation x(3) = y(3) is definable. In this paper, we will restrict our attention to definitions expressed completely in ℛ (Note: All sets and degrees discussed for the remainder of this paper will be recursively enumerable.) Ultimately, one would like to find some degree-theoretic properties definable in terms of the ordering of Turing reducibility and quantifiers over the recursively enumerable degrees that would define the relation of jump equivalence or define one or more of the jump classes Hn = {w∣ wn = 0n+1} or Ln = {w ∣ wn = 0n}. Such a result could very likely then be used as a springboard to other general definability results for the recursively enumerable degrees. It would be especially interesting to know whether every recursively enumerable degree is definable and whether every arithmetical degree-invariant property of the recursively enumerable sets is definable in .

Abstract We show that the partial order of -sets under inclusion is elementarily definable with parameters in the semilattice of r.e. wtt-degrees. Using a result of E. Herrmann, we can deduce that this semilattice has an undecidable theory, thereby solving an open problem of P. Odifreddi.

Ambos-Spies (1984a) showed that the two basic nondistributive lattices can be embedded in Rp-T, the polynomial-time Turing degrees of the recursive sets. We introduce more general techniques to extend his results to show that every recursive lattice can be embedded in Rp-T. In addition to lattice-theoretic representation theorems, we use the scheme of priority style arguments coupled with “looking back” techniques presented in Shinoda and Slaman (1988, 1990). We also generalize the density type results of Ladner (1975) and many others to settle the full extension of the embedding problem for Rp-T. Combined with the logical analysis of sentences with one alternation of quantifiers (Shore 1978, Lerman 1983), these results suffice to decide the full ∀∃-theory of Rp-T. They also give a strong nonhomogeneity result: the p-time degrees of the sets recursive in (and, if desired, p-time above) two distinct sets A and B are almost never isomorphic. The situation for the p-time many-one degrees is quite different. We decide the extension of the embedding problem (differently than for Rp-T) but not the ∀∃-theory.

A notion of reducibility ≤r between sets is specified by giving a set of procedures for computing one set from another. We say that a set A is r-reducible to a set B, A ≤rB, if one of the procedures applied to B gives A. Associated with any such reducibility notion is the structure of r-degrees, the equivalence classes of sets with respect to this reducibility, with the induced ordering. The most general notion of a computable reducibility is that of Turing, ≤T. Here we say that A ≤TB if there is a Turing machine φe which, when equipped with an oracle for B, computes A: φeB = A. Such Turing degree computations are characterized by the phenomenon that only during the computation itself do we discover which questions about B need to be answered to compute A(x). In contrast, for nearly all other computable reducibilities the set of questions needed is given in advance by a recursive procedure. Perhaps the most common example of such a procedure is many-one reducibility, ≤m: A ≤mB if there is a recursive function f such that x ∈ A ⇔ f(x) ∈ B. Reducibilities with the property that the output, A(x), is determined by the answers that B gives to a set of questions calculated recursively from x are said to be of tabular type. The most general tabular reducibility is called truth-table reducibility, ≤tt. The procedures [e] associated with this reducibility are specified by a recursive function f (= {e}) which, for each x, gives a set of n questions about the oracle and, for each of the possible 2n sets of answers, gives the corresponding output. As usual this defines A ≤ttB as “there is an e such that [e]B = A”. It is with this notion of reducibility and the associated tt-degrees that we shall be concerned in this paper. Basic information on several such strong reducibilities can be found in Rogers [28]. For more information we recommend the survey articles by Odifreddi [25] and Degtev [2] as well as Odifreddi's book [26].

In this paper we introduce a new hierarchy of sets and operators which we call the REA hierarchy for “recursively enumerable in and above”. The hierarchy is generated by composing (possibly) transfinite sequences of the pseudo-jump operators considered in Jockusch and Shore [1983]. We there studied pseudo-jump operators defined by analogy with the Turing jump as ones taking a set A to A ⊕ for some index e. We would now call these 1-REA operators and will extend them to α-REA operators for recursive ordinals α in analogy with the iterated Turing jump operators (A → A(α) for α < and Kleene's hyperarithmetic hierarchy. The REA sets will then, of course, be the results of applying these operators to the empty set. They will extend and generalize Kleene's H sets but will still be contained in the class of set singletons thus providing us with a new richer subclass of the set singletons which, as we shall see, is related to the work of Harrington [1975] and [1976] on the problems of Friedman [1975] about the arithmetic degrees of such singletons. Their degrees also give a natural class extending the class H of Jockusch and McLaughlin [1969] by closing it off under transfinite iterations as well as the inclusion of [d, d′] for each degree d in the class. The reason for the class being closed under this last operation is that the REA operators include all operators and so give a new hierarchy for them as well as the sets. This hierarchy also turns out to be related to the difference hierarchy of Ershov [1968], [1968a] and [1970]: every α-r.e. set is α-REA but each level of the REA hierarchy after the first extends all the way through the difference hierarchy although never entirely encompassing even the next level of the difference hierarchy.

Relativization—the principle that says one can carry over proofs and theorems about partial recursive functions and Turing degrees to functions partial recursive in any given set A and the Turing degrees of sets in which A is recursive—is a pervasive phenomenon in recursion theory. It led H. Rogers, Jr. [15] to ask if, for every degree d, (≥ d), the partial ordering of Turing degrees above d, is isomorphic to all the degrees . We showed in Shore [17] that this homogeneity conjecture is false. More specifically we proved that if, for some n, the degree of Kleene's (the complete set) is recursive in d(n) then ≇ (≤ d). The key ingredient of the proof was a new version of a result from Nerode and Shore [13] (hereafter NS I) that any isomorphism φ: → (≥ d) must be the identity on some cone, i.e., there is an a called the base of the cone such that b ≥ a ⇒ φ(b) = b. This result was combined with information about minimal covers from Jockusch and Soare [8] and Harrington and Kechris [3] to derive a contradiction from the existence of such an isomorphism if deg( ) ≤ d(n).

Early work combining recursion theory and algebra had (at least) two different sets of motivations. First the precise setting of recursion theory offered a chance to make formal classical concerns as to the effective or algorithmic nature of algebraic constructions. As an added benefit the formalization gives one the opportunity of proving that certain constructions cannot be done effectively even when the original data is presented in a recursive way. One important example of this sort of approach is the work of Frohlich and Shepardson [1955] in field theory. Another motivation for the introduction of recursion theory to algebra is given by Rabin [1960]. One hopes to mathematically enrich algebra by the additional structure provided by the notion of computability much as topological structure enriches group theory. Another example of this sort is provided in Dekker [1969] and [1971] where the added structure is that of recursive equivalence types. (This particular structural view culminates in the monograph of Crossley and Nerode [1974].) More recently there is the work of Metakides and Nerode [1975], [1977] which combines both approaches. Thus, for example, working with vector spaces they show in a very strong way that one cannot always effectively extend a given (even recursive) independent set to a basis for a (recursive) vector space.

Ever since Post [4] the structure of recursively enumerable sets and their classification has been an important area in recursion theory. It is also intimately connected with the study of the lattices and of r.e. sets and r.e. sets modulo finite sets respectively. (This lattice theoretic viewpoint was introduced by Myhill [3].) Key roles in both areas have been played by the lattice of r.e. supersets, , of an r.e. set A (along with the corresponding modulo finite sets) and more recently by the group of automorphisms of and . Thus for example we have Lachlan's deep result [1] that Post's notion of A being hyperhypersimple is equivalent to (or ) being a Boolean algebra. Indeed Lachlan even tells us which Boolean algebras appear as —precisely those with Σ3 representations. There are also many other simpler but still illuminating connections between the older typology of r.e. sets and their roles in the lattice . (r-maximal sets for example are just those with completely uncomplemented.) On the other hand, work on automorphisms by Martin and by Soare [8], [9] has shown that most other Post type conditions on r.e. sets such as hypersimplicity or creativeness which are not obviously lattice theoretic are in fact not invariant properties of . In general the program of analyzing and classifying r.e. sets has been directed at the simple sets. Thus the subtypes of simple sets studied abound — between ten and fifteen are mentioned in [5] and there are others — but there seems to be much less known about the nonsimple sets. The typologies introduced for the nonsimple sets begin with Post's notion of creativeness and add on a few variations. (See [5, §8.7] and the related exercises for some examples.) Although there is a classification scheme for r.e. sets along the simple to creative line (see [5, §8.7]) it is admitted to be somewhat artificial and arbitrary. Moreover there does not seem to have been much recent work on the nonsimple sets.

One general program of α-recursion theory is to determine as much as possible of the lattice structure of (α), the lattice of α-r.e. sets under inclusion. It is hoped that structure results will shed some light on whether or not the theory of (α) is decidable with respect to a suitable language for lattice theory. Fix such a language ℒ. Many of the basic results about the lattice structure involve various sorts of simple α-r.e. sets (we use definitions which are definable in ℒ over (α)). It is easy to see that simple sets exist for all admissible α. Chong and Lerman [1] have found some necessary and some sufficient conditions for the existence of hhsimple α-r.e. sets, although a complete determination of these conditions has not yet been made. Lerman and Simpson [9] have obtained some partial results concerning r-maximal α-r.e. sets. Lerman [6] has shown that maximal α-r.e. sets exist iff a is a certain sort of constructibly countable ordinal. Lerman [5] has also investigated the congruence relations, filters, and ideals of (α). Here various sorts of simple sets have also proved to be vital tools. The importance of simple α-r.e. sets to the study of the lattice structure of (α) is hence obvious. Lerman [6, Q22] has posed the following problem: Find an admissible α for which all simple α-r.e. sets have the same 1-type with respect to the language ℒ. The structure of (α) for such an α would be much less complicated than that of (ω). Lerman [7] showed that such an α could not be a regular cardinal of L. We show that there is no such admissible α.

In this paper we will present an application of generalized recursion theory to (noncombinatorial) set theory. More precisely we will combine a priority argument in α-recursion theory with a forcing construction to prove a theorem about the interdefinability of certain subsets of admissible ordinals. Our investigation was prompted by G. Sacks and S. Simpson asking [6] if it is obvious that there are, for each Σn-admissible α, Σn (over Lα) subsets of α which are Δn-incomparable. If one understands “B is Δn in C” to mean that there are Σn/Lα reduction procedures which put out B and when one feeds in C, then the answer is an unqualified “yes.” In this sense “Δn in” is a direct generalization of “α-recursive in” (replace Σ1 by Σn in the definition) and so amenable to the methods of [7, §§3, 5]. Indeed one simply chooses a complete Σn−1 set A and mimics the construction of [6] as modified in [7, §5] to produce two α-A-r.e. sets B and C neither of which is α-A-recursive in the other. By the remarks on translation [7, §3] this will immediately give the desired result for this definition of “Δn in.” There is, however, the more obvious and natural notion of “Δn in” to be considered: B is Δn in C iff there are Σn and Πn formulas of ⟨Lα, C⟩ which define B.

Although there are many characterizations of weakly compact cardinals (e.g. in terms of indescnbability and tree properties as well as compactness) the most interesting set-theoretic (combinatorial) one is in terms of partition relations. To be more precise we define for κ and α cardinals and n an integer the partition relation of Erdös, Hajnal and Rado [2] as follows: For every function F: [κ]n→ α (called a partition of [κ]n, the n-element subsets of κ, into α pieces), there exists a set C⊆ κ (called homogeneous for F) such that card C = κ and F″[C]n≠ α, i.e. some element of the range is omitted when F is restricted to the n-element subsets of C. It is the simplest (nontrivial) of these relations, i.e. , that is the well-known equivalent of weak compactness.1 Two directions of inquiry immediately suggest themselves when weak compactness is described in terms of these partition relations: (a) Trying to strengthen the relation by increasing the superscript—e.g., —and (b) trying to weaken the relation by increasing the subscript—e.g., . As it turns out, the strengthening to is only illusory for using the equivalence of to the tree property one quickly sees that implies (and so is equivalent to) for every n. Thus is the strongest of these partition relations. The second question seems much more difficult.

A significant portion of the study of large cardinals in set theory centers around the concept of “partition relation”. To best capture the basic idea here, we introduce the following notation: for x and y sets, κ an infinite cardinal, and γ an ordinal less than κ, we let [x]γ denote the collection of subsets of x of order-type γ and abbreviate with the partition relation for each function F from into y there exists a subset C of κ of cardinality κ such that (such that for each α < γ) the range of F on [С]γ ([С]α) has cardinality 1. Now although each infinite cardinal κ satisfies the relation for each n and m in ω (F. P. Ramsey [8]), a connection with large cardinals arises when one asks, “For which uncountable κ do we have κ → (κ)2?” Indeed, any uncountable cardinal κ which satisfies κ → (κ)2 is strongly inaccessible and weakly compact (see [9]). As another example one can look at the improvements of Scott's original result to the effect that if there exists a measurable cardinal then there exists a nonconstructible set. Indeed, if κ is a measurable cardinal then κ → (κ)< ω, and as Solovay [11] has shown, if there exists a cardinal κ such that κ → (κ)< ω3 (κ → (ℵ1)< ω, even) then there exists a nonconstructible set of integers.