We show that in the model obtained by iteratively pseudo-intersecting a Ramsey ultrafilter via a length- ω 2 countable support iteration of restricted Mathias forcing over a ground model satisfying CH , there is a unique Q -point up to isomorphism. In particular, it is consistent that there is only one Q -point while there are 2 c -many near-coherence classes of ultrafilters.

We expand the results of Rosłanowski and Shelah [11] , [10] to all perfect Abelian Polish groups ( H , + ) . In particular, we show that if α < ω 1 and 4 ≤ k < ω , then there is a ccc forcing notion adding a Σ 2 0 set B ⊆ H which has ℵ α many pairwise k –overlapping translations but not a perfect set of such translations. The technicalities of the forcing construction led us to investigations of the question when, in an Abelian group, X − X ⊆ Y − Y imply that a translation of X or − X is included in Y .

Abstract We construct a Borel maximal cofinitary group.

Abstract We answer a question of Usuba by showing that the combinatorial principle $\mathrm {UB}_\lambda $ can fail at a singular cardinal. Furthermore, $\lambda $ can be taken to be $\aleph _\omega .$

Abstract There is a Turing functional $\Phi $ taking $A^\prime $ to a theory $T_A$ whose complexity is exactly that of the jump of A, and which has the property that $A \leq _T B$ if and only if $T_A \trianglelefteq T_B$ in Keisler’s order. In fact, by more elaborate means and related theories, we may keep the complexity at the level of A without using the jump.

For a set $M$, $\operatorname{fin}(M)$ denotes the set of all finite subsets of $M$, $M^2$ denotes the Cartesian product $M\times M$, $[M]^2$ denotes the set of all $2$-element subsets of $M$, and $\operatorname{seq}^{1-1}(M)$ denotes the set of all finite sequences without repetition which can be formed with elements of $M$. Furthermore, for a set $S$, let $|S|$ denote the cardinality of $S$. Under the assumption that the four cardinalities $|[M]^2|$, $|M^2|$, $|\operatorname{fin}(M)|$, $|\operatorname{seq}^{1-1}(M)|$ are pairwise distinct and pairwise comparable in ZF, there are six possible linear orderings between these four cardinalities. We show that at least five of the six possible linear orderings are consistent with ZF.

Abstract A permutation group G on a set A is ${\kappa }$ -homogeneous iff for all $X,Y\in \bigl [ {A} \bigr ]^ {\kappa } $ with $|A\setminus X|=|A\setminus Y|=|A|$ there is a $g\in G$ with $g[X]=Y$ . G is ${\kappa }$ -transitive iff for any injective function f with $\operatorname {dom}(f)\cup \operatorname {ran}(f)\in \bigl [ {A} \bigr ]^ {\le {\kappa }} $ and $|A\setminus \operatorname {dom}(f)|=|A\setminus \operatorname {ran}(f)|=|A|$ there is a $g\in G$ with $f\subset g$ . Giving a partial answer to a question of P. M. Neumann [6] we show that there is an ${\omega }$ -homogeneous but not ${\omega }$ -transitive permutation group on a cardinal ${\lambda }$ provided (i) ${\lambda }<{\omega }_{\omega }$ , or (ii) $2^{\omega }<{\lambda }$ , and ${\mu }^{\omega }={\mu }^+$ and $\Box _{\mu }$ hold for each ${\mu }\le {\lambda }$ with ${\omega }=\operatorname {cf}({\mu })<{{\mu }}$ , or (iii) our model was obtained by adding $(2^{\omega })^+$ many Cohen generic reals to some ground model. For ${\kappa }>{\omega }$ we give a method to construct large ${\kappa }$ -homogeneous, but not ${\kappa }$ -transitive permutation groups. Using this method we show that there exist ${\kappa }^+$ -homogeneous, but not ${\kappa }^+$ -transitive permutation groups on ${\kappa }^{+n}$ for each infinite cardinal ${\kappa }$ and natural number $n\ge 1$ provided $V=L$ .

We study the set sp(i)={|A|:A⊆[ω]ω is a maximal independent family}, referred to as the spectrum of independence. We develop a forcing notion, which allows us to adjoin a maximal independent family of arbitrary cardinality, and so in particular of cardinality ℵω. Moreover, given an arbitrary set Θ of uncountable cardinals, our techniques allow to obtain a cardinal preserving generic extension in which Θ⊆sp(i), thus showing that sp(i) can be arbitrarily large. For finite Θ, as well as certain countably infinite Θ, we can obtain a precise equality, i.e. models of sp(i)=Θ.

Abstract The notion of a complete type can be generalized in a natural manner to allow assigning a value in an arbitrary Boolean algebra $\mathcal {B}$ to each formula. We show some basic results regarding the effect of the properties of $\mathcal {B}$ on the behavior of such types, and show they are particularity well behaved in the case of NIP theories. In particular, we generalize the third author’s result about counting types, as well as the notion of a smooth type and extending a type to a smooth one. We then show that Keisler measures are tied to certain Boolean types and show that some of the results can thus be transferred to measures—in particular, giving an alternative proof of the fact that every measure in a dependent theory can be extended to a smooth one. We also study the stable case. We consider this paper as an invitation for more research into the topic of Boolean types.

Abstract A wide Aronszajn tree is a tree of size and height $\omega _{1}$ with no uncountable branches. We prove that under $MA(\omega _{1}\!)$ there is no wide Aronszajn tree which is universal under weak embeddings. This solves an open question of Mekler and Väänänen from 1994. We also prove that under $MA(\omega _{1}\!)$ , every wide Aronszajn tree weakly embeds in an Aronszajn tree, which combined with a result of Todorčević from 2007, gives that under $MA(\omega _{1}\!)$ every wide Aronszajn tree embeds into a Lipschitz tree or a coherent tree. We also prove that under $MA(\omega _{1}\!)$ there is no wide Aronszajn tree which weakly embeds all Aronszajn trees, improving the result in the first paragraph as well as a result of Todorčević from 2007 who proved that under $MA(\omega _{1}\!)$ there are no universal Aronszajn trees.

Abstract We show that it is independent whether club $\kappa $ -Miller forcing preserves $\kappa ^{++}$ . We show that under $\kappa ^{<\kappa }> \kappa $ , club $\kappa $ -Miller forcing collapses $\kappa ^{<\kappa }$ to $\kappa $ . Answering a question by Brendle, Brooke-Taylor, Friedman and Montoya, we show that the iteration of ultrafilter $\kappa $ -Miller forcing does not have the Laver property.

Abstract We present three examples of countable homogeneous structures (also called Fraïssé limits ) whose automorphism groups are not universal, namely, fail to contain isomorphic copies of all automorphism groups of their substructures. Our first example is a particular case of a rather general construction on Fraïssé classes, which we call diversification , leading to automorphism groups containing copies of all finite groups. Our second example is a special case of another general construction on Fraïssé classes, the mixed sums , leading to a Fraïssé class with all finite symmetric groups appearing as automorphism groups and at the same time with a torsion-free automorphism group of its Fraïssé limit. Our last example is a Fraïssé class of finite models with arbitrarily large finite abelian automorphism groups, such that the automorphism group of its Fraïssé limit is again torsion-free.

Abstract Our aim is to solve a quite old question on the difference between expandability and compact expandability. Toward this, we further investigate the logic of countable cofinality.

Abstract We continue our study of the class ${\cal C}\left( D \right)$ , where D is a uniform ultrafilter on a cardinal κ and ${\cal C}\left( D \right)$ is the class of all pairs $\left( {{\theta _1},{\theta _2}} \right)$ , where $\left( {{\theta _1},{\theta _2}} \right)$ is the cofinality of a cut in ${J^\kappa }/D$ and J is some ${\left( {{\theta _1} + {\theta _2}} \right)^ + }$ -saturated dense linear order. We give a combinatorial characterization of the class ${\cal C}\left( D \right)$ . We also show that if $\left( {{\theta _1},{\theta _2}} \right) \in {\cal C}\left( D \right)$ and D is ${\aleph _1}$ -complete or ${\theta _1} + {\theta _2} > {2^\kappa }$ , then ${\theta _1} = {\theta _2}$ .

Abstract We show that under Dickson’s conjecture about the distribution of primes in the natural numbers, the theory Th (ℤ , +, 1, 0, Pr) where Pr is a predicate for the prime numbers and their negations is decidable, unstable, and supersimple. This is in contrast with Th (ℤ , +, 0, Pr, <) which is known to be undecidable by the works of Jockusch, Bateman, and Woods.

Abstract We introduce the notion of pseudoalgebraicity to study atomic models of first order theories (equivalently models of a complete sentence of ${L_{{\omega _1},\omega }}$ ). Theorem: Let T be any complete first-order theory in a countable language with an atomic model. If the pseudominimal types are not dense, then there are 2ℵ0 pairwise nonisomorphic atomic models of T, each of size ℵ1.

Abstract Theorem. Suppose that k = (K, $$\prec_k$$ ) is an ℵ0-presentable abstract elementary class with Löwenheim–Skolem number ℵ0, satisfying the joint embedding and amalgamation properties in ℵ0. If K has only countably many models in ℵ1, then all are small. If, in addition, k is almost Galois ω-stable then k is Galois ω-stable. Suppose that k = (K, $$\prec_k$$ ) is an ℵ0-presented almost Galois ω-stable AEC satisfying amalgamation for countable models, and having a model of cardinality ℵ1. The assertion that K is ℵ1-categorical is then absolute.

Abstract The mad spectrum is the set of all cardinalities of infinite maximal almost disjoint families on ω. We treat the problem to characterize those sets ${\rm {\cal A}} $ which, in some forcing extension of the universe, can be the mad spectrum. We give a complete solution to this problem under the assumption $\vartheta ^{ < \vartheta } = \vartheta $ , where $\vartheta = {\rm{min}}\left( {\rm {\cal A}} \right) $ .

Abstract We prove that it is relatively consistent with ZF + CH that there exist two models of cardinality $\aleph _2 $ such that the second player has a winning strategy in the Ehrenfeucht–Fraïssé-game of length ω1 but there is no σ-closed back-and-forth set for the two models. If CH fails, no such pairs of models exist.

