Suppose κ is a regular uncountable cardinal, λ is a cardinal > 1, and is a κ-complete uniform ideal on κ. This paper deals with a saturation property Sat(κ, λ, ) of , which is a weakening of usual λ-saturatedness. Roughly speaking, Sat(κ, λ, ) means that can be densely extended to λ-saturated ideals on small fields of subsets of κ. We will show that some consequences of the existence of a λ-saturated ideal on κ follow from weaker ∃: Sat(κ, λ, ), and that ∃: Sat(κ, λ, ) is connected with weak compactness and complete ineffability of κ in much the same way as the existence of a saturated ideal on κ is connected with measurability of κ.

In §2, we define Sat(κ, λ, ), mention a few results that can be proved by straightforward adaptation of known methods, and discuss generic ultrapowers of ZFC−, which will be used repeatedly in the subsequent sections as a main technical tool. A related concept Sat(κ, λ) is also defined and shown to be equivalent to ∃: Sat(κ, λ, ) under a certain condition.

In §3, we show that ∃: Sat(κ, κ, ) implies that κ is highly Mahlo, improving results in [KT] and [So].

The theory of objects recursive in functions of higher types was developed originally by Kleene [Kl 1,2]. The sets of objects of finite types are defined by Kleene as follows:

T0 = ω = the set of nonnegative integers,

and, for all i ∈ ω,

Ti+1 = Tiω = the set of total functions from Ti to ω.

In order to study and classify the functions recursive in Kolmogorov's R-operator, it is necessary to discuss recursion in partial functions of higher types. Accordingly, we define the partial objects of higher finite types by

and, for all i ∈ ω,

= the set of partial functions from Ti to ω.

In addition to considering the partial functions from Ti to ω, the “hereditary partial” functions also have to be considered. For example, Hinman has studied objects of type 2 which act on partial functions from ω to ω. In case of dealing with a function F which has partial functions in its domain, we usually require that F be consistent, i.e. if F(f) is defined and g is an object of the same type as f, defined at least at all points where f is defined (in short, g extends f—notation: g ⊇ f), then F(g) is defined and is equal to F(f). Now we can define the higher type partial objects which are consistent by

and, for all i ∈ ω,

= the set of consistent partial functions from to ω.

The classification of algebraic structures which can be embedded into ℛ, the uppersemilattice of recursively enumerable degrees, is the key to answering certain questions about Th(ℛ), the elementary theory of ℛ. In particular, these classification problems are important for answering decidability questions about fragments of Th(ℛ). Thus the solutions of Fried berg [F] and Mučnik [M] to Post's problem were easily extended to show that all finite partially ordered sets are embeddable into ℛ, and hence that ∃1 ∩ Th(ℛ), the existential theory of ℛ, is decidable. (The language used is ℒ′, the pure predicate calculus together with a binary relation symbol ≤ to be interpreted as the ordering of ℛ) The problem of determining which finite lattices are embeddable into ℛ has been a long-standing open problem, and is one of the major obstacles to determining whether ∀2 ∩ Th(ℛ), the universal-existential theory of ℛ, is decidable. Shore has obtained some nice partial results in this direction. Embeddings also played a central role in showing that Th(ℛ) is not ℵ0-categorical (Lerman, Shore and Soare [LeShSo]), thus resolving a problem posed by Jockusch. Harrington and Shelah [HS] embedded all 0′-presentable partially ordered sets into ℛ in such a way that the partially ordered sets can be uniformly recovered from four parameters. They used these embeddings to show that Th(ℛ) is undecidable.

The first nontrivial extension of the embeddings of Friedberg and Mučnik to lattice embeddings was obtained independently by Lachlan [La1] and Yates [Y] who showed that the four-element Boolean algebra can be embedded into ℛ. Thomason [T] and Lerman independently extended this result to include all finite distributive lattices. The nondistributive case, however, was much more difficult. Lachlan [La2] embedded the two five-element nondistributive lattices M 5 and N 5 (see Figures 1 and 2) into ℛ, and his proof could easily have been extended to include a larger class of lattices.