Abstract In the first part we show a counterexample to a conjecture by Shelah regarding the existence of indiscernible sequences in dependent theories (up to the first inaccessible cardinal). In the second part we discuss generic pairs, and give an example where the pair is not dependent. Then we define the notion of directionality which deals with counting the number of coheirs of a type and we give examples of the different possibilities. Then we discuss nonsplintering, an interesting notion that appears in the work of Rami Grossberg, Andrés Villaveces and Monica VanDieren, and we show that it is not trivial (in the sense that it can be different than splitting) whenever the directionality of the theory is not small. In the appendix we study dense types in RCF.

Abstract Our results in this paper increase the model-theoretic precision of a widely used method for building ultrafilters, and so advance the general problem of constructing ultrafilters whose ultrapowers have a precise degree of saturation. We begin by showing that any flexible regular ultrafilter makes the product of an unbounded sequence of finite cardinals large, thus saturating any stable theory. We then prove directly that a “bottleneck” in the inductive construction of a regular ultrafilter on λ (i.e., a point after which all antichains of ${\cal P}\left( \lambda \right)/{\cal D}$ have cardinality less than λ) essentially prevents any subsequent ultrafilter from being flexible, thus from saturating any nonlow theory. The constructions are as follows. First, we construct a regular filter ${\cal D}$ on λ so that any ultrafilter extending ${\cal D}$ fails to ${\lambda ^ + }$ -saturate ultrapowers of the random graph, thus of any unstable theory. The proof constructs the omitted random graph type directly. Second, assuming existence of a measurable cardinal κ, we construct a regular ultrafilter on $\lambda > \kappa$ which is λ-flexible but not ${\kappa ^{ + + }}$ -good, improving our previous answer to a question raised in Dow (1985). Third, assuming a weakly compact cardinal κ, we construct an ultrafilter to show that ${\rm{lcf}}\left( {{\aleph _0}} \right)$ may be small while all symmetric cuts of cofinality κ are realized. Thus certain families of precuts may be realized while still failing to saturate any unstable theory.

Abstract We prove that the strong polarized relation is consistent with ZFC, for a singularμwhich is a limit of measurable cardinals.

Abstract We address the following question: Can we expand an NIP theory by adding a linear order such that the expansion is still NIP? Easily, if acl(A)=A for all A, then this is true. Otherwise, we give counterexamples. More precisely, there is a totally categorical theory for which every expansion by a linear order has IP. There is also an ω-stable NDOP theory for which every expansion by a linear order interprets pseudofinite arithmetic.

Abstract We present a method to iterate finitely splitting lim-sup tree forcings along non-wellfounded linear orders. As an application, we introduce a new method to force (weak) measurability of all definable sets with respect to a certain (non-ccc) ideal.

Abstract We prove the statement in the title.

Abstract We construct a model of ZFC satisfying the Dual Borel Conjecture in which there is a set of size ℵ1 that does not have measure zero.

Abstract There is a proper countable support iteration of length ω adding no new reals at finite stages and adding a Sacks real in the limit.

Abstract We study when classes can have the disjoint amalgamation property for a proper initial segment of cardinals. For every natural number k, there is a class Kk, defined by a sentence in Lω1,ω that has no models of cardinality greater than ℶk + 1, but Kk has the disjoint amalgamation property on models of cardinality less than or equal to ℵk − 3 and has models of cardinality ℵk − 1. More strongly, we can have disjoint amalgamation up to ℵ∝ for ∝ < ω1, but have a bound on size of models. For every countable ordinal ∝, there is a class K∝ defined by a sentence in Lω1,ω that has no models of cardinality greater than ℶω1, but K does have the disjoint amalgamation property on models of cardinality less than or equal to ℵ∝. Finally we show that we can extend the ℵ∝ to ℶ∝ in the second theorem consistently with ZFC and while having ℵi ≪ ℶi for 0 < i < ∝. Similar results hold for arbitrary ordinals ∝ with ∣∝∣ = k and Lk + ω.

Abstract In this paper, we investigate the extent to which techniques used in [10], [2], and [3]—developed to prove coloring theorems at successors of singular cardinals of uncountable cofinality—can be extended to cover the countable cofinality case.

Abstract For f, g ∈ ωω let be the minimal number of uniform g-splitting trees (or: Slaloms) to cover the uniform f-splitting tree, i.e., for every branch v of the f-tree, one of the g-trees contains v. is the dual notion: For every branch v, one of the g-trees guesses v(m) infinitely often. It is consistent that for ℵ1 many pairwise different cardinals κ∊ and suitable pairs (f∊, g∊). For the proof we use creatures with sufficient bigness and halving. We show that the lim-inf creature forcing satisfies fusion and pure decision. We introduce decisiveness and use it to construct a variant of the countable support iteration of such forcings, which still satisfies fusion and pure decision.

Abstract We prove Los conjecture = Morley theorem in ZF. with the same characterization, i.e., of first order countable theories categorical in ℵα for some (eqiuvalently for every ordinal) α > 0. Another central result here in this context is: the number of models of a countable first order T of cardinality ℵα is either ≥ ∣α∣ for every α or it has a small upper bound (independent of α close to ⊐2).

Abstract We use κ-free but not Whitehead Abelian groups to construct Abstract Elementary Classes (AEC) which satisfy the amalgamation property but fail various conditions on the locality of Galois-types. We introduce the notion that an AEC admits intersections. We conclude that for AEC which admit intersections, the amalgamation property can have no positive effect on locality: there is a transformation of AEC's which preserves non-locality but takes any AEC which admits intersections to one with amalgamation. More specifically we have: Theorem 5.3. There is an AEC with amalgamation which is not (ℵ0, ℵ1)-tame but is ( , ∞)-tame; Theorem 3.3. It is consistent with ZFC that there is an AEC with amalgamation which is not (≤ ℵ2, ≤ ℵ2)-compact.

Abstract This article is devoted to two different generalizations of projective Boolean algebras: openly generated Boolean algebras and tightly σ-filtered Boolean algebras. We show that for every uncountable regular cardinal κ there are 2κ pairwise non-isomorphic openly generated Boolean algebras of size κ > ℵ1 provided there is an almost free non-free abelian group of size κ. The openly generated Boolean algebras constructed here are almost free. Moreover, for every infinite regular cardinal κ we construct 2κ pairwise non-isomorphic Boolean algebras of size κ that are tightly σ-filtered and c.c.c. These two results contrast nicely with Koppelberg's theorem in [12] that for every uncountable regular cardinal κ there are only 2κ isomorphism types of projective Boolean algebras of size κ.

Abstract We show that many singular cardinals λ above a strongly compact cardinal have regular ultrafilters D that violate the finite square principle introduced in [3]. For such ultrafilters D and cardinals λ there are models of size λ for which Mλ/D is not λ++-universal and elementarily equivalent models M and N of size λ for which Mλ/D and Nλ/D are non-isomorphic. The question of the existence of such ultrafilters and models was raised in [1].

Abstract We consider the notion of bounded m-ary patch-width defined in [9], and its very close relative m-constructibility defined below. We show that the notions of m-constructibility all coincide for m ≥ 3, while 1-constructibility is a weaker notion. The same holds for bounded m-ary patch-width. The case m = 2 is left open.

Abstract Let S be the set of those α ∈ ω2 that have cofinality ω1. It is consistent relative to a measurable that the nonempty player wins the pressing down game of length ω1, but not the Banach-Mazur game of length ω + 1 (both games starting with S).

Abstract Let μ be singular of uncountable cofinality. If μ > 2cf(μ), we prove that in ℙ = ([μ]μ, ⊇) as a forcing notion we have a natural complete embedding of Levy(ℵ0, μ+) (so ℙ collapses μ+to ℵ0) and even Levy ( ). The “natural” means that the forcing ({p∈ [μ] :pclosed}, ⊇) is naturally embedded and is equivalent to the Levy algebra. Also if ℙ fails theχ-c.c. then it collapsesχto ℵ0(and the parallel results for the case μ > ℵ0is regular or of countable cofinality). Moreover we prove: for regular uncountableκ, there is a familyPof κpartitionsĀ= ⟨Aα:α<κ⟩ ofκsuch that for anyA∈ [κ]κfor some ⟨Aα:α<κ⟩ ∈Pwe have α <κ⇒ ∣Aα∩A∣ =κ.

Abstract We show that there is a restriction, or modification of the finite-variable fragments of First Order Logic in which a weak form of Craig's Interpolation Theorem holds but a strong form of this theorem does not hold. Translating these results into Algebraic Logic we obtain a finitely axiomatizable subvariety of finite dimensional Representable Cylindric Algebras that has the Strong Amalgamation Property but does not have the Superamalgamation Property. This settles a conjecture of Pigozzi [12].

Baizhanov and Baldwin [1] introduce the notions of benign and weakly benign sets to investigate the preservation of stability by naming arbitrary subsets of a stable structure. They connect the notion with work of Baldwin, Benedikt, Bouscaren, Casanovas, Poizat, and Ziegler. Stimulated by [1], we investigate here the existence of benign or weakly benign sets. Definition 0.1. (1) The set A is benign in M if for every α, β ∊ M if p = tp(α/A) = tp(β/A) then tp*(α/A) = tp*(β/A) where the *-type is the type in the language L* with a new predicate P denoting A. (2) The set A is weakly benign in M if for every α,β ∊ M if p = stp(α/A) = stp(β/A) then tp*(α/A) = tp*(β/A) where the *-type is the type in language with a new predicate P denoting A. Conjecture 0.2 (too optimistic). If M is a model of stable theory T and A ⊆ M then A is benign. Shelah observed, after learning of the Baizhanov-Baldwin reductions of the problem to equivalence relations, the following counterexample. Lemma 0.3. There is an ω-stable rank 2 theory T with ndop which has a model M and set A such that A is not benign in M.

Abstract We consider a family of finite universes. The second order existential quantifier Qℜ means for each U Є quantifying over a set of n(ℜ)-place relations isomorphic to a given relation. We define a natural partial order on such quantifiers called interpretability. We show that for every Qℜ, either Qℜ is interpretable by quantifying over subsets of U and one to one functions on U both of bounded order, or the logic L(Qℜ) (first order logic plus the quantifier Qℜ) is undecidable.

Abstract We prove that the property “P doesn't make the old reals Lebesgue null” is preserved under countable support iterations of proper forcings, under the additional assumption that the forcings are nep (a generalization of Suslin proper) in an absolute way. We also give some results for general Suslin ccc ideals.

Abstract. For a stationary set S ⊆ ω1, and a ladder system C over S, a new type of gaps called C-Hausdorff is introduced and investigated. We describe a forcing model of ZFC in which, for some stationary set S, for every ladder C over S, every gap contains a subgap that is C-Hausdorff. But for every ladder E over ω1 ∖ S there exists a gap with no subgap that is E-Hausdorff. A new type of chain condition, called polarized chain condition, is introduced. We prove that the iteration with finite support of polarized c.c.c. posets is again a polarized c.c.c. poset.

Abstract We prove, in ZFC, the existence of a definable, countably saturated elementary extension of the reals.

Abstract. The authors show, by means of a finitary version of the combinatorial principle of [7]. the consistency of the failure, relative to the consistency of supercompact cardinals, of the following: for all regular filters D on a cardinal λ. if Mi and Ni are elementarily equivalent models of a language of size ≤ λ, then the second player has a winning strategy in the Ehrenfeucht-Fraïssé game of length λ+ on ΠiMi/D and ΠiNi/D. If in addition 2λ = λ+ and i < λ implies |Mi| + |Ni| ≤ λ+ this means that the ultrapowers are isomorphic. This settles negatively conjecture 18 in [2].

We establish the eventual periodicity of the spectrum of any monadic second-order formula where: (i) all relation symbols, except equality, are unary, and (ii) there is only one function symbol and that symbol is unary.

Abstract We answer a question of Just, Miller, Scheepers and Szeptycki whether certain diagonalization properties for sequences of open covers are provably closed under taking finite or countable unions.

Abstract The paper is concerned with the existence of a universal graph at the successor of a strong limit singular μ of cofinality ℵ0. Starting from the assumption of the existence of a supercompact cardinal, a model is built in which for some such μ there are μ++ graphs on μ+ that taken jointly are universal for the graphs on μ+, while . The paper also addresses the general problem of obtaining a framework for consistency results at the successor of a singular strong limit starting from the assumption that a supercompact cardinal κ exists. The result on the existence of universal graphs is obtained as a specific application of a more general method.

Abstract Any model of ZFC + GCH has a generic extension (made with a poset of size ℵ2) in which the following hold: there exists a -well ordering of the reals, The proof consists in iterating posets designed to change at will the guessing properties of ladder systems on ω1. Therefore, the study of such ladders is a main concern of this article.

Abstract This paper is motivated by the question whether there exists a logic capturing polynomial time computation over unordered structures. We consider several algorithmic problems near the border of the known, logically defined complexity classes contained in polynomial time. We show that fixpoint logic plus counting is stronger than might be expected, in that it can express the existence of a complete matching in a bipartite graph. We revisit the known examples that separate polynomial time from fixpoint plus counting. We show that the examples in a paper of Cai, Fürer, and Immerman, when suitably padded, are in choiceless polynomial time yet not in fixpoint plus counting. Without padding, they remain in polynomial time but appear not to be in choiceless polynomial time plus counting. Similar results hold for the multipede examples of Gurevich and Shelah, except that their final version of multipedes is, in a sense, already suitably padded. Finally, we describe another possible candidate, involving determinants, for the task of separating polynomial time from choiceless polynomial time plus counting.

Abstract Assume (ℵ0, ℵ1) → (λ, λ+). Assume M is a model of a first order theory T of cardinality at most λ+ in a language of cardinality ≤ λ. Let N be a model with the same language. Let Δ be a set of first order formulas in and let D be a regular filter on λ. Then M is Δ-embeddable into the reduced power Nλ/D, provided that every Δ-existential formula true in M is true also in N. We obtain the following corollary: for M as above and D a regular ultrafilter over λ, Mλ/D is λ++-universal. Our second result is as follows: For i < μ let Mi, and Ni, be elementarily equivalent models of a language which has cardinality ≤ λ. Suppose D is a regular filter on λ and (ℵ0, ℵ1) → (λ, λ+) holds. We show that then the second player has a winning strategy in the Ehrenfeucht-Fraïssé game of length λ+ on ΠiMi/D and ΠiNi/D. This yields the following corollary: Assume GCH and λ regular (or just (ℵ0, ℵ1) → (λ, λ+) and 2λ = λ+. For L, Mi and Ni be as above, if D is a regular filter on λ, then ΠiMi/D ≅ ΠiNi/D.

Abstract If T is a model complete theory with the strict order property, then the theory of the models of T with an automorphism has no model companion.

Abstract We prove the consistency result from the title. By forcing we construct a model of g = ℵ1, b = cf(Sym(ω)) = ℵ2.

Abstract It is proved that the following conditions are equivalent: (a) there exists a complete, atomless, σ–centered Boolean algebra, which does not contain any regular, atomless, countable subalgebra. (b) there exists a nowhere dense ultrafilter on ω. Therefore, the existence of such algebras is undecidable in ZFC. In “forcing language” condition (a) says that there exists a non–trivial σ–centered forcing not adding Cohen reals.

Abstract We prove a main gap theorem for locally saturated submodels of a homogeneous structure. We also study the number of locally saturated models, which are not elementarily embeddable into each other.

Abstract The Mycielski ideal is defined to consist of all setsA⊆ℕksuch that {f↾X:f∈A} ≠Xkfor all . It will be shown that the covering numbers for these ideals are all equal. However, the covering numbers of the closely associated Rosłanowski ideals will be shown to be consistently different.

Abstract A fairly quotable special, but still representative, case of our main result is that for 2 ≤ n < ω, there is a natural number m(n) such that, the following holds. Assume GCH: If λ < μ are regular, there is a cofinality preserving forcing extension in which 2λ = μ and, for all σ < λ ≤ κ < η such that η(+m(n)−+) ≤ μ, This generalizes results of [3], Section 1. and the forcing is a “many cardinals” version of the forcing there.

Abstract We address ZFC inequalities between some cardinal invariants of the continuum, which turned out to be true in spite of strong expectations given by [11].

Abstract It is consistent that there is a set mapping from the four-tuples of ωninto the finite subsets with no free subsets of sizetnfor some natural numbertn. For anyn< ω it is consistent that there is a set mapping from the pairs of ωninto the finite subsets with no infinite free sets. For anyn< ω it is consistent that there is a set mapping from the pairs of ωninto ωnwith no uncountable free sets.

This paper grew as a continuation of [Sh462] but in the present form it can serve as a motivation for it as well. We deal with the same notions, all defined in 1.1, and use just one simple lemma from there whose statement and proof we repeat as 2.1. Originally entangledness was introduced, in [BoSh210] for example, in order to get narrow boolean algebras and examples of the nonmultiplicativity of c.c-ness. These applications became marginal when other methods were found and successfully applied (especially Todorčevic walks) but after the pcf constructions which made their début in [Sh-g] and were continued in [Sh462] it seems that this notion gained independence. Generally we aim at characterizing the existence of strong and weak entangled orders in cardinal arithmetic terms. In [Sh462, §6] necessary conditions were shown for strong entangledness which in a previous version was erroneously proved to be equivalent to plain entangledness. In §1 we give a forcing counterexample to this equivalence and in §2 we get those results for entangledness (certainly the most interesting case). A new construction of an entangled order ends this section. In §3 we get weaker results for positively entangledness, especially when supplemented with the existence of a separating point (Definition 2.2). An antipodal case is defined in 3.10 and completely characterized in 3.11. Lastly we outline in 3.12 a forcing example showing that these two subcases of positive entangledness comprise no dichotomy. The work was done during the fall of 1994 and the winter of 1995. The second author proved Theorems 1.2, 2.14, the result that is mentioned in Remark 2.11 and what appears in this version as Theorem 2.10(a) with the further assumptionden(I)θ< μ. The first author is responsible for waving off this assumption (actually by showing that it holds in the general case), for Theorems 2.12 and 2.13 in Section 2 and for the work which is presented in Section 3.

Abstract We prove for any μ = μ<μ < θ < λ. λ large enough (just strongly inaccessible Mahlo) the consistency of and even for σ < μ. The new point is that possibly 0 > μ+.

Abstract We consider a finite universe (more exactly—a family of them), second order quantifiers QK, where for each this means quantifying over a family of n(K)-place relations closed under permuting . We define some natural orders and shed some light on the classification problem of those quantifiers.

Abstract We deal with several pcf problems: we characterize another version of exponentiation: maximal number ofk-branches in a tree withλnodes, deal with existence of independent sets in stable theories, possible cardinalities of ultraproducts and the depth of ultraproducts of Boolean Algebras. Also we give cardinal invariants for eachλwith a pcf restriction and investigate furtherTD{f). The sections can be read independently, although there are some minor dependencies.

Abstract We present two different types of models where, for certain singular cardinals λ of uncountable cofinality, λ → (λ, ω + 1)2, although λ is not a strong limit cardinal, We announce, here, and will present in a subsequent paper, [7], that, for example, consistently, and consistently, .

Abstract Suppose λ is a singular cardinal of uncountable cofinality κ. For a model of cardinality λ, let No( ) denote the number of isomorphism types of models of cardinality λ which areL∞λ-equivalent to . In [7] Shelah considered inverse κ-systems of abelian groups and their certain kind of quotient limits Gr( )/ Fact( ). In particular Shelah proved in [7, Fact 3.10] that for every cardinal Μ there exists an inverse κ-system such that consists of abelian groups having cardinality at most Μκand card(Gr( )/ Fact( )) = Μ. Later in [8, Theorem 3.3] Shelah showed a strict connection between inverse κ-systems and possible values of No (under the assumption that θκ< λ for every θ < λ): if is an inverse κ-system of abelian groups having cardinality < λ, then there is a model such that card( ) = λ and No( ) = card(Gr( )/ Fact( )). The following was an immediate consequence (when θκ< λ for every θ < λ): for every nonzero Μ < λ or Μ = λκthere is a model , of cardinality λ with No( ) = Μ. In this paper we show: for every nonzero Μ ≤ λκthere is an inverse κ-system of abelian groups having cardinality < λ such that card(Gr( )/ Fact( )) = Μ (under the assumptions 2κ< λ and θ<κ< λ for all θ < λ when Μ > λ), with the obvious new consequence concerning the possible value of No. Specifically, the case No( ) = λ is possible when θκ> λ for every λ < λ.

Abstract Let be the class of structures 〈λ, <, A〉, where A ⊆ λ is disjoint from a club, and let be the class of structures 〈λ, <, A), where A ⊆ λ contains a club. We prove that if λ = λ<κ is regular, then no sentence of Lλ + κ separates and On the other hand, we prove that if λ = μ+ , μ = μ<μ, and a forcing axiom holds (and if μ = ℵ0), then there is a sentence of Lλλ which separates and .