In [2], Carlson and Simpson proved a dualized version of Ramsey's theorem obtained by coloring partitions of ω instead of subsets of ω. It was at the suggestion of Simpson that the author undertook to study the notion dual to that of a Ramsey ultrafilter. After stating the basic terminology and notation used in the paper in §1, in §2 we establish some basic properties of the lattice of all partitions of a cardinal κ. §3 is devoted to the study of families of pairwise disjoint partitions of ω. §4 is concerned with descending sequences of partitions. In §5, we give some examples of filters of partitions. Properties of such filters are discussed in §6. Co-Ramsey filters are introduced in §7, and it is shown how they can be associated with Ramsey ultrafilters. The main result of §8 is Proposition 8.1, which asserts the existence of a co-Ramsey filter under the continuum hypothesis.

We use standard set theoretic conventions and notation. Let κ be a cardinal. We set κ* = κ − {0}. For every ordinal α ≤ κ, (κ)α denotes the set of those sequences X(ν), ν < α, of pairwise disjoint nonempty subsets of κ such that ⋃ν<αX(ν) = κ, and ⋂X(ν) < ⋂X(ν′) whenever ν < ν′. We also let (κ)≤α = ⋃β≤α(κ)β and (κ)<α = ⋃β<α(κ)β. Given X ∈ (κ)α, we put xν = ⋂X(ν) for every ν < α, and we denote by Ax the set of all xν, 0 < ν < α.

Qλ is the set of nonprincipal filters on ω which are generated by fewer than λ sets, for λ a fixed uncountable, regular cardinal ≤ c. We analyze forcing with Qλ, where Qλ is partially ordered in such a way that a filter F1 is more informative than F2 iff F1 includes F2. Qλ-forcing adjoins an ultrafilter on ω but adds no new reals. We analyze Qλ-forcing from a forcing-theoretic viewpoint. We also analyze the properties of Qλ-generic ultrafilters. These properties are independent of ZFC and depend very much on the ground model. In particular, we study Qλ-forcing over ground models which are Cohen real extensions, random real extensions, and models which satisfy Martin's Axiom.

In §2 we give notations and definitions, and review some of the basic facts about forcing and ultrafilters which we will use. In §3 we introduce Qλ-forcing and prove some basic lemmas about it. §4 studies Qc-forcing. §§5, 6, and 7 analyze Qλ-forcing over ground models of Martin's Axiom, ground models which are generated by Cohen reals, and ground models which are generated by random reals, respectively. Qλ-forcing over Cohen real and random real models is isomorphic to the notion of forcing which adjoins a Cohen generic subset of λ; this is proved in §8.

We give a new characterization of the hyperarithmetic sets: a set X of integers is recursive in e α if and only if there is a Turing machine which computes X and “halts” in less than or equal to the ordinal number ωα of steps. This result represents a generalization of the well-known “limit lemma” due to J. R. Shoenfield [Sho-1] and later independently by H. Putnam [Pu] and independently by E. M. Gold [Go]. As an application of this result, we give a recursion theoretic analysis of clopen determinacy: there is a correlation given between the height α of a well-founded tree corresponding to a clopen game A ⊆ ωω and the Turing degree of a winning strategy ƒ for one of the players—roughly, ƒ can be chosen to be recursive in 0 α and this is the best possible (see §4 for precise results).

Definition. A cardinal κ is strong iff for every x there is an elementary embedding j:V → M with critical point κ such that x ∈ M.

κ is superstrong iff ∃j:V → M with critical point κ such that Vj(κ) ∈ M.

These definitions are natural weakenings of supercompactness and hugeness respectively and display some of the same relations. For example, if κ is superstrong then Vκ ⊨ “∃ proper class of strong cardinals”, but the smallest superstrong cardinal is less than the smallest strong cardinal (if both types exist). (See [SRK] and [Mo] for the arguments involving supercompact and huge, which translate routinely to strong and superstrong.)