Abstract Saturation is (μ, κ)-transferable in T if and only if there is an expansion T1 of T with |T1| = |T| such that if M is a μ-saturated model of T1 and |M| ≥ κ then the reduct M|L(T) is κ-saturated. We characterize theories which are superstable without f.c.p., or without f.c.p. as, respectively those where saturation is (ℵ0, λ)-transferable or (κ(T), λ)-transferable for all λ. Further if for some μ ≥ |T|,2μ > μ+, stability is equivalent to for all μ ≥ |T|, saturation is (μ, 2μ)-transferable.

Abstract We will prove that there exists a model of ZFC+“c =” in which every M ⊆ ℝ of cardinality less than continuum c is meager, and such that for every X ⊆ ℝ of cardinality c there exists a continuous function f : ℝ → ℝ with f[X] = [0, 1]. In particular in this model there is no magic set, i.e., a set M ⊆ ℝ such that the equation f[M] = g[M] implies f = g for every continuous nowhere constant functions f,g: ℝ → ℝ.

Abstract We consider various versions of the ♣ principle. This principle is a known consequence of ◊. It is well known that ◊ is not sensitive to minor changes in its definition, e.g., changing the guessing requirement form “guessing exactly” to “guessing modulo a finite set”. We show however, that this is not true for ♣. We consider some other variants of ♣ as well.

Abstract We give some general criteria, when κ-complete forcing preserves largeness properties—like κ-presaturation of normal ideals on λ (even when they concentrate on small cofinalities). Then we quite accurately obtain the consistency strength “NSλ is αi-preserving”, for λ > α2.

Abstract In this paper we prove a strong nonstructure theorem for κ(T)-saturated models of a stable theory T with dop. This paper continues the work started in [1].

Abstract Let I be an ideal of subsets of a Polish space X, containing all singletons and possessing a Borel basis. Assuming that I does not satisfy ccc, we consider the following conditions (B), (M) and (D). Condition (B) states that there is a disjoint family F ⊆ P(X) of size ϲ, consisting of Borel sets which are not in I. Condition (M) states that there is a Borel function f : X → X with f−1[{x}] ∉ I for each x ∈ X. Provided that X is a group and I is invariant, condition (D) states that there exist a Borel set B ∉ I and a perfect set P ⊆ X for which the family {B+x : x ∈ P} is disjoint. The aim of the paper is to study whether the reverse implications in the chain (D) ⇒ (M) ⇒ (B) ⇒ not-ccc can hold. We build a σ-ideal on the Cantor group witnessing (M) & ¬(D) (Section 2). A modified version of that σ-ideal contains the whole space (Section 3). Some consistency results on deriving (M) from (B) for “nicely” defined ideals are established (Sections 4 and 5). We show that both ccc and (M) can fail (Theorems 1.3 and 5.6). Finally, some sharp version's of (M) for invariant ideals on Polish groups are investigated (Section 6).

We work throughout in a finite relational language L. This paper is built on [2] and [3]. We repeat some of the basic notions and results from these papers for the convenience of the reader but familiarity with the setup in the first few sections of [3] is needed to read this paper. Spencer and Shelah [6] constructed for each irrational α between 0 and 1 the theory Tα as the almost sure theory of random graphs with edge probability n−α. In [2] we proved that this was the same theory as the theory Tα built by constructing a generic model in [3]. In this paper we explore some of the more subtle model theoretic properties of this theory. We show that Tα has the dimensional order property and does not have the finite cover property. We work in the framework of [3] so probability theory is not needed in this paper. This choice allows us to consider a wider class of theories than just the Tα. The basic facts cited from [3] were due to Hrushovski [4]; a full bibliography is in [3]. For general background in stability theory see [1] or [5]. We work at three levels of generality. The first is given by an axiomatic framework in Context 1.10. Section 2 is carried out in this generality. The main family of examples for this context is described in Example 1.3. Sections 3 and 4 depend on a function δ assigning a real number to each finite L-structure as in these examples. Some of the constructions in Section 3 (labeled at the time) use heavily the restriction of the class of examples to graphs. The first author acknowledges useful discussions on this paper with Sergei Starchenko.

Abstract After small forcing, any <κ-closed forcing will destroy the supercompactness and even the strong compactness of κ.

Abstract In this paper we show that the compactness of a Loeb space depends on its cardinality, the nonstandard universe it belongs to and the underlying model of set theory we live in. In §1 we prove that Loeb spaces are compact under various assumptions, and in §2 we prove that Loeb spaces are not compact under various other assumptions. The results in §1 and §2 give a quite complete answer to a question of D.Ross in [9], [11] and [12].

Abstract The monadic second-order theory of trees allows quantification over elements and over arbitrary subsets. We classify the class of trees with respect to the question: does a tree T have definable Skolem functions (by a monadic formula with parameters)? This continues [6] where the question was asked only with respect to choice functions. A natural subclass is defined and proved to be the class of trees with definable Skolem functions. Along the way we investigate the spectrum of definable well orderings of well ordered chains.

We study combinatorial principles known as stick and club. Several variants of these principles and cardinal invariants connected to them are also considered. We introduce a new kind of side by-side product of partial orderings which we call pseudo-product. Using such products, we give several generic extensions where some of these principles hold together with ¬CH and Martin's axiom for countable p.o.-sets. An iterative version of the pseudo-product is used under an inaccessible cardinal to show the consistency of the club principle for every stationary subset of limits of ω1 together with ¬CH and Martin's axiom for countable p.o.-sets.

Let κ be an uncountable cardinal and the edges of a complete graph with κ vertices be colored with ℵ0 colors. For the Erdős-Rado theorem implies that there is an infinite monochromatic subgraph. However, if , then it may be impossible to find a monochromatic triangle. This paper is concerned with the latter situation. We consider the types of colorings of finite subgraphs that must occur when . In particular, we are concerned with the case ℵ1 ≤ κ ≤ ℵω. The study of these color patterns (known as identities) has a history that involves the existence of compactness theorems for two cardinal models [4]. When the graph being colored has size ℵ1, the identities that must occur ( (ℵ1)) have been classified by Shelah [6]. If the graph has size greater than or equal to ℵω the identities that must occur ( (ℵω)) have also been classified in [5]. This leaves open the question of how the sets (ℵm) (2 ≤ m < ω) fit between (ℵ1) and ⊆ (ℵω). Some progress in this direction has been made in the paper [2]. It is there shown that if ZFC is consistent then so is for each m < ω. The number of colors is fixed at ℵ0 as it is the natural place to start and the results here can be generalized to more colors. We first give some definitions and establish some notation.

Abstract Gurevich and Shelah have shown that Peano Arithmetic cannot be interpreted in the monadic second-order theory of short chains (hence, in the monadic second-order theory of the real line). We will show here that it is consistent that the monadic second-order theory of no chain interprets Peano Arithmetic.

In the present paper we are interested in simple forcing notions and Forcing Axioms. A starting point for our investigations was the article [4] in which several problems were posed. We answer some of those problems here. In the first section we deal with the problem of adding Cohen reals by simple forcing notions. Here we interpret simple as of small size. We try to establish as weak as possible versions of Martin Axiom sufficient to conclude that some forcing notions of size less than the continuum add a Cohen real. For example we show that MA(σ-centered) is enough to cause that every small σ-linked forcing notion adds a Cohen real (see Theorem 1.2) and MA(Cohen) implies that every small forcing notion adding an unbounded real adds a Cohen real (see Theorem 1.6). A new almost ωω-bounding σ-centered forcing notion ℚ⊚ appears naturally here. This forcing notion is responsible for adding unbounded reals in this sense, that MA(ℚ⊚) implies that every small forcing notion adding a new real adds an unbounded real (see Theorem 1.13). In the second section we are interested in Anti-Martin Axioms for simple forcing notions. Here we interpret simple as nicely definable. Our aim is to show the consistency of AMA for as large as possible class of ccc forcing notions with large continuum. It has been known that AMA(ccc) implies CH, but it has been (rightly) expected that restrictions to regular (simple) forcing notions might help.

Abstract LetSbe the group of all permutations of the set of natural numbers. The cofinality spectrumCF(S)ofSis the set of all regular cardinalsλsuch thatScan be expressed as the union of a chain ofλproper subgroups. This paper investigates which setsCof regular uncountable cardinals can be the cofinality spectrum ofS. The following theorem.is the main result of this paper. Theorem.Suppose that V ⊨ GCH. Let C be a set of regular uncountable cardinals which satisfies the following conditions. (a)C contains a maximum element. (b)Ifμis an inaccessible cardinal such thatμ= sup(C∩μ),thenμ∈C. (c)ifμis a singular cardinal such thatμ= sup(C∩μ),thenμ+∈C. Then there exists a c.c.c. notion of forcing ℙ such that Vℙ⊨ CF(S) = C. We shall also investigate the connections between the cofinality spectrum andpcftheory; and show thatCF(S)cannot be an arbitrarily prescribed set of regular uncountable cardinals.

Abstract We study the cardinal invariants of measure and category after adding one random real. In particular, we show that the number of measure zero subsets of the plane which are necessary to cover graphs of all continuous functions may be large while the covering for measure is small.

Let κ be an uncountable cardinal and the edges of a complete graph with κ vertices be colored with ℵ0 colors. For the Erdős-Rado theorem implies that there is an infinite monochromatic subgraph. However, if , then it may be impossible to find a monochromatic triangle. This paper is concerned with the latter situation. We consider the types of colorings of finite subgraphs that must occur when the edges of the complete graph on vertices are colored with ℵ0 colors. In particular, we are concerned with the case ℵ1 ≤ κ ≤ ℵω. The study of these color patterns (known as identities) has a history that involves the existence of compactness theorems for two cardinal models [2]. When the graph being colored has size ℵ1, the identities that must occur have been classified by Shelah [4]. If the graph has size greater than or equal to ℵω the identities have also been classified in [3]. The number of colors is fixed at ℵ0 as it is the natural place to start and the results here can be generalized to situations where more colors are used. There is one difference that we now make explicit. When countably many colors are used we can define the following coloring of the complete graph on vertices. First consider the branches in the complete binary tree of height ω to be vertices of a complete graph.

Abstract The main result of this paper is a probabilistic construction of finite rigid structures. It yields a finitely axiomatizable class of finite rigid structures where no formula with counting quantifiers defines a linear order.

Abstract There exists a family of sets of countable ordinals such that: (1) maxBα=α, (2) ifα∈BβthenBα⊆Bβ, (3) ifλ≤αandλis a limit ordinal thenBα∩λis not in the ideal generated by theBβ,β<α, and by the bounded subsets ofλ, (4) there is a partition ofω1such that for everyαand everyn,Bα∩Anis finite.

Abstract It is unprovable that every complete subalgebra of a countably closed complete Boolean algebra is countably closed.

Abstract If T has only countably many complete types, yet has a type of infinite multiplicity then there is a c.c.c. forcing notion such that, in any -generic extension of the universe, there are non-isomorphic models M1 and M2 of T that can be forced isomorphic by a c.c.c. forcing. We give examples showing that the hypothesis on the number of complete types is necessary and what happens if ‘c.c.c’ is replaced by other cardinal-preserving adjectives. We also give an example showing that membership in a pseudo-elementary class can be altered by very simple cardinal-preserving forcings.

Abstract The monadic second-order theory of trees allows quantification over elements and over arbitrary subsets. We classify the class of trees with respect to the question: does a tree T have a definable choice function (by a monadic formula with parameters)? A natural dichotomy arises where the trees that fall in the first class don't have a definable choice function and the trees in the second class have even a definable well ordering of their elements. This has a close connection to the uniformization problem.

Abstract We give a solution stated in the title to problem 3 of part 1 of the problems listed in the book of Eklof and Mekler [2], p. 453. There, in pp. 241-242, this is discussed and proved in some cases. The existence of strongly λ-free ones was proved earlier by the criteria in [5] and [3]. We can apply a similar proof to a large class of other varieties in particular to the variety of (non-commutative) groups.

Let us draw a graph R on {0, 1, …, n-1} by having an edge {i, j} with probability p(i-j), where Σiπ <∞, and let Mn, (=, <,R). For a first-order sentence ψ let αnψ be the probability of Mn ⊨ ψ. We know that the sequence α1ψ⁠, α2ψ⁠, …, αnψ … does not necessarily converge. But here we find a weaker substitute which we call the very weak 0–1 law. We prove that limn┤ ∞ (αnψ - αn+1ψ) = 0 For this we need a theorem on the (first-order) theory of distorted sum of models.

This paper is concerned with a class K of models and an abstract notion of submodel ≤. Experience in first order model theory has shown the desirability of finding a ‘monster model’ to serve as a universal domain for K. In the original constructions of Jónsson and Fraïssé, K was a universal class and ordinary substructure played the role of ≤. Working with a cardinal λ satisfying λ<λ = λ guarantees appropriate downward Löwenheim-Skolem theorems; the existence and uniqueness of a homogeneous-universal model appears to depend centrally on the amalgamation property. We make this apparent dependence more precise in this paper. The major innovation of this paper is the introduction of a weaker notion (chain homogeneous-universal) to replace the natural notion of (K, <)-homogeneous-universal model. Modulo a weak extension of ZFC (provable if V = L), we show (Corollary 5.24) that a class K obeying certain minimal restrictions satisfies a fundamental dichotomy. For arbitrarily large λ, either K has the maximal number of models in power λ or K has a unique chain homogeneous-universal model of power λ. We show (5.25) in a class with amalgamation this dichotomy holds for the notion of K-homogeneous-universal model in the more normal sense. The methods here allow us to improve our earlier results [5] in two other ways: certain requirements on all chains of a given length are replaced by requiring winning strategies in certain games; the notion of a canonically prime model is avoided. A full understanding of these extensions requires consideration of the earlier papers but we summarize them quickly here.

Abstract We show that it is consistent with ZFC (relative to large cardinals) that every infinite Boolean algebraBhas an irredundant subsetAsuch that 2∣A∣= 2∣B∣. This implies in particular thatBhas 2∣B∣subalgebras. We also discuss some more general problems about subalgebras and free subsets of an algebra. The result on the number of subalgebras in a Boolean algebra solves a question of Monk from [6]. The paper is intended to be accessible as far as possible to a general audience, in particular we have confined the more technical material to a “black box” at the end. The proof involves a variation on Foreman and Woodin's model in which GCH fails everywhere.

Abstract The bounded proper forcing axiom BPFA is the statement that for any family of ℵ1 many maximal antichains of a proper forcing notion, each of size ℵ1, there is a directed set meeting all these antichains. A regular cardinal κ is called ∑1-reflecting, if for any regular cardinal χ, for all formulas φ, “H(χ) ⊨ ‘φ’” implies “∃δ < κ, H(δ) ⊨ ‘φ’”. We investigate several algebraic consequences of BPFA, and we show that the consistency strength of the bounded proper forcing axiom is exactly the existence of a ∑1-reflecting cardinal (which is less than the existence of a Mahlo cardinal). We also show that the question of the existence of isomorphisms between two structures can be reduced to the question of rigidity of a structure.

Abstract We study how equivalent nonisomorphic models of unsuperstable theories can be. We measure the equivalence by Ehrenfeucht-Fraïssé games. This paper continues [HS].

Abstract Assuming 0#does not exist, we present a combinatorial approach to Jensen's method of coding by a real. The forcing uses combinatorial consequences of fine structure (including the Covering Lemma, in various guises), but makes no direct appeal to fine structure itself.

Abstract We lay the combinatorial foundations for [5] by setting up and proving the essential properties of the coding apparatus for singular cardinals. We also prove another result concerning the coding apparatus for inaccessible cardinals.

G. McColm (1990) conjectured that positive elementary inductions are bounded in a class K of finite structures if every (FO+LFP) formula is equivalent to a first-order formula in K. Here (FO+LFP) is the extension of first-order logic with the least fixed point operator. We disprove the conjecture. Our main results are two model-theoretic constructions, one deterministic and the other randomized, each of which refutes McColm's conjecture.>

Abstract In this paper, we consider certain cardinals in ZF (set theory without AC, the axiom of choice). In ZFC (set theory with AC), given any cardinals and , either ≤ or ≤ . However, in ZF this is no longer so. For a given infinite set A consider seq1-1(A), the set of all sequences of A without repetition. We compare |seq1-1(A)|, the cardinality of this set, to | |, the cardinality of the power set of A. What is provable about these two cardinals in ZF? The main result of this paper is that ZF ⊢ ∀A(| seq1-1(A)| ≠ | |), and we show that this is the best possible result. Furthermore, it is provable in ZF that if B is an infinite set, then | fin(B)| < | (B*)| even though the existence for some infinite set B* of a function ƒ from fin(B*) onto (B*) is consistent with ZF.

Abstract We study how equivalent nonisomorphic models an unsuperstable theory can have. We measure the equivalence by Ehrenfeucht-Fraisse games. This paper continues the work started in [HT].

Abstract In § 1 of this paper, we characterize the isomorphism property of nonstandard universes in terms of the realization of some second-order types in model theory. In §2, several applications are given. One of the applications answers a question of D. Ross in [this Journal, vol. 55 (1990), pp. 1233–1242] about infinite Loeb measure spaces.

If two models of a first-order theory are isomorphic, then they remain isomorphic in any forcing extension of the universe of sets. In general however, such a forcing extension may create new isomorphisms. For example, any forcing that collapses cardinals may easily make formerly nonisomorphic models isomorphic. However, if we place restrictions on the partially-ordered set to ensure that the forcing extension preserves certain invariants, then the ability to force nonisomorphic models of some theory T to be isomorphic implies that the invariants are not sufficient to characterize the models of T. A countable first-order theory is said to be classifiable if it is superstable and does not have either the dimensional order property (DOP) or the omitting types order property (OTOP). If T is not classifiable, Shelah has shown in [5] that sentences in L∞,λ do not characterize models of T of power λ. By contrast, in [8] Shelah showed that if a theory T is classifiable, then each model of cardinality λ is described by a sentence of L∞,λ. In fact, this sentence can be chosen in the . ( is the result of enriching the language by adding for each μ < λ a quantifier saying the dimension of a dependence structure is greater than μ) Further work ([3], [2]) shows that ⊐+ can be replaced by ℵ1.

Abstract We conclude the discussion of additivity, Baire number, uniformity, and covering for measure and category by constructing the remaining 5 models. Thus we complete the analysis of Cichoń's diagram.

Abstract It is proved that—consistently — there can be no ccc closed P-sets in the remainder space ω*.

Abstract If ZFC is consistent, then each of the following is consistent with : (1) X ⊆ ℝ is of strong measure zero iff ∣X∣ ≤ ℵ1 + there is a generalized Sierpinski set. (2) The union of ℵ many strong measure zero sets is a strong measure zero set + there is a strong measure zero set of size ℵ2 + there is no Cohen real over L.

Abstract We build models where all -sets of reals are measurable and (or) have the property of Baire and (or) are Ramsey. We will show that there is no implication between any of these properties for -sets of reals.

Abstract We give an example of a countable theory T such that for every cardinal λ ≥ ℵ2 there is a fully indiscernible set A of power λ such that the principal types are dense over A, yet there is no atomic model of T over A. In particular, T(A) is a theory of size λ where the principal types are dense, yet T(A) has no atomic model.