Given any two types of large cardinals, a typical vague question which is often asked is “How large is the gap in consistency strength?” In one sense the gap might be considered relatively small, since the “higher degree” strong cardinals described below (a standard trick that is nearly always available) and the Shelah and Woodin hierarchies of cardinals (see [St] for a definition of these) seem to be (at least at this point in time) the only “natural” large cardinal properties lying between strong cardinals and superstrong cardinals in consistency strength.

We will consider Tarski's work in pure model theory and classical logic. His work in applied model theory—the model theory of various special theories—is discussed by Doner and van den Dries [1987], and McNulty [1986]. (However, the separation of “pure” and “applied” only becomes natural as the subjects mature; so we shall discuss applied model theory at least to some extent in Tarski's earlier work.)

Alfred Tarski (1901–1983) was awarded a Ph.D. in mathematics at Warsaw University in 1924. His teachers included the two leaders of the renowned Polish logic school, the logician-philosophers L. Leśniewski and J. Łukasiewicz. (Very soon Tarski was recognized as the third leader of the school.) Another teacher was the philosopher T. Kotarbiński, to whom Tarski dedicated his collected papers [56m]. Leśniewski was Tarski's thesis advisor; he transmitted to Tarski his interests in the metalanguage and in the theory of definition. Tarski's thesis ([23a], [24]) was about protothetic—the sentential calculus augmented by quantifiable variables ranging over truth functions. Its main result was that all the connectives are definable using only ↔ and ∀. By the same year, 1924, Tarski also had begun his prolific writings in set theory, and had discovered together with S. Banach, the leader of the Polish mathematicians, their famous “paradox” [24d] in measure theory. (For details see Lévy [1987].)

In 1927-29 Tarski held a seminar at Warsaw University on results he obtained in 1926-28. The seminar lay at the heart of what is now called model theory. The brief history of model theory up to that time had begun with the paper of L. Löwenheim [1915].

Given an admissible indexing φ of the countable atomless Boolean algebra ℬ, an automorphism F of ℬ is said to be recursively presented (relative to φ) if there exists a recursive function p ϵ Sym(ω) such that F ∘ φ = φ ∘ p. Our key result on recursiveness: Both the subset of Aut(ℬ) consisting of all those automorphisms which are recursively presented relative to some indexing, and its complement, the set of all “totally nonrecursive” automorphisms, are uncountable.

This arises as a consequence of the following combinatorial investigations: (1) A comparison of the cycle structures of ƒ and , where ƒ is a permutation of some free basis of ℬ and is the automorphism of ℬ induced by ƒ.(2) An explicit description of the permutations of ω whose conjugacy classes in Sym(ω) are (a) uncountable, (b) countably infinite, and (c) finite.

Let be any proper ideal of subsets of the real line R which contains all finite subsets of R. We define an ideal * ∣ as follows: X ∈ * ∣ if there exists a Borel set B ⊂ R × R such that X ⊂ B and for any x ∈ R we have {y ∈ R: 〈x, y〉 ∈ B} ∈ . We show that there exists a family ⊂ * ∣ of power ω1 such that ⋃ ∉ * ∣ .

In the last section we investigate properties of ideals of Lebesgue measure zero sets and meager sets in Cohen extensions of models of set theory.

A distinctive feature of modern mathematics is the interaction between its various branches and the blurring of the boundaries between different areas. This is strikingly illustrated in the work of Alfred Tarski. He was a logician first and an algebraist second. His contributions to algebra can be divided into three (ill-defined and overlapping) categories, general algebra, the study of various algebraic structures arising from problems outside algebra, mostly in logic and set theory, and the use of concepts and techniques from logic in the study of algebraic structures. Even more roughly, these three categories could be labeled as pure algebra, applications of algebra to logic, and applications of logic to algebra.