In a series of papers culminating in [9], M. Talagrand, the second author, and others investigated at length the properties and structure of pointwise compact sets of measurable functions. A number of problems, interesting in themselves and important for the theory of Pettis integration, were solved subject to various special axioms. It was left unclear just how far the special axioms were necessary. In particular, several results depended on the fact that it is consistent to suppose that every countable relatively pointwise compact set of Lebesgue measurable functions is ‘stable’ in Talagrand's sense, the point being that stable sets are known to have a variety of properties not shared by all pointwise compact sets. In the present paper we present a model of set theory in which there is a countable relatively pointwise compact set of Lebesgue measurable functions which is not stable and discuss the significance of this model in relation to the original questions. A feature of our model which may be of independent interest is the following: in it, there is a closed negligible set Q ⊆ [0, 1]2 such that whenever D ⊆ [0,1] has outer measure 1, then has inner measure 1 (see 2G below). We embark immediately on the central ideas of this paper, setting out a construction of a partially ordered set which forces a fairly technical proposition in measure theory (IS below); the relevance of this proposition to pointwise compact sets will be discussed in §2.

Abstract Let σ( ) denote the number of automorphisms of a model of power ω1. We derive a necessary and sufficient condition in terms of trees for the existence of an with . We study the sufficiency of some conditions for . These conditions are analogous to conditions studied by D. Kueker in connection with countable models.

Abstract Our theme is that not every interesting question in set theory is independent of ZFC. We give an example of a first order theoryTwith countableD(T)which cannot have a universal model at ℵ1; without CH; we prove in ZFC a covering theorem from the hypothesis of the existence of a universal model for some theory; and we prove—again in ZFC—that for a large class of cardinals there is no universal linear order (e.g. in every regular ). In fact, what we show is that if there is a universal linear order at a regularλand its existence is not a result of a trivial cardinal arithmetical reason, thenλ“resembles” ℵ1—a cardinal for which the consistency of having a universal order is known. As for singular cardinals, we show that for many singular cardinals, if they are not strong limits then they have no universal linear order. As a result of the nonexistence of a universal linear order, we show the nonexistence of universal models for all theories possessing the strict order property (for example, ordered fields and groups, Boolean algebras,p-adic rings and fields, partial orders, models of PA and so on).

A well-known question of Feferman asks whether there is a logic which extends the logic , is ℵ0-compact and satisfies the interpolation theorem. (Cf. Makowsky [M] for background and terminology.) The same question was open when ℵ1 in is replaced by any other uncountable cardinal κ. We shall show that when κ is an uncountable strongly compact cardinal and there is a strongly compact cardinal > κ, then there is such a logic. It is impossible to prove the existence of uncountable strongly compact cardinals in ZFC. However, the logic that we describe has a simple and natural definition, together with several other pleasant properties. For example it satisfies Robinson's lemma, PPP (pair preservation property, viz. the theory of the sum of two models is the sum of their theories), versions of the elementary chain lemma for chains of length < λ, and isomorphism of (suitable) ultralimits. This logic is described in §2 below; we call it 1. It is not a new logic—it was introduced in [Sh, Part II, §3] as an example of a logic which has the amalgamation and joint embedding properties. See the transparent presentation in [M]. But we shall repeat all the definitions. In [HS] we presented a logic with some of the same properties as 1, also based on a strongly compact cardinal λ; but unlike 1, it was not a sublogic of λ,λ.

Abstract In this paper we will study four forcing notions, two of them giving a minimal degree of constructibility. These constructions give answers to questions in [Ih].

A technique is developed for establishing lower bounds on the computational complexity of certain natural problems. The results have the form of time-space trade-off and exhibit the power of nondeterminism. In particular, a form of the clique problem is defined, and it is proved that: a nondeterministic log-space Turing machine solves the problem in linear time, but no deterministic machine (in a very general use of this term) with sequential-access input tape and work space n σ solves the problem in time n 1+τ if σ + 2τ < 1/2.

Abstract It is consistent that, for every n ≥ 2, every stationary subset of ωn consisting of ordinals of cofinality ωκ, where κ = 0 or κ ≤ n − 3, reflects fully in the set of ordinals of cofinality ωn−1. We also show that this result is best possible.

Abstract In this work we give a complete answer as to the possible implications between some natural properties of Lebesgue measure and the Baire property. For this we prove general preservation theorems for forcing notions. Thus we answer a decade-old problem of J. Baumgartner and answer the last three open questions of the Kunen-Miller chart about measure and category. Explicitly, in §1: (i) We prove that if we add a Laver real, then the old reals have outer measure one. (ii) We prove a preservation theorem for countable-support forcing notions, and using this theorem we prove (iii) If we add ω2 Laver reals, then the old reals have outer measure one. From this we obtain (iv) Cons(ZF) ⇒ Cons(ZFC + ¬ B(m) + ¬ U(m) + U(c)). In §2: (i) We prove a preservation theorem, for the finite support forcing notion, of the property “F ⊆ ωω is an unbounded family.” (ii) We introduce a new forcing notion making the old reals a meager set but the old members of ωω remain an unbounded family. Using this we prove (iii) Cons(ZF) ⇒ Cons(ZFC + U(m) + ¬ B(c) + ¬ U(c) + C(c)). In §3: (i) We prove a preservation theorem, for the finite support forcing notion, of a property which implies “the union of the old measure zero sets is not a measure zero set,” and using this theorem we prove (ii) Cons(ZF) ⇒ Cons(ZFC + ¬U(m) + C(m) + ¬ C(c)).

For e.g. λ = μ+, μ regular, λ larger than the continuum, we prove a strong nonpartition result (stronger than λ → [λ; λ]2). As a consequence, the product of two topological spaces of cellularity <λ may have cellularity λ, or, in equivalent formulation, the product of two λ-c.c. Boolean algebras may lack the λ-c.c. Also λ-S-spaces and λ-L-spaces exist. In fact we deal not with successors of regular λ but with regular λ above the continuum which has a nonreflecting stationary subset of ordinals with uncountable cofinalities; sometimes we require λ to be not strong limit. The paper is self-contained. On the nonpartition results see the closely related papers of Todorčević [T1], Shelah [Sh276] and [Sh261], and Shelah and Steprans [ShSt1]. On the cellularity of products see Todorčević [T2] and [T3], where such results were obtained for (e.g.) cf and ; the class of cardinals he gets is quite disjoint from ours. In [Sh282] such results were obtained for more successors of singulars (mainly λ+, λ > 2cf λ). Also, concerning S and L spaces, Todorčević gets existence. Todorčević's work on cardinals like relies on [Sh68] (see more in [ShA2, Chapter XIII]) (the scales appearing in the proof of ). The problem was stressed in a preliminary version of the surveys of Juhasz and Monk. We give a detailed proof for one strong nonpartition theorem (1.1) and then give various strengthenings. We then use 1.10 to get the consequences (in 1.11 and 1.12).

Abstract We prove that the following are consistent with ZFC: 1. 2ω = ℵω1 + #x039A;c = ℵω1 + ΚΒ = ΚU = ω2 (for measure and category simultaneously). 2. . This concludes the discussion about the cofinality of Κc.

Abstract In spite of the fact that true arithmetic reduces to the monadic second-order theory of the real line, Peano arithmetic cannot be interpreted in the monadic second-order theory of the real line.

Abstract We introduce the class PIO of functions computable in time that is polynomial in max {the length of input, the length of output}, observe that there is no notation system for total PIO functions but there are notation systems for partial PIO functions, and give an algebra of partial PIO functions from binary strings to binary strings.

Abstract We deal with the consistency strength of ZFC + variants of MA + suitable sets of reals are measurable (and/or Baire, and/or Ramsey). We improve the theorem of Harrington and Shelah [2] repairing the asymmetry between measure and category, obtaining also the same result for Ramsey. We then prove parallel theorems with weaker versions of Martin's axiom (MA(σ-centered), (MA(σ-linked)), , MA(K)), getting Mahlo, inaccessible and weakly compact cardinals respectively. We prove that if there exists r ∈ R such that and MA holds, then there exists a -selective filter on ω, and from the consistency of ZFC we build a model for ZFC + MA(I) + every -set of reals is Lebesgue measurable, has the property of Baire and is Ramsey.

Abstract It is consistent that for many cardinals λ there is a family of at least λ+ unbounded subsets of λ which have uniformization properties. In particular if it is consistent that a supercompact cardinal exists, then it is consistent that ℵω has such a family. We have applications to point set topology, Whitehead groups and reconstructing separable abelian p-groups from their socles.

Abstract We get consistency results on I(λ, T, T) under the assumption that D(T) has cardinality > ∣T∣. We get positive results and consistency results on IE(λ, T1, T). The interest is model-theoretic, but the content is mostly set-theoretic: in Theorems 1–3, combinatorial; in Theorems 4–7 and 11(2), to prove consistency of counterexamples we concentrate on forcing arguments; and in Theorems 8–10 and 11(1), combinatorics for counterexamples; the rest are discussion and problems. In particular: (A) By Theorems 1 and 2, if T ⊆ T1 are first order countable, T complete stable but ℵ0-unstable, λ > ℵ0, and ∣D(T)∣ > ℵ0, then IE(λ, T1, T) > Min{2λ, ℶ2}. (B) By Theorems 4,5,6 of this paper, if e.g. V = L, then in some generic extension of V not collapsing cardinals, for some first order T ⊆ T1, ∣T∣ = ℵ0, ∣T1∣ = ℵ1, ∣D(T)∣ = ℵ2 and IE(ℵ2, T1, T) = 1. This paper (specifically the ZFC results) is continued in the very interesting work of Baldwin on diversity classes [Bl]. Some more advances can be found in the new version of [Sh300] (see Chapter III, mainly §7); they confirm 0.1, 0.2 and 14(1), 14(2).

Throughout this paper κ denotes an infinite cardinal, S = Sym(κ) and G is a subgroup of S. We shall be seeking the subgroups G with [S: G] < 2κ. In [2], the following result was proved. Theorem 1. If [S: G] ≤ κthen there exists a subset Δ of k such that ∣Δ∣ < k and S(Δ) ≤ G. Here S(Δ) = Sym(K/⊿) is the pointwise stabilizer of Δ in S. However, the converse of Theorem 1 is not true. For if cf(κ) ≤ ∣Δ∣ < κ, then [S: S(Δ)] ≥ κcf(κ) > κ. This suggests that a substantially sharpened version of Theorem 1 may be true. Question 1 [2]. Is it provable in ZFC, or even in ZFC with GCH, that if [S: G] ≤ κ then there is a subset Δ of κ such that ∣Δ∣ < cf(κ) and S(Δ) ≤ G? At least two of the authors of [2] made a serious attempt to answer the above question positively. In §3, we shall see that they were essentially trying to prove that measurable cardinals do not exist. The following result, due independently to Semmes [5] and Neumann [2], suggests a second way in which Theorem 1 might be improved. Theorem 2. If k = ℵ0and then there is a finite subset Δ of k such thatS(Δ) ≤ G. Question 2 [2]. Is it provable in ZFC that if [S: G] < 2κ then there is a subset Δ of κ such that ∣Δ∣ < κ and S(Δ) < G? This question will be answered negatively in §4.

Log-size Parabolic Clique Problem is a version of Clique Problem solvable in linear time by a log-space nondeterministic Turning machine. However, no deterministic machine (in a very general sense of this term) with sequential-access read-only input tape and work space nσ solves Log-size Parabolic Clique Problem within time n1 + τ if σ + 2τ < 1/2.

Abstract This paper belongs to cylindric-algebraic model theory understood in the sense of algebraic logic. We show the existence of isomorphic but not lower base-isomorphic cylindric set algebras. These algebras are regular and locally finite. This solves a problem raised in [N 83] which was implicitly present also in [HMTAN 81]. This result implies that a theorem of Vaught for prime models of countable languages does not continue to hold for languages of any greater power.

Abstract We define the notion of Souslin forcing, and we prove that some properties are preserved under iteration. We define a weaker form of Martin's axiom, namely , and using the results on Souslin forcing we show that is consistent with the existence of a Souslin tree and with the splitting number s = ℵ1. We prove that proves the additivity of measure. Also we introduce the notion of proper Souslin forcing, and we prove that this property is preserved under countable support iterated forcing. We use these results to show that ZFC + there is an inaccessible cardinal is equiconsistent with ZFC + the Borel conjecture + -measurability.

In this paper we solve some of Pál Erdős's favorite problems on uncountably chromatic graphs. Generalizing a finite graph theory result of Tutte, Erdős and R. Rado showed that for every infinite cardinal κ there exists a triangle-free, κ-chromatic graph of size κ. For κ = ℵ0, Erdős established the existence of ℵ0-chromatic graphs excluding even C4, C5,…, Cn, i.e. circuits up to a given length. For κ < ℵ0 the situation is different. As shown by Erdős and A. Hajnal, a graph is necessarily countably chromatic if it omits any finite bipartite graph. We can, however, exclude any finite list of nonbipartite graphs (this obviously reduces to excluding finitely many odd circuits). They posed an even stronger conjecture, namely, that similar examples must occur in every uncountably chromatic graph. To be specific, they conjectured that for every infinite κ, every κ-chromatic graph contains a κ-chromatic triangle-free subgraph. Here we show that this may not be true for κ = ℵ1 i.e. we exhibit a model where it is false. We must emphasize that the conjecture is probably false already in ZFC, but we have been unable to show this.

Let G = G(n, p) be the random graph with n vertices and edge probability p and ƒ(n, p, A) be the probability that G has A, where A is a first order property of graphs. The evolution of the random graph is discussed in terms of a spectrum of p = p(n) where ƒ(n, p, A) changes. A partial characterization of possible spectra is given. When p = n-a, a irrational, and A is any first order statement, it is shown that lim ƒ(n, p, A) = 0 or 1.

Etude des algebres de Boole superatomiques dans le modele de Mitchell. Consistance de la theorie des ensembles de Zermelo-Fraenkel avec axiome du choix et une algebre de Boole superatomique. Existence d'espaces topologiques dissemines de dimension nulle

Abstract We prove that MM (Martin maximum) is equivalent (in ZFC) to the older axiom SPFA (semiproper forcing axiom). We also prove that SPFA does not imply SPFA+ or even PFA+ (using the consistency of a large cardinal).

One way to cope with an NP-hard problem is to find an algorithm that is fact on average with respect to a natural probability distribution on inputs. We consider from that point of view the Hamiltonian Path Problem. Our algorithm for the Hamiltonian Path Problem constructs or establishes the nonexistence of a Hamiltonian path. For a fixed probability p, the expected run-time of our algorithm on a random graph with n vertices and the edge probability p is $O(n)$. The algorithm is adaptable to directed graphs.

Abstract Forcing extensions yield models of ZFC in which a long sequence of club subsets of ω1, has the following property: every subsequence of size ℵ1, has a finite intersection.

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.

Abstract 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.

We prove that the three extensions of first-order logic by means of positive inductions, monotone inductions, and so-called non-monotone (in our terminology, inflationary) inductions respectively, all have the same expressive power in the case of finite structures. As a by-product, the collapse of the corresponding fixed-point hierarchies can be deduced.

Abstract The theory of trees with additional unary predicates and quantification over nodes and branches embraces a rich branching time logic. This theory was reduced in the companion paper to the first-order theory of binary, bounded, well-founded trees with additional unary predicates. Here we prove the decidability of the latter theory.

A fundamental problem in the theory of abelian groups is to determine the structure of Ext(A, Z) for arbitrary abelian groups A. This problem was raised by L. Fuchs in 1958, and since then has been the center of considerable activity and progress. We briefly summarize the present state of this problem. It is a well-known fact that where tA denotes the torsion subgroup of A. Thus the structure problem for Ext(A, Z) breakdown to the two distinct cases, torsion and torsion free groups. For a torsion group T, which is compact and reduced, and its structure is known explicitly [12]. For torsion free A, Ext(A, Z) is divisible; hence it has a unique representation Thus Ext(A, Z) is characterized by countably many cardinal numbers, which we denote as follows: ν0(A) is the rank of the torsion free part of Ext(A, Z), and νp(A) are the ranks of the p-primary parts of Ext(A, Z), Extp(A, Z). If A is free it is an elementary fact that Ext(A, Z) = 0. The second named author has shown [16] that in the presence of V = L the converse is also true. For countable torsion free, nonfree A, C. Jensen [13] has shown that νp(A) is either finite or and νp(A) ≤ ν0(A). Therefore, the case for uncountable, nonfree, torsion free groups A remains to be studied.

The minimal Gödel class with identity (MGCI) is the class of closed, prenex quantificational formulas whose prefixes have the form ∀x1∀x2∃x3 and whose matrices contain arbitrary predicate letters and the identity sign “=”, but contain no function signs or individual constants. The MGCI was shown undecidable (for satisfiability) in 1983 [Go2]; this both refutes a claim of Gödel's [Gö, p. 443] and settles the decision problem for all prefix-classes of quantification theory with identity. In this paper, we show the decidability of a natural subclass of the MGCI. The formulas in this subclass can be thought of as exploiting only half of the power of the existential quantifier. That is, since an MGCI formula has prefix ∀x1∀x2∃x3, in general its truth in a model requires for any elements a and b, the existence of both a witness for and a witness for . The formulas we consider demand less: they require, for any elements a and b, a witness for the unordered pair {a, b}, that is, a witness either for or for .

Abstract Assume G.C.H. We prove that for singular λ, □λ implies the diamonds hold for many S ⊆ λ+ (including S ⊆ {δ:δ ∈ λ+, cf δ = cf λ}.) We also have complementary consistency results.

§1. A counterexample and preservation of “proper + X”. Theorem. Suppose V satisfies , , and for some A ⊆ ω1, every B ⊆ ω1, belongs to L[A]. Then we can define a countable support iteration such that the following conditions hold: a) EachQiis proper and ⊩Pi “Qi, has power ℵ1”. b) Each Qi is -complete for some simple ℵ1-completeness system. c) Forcing with Pα = Lim adds reals. Proof. We shall define Qi by induction on i so that conditions a) and b) are satisfied, and Ci, is a Qi-name of a closed unbounded subset of ω1. Let : ξ < ω1› ∈ L[A] be a list of all functions f which are from δ to δ for some δ < ω1 and let h: ω1 → ω1, h ∈ L[A], be defined by h(α) = Min{β: β > α and Lβ[A]⊨ “∣α∣ = ℵ0”}. Suppose we have defined Qj for every j < i; then Pi is defined, is proper (as each Qj, j < i, is proper, and by III 3.2) and has a dense subset of power ℵ (by III 4.1). Let Gi ⊆ Pi be generic so clearly there is B ⊆ ω1, such that in V[Gi] every subset of ω1 belongs to L[A, B], The following now follows: Fact. In V[Gi], every countableN ⥽(H(ℵ2), ∈, A, B) is isomorphic toLβ[A ∩ δ, B ∩ δ] for some β < h(δ), where δ = δ(N) = ω1, ∩ N.

We prove several independence results relevant to an old question in the folklore of set theory. These results complement those in [Sh, Chapter XIII, §4]. The question is the following. Suppose V ⊨ “ZFC + CH” and r is a real not in V. Must V[r] ⊨ CH? To avoid trivialities assume = . We answer this question negatively. Specifically we find pairs of models (W, V) such that W ⊨ ZFC + CH, V = W[r], r a real, = and V ⊨ ¬CH. Actually we find a spectrum of such pairs using ZFC up to “ZFC + there exist measurable cardinals”. Basically the nicer the pair is as a solution, the more we need to assume in order to construct it. The relevant results in [Sh, Chapter XIII] state that if a pair (of inner models) (W, V) satisfies (1) and (2) then there is an inaccessible cardinal in L; if in addition V ⊨ 2ℵ0 > ℵ2 then 0# exists; and finally if (W, V) satisfies (1), (2) and (3) with V ⊨ 2ℵ0 > ℵω, then there is an inner model with a measurable cardinal. Definition 1. For a pair (W, V) we shall consider the following conditions: (1) V = W[r], r a real, = , W ⊨ ZFC + CH but CH fails in V. (2) W ⊨ GCH. (3) W and V have the same cardinals.

Abstract We discuss the problem of finding forcing posets which introduce closed unbounded subsets to a given stationary set.