Before Tarski came to the United States in 1939, he had written a series of papers on both the axiomatic and the structural aspects of Boolean algebras, and his inclination to algebraize mathematical problems is well illustrated by his paper [38g], Algebraische Fassung des Massproblems. Many of his later investigations of various types of algebraic structures are inspired by work done in this earlier period. However, beginning around 1940 there is a much greater emphasis on the study of algebra in its various aspects.

The paper [41], On the calculus of relations, is a landmark event in this respect. The object here was to find an axiomatic basis for the arithmetic of binary relations. The axioms that he chose are simple and natural (see Monk [1986]).

Let κ and λ be infinite cardinals such that λ ≤ λ (we have new information for the case when κ ≤ λ). Let T be a theory in Lκ +, ω of cardinality at most κ, let . Now define

Our main concept in this paper is is a theory in Lκ +, ω of cardinality κ at most, and φ(x, y) ϵ Lκ +, ω }. This concept is interesting because of

Theorem 1. Let T ⊆ Lκ +, ω of cardinality ≤ κ, and . If

then (∀χ > κ)I(χ, T) = 2 χ (where I(χ, T) stands for the number of isomorphism types of models of T of cardinality χ).

Many years ago the second author proved that . Here we continue that work by proving

Theorem 2. .

Theorem 3. For every κ ≤ λ we have .

For some κ or λ we have better bounds than in Theorem 3, and this is proved via a new two cardinal theorem.

Theorem 4. For every T ⊆ Lκ +, ω, and any set of formulas ⊆ Lκ +, ω such that T ⊇ Lκ +, ω, if T is (, μ)-unstable for μ satisfying μμ*(λ,κ) = μ then T is -unstable (i.e. for every χ ≥ λ, T is (, χ)-unstable). Moreover, T is Lκ +, ω-unstable.

In the second part of the paper, we show that always in the applications it is possible to replace the function I(χ, T) by the function IE(χ, T), and we give an application of the theorems to Boolean powers.

The concept of "partition relation" has proven to be extremely important in the development of the theory of large cardinals. This is due in good part to the fact that the ordinal numbers which appear as parameters in partition relations provide a natural way to define a detailed hierarchy of the corresponding large cardinal axioms. In particular, the study of cardinals satisfying Ramsey-Erdös-style partition relations has yielded a great number of very interesting large cardinal axioms which lie in strength strictly between inaccessibility and measurability. It is the purpose of this paper to show that this phenomenon does not occur if we use infinite exponent partition relations; no such partition relation has consistency strength strictly between inaccessibility and measurability. We also give a complete determination of which infinite exponent partition relations hold, assuming that there is no inner model of set theory with a measurable cardinal.

Our notation is standard. If F is a function and x is a set, then F″x denotes the range of F on x. If X is a set of ordinals and α is an ordinal, then [X]α is the collection of all subsets of X of order type α. We identify a member of [X]α with a strictly increasing function from α to X. If p ∈ [X]α and q ∈ [α]β, then the composition of p with q, which we denote pq, is a member of [X]β.

It has been considered desirable by many set theorists to find maximality properties which state that the universe has in some sense “many sets”. The properties isolated thus far have tended to be consistent with each other (as far as we know). For example it is a widely held view that the existence of a supercompact cardinal is consistent with the axiom of determinacy holding in L(R). This consistency has been held to be evidence for the truth of these properties. It is with this in mind that the first author suggested the following:

Maximality Principle If P is a partial ordering and G ⊆ P is a V-generic ultrafilter then either

• a) there is a real number r ∈ V [G] with r ∉ V, or

• b) there is an ordinal α such that α is a cardinal in V but not in V[G].

This maximality principle applied to garden variety partial orderings has startling results for the structure of V.

For example, if for some , then P = 〈{p: p ⊆ κ, ∣p∣ < κ}, ⊆〉 neither adds a real nor collapses a cardinal. Thus from the maximality principle we can deduce that the G. C. H. fails everywhere and there are no inaccessible cardinals. (Hence this principle contradicts large cardinals.) Similarly one can show that there are no Suslin trees on any cardinal κ. These consequences help justify the title “maximality principle”.

Since the maximality principle implies that the G. C. H. fails at strong singular limit cardinals it has consistency strength at least that of “many large cardinals”. (See [M].) On the other hand it is not known to be consistent, relative to any assumptions.

Suppose T is superstable. Let ≤ denote the fundamental order on complete types, [p] the class of the bound of p, and U(—) Lascar's foundation rank (see [LP]). We prove

Theorem 1. If q < p and there is no r such that q < r < p, then U(q) + 1 = U(p).

Theorem 2. Suppose U(p) < ω and ξ1 < … < ξk is a maximal descending chain in the fundamental order with ξk = [p]. Then k = U(p).

That the finiteness of U(p) in Theorem 2 is necessary follows from

Theorem 3. There is an ω-stable theory with a type p ϵ S 1(ϕ) such that

(1) U(p) = ω + 1, and

(2) there is a maximal descending chain of proper extensions of [p] which has order type ω.

Alfred Tarski identified decidability within various logical formalisms as one of the principal themes for investigation in mathematical logic. This is evident already in the focus of the seminar he organized in Warsaw in 1926. Over the ensuing fifty-five years, Tarski put forth a steady stream of theorems concerning decidability, many with far-reaching consequences. Just as the work of the 1926 seminar reflected Tarski's profound early interest in decidability, so does his last work, A formalization of set theory without variables, a monograph written in collaboration with S. Givant [8−m]. An account of the Warsaw seminar can be found in Vaught [1986].

Tarski's work on decidability falls into four broad areas: elementary theories which are decidable, elementary theories which are undecidable, the undecidability of theories of various restricted kinds, and what might be called decision problems of the second degree. An account of Tarski's work with decidable elementary theories can be found in Doner and van den Dries [1987] and in Monk [1986] (for Boolean algebras). Vaught [1986] discusses Tarski's contributions to the method of quantifier elimination. Our principal concern here is Tarski's work in the remaining three areas.

We will say that a set of elementary sentences is a theory provided it is closed with respect to logical consequence and we will say that a theory is decidable or undecidable depending on whether it is a recursive or nonrecursive set. The notion of a theory may be restricted in a number of interesting ways. For example, an equational theory is just the set of all universal sentences, belonging to some elementary theory, whose quantifier-free parts are equations between terms.

Quoi qu'en pensent certains, la déviation de Saharon Shelah n'est pas qu'une construction technique servant à un résultat plus technique encore, le théorème de classification; c'est la notion de dépendance la plus générale qui soit apparue dans un contexte mathématique, si bien que toute propriété qu'on pourra attribuer à cette déviation sera, dans le fond, une propriété de la notion même de corrélation.

L'auteur de ces lignes a trouvé la vie beaucoup plus plaisante quand il a pu lire la déviation, associée à une théorie stable T, dans un ordre qu'il était facile de définir sur les types complets au-dessus des modèles de T; s'il a qualifié cet ordre de “fondamental”, ce n'est pas pour donner une emphase hors de propos à sa modeste contribution au démélage de l'échevau shelahien, mais parce que le rang U de Lascar n'était autre que le rang de fondation de l'ordre fondamental.

L'ordre fondamental condense l'essentiel de la déviation, sous une forme pour ainsi dire graphique; certes, tout ne peut s'y retrouver, et en particulier des théories peuvent avoir des ordres fondamentaux semblables si on se limite aux 1-types, et fort différents si on regarde aussi les bitypes; mais il est clair que dès qu'apparait l'ordre fondamental se pose de façon urgente le problème de décrire tous les ordres qui peuvent être ordre fondamental d'une théorie stable: tant que ce programme n'est pas rempli, il reste des propriétés cachées de la déviation.