Abstract Assume ZFC + “There is a weakly compact cardinal” is consistent. Then: (i) For every S ⊆ ω, ZFC + “S and the monadic theory of ω2 are recursive each in the other” is consistent; and (ii) ZFC + “The full second-order theory of ω2 is interpretable in the monadic theory of ω2” is consistent.

Abstract Under a weak set-theoretic assumption we interpret second-order logic in the monadic theory of order.

Abstract The set of all words in the alphabet {l, r} forms the full binary tree T. If x ∈ T then xl and xr are the left and the right successors of x respectively. We consider the monadic second-order language of the full binary tree with the two successor relations. This language allows quantification over elements of rand over arbitrary subsets of T. We prove that there is no monadic second-order formula ϕ*(X, y) such that for every nonempty subset X of T there is a unique y ∈ X that satisfies ϕ*(X, y) in T.

Abstract In a paper of 1933 Gödel proved that every satisfiable first-order ∀ 2 ∃* sentence has a finite model. Actually he constructed a finite model in an ingenious and sophisticated way. In this paper we use a simple and straightforward probabilistic argument to establish existence of a finite model of an arbitrary satisfiable ∀ 2 ∃* sentence.

Abstract We characterize the ordinals α of uncountable cofinality such that α is the standard part of a nonstandard model of ZFC (or equivalently KP).

Abstract We prove that the logics of Magidor-Malitz and their generalization by Rubin are distinct even for PC classes. Let M ⊨ Qnx1 … xnφ(x1 … xn) mean that there is an uncountable subset A of ∣M∣ such that for every a1 …, an ∈ A, M ⊨ φ[a1, …, an]. Theorem 1.1 (Shelah) (♢ℵ1). For every n ∈ ωthe classKn+1 = {‹A, R› ∣ ‹A, R› ⊨ ¬ Qn+1x1 … xn+1R(x1, …, xn+1)} is not an ℵ0-PC-class in the logic ℒn, obtained by closing first order logic underQ1, …, Qn. I.e. for no countable ℒn-theory T, isKn+1the class of reducts of the models of T. Theorem 1.2 (Rubin) (♢ℵ1). Let M ⊨ QE x yφ(x, y) mean that there is A ⊆ ∣M∣ such thatEA, φ = {‹a, b› ∣ a, b ∈ A and M ⊨ φ[a, b]) is an equivalence relation on A with uncountably many equivalence classes, and such that each equivalence class is uncountable. Let KE = {‹A, R› ∣ ‹A, R› ⊨ ¬ QExyR(x, y)}. Then KE is not an ℵ0-PC-class in the logic gotten by closing first order logic under the set of quantifiers {Qn ∣ n ∈ ω) which were defined in Theorem 1.1.

Abstract The class of stable posets is defined and investigated. We give a forcing construction of a universe of set theory which satisfies a weak form of Martin's Axiom and 2ℵ0 > ℵ1 and yet some propositions which follow from CH hold in this universe.

Abstract We improve the canonization theorems generalizing the Erdös-Rado theorem, and as a result complete the answer to “When does a Hausdorff space of cardinality χ necessarily have a discrete subspace of cardinality k” We also improve the results on existence of free subsets.

The use of the temporal logic formalism for program reasoning is reviewed. Several aspects of responsiveness and fairness are analyzed, leading to the need for an additional temporal operator: the 'until' operator -U. Some general questions involving the 'until' operator are then discussed. It is shown that with the addition of this operator the temporal language becomes expressively complete. Then, two deductive systems DX and DUX are proved to be complete for the languages without and with the new operator respectively.

Abstract Theorem 1. (◊ℵ1,) If B is an infinite Boolean algebra (BA), then there is B1, such that ∣ Aut (B1) ≤∣B1∣ = ℵ1 and 〈B1, Aut (B1)〉 ≡ 〈B, Aut(B)〉. Theorem 2. (◊ℵ1) There is a countably compact logic stronger than first-order logic even on finite models. This partially answers a question of H. Friedman. These theorems appear in §§1 and 2. Theorem 3. (a) (◊ℵ1) If B is an atomic ℵ-saturated infinite BA, Ψ Є Lω1ω and 〈B, Aut (B)〉 ⊨Ψ then there is B1, Such that ∣Aut(B1)∣ ≤ ∣B1∣ =ℵ1, and 〈B1, Aut(B1)〉⊨Ψ. In particular if B is 1-homogeneous so is B1. (b) (a) holds for B = P(ω) even if we assume only CH.

Abstract Silver and subsequently Galvin and Hajnal, got bounds on , for ℵα strong limit cardinal of cofinality > ℵ0. We somewhat improve those results.

Abstract We prove the independence of a strong partition relation on ℵω, answering a question of Erdös and Hajnal. We then give an almost complete answer to the free subset problem.

Abstract We prove independence results concerning the number of nonisomorphic models (using the S-chain condition and S-properness) and the consistency of “ there is a universal linear order of power ℵ1”. Most of these results were announced in [Sh 4], [Sh 5]. In subsequent papers we shall prove an analog f MA for forcing which does not destroy stationary subsets of ω1 investigate -properness for various filters and prove the consistency with G.C.H. of an axiom implying SH (for ℵ1), and connected results.

Abstract We analyse here the monadic theory of the rational order, the monadic theory of the real line with quantification over “small” subsets and models of these theories. We prove that the results are in some sense the best possible.

Abstract We prove there are theories (stable or countable) for which over every A there is a prime model but it is not necessarily unique. We also give a simplified proof of the uniqueness theorem for countable stable theories.

Abstract Let T be a complete countable first-order theory such that every ultrapower of a model of T is saturated. If T has a model omitting a type p in every cardinality < ℶ′, then T has a model omitting p in every cardinality. There is also a related theorem, and an example showing the ℶ′ cannot be improved.

Let M be a countable algebraically closed group, κ an uncountable cardinal. We will prove in this paper the following theorems. Theorem 1. There is an algebraically closed group N of cardinality κ which is ∞ – ω-equivalent to M. Theorem 2. There is an algebraically closed group N of cardinality κ which is ∞ – ω-equivalent to M, and contains a free abelian group of cardinality κ. Theorem 3. There are 2κ nonisomorphic algebraically closed groups of cardinality κ which are ∞ – ω-equivalent to M. Theorem 4. There is an algebraically closed group N of cardinality κ which is ∞ – ω-equivalent to M and satisfies: Every subgroup of N of uncountable reqular cardinality contains a free subgroup of the same cardinality. Theorems 2 and 4 illustrate Theorem 3 by exhibiting two groups N ≡ ∞ωM of cardinality κ which are nonisomorphic by obvious reasons. We state and prove Theorem 1 separately in order to give an easy example of our principal tool: the use of automorphisms instead of indiscernibles (see §2).

Abstract Answering a problem of Fuhrken we prove that for every κ, 1 ≤ κ ≤ ℵ0, there is a (countable) complete theory T, with no prime model, and exactly κ minimal models (up to isomorphism).

Abstract We prove that every model of T = Th(ω, <,…) (T countable) has an end extension; and that every countable theory with an infinite order and Skolem functions has nonisomorphic countable models; and that if every model of T has an end extension, then every ∣T∣-universal model of T has an end extension definable with parameters.

Abstract We shall prove that if a model of cardinality κ can be expanded to a model of a sentence ψ of by adding a suitable predicate in more than κ ways, then, it has a submodel of power μ which can be expanded to a model of ψ in > μ ways provided that λ, κ, μ satisfy suitable conditions.

The main result of this paper is the following transfer theorem: If T is an elementary theory which has a κ-like model where κ is hyperinaccessible of type ω, then T has a λ-like model for each λ > card(T). Helling [3] obtained the same conclusion under the stronger hypothesis that κ is weakly compact. Fuhrken conjectured in [1] that the same conclusion would result if κ were merely inaccessible. (He also showed there the connection with a problem about generalized quantifiers.) Thus, our theorem lies properly between Helling's theorem and Fuhrken's conjecture. In [9] it is shown that this theorem is actually the best possible. This theorem and the other results of this paper were announced by the authors in [10]. In §1 we prove as Theorem 1 a slightly stronger form of the above theorem. This theorem is generalized in §2 to Theorem 2 which concerns theories which permit the omitting of types. The methods used in §§1 and 2 are also applicable to problems regarding Hanf numbers as well as to two-cardinal problems.

If T is a complete first-order totally transcendental theory then over every T-structure A there is a prime model unique up to isomorphism over A. Moreover M is a prime model over A iff: (1) every finite sequence from M realizes an isolated type over A, and (2) there is no uncountable indiscernible set over A in M. The existence of prime models was proved by Morley [3] and their uniqueness for countable A by Vaught [9]. Sacks asked (see Chang and Keisler [1, question 25]) whether the prime model is unique. After proving this I heard Ressayre had proved that every two strictly prime models over any T-structure A are isomorphic, by a strikingly simple proof. From this follows If T is totally transcendental, M a strictly prime model over A then every elementary permutation of A can be extended to an automorphism of M. (The existence of M follows by [3].) By our results this holds for any prime model. On the other hand Ressayre's result applies to more theories. For more information see [6, §0A]. A conclusion of our theorem is the uniqueness of the prime differentially closed field over a differential field. See Blum [8] for the total transcendency of the theory of differentially closed fields. We can note that the prime model M over A is minimal over A iff in M there is no indiscernible set over A (which is infinite).

We prove here theorems of the form: if T has a model M in which P1(M) is κ1-like ordered, P2(M) is κ2-like ordered …, and Q1(M) is of power λ1, …, then T has a model N in which P1(M) is κ1′-like ordered …, Q1(N) is of power λ1′, …. (In this article κ is a strong-limit singular cardinal, and κ′ is a singular cardinal.) We also sometimes add the condition that M, N omits some types. The results are seemingly the best possible, i.e. according to our knowledge about n-cardinal problems (or, more precisely, a certain variant of them).

Abstract Morley conjectured that if an infinite first-order theory T is categorical in the power |T| > ℵ0, then it has a model of power < |T| Here we affirm this conjecture for the case |T|ℵ0=|T|.

Abstract We shall prove that if is an ultrafilter and λℵ0 = λ. This affirms a conjecture of Keisler.