BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Characteristic earlier results were of the form CON(2ℵ0→[λ]n,22), with 2ℵ0 an ex-large cardinal, in the best case the first weakly Mahlo cardinal. Characteristic new results are CON((2ℵ0=ℵm)+ℵl→[ℵk]n,22), for suitable k<l<m. So we improve in three respects: the continuum may be small (e.g. not a weakly Mahlo), we use no large cardinal, and the cardinals λ involved are <2ℵ0 after the forcing.
We look for partition theorems for large subtrees for suitable uncountable trees and colourings. We concentrate on sub-trees of κ≥2 expanded by a well ordering of each level. Unlike earlier works, we do not ask the embedding to preserve the height of the tree but the equality of levels is preserved. We get consistency results without large cardinals. The intention is to apply it to model theoretic problems.
Answering a question of Harrington, we show that there exists a proper forcing notion, which adds a minimal real η∈∏i<ωni∗, which is eventually different from any old real in ∏i<ωni∗, where the sequence ⟨ni∗∣i<ω⟩ grows slowly.
We show that for a Suslin ccc forcing notion Q adding a Hechler real, ``ZF+DCω1+all sets of reals are IQ,ℵ0-measurable'' implies the existence of an inner model with a measurable cardinal. We also introduce a wide class of Suslin ccc forcing notions which add a Hechler real, so that the above result applies to them.
This paper continues a line of investigation of the Halpern--Läuchli Theorem at uncountable cardinals. We prove in ZFC that the Halpern--Läuchli Theorem for one tree of height κ holds whenever κ is strongly inaccessible and the coloring takes less than κ colors. We prove consistency of the Halpern--Läuchli Theorem for finitely many trees of height κ, where κ is a strong limit cardinal of countable cofinality. On the other hand, we prove failure of weak forms of Halpern--\Lauchli\ for trees of height κ, whenever κ is a strongly inaccessible, non-Mahlo cardinal or a singular strong limit cardinal with cofinality the successor of a regular cardinal. We also prove failure in L of a weak version for all strongly inaccessible, non-weakly compact cardinals.
We consider stability theory for Polish spaces and more generally for definable structures (say, with elements of a set of reals). We clarify by proving some equivalent conditions for ℵ0-stability. We succeed to prove existence of indiscernibles under reasonable conditions; this gives strong evidence that such a theory exists.
We prove that, consistently with ZFC, no ultraproduct of countably infinite (or separable metric, non-compact) structures is isomorphic to a reduced product of countable (or separable metric) structures associated to the Fréchet filter. Since such structures are countably saturated, the Continuum Hypothesis implies that they are isomorphic when elementarily equivalent.
The notion of a complete type can be generalized in a natural manner to allow assigning a value in an arbitrary Boolean algebra B to each formula. We show some basic results regarding the effect of the properties of 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.
For a countable ordinal epsilon we construct a Sigma^0_2 subset of the Cantor space for which one may force aleph_epsilon translations with intersections of size 2i, but such that it has no perfect set of such translations in any ccc extension. These sets have uncountably many translations with intersections of size 2i in ZFC, so this answers Problem 3.4 of arxiv:1711.04058 .
For λ inaccessible, we may consider (<λ)-support iteration of some specific (<λ)-complete λ+-c.c. forcing notion. But this fails a "preservation by restricting to a sub-sequence of the forcing, we "correct" the iteration to regain it. This is used in another paper in the consistency of cov(meagre)<dλ.
We study PC-exact saturation for stable and simple theories. Among other results, we show that PC-exact saturation characterizes the stability cardinals of size at least continuum of a countable stable theory and, additionally, that simple unstable theories have PC-exact saturation at singular cardinals, satisfying mild set-theoretic hypotheses, which had previously been open even for the random graph. We characterize supersimplicity of countable theories in terms of having PC-exact saturation at singular cardinals of countable cofinality. We also consider the local analogue of PC-exact saturation, showing that local PC-exact saturation for singular cardinals of countable cofinality characterizes supershort theories.
We lay the foundations of the first-order model theory of Coxeter groups. Firstly, with the exception of the 2-spherical non-affine case (which we leave open), we characterize the superstable Coxeter groups of finite rank, which we show to be essentially the Coxeter groups of affine type. Secondly, we characterize the Coxeter groups of finite rank which are domains, a central assumption in the theory of algebraic geometry over groups, which in many respects (e.g. λ-stability) reduces the model theory of a given Coxeter system to the model theory of its associated irreducible components. In the second part of the paper we move to specific definability questions in right-angled Coxeter groups (RACGs) and 2-spherical Coxeter groups. In this respect, firstly, we prove that RACGs of finite rank do not have proper elementary subgroups which are Coxeter groups, and prove further that reflection independent ones do not have proper elementary subgroups at all. Secondly, we prove that if the monoid Sim(W,S) of S-self-similarities of W is finitely generated, then W is a prime model of its theory. Thirdly, we prove that in reflection independent RACGs of finite rank the Coxeter elements are type-determined. We then move to 2-spherical Coxeter groups, proving that if (W,S) is irreducible, 2-spherical even and not affine, then W is a prime model of its theory, and that if WΓ and WΘ are as in the previous sentence, then WΓ is elementary equivalent to WΘ if and only if Γ≅Θ, thus solving the elementary equivalence problem for most of the 2-spherical Coxeter groups. In the last part of the paper we focus on model theoretic applications of the notion of reflection length from Coxeter group theory, proving in particular that affine Coxeter groups are not connected.
This paper opens and discusses the question originally due to Daniel Herden, who asked for which graph (μ,R) we can find a family {Gα:α<μ} of abelian groups such that for each α,β∈μ: Ext(Gα,Gβ)=0⟺(α,β)∈R. In this regard, we present four results. First, we give a connection to Quillen's small object argument which helps Ext vanishes and uses to present useful criteria to the question. Suppose λ=λℵ0 and μ=2λ. We apply Jensen's diamond principle along with the criteria to present λ-free abelian groups representing bipartite graphs. Third, we use a version of the black box to construct in ZFC, a family of ℵ1-free abelian groups representing bipartite graphs. Finally, applying forcing techniques, we present a consistent positive answer for general graphs.
Consider the Hales-Jewett theorem. The k-dimensional version of it tells us that the combinatorial space UM,Λ={η∣η:M→Λ} has, under suitable assumptions, monochromatic k-dimensional subspaces, where by a k-dimensional subspace we mean there exist a partition ⟨N0,N1,⋯,Nk⟩ of M such that N1,⋯,Nk=∅ (but we allow N0 to be empty) and some ρ0:N0→Λ, such that the subspace consists of those ρ∈UM,Λ such that for 0<l<k+1,ρ↾Nl is constant and ρ↾N0=ρ0. It seems natural to think it is better to have each Nl,0<l<k+1 a singleton. However it is then impossible to always find monochromatic k-dimensional subspaces (for example color η by 0 if ∣η−1{α}∣ is an even number and by 1 otherwise). But modulo restricting the sign of each ∣η−1{α}∣, we prove the parallel theorem -- whose proof is not related to the Hales-Jewett theorem. We then connect the two numbers by showing that the Hales-Jewett numbers are not too much above the present ones. This gives an alternative proof of the Hales-Jewett theorem.
We force the existence of a non-trivial κ-complete ultrafilter over κ which fails to satisfy the Galvin property. This answers a question asked by the first author and Moti Gitik.
We prove that the statement "for every infinite cardinal nu, every graph with list chromatic nu has coloring number at most beth_omega (nu)" proved by Kojman [6] using the RGCH theorem [11] implies the RGCG theorem via a short forcing argument. Similarly, a better upper bound than beth_omega (nu) in this statement implies stronger forms of the RGCH theorem hold, whose consistency and the consistency of their negations are wide open. Thus, the optimality of Kojman's upper bound is a purely cardinal arithmetic problem, and, as discussed below, is hard to decide.
A central theme in set theory is to find universes with extreme, well-understood behaviour. The case we are interested in is assuming GCH and has a strong forcing axiom of higher order than usual. Instead of "for every suitable forcing notion for~λ" we shall say "for every such family of forcing notions, depending on stationary S⊆λ, for some such stationary set we have\dots". Such notions of forcing are important for Abelian group theory, but this application is delayed for a sequel.
We show if we use countable support iteration of forcing notions not adding reals that satisfy additional conditions, then the limit forcing does not add reals. As a result we prove that we can amalgamate two earlier methods and prove the consistency with ZFC + GCH of two statements gotten separately earlier: Souslin hypothesis and non-club guessing. We also answer a question of Justin Moore by proving the consistency of one further case of "strong failure of club guessing" with GCH.
We prove the consistency of: for suitable strongly inaccessible cardinal lambda the dominating number, i.e. the cofinality of lambda^lambda is strictly bigger than cov(meagre_lambda), i.e. the minimal number of nowhere dense subsets of 2^lambda needed to cover it. This answers a question of Matet.
The cardinal invariants h,b,s of P(ω) are known to satisfy that ω1≤h≤min{b,s}. We prove that all inequalities can be strict. We also introduce a new upper bound for h and show that it can be less than s. The key method is to utilize finite support matrix iterations of ccc posets following \cite{BlassShelah}.
We prove that it is consistent with large values of the continuum that there are no S-spaces. We also show that we can also have that compact separable spaces of countable tightness have cardinality at most the continuum.
We show that if for any two elementary equivalent structures M,N of size at most continuum in a countable language, Mω/U≃Nω/U for some ultrafilter U on ω, then CH holds. We also provide some consistency results about Keisler and Shelah isomorphism theorems in the absence of CH.
The paper settles the problem of the consistency of the existence of a single universal graph between a strong limit singular and its power. Assuming that in a model of GCH κ is supercompact and the cardinals θ<κ, λ>κ are regular, as an application of a more general method we obtain a forcing extension in which cf(κ)=θ, the Singular Cardinal Hypothesis fails at κ and there exists a universal graph in cardinality λ∈(κ,2κ).
We find new "reasons" for a class of models for not having a universal model in a cardinal λ. This work, though it has consequences in model theory, is really in combinatorial set theory. We concentrate on a prototypical class which is a simply defined class of models, of combinatorial character - models of Tceq (essentially another representation of Tfeq which was already considered but the proof with Tceq is more transparent). Models of Tceq consist essentially of an equivalence relation on one set and a family of choice functions for it. This class is not simple (in the model theoretic sense) but seems to be very low among the non-simple (first order complete countable) ones. We give sufficient conditions for the non-existence of a universal model for it in λ. This work is continued in [Sh:F2071].
We generalize the Hart-Shelah example \cite{HaSh:323} to higher infinitary logics. We build, for each natural number k≥2 and for each infinite cardinal λ, a sentence ψkλ of the logic L(2λ)+,ω that (modulo mild set theoretical hypotheses around λ and assuming 2λ<λ+m) is categorical in λ+,…,λ+k−1 but not in ℶk+1(λ)+ (or beyond); we study the dimensional encoding of combinatorics involved in the construction of this sentence and study various model-theoretic properties of the resulting abstract elementary class K∗(λ,k)=(Mod(ψkλ),≺(2λ)+,ω) in the finite interval of cardinals λ,λ+,…,λ+k.
Cichoń's diagram lists twelve cardinal characteristics (and the provable inequalities between them) associated with the ideals of null sets, meager sets, countable sets, and σ-compact subsets of the irrationals. It is consistent that all entries of Cichoń's diagram are pairwise different (apart from add(M) and cof(M), which are provably equal to other entries). However, the consistency proofs so far required large cardinal assumptions. In this work, we show the consistency without such assumptions.
Given a forcing notion P that forces certain values to several classical cardinal characteristics of the reals, we show how we can compose P with a collapse (of a cardinal λ>κ to κ) such that the composition still forces the previous values to these characteristics. We also show how to force distinct values to m, p and h and also keeping all the values in Cichoń's diagram distint, using the Boolean Ultrapower method of arXiv:1708.03691 . (In arXiv:2006.09826 , the same was done for the newer Cichoń's Maximum construction, which avoids large cardinals.)
We construct, in ZFC, a countably compact subgroup of 2c without non-trivial convergent sequences, answering an old problem of van Douwen. As a consequence we also prove the existence of two countably compact groups G0 and G1 such that the product G0×G1 is not countably compact, thus answering a classical problem of Comfort.
We note that some form of the condition "p1,p2 have a ≤Q-lub in Q" is necessary in some forcing axiom for λ-complete μ+-c.c. forcing notions. We also show some versions are really stronger than others.
We prove that if μ>cf(μ)=ω and 2μ=μ+ then (μμ+)↛(μμμ+ ℵ2).
This paper is a continuation of [BaSh], where we studied the behaviour of the abelianization functor under inverse limits. Our main result in [BaSh] was that if T is a countable directed poset and G:T→Grp is a diagram of groups that satisfies the Mittag-Leffler condition, then the natural map Ab(limt∈TGt)→limt∈TAb(Gt) is surjective, and its kernel is a cotorsion group. The abelianization is an example of a left adjoint functor from groups to abelian groups. In this paper we study the behaviour under inverse limits of left adjoint functors from pointed sets to abelian groups. Such functors are classified by abelian groups, where to the abelian group A corresponds the left adjoint functor LA:Set∗→Ab given by LA(Y)=⨁Y∖{∗}A. If T is a directed poset and X:T→Set∗ is a is diagram of pointed sets, we show that the natural map ρ:LA(limt∈TXt)→limt∈TLA(Xt) is injective. If, in addition, T is countable and X satisfies the Mittag-Leffler condition, we show that the cokernel of ρ is an algebraically compact group. Compared with the main result in [BaSh], algebraically compact is much stronger then cotorsion as it also requires the Ulm length to be ≤1. We also show that this result, even in its weak form of cotorsion, does not extend to uncountable diagrams. Namely, if A is not the product of a divisible group and a bounded group, we construct a directed poset T with ∣T∣=2ℵ0 and a diagram X:T→Set∗, that satisfies the Mittag-Leffler condition, such that the cokernel of ρ is not cotorsion.
A permutation group G on a set A is κ-homogeneous iff for all X,Y∈[A]κ with ∣A∖X∣=∣A∖Y∣=∣A∣ there is a g∈G with g[X]=Y. G is κ-transitive iff for any injective function f with dom(f)∪ran(f)∈[A]≤κ and ∣A∖dom(f)∣=∣A∖ran(f)∣=∣A∣ there is a g∈G with f⊂g. Giving a partial answer to a question of P. M. Neumann we show that there is an ω-homogeneous but not ω-transitive permutation group on a cardinal λ provided (i) λ<ωω, or (ii) 2ω<λ, and μω=μ+ and □μ hold for each μ≤λ with ω=cf(μ)<μ, or (iii) our model was obtained by adding ω1 many Cohen generic reals to some ground model. For κ>ω we give a method to construct large κ-homogeneous, but not κ-transitive permutation groups. Using this method we show that there exists κ+-homogeneous, but not κ+-transitive permutation groups on κ+n for each infinite cardinal κ and natural number n≥1 provided V=L.
We prove the consistency of: for suitable strongly inaccessible cardinal lambda the dominating number, i.e., the cofinality of ^{lambda}lambda, is strictly bigger than cov_lambda(meagre), i.e. the minimal number of nowhere dense subsets of ^{lambda}2 needed to cover it. This answers a question of Matet.
We show that if cf(2ℵ0)=ℵ1, then any non-trivial ℵ1-closed forcing notion of size ≤2ℵ0 is forcing equivalent to Add(ℵ1,1), the Cohen forcing for adding a new Cohen subset of ω1. We also produce, relative to the existence of suitable large cardinals, a model of ZFC in which 2ℵ0=ℵ2 and all ℵ1-closed forcing notion of size ≤2ℵ0 collapse ℵ2, and hence are forcing equivalent to Add(ℵ1,1). These results answer a question of Scott Williams from 1978. We also extend a result of Todorcevic and Foreman-Magidor-Shelah by showing that it is consistent that every partial order which adds a new subset of ℵ2, collapses ℵ2 or ℵ3.
We show that ZF+DC+"all Turing invariant sets of reals have the perfect set property" implies that all sets of reals have the perfect set property. We also show that this result generalizes to all countable analytic equivalence relations.
In this paper the Erdos-Rado theorem is generalized to the class of well founded trees.
Let inv denote the cardinal invariants Depth^+ and Length^+ on Boolean algebras. For many singular cardinals we create a strict inequality between the product of the inv values and the inv of the product algebra. The proof holds in ZFC.
It is consistent that ℵ1<add(Null)<add(Meager)=b<cov(Null)<non(Meager)<cov(Meager)=2ℵ0. Assuming four strongly compact cardinals, it is consistent that ℵ1<add(Null)<add(Meager)=b<cov(Null)<non(Meager)<cov(Meager)<non(Null)<cof(Meager)=d<cof(Null)<2ℵ0.
We prove the consistency of the statement uℵω<2ℵω. We show that the consistency strength of this statement is exactly a measurable cardinal μ so that o(μ)=μ++.
We prove the consistency of rλ<dλ and even uλ<dλ for a singular cardinal λ.
We construct a Borel maximal eventually different family.
We describe a framework for proving consistency results about singular cardinals of arbitrary cofinality and their successors. This framework allows the construction of models in which the Singular Cardinals Hypothesis fails at a singular cardinal of uncountable cofinality, while its successor enjoys various combinatorial properties. As a sample application, we prove the consistency (relative to that of ZFC plus a supercompact cardinal) of there being a strong limit singular cardinal κ of uncountable cofinality where SCH fails and for which there is a collection of graphs on κ+ whose size is less than 2κ and such that any graph on κ+ embeds into one of the graphs in the collection.
We try to build, provably in ZFC, for a first order T a model in which any isomorphism between two Boolean algebras is definable. The problem, compared to [Sh:384], is with pseudo-finite Boolean algebras. A side benefit is that we do not use Skolem function (which do not matter for proving compactness of logics but still are of interest). Let lambda be 2^mu if regular and its successor otherwise. Model theoretically we investigate notions of bigness of types, usually those are ideals of the set of formulas in a model, definable in appropriate sense. We build a model of cardinality lambda^plus by a sequence of models M_alpha of cardinality lambda for alpha less than lambda^plus, each M_alpha equips with a sequence (M_alpha, i, a_alpha, i, Omega_alpha, i) : i in S_I subseteq lambda, with M_alpha, i is of cardinality less than lambda, precedes-increasing continuous with i, Omega_alpha, i a bigness notion defined using parameters from M_alpha, i and a_alpha, i realized in M_alpha, i plus 1 over M_alpha,i a Omega_alpha, i-big type. As alpha increase, not only M_alpha increase, but this extra structure increasing modulo a club of lambda, this is why we have insisted on lambda being regular. This can be considered as a way to omit types of cardinality lambda, which in general is hard. The fact that lambda is not too much larger than mu helps us to guarantee that any possible automorphism of structures be defined in M equals union bracket M_alpha: alpha less than lambda^plus bracket by approximations of cardinal mu and so we can enumerate them all.
We show that under Dickson's conjecture about the distribution of primes in the natural numbers, the theory Th(Z,+,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(Z,+,0,Pr,<) which is known to be undecidable by the works of Jockusch, Bateman and Woods.
The theme of the first two sections, is to prepare the framework of how from a "complicated" family of index models I in K_1 we build many and/or complicated structures in a class K_2. The index models are characteristically linear orders, trees with kappa+1 levels (possibly with linear order on the set of successors of a member) and linearly ordered graph, for this we phrase relevant complicatedness properties (called bigness). We say when M in K_2 is represented in I in K_1. We give sufficient conditions when {M_I:I\in K^1_λ} is complicated where for each I in K^1_lambda we build M_I in K^2 (usually in K^2_lambda) represented in it and reflecting to some degree its structure (e.g. for I a linear order we can build a model of an unstable first order class reflecting the order). If we understand enough we can even build e.g. rigid members of K^2_lambda. Note that we mention "stable", "superstable", but in a self contained way, using an equivalent definition which is useful here and explicitly given. We also frame the use of generalizations of Ramsey and Erdos-Rado theorems to get models in which any I from the relevant K_1 is reflected. We give in some detail how this may apply to the class of separable reduced Abelian p-group and how we get relevant models for ordered graphs (via forcing). In the third section we show stronger results concerning linear orders. If for each linear order I of cardinality lambda>aleph_0 we can attach a model M_I in K_lambda in which the linear order can be embedded so that for enough cuts of I, their being omitted is reflected in M_I, then there are 2^lambda non-isomorphic cases.
For an ultrafilter D on a cardinal κ, we wonder for which pair (θ1,θ2) of regular cardinals, we have: for any (θ1+θ2)+−saturated dense linear order J,Jκ/D has a cut of cofinality (θ1,θ2). We deal mainly with the case θ1,θ2>2κ.
We are interested in subgroups of the reals that are small in one and large in another sense. We prove that, in ZFC, there exists a non-meager Lebesgue null subgrooup of R, while it isconsistent there there is no non-null meager subgroup of R.
Assuming the generalized continuum hypothesis we construct arbitrarily big indecomposable Banach spaces. i.e., such that whenever they are decomposed as X⊕Y, then one of the closed subspaces X or Y must be finite dimensional. It requires alternative techniques compared to those which were initiated by Gowers and Maurey or Argyros with the coauthors. This is because hereditarily indecomposable Banach spaces always embed into ℓ∞ and so their density and cardinality is bounded by the continuum and because dual Banach spaces of densities bigger than continuum are decomposable by a result due to Heinrich and Mankiewicz. The obtained Banach spaces are of the form C(K) for some compact connected Hausdorff space and have few operators in the sense that every linear bounded operator T on C(K) for every f∈C(K) satisfies T(f)=gf+S(f) where g∈C(K) and S is weakly compact or equivalently strictly singular. In particular, the spaces carry the structure of a Banach algebra and in the complex case even the structure of a C∗-algebra.
We propose an extension of the Ehrenfeucht-Fraisse game able to deal with logics augmented with Lindstrom quantifiers. We describe three different games with varying balance between simplicity and ease of use.
This was supposed to be an appendix to the book "Non-structure", and probably will be if it materializes. It presents relevant material, sometimes new, which was used in works which were supposed to be part of that book. In section 1 we deal with partition theorems on trees with omega levels; it is self contained. In section 2 we deal with linear orders which are countable union of scattered ones with unary predicated, it is self contained. In section 3 we deal mainly with pcf theory but just quote. In section 4, on normal ideals, we repeat [Sh:247]. This is used in [Sh:331].
We introduce the notion of pseudo-algebraicity to study atomic models of first order theories (equivalently models of a complete sentence of Lω1,ω. Theorem: Let T be any complete first-order theory in a countable language with an atomic model. If the pseudo-minimal types are not dense, then there are 2ℵ1 pairwise non-isomorphic atomic models of T, each of size ℵ1.
A theory T is said to have exact saturation at a singular cardinal κ if it has a κ-saturated model which is not κ+-saturated. We show, under some set-theoretic assumptions, that any simple theory has exact saturation. Also, an NIP theory has exact saturation if and only if it is not distal. This gives a new characterization of distality.
Suppose that P is a forcing notion, L is a language (in V), τ˙ a P-name such that P⊩ "τ˙ is a countable L-structure". In the product P×P, there are names τ1˙,τ2˙ such that for any generic filter G=G1×G2 over P×P, τ˙1[G]=τ˙[G1] and τ˙2[G]=τ˙[G2]. Zapletal asked whether or not P×P⊩τ˙1≅τ˙2 implies that there is some M∈V such that P⊩τ˙≅Mˇ. We answer this negatively and discuss related issues.
Non-forking is one of the most important notions in modern model theory capturing the idea of a generic extension of a type (which is a far-reaching generalization of the concept of a generic point of a variety). To a countable first-order theory we associate its non-forking spectrum - a function of two cardinals kappa and lambda giving the supremum of the possible number of types over a model of size lambda that do not fork over a sub-model of size kappa. This is a natural generalization of the stability function of a theory. We make progress towards classifying the non-forking spectra. On the one hand, we show that the possible values a non-forking spectrum may take are quite limited. On the other hand, we develop a general technique for constructing theories with a prescribed non-forking spectrum, thus giving a number of examples. In particular, we answer negatively a question of Adler whether NIP is equivalent to bounded non-forking. In addition, we answer a question of Keisler regarding the number of cuts a linear order may have. Namely, we show that it is possible that ded(kappa) < ded(kappa)^omega.
We list some open problems, concerning the polarized partition relation. We solve a couple of them by showing that for every singular cardinal μ one can force the strong polarized relation with respect to the pair μ+,μ.
We study zero-one laws for random graphs. We focus on the following question that was asked by many: Given a graph property P, is there a language of graphs able to express P while obeying the zero-one law? Our results show that on the one hand there is a (regular) language able to express connectivity and k-colorability for any constant k and still obey the zero-one law. On the other hand we show that in any (semiregular) language strong enough to express Hamiltonicity one can interpret arithmetic and thus the zero-one law fails miserably. This answers a question of Blass and Harary.
Using a finite support iteration of ccc forcings, we construct a model of ℵ1<add(N)<cov(N)<b<non(M)<cov(M)=c.
We prove two ZFC inequalities between cardinal invariants. The first inequality involves cardinal invariants associated with an analytic P-ideal, in particular the ideal of subsets of ω of asymptotic density 0. We obtain an upper bound on the ∗-covering number, sometimes also called the weak covering number, of this ideal by proving in Section \ref{sec:covz0} that cov∗(Z0)≤d. In Section \ref{sec:skbk} we investigate the relationship between the bounding and splitting numbers at regular uncountable cardinals. We prove in sharp contrast to the case when κ=ω, that if κ is any regular uncountable cardinal, then sκ≤bκ.
We study aleph_0-stable theories, and prove that if T either has eni-DOP or is eni-deep, then its class of countable models is Borel complete. We introduce the notion of lambda-Borel completeness and prove that such theories are lambda-Borel complete. Using this, we conclude that an aleph_0-stable theory has 2^lambda pairwise non-L(infinity,aleph_0) equivalent models of size lambda for all infinite cardinals lambda if and only if T either has eni-DOP or is eni-deep.
The mad spectrum is the set of all cardinalities of infinite maximal almost disjoint families on omega. We treat the problem to characterize those sets A which, in some forcing extension of the universe, can be the mad spectrum. We solve this problem to some extent. What remains open is the possible values of min(A) and max(A).
Using the method of decisive creatures (math.LO/0601083) we show the consistency of "there is no increasing omega_2 --chain of Borel sets and non(N)=non(M)= omega_2=2^omega". Hence, consistently, there are no monotone hulls for the ideal M cap N . This answers Balcerzak and Filipczak. Next we use FS iteration with partial memory to show that there may be monotone Borel hulls for the ideals M, N even if they are not generated by towers.
We show that some set-theoretic assumptions (for example Martin's Axiom) imply that there is no translation invariant Borel hull operation on the family of Lebesgue null sets and on the family of meager sets in (in R^n). We also prove that if the meager ideal admits a monotone Borel hull operation, then there is also a monotone Borel hull operation on the sigma-algebra of sets with the property of Baire.
The study of the global structure of ultrafilters on the natural numbers with respect to the quasi-orders of Rudin-Keisler and Rudin-Blass reducibility was initiated in the 1970s by Blass, Keisler, Kunen, and Rudin. In a 1973 paper Blass studied the special class of P-points under the quasi-ordering of Rudin-Keisler reducibility. He asked what partially ordered sets can be embedded into the P-points when the P-points are equipped with this ordering. This question is of most interest under some hypothesis that guarantees the existence of many P-points, such as Martin's axiom for σ-centered posets. In his 1973 paper he showed under this assumption that both ω1 and the reals can be embedded. This result was later repeated for the coarser notion of Tukey reducibility. We prove in this paper that Martin's axiom for σ-centered posets implies that every partial order of size at most continuum can be embedded into the P-points both under Rudin-Keisler and Tukey reducibility.
We prove that if the bounding number (d) is bigger than the reaping number (r), then the latter has uncountable cofinality.
In this note we show that the p-rank of Ext(A,B) for countable torsion-free abelian groups A and B is either countable or the size of the continuum.
Assume a complete superstable theory is superstable, and let P be a class of regular types, typically closed under automorphisms of the monster and non-orthogonality. We define the notion of P-NDOP and prove the existence of P-decompositions and derive an analog of Sh401 for superstable theories with P-NDOP. In this context, we also find a sufficient condition on P-decompositions that imply non-isomorphic models. For this, we investigate natural structures on the types in P\intersect S(M) modulo non-orthogonality.
We study countable saturation of the metric reduced products and introduce continuous fields of metric models indexed by locally compact, separable, completely metrizable spaces. Saturation of the reduced product depends both on the underlying index space and the model. By using the Gelfand--Naimark duality we conclude that the assertion that the \vCech--Stone remainder of the half-line has only trivial automorphisms is independent from ZFC. The consistency of this statement follows from Proper Forcing Axiom and this is the first known example of a connected space with this property.
This paper generalizes Shelah's generic pair conjecture (now theorem) for the measurable cardinal case from first order theories to finite diagrams. We use homogeneous models in the place of saturated models.
The \emph{linear refinement number} lr is the minimal cardinality of a centered family in [ω]ω such that no linearly ordered set in ([ω]ω,⊆∗) refines this family. The \emph{linear excluded middle number} lx is a variation of lr. We show that these numbers estimate the critical cardinalities of a number of selective covering properties. We compare these numbers to the classic combinatorial cardinal characteristics of the continuum. We prove that lr=lx=fd in all models where the continuum is at most ℵ2, and that the cofinality of lr is uncountable. Using the method of forcing, we show that lr and lx are not provably equal to d, and rule out several potential bounds on these numbers. Our results solve a number of open problems.
Let C be a finite connected graph for which there is a countable universal C-free graph, and whose tree of blocks is a path. Then the blocks of C are complete. This generalizes a result of Furedi and Komjath, and fits naturally into a set of conjectures regarding the existence of countable C-free graphs, with C an arbitrary finite connected graph.
We give a full solution to the question of existence of indiscernibles in dependent theories by proving the following theorem: for every θ there is a dependent theory T of size θ such that for all κ and δ, κ→(δ)T,1 iff κ→(δ)θ<ω. This means that unless there are good set theoretical reasons, there are large sets with no indiscernible sequences.
Consider an a.e.c. (abstract elementary class), that is, a class K of models with a partial order refining inclusion (submodel) which satisfy the most basic properties of an elementary class. Our test question is trying to show that the function dot I (lambda, K), counting the number of models in K of cardinality lambda up to isomorphism, is "nice", not chaotic, even without assuming it is sometimes 1, i.e. categorical in some lambda's. We prove here that for some closed unbounded class C of cardinals we have (a), (b) or (c) where (a) for every lambda in C of cofinality aleph_0, dot I (lambda, K) greater than or equal to lambda, (b) for every lambda in C of cofinality aleph_0 and M belongs to K_lambda, for every cardinal kappa greater than or equal to lambda there is N_kappa of cardinality kappa extending M (in the sense of our a.e.c.), (c) mathfrak k is bounded; that is, dot I (lambda, K) = 0 for every lambda large enough (equivalently lambda greater than or equal to beth_{delta_*} where delta_* = (2^{LST(mathfrak k)})^+). Recall that an important difference of non-elementary classes from the elementary case is the possibility of having models in K, even of large cardinality, which are maximal, or just failing clause (b).
The following pcf results are proved: 1. Assume that kappa > aleph_0 is a weakly compact cardinal. Let mu > 2^kappa be a singular cardinal of cofinality kappa. Then for every regular lambda < pp^+_{Gamma(kappa)} (mu) there is an increasing sequence (lambda_i | i < kappa) of regular cardinals converging to mu such that lambda = tcf(prod_{i < kappa} lambda_i, <_{J^{bd}_kappa}). 2. Let mu be a strong limit cardinal and theta a cardinal above mu. Suppose that at least one of them has an uncountable cofinality. Then there is sigma_* < mu such that for every chi < theta the following holds: theta > sup{sup pcf_{sigma_*-complete} (frak a) | frak a subseteq Reg cap (mu^+, chi) and |frak a| < mu}. As an application we show that: if kappa is a measurable cardinal and j:V to M is the elementary embedding by a kappa-complete ultrafilter over kappa, then for every tau the following holds: 1. if j(tau) is a cardinal then j(tau) = tau; 2. |j(tau)| = |j(j(tau))|; 3. for any kappa-complete ultrafilter W on kappa, |j (tau)| = |j_W(tau)|. The first two items provide affirmative answers to questions from Gitik and Shelah (1993) [2] and the thrid to a question of D. Fremlin.
We show the consistency of "there is a nice sigma --ideal I on the reals with add(I)= omega_1 which cannot be represented as the union of a strictly increasing sequence of length omega_1 of sigma-subideals". This answers a question by Borodulin-Nadzieja and Glab.
We show that it is consistent that the Borel Conjecture and the dual Borel Conjecture hold simultaneously.
A dependent theory is a (first order complete theory) T which does not have the independence property. A main result here is: if we expand a model of T by the traces on it of sets definable in a bigger model then we preserve its being dependent. Another one justifies the cofinality restriction in the theorem (from a previous work) saying that pairwise perpendicular indiscernible sequences, can have arbitrary dual-cofinalities in some models containing them.
We try to understand complete types over a somewhat saturated model of a complete first order theory which is dependent (previously called NIP), by "decomposition theorems for such types". Our thesis is that the picture of dependent theory is the combination of the one for stable theories and the one for the theory of dense linear order or trees (and first we should try to understand the quite saturated case). As a measure of our progress, we give several applications considering some test questions; in particular we try to prove the generic pair conjecture and do it for measurable cardinals.
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 non-splintering, 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.
Let λbe a cardinal with λ=λ^{\aleph_0} and p be either 0 or a prime number. We show that there are fields K_0 and K_1 of cardinality λand characteristic p such that the automorphism group of K_0 is a free group of cardinality 2^λand the automorphism group of K_1 is a free abelian group of cardinality 2^λ. This partially answers a question from [8] and complements results from [15], [16] and [17]. The methods developed in the proof of the above statement also allow us to show that the above cardinal arithmetic assumption is consistently not necessary for the existence of such fields and that the existence of a cardinal λof uncountable cofinality with the property that there is no field of cardinality λwhose automorphism group is a free group of cardinality greater than λimplies the existence of large cardinals in certain inner models of set theory.
We show that many countable support iterations of proper forcings preserve Souslin trees. We establish sufficient conditions in terms of games and we draw connections to other preservation properties. We present a proof of preservation properties in countable support interations in the so-called Case A that does not need a division into forcings that add reals and those who do not.
Our original aim was, in Abelian group theory to prove the consistency of: lambda is strong limit singular and for some properties of abelian groups which are relatives of being free, the compactness in singular fails. In fact this should work for R-modules, etc. As in earlier cases part of the work is analyzing how to move between the set theory and the algebra. Set theoretically we try to force a universe which satisfies G.C.H. and diamond holds for many stationary sets but, for every regular uncountable lambda, in some sense anything which "may" hold for some stationary set, does hold for some stationary set. More specifically we try to get a universe satisfying GCH such that e.g. for regular kappa < lambda there are pairs (S,B), S \subseteq S^λ_κstationary, B \subseteq H (lambda), which satisfies some pregiven forcing axiom related to (S,B), (so (lambda\ S)-complete, i.e. "trivial outside S) but no more, i.e. slightly stronger versions fail. So set theoretically we try to get a universe satisfying G.C.H. but still satisfies "many", even for a maximal family in some sense, of forcing axioms of the form "for some stationary" while preserving GCH. As completion of the work lagged for a while, here we deal only with the set theory.
We show that in contrast with the Cohen version of Solovay's model, it is consistent for the continuum to be Cohen-measurable and for every function to be continuous on a non-meagre set.
We prove that for any regular kappa and mu > kappa below the first fix point (lambda = aleph_lambda) above kappa, there is a graph with chromatic number > kappa, and mu^kappa nodes but every subgraph of cardinality < mu has chromatic number less than or equal to kappa.
We defined ordered black boxes in which for a partial J we try to predict just a bound in J to a function restricted to Cα. The existence results are closely related to pcf, propagating downward. We can start with trivial cases.
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.
There is much more known about the family of superstable theories when compared to stable theories. This calls for a search of an analogous "super-dependent" characterization in the context of dependent theories. This problem has been treated in \cite{Sh:783,Sh:863}, where the candidates "Strongly dependent", "Strongly dependent^2" and others were considered. These families generated new families when we are considering intersections with the stable family. Here, continuing \cite[§2, §5E,F,G]{Sh:863}, we deal with several candidates, defined using dividing properties and related ranks of types. Those candidates are subfamilies of "Strongly dependent". Fulfilling some promises from \cite{Sh:863} in particular \cite[1.4(4)]{Sh:863}, we try to make this self contained within reason by repeating some things from there. More specifically we fulfil some promises from \cite{Sh:863} to to give more details, in particular: in \S4 for \cite[1.4(4)]{Sh:863}, in \S2 for \cite[5.47(2)=Ldw5.35(2)]{Sh:863} and in \S1 for \cite[5.49(2)]{Sh:863}
In earlier work of the second and third author the equivalence of a finite square principle square^fin_{lambda,D} with various model theoretic properties of structures of size lambda and regular ultrafilters was established. In this paper we investigate the principle square^fin_{lambda,D}, and thereby the above model theoretic properties, at a regular cardinal. By Chang's Two-Cardinal Theorem, square^fin_{lambda,D} holds at regular cardinals for all regular filters D if we assume GCH. In this paper we prove in ZFC that for certain regular filters that we call "doubly^+ regular", square^fin_{lambda,D} holds at regular cardinals, with no assumption about GCH. Thus we get new positive answers in ZFC to Open Problems 18 and 19 in the book "Model Theory" by Chang and Keisler.
It is well-known that every non-isolated point in a compact Hausdorff space is the accumulation point of a discrete subset. Answering a question raised by Z. Szentmiklossy and the first author, we show that this statement fails for countably compact regular spaces, and even for omega-bounded regular spaces. In fact, there are kappa-bounded counterexamples for every infinite cardinal kappa. The proof makes essential use of the so-called 'strong colorings' that were invented by the second author.
We characterize and construct linearly ordered sets, abelian groups and fields that are {\emph symmetrically complete}, meaning that the intersection over any chain of closed bounded intervals is nonempty. Such ordered abelian groups and fields are important because generalizations of Banach's Fixed Point Theorem hold in them. We prove that symmetrically complete ordered abelian groups and fields are divisible Hahn products and real closed power series fields, respectively. We show how to extend any given ordered set, abelian group or field to one that is symmetrically complete. A main part of the paper establishes a detailed study of the cofinalities in cuts.
In this note we prove and disprove some chain conditions in type definable and definable groups in dependent, strongly dependent and strongly^{2} dependent theories.
We define the strong splitting number, prove that it equals s when exists, and put some restrictions on the possibility that s is a singular carcinal.
We investigate the class of models of a general dependent theory. We continue math.LO/0702292 in particular investigating so called "decomposition of types"; thesis is that what holds for stable theory and for Th(Q,<) hold for dependent theories. Another way to say this is: we have to look at small enough neighborhood and use reasonably definable types to analyze a type. We note the results understable without reading. First, a parallel to the "stability spectrum", the "recounting of types", that is assume lambda = lambda^{< lambda} is large enough, M a saturated model of T of cardinality lambda, let bold S_{aut}(M) be the number of complete types over M up to being conjugate, i.e. we identify p,q when some automorphism of M maps p to q . Whereas for independent T the number is 2^lambda, for dependent T the number is <= lambda moreover it is <= | alpha |^{|T|} when lambda = aleph_alpha. Second, for stable theories "lots of indiscernibility exists" a "too good indiscernible existence theorem" saying, e.g. that if the type tp (d_beta ; {d_beta : beta < alpha}) is increasing for alpha < kappa = cf(kappa) and kappa > 2^{|T|} then <d_alpha : alpha in S> is indiscernible for some stationary S subseteq kappa. Third, for stable T,a model is kappa-saturated iff it is aleph_epsilon-saturated and every infinite indiscernible set (of elements) of cardinality < kappa can be increased. We prove here an analog. Fourth, for p in S(M), the number of ultrafilters on the outside definable subsets of M extending p has an absolute bound 2^{|T|} . Restricting ourselves to one phi(x, y), the number is finite, with an absolute found (well depending on T and phi).
We prove that any Boolean algebra with the subsequential completeness property contains an independent family of size continuum. This improves a result of Argyros from the 80ties which asserted the existence of an uncountable independent family. In fact we prove it for a bigger class of Boolean algebras satisfying much weaker properties. It follows that the Stone spaces of all such Boolean algebras contains a copy of the Cech-Stone compactification of the integers and the Banach space of contnuous functions on them has l∞ as a quotient. Connections with the Grothendieck property in Banach spaces are discussed.
An essay on Model Theory: Why am I interested in model theory? What are, in my opinion, the most challenging problems in model theory?
This article continues Rosłanowski and Shelah math.LO/9906024, math.LO/0508272, math.LO/0210205, math.LO/0611131 and math.LO/0605067. We introduce here a new property of <lambda-strategically complete forcing notions which implies that their lambda-support iterations do not collapse lambda^+ (for a strongly inaccessible cardinal lambda).
We reconsider here the following related pcf questions and make some advances: (Q1) concerning the ideal {check I}_kappa [lambda] how much reflection do we have for the bad set S^{bd}_{lambda, kappa} subseteq {delta < lambda : cf(delta)= kappa} assuming it is well defined? (Q2) for an ideal J on kappa how large are S^{bd}_J[f],S^{ch}_J[f] for f=< f_alpha : alpha<lambda > which is <_J-increasing and cofinal in (prod limits_{i< kappa} lambda_i,<_J) ? (Q3) are there somewhat free black boxes?
We deal with incompactness. Assume the existence of non-reflecting stationary set of cofinality kappa . We prove that one can define a graph G whose chromatic number is > kappa, while the chromatic number of every subgraph G' subseteq G,|G'| < |G| is <= kappa . The main case is kappa = aleph_0.
We investigate the behaviour of concepts from dependent theories when applied to real closed fields. Our main focus is on the concept of perpendicular indiscernible sequences, a concept first introduced in section 4 of math.LO/0009056 . This is essentially the MSc. thesis of the first author written under he guidance of the second author.
We continue our investigation on pcf with weak form of choice. Characteristically we assume DC + P(Y) when looking and prod_{s in Y} delta_s. We get more parallel of theorems on pcf.
We prove the consistency of a singular cardinal λ with small value of the ultrafilter number uλ, and arbitrarily large value of 2λ.
We prove that the statement `For all Borel ideals I and J on ω, every isomorphism between Boolean algebras P(ω)/I and P(ω)/J has a continuous representation' is relatively consistent with ZFC. In this model every isomorphism between P(ω)/I and any other quotient P(ω)/J over a Borel ideal is trivial for a number of Borel ideals I on ω. We can also assure that the dominating number is equal to ℵ1 and that 2ℵ1>2ℵ0. Therefore the Calkin algebra has outer automorphisms while all automorphisms of P(ω)/Fin are trivial. Proofs rely on delicate analysis of names for reals in a countable support iteration of suslin proper forcings.
Algebras on the natural numbers and their clones of term operations can be classified according to their descriptive complexity. We give an example of a closed algebra which has only unary operations and whose clone of term operations is not Borel. Moreover, we provide an example of a coatom in the clone lattice whose obvious definition via an ideal of subsets of natural numbers would suggest that it is complete coanalytic, but which turns out to be a rather simple Borel set.
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 bounded arithmetic.
This note gives an informal overview of the proof in our paper "Borel Conjecture and Dual Borel Conjecture", see arXiv:1105.0823.
This paper can be viewed as a continuation of [KS09] that dealt with the automorphism tower problem without Choice. Here we deal with the inequation which connects the automorphism tower and the normalizer tower without Choice and introduce a new proof to a theorem of Fried and Kollár that any group can be represented as an automorphism group of a field. The proof uses a simple construction: working more in graph theory, and less in algebra.
Let c be the cardinality of the continuum. We give a family of pairwise incomparable clones (on a countable base set) 2^c members, all with the same unary fragment, namely the set of all unary operations. We also give, for each n, a family of 2^c clones all with the same n-ary fragment, and all containing the set of all unary operations.
We prove that if there is a dominating family of size ℵ1, then there is are ℵ1 many compact subsets of ωω whose union is a maximal almost disjoint family of functions that is also maximal with respect to infinite partial functions.
How many endomorphisms does a Boolean algebra have? Can we find Boolean algebras with as few endomorphisms as possible? Of course from any ultrafilter of the Boolean algebra we can define an endomorphism, and we can combine finitely many such endomorphisms in some reasonable ways. We prove that in any cardinality lambda=lambda^ {aleph_0} there is a Boolean algebra with no other endomorphisms. For this we use the so called "black boxes", but in a self contained way. We comment on how necessary the restriction on the cardinal is.
Ordinary infinitary languages L_{lambda, kappa} satisfy the Interpolation Theorem only in the case lambda <= {aleph_1}, kappa = {aleph_0}, this include first order logic of course. There are also some pairs of such logics satifying interpolation, e.g. (L_{lambda^+,{aleph_0}}, L_{(2^lambda)^+, lambda^+}) . Does this come from an intermidiate logic satisfying it? Is it nice? unique? We define for kappa = beth_kappa a new logic L^1_kappa such that L_{kappa omega}< L^1_kappa LL_{kappa kappa} and L^1_kappa is very nice; in particular satisfies the Interpolation Theorem. Moreover, L^1_kappa has a model--theoretic characterization in the style of Lindstrom's Theorem in terms of a form of undefinability of well--order. We also define for strong limit kappa of cofinality aleph_0 a logic L^2_{kappa^+} such that L_{kappa^+, {aleph_0}}<L^2_{kappa^+}<L_{kappa^+, kappa} and L^2_{kappa^+} satisfies the Interpolation Theorem.
Our aim is to improve the negative results i.e. non-existence of limit models, and the failure of the generic pair property from math.LO/0609636 to inaccessible lambda as promised there. The motivation is that in [Sh:F756] the positive results are for lambda measurable hence inaccessible, whereas in math.LO/0609636 in the negative results obtained only on non-strong limit cardinals.
We show that there exist two proper creature forcings having a simple (Borel) definition, whose product is not proper. We also give a new condition ensuring properness of some forcings with norms.
This paper investigates a connection between the ordering triangleleft^ast among theories in model theory and the (N)SOP_n hierarchy of Shelah. It introduces two properties which are natural extensions of this hierarchy, called SOP_2 and SOP_1, and gives a strong connection between SOP_1 and the maximality in Keisler ordering. Together with the known results about the connection between the (N)SOP_n hierarchy and the existence of universal models in the absence of GCH, the paper provides a step toward the classification of unstable theories without the strict order property.
Let m>2 be an integer. We show that ZF + "For every integer n, Every countable family of non-empty sets of cardinality at most n has an infinite partial choice function" is not strong enough to prove that every countable set of m-element sets has a choice function. In the case where m=p is prime, to obtain the independence result we make use of a permutation model in which the set of atoms has the structure of a vector space over the field of p elements. When m is non-prime, a suitable permutation model is built from the models used in the prime cases.
We show a general scheme of Ramsey-type results for partitions of countable sets of finite functions, where "one piece is big" is interpreted in the language originating in creature forcing. The heart of our proofs follows Glazer's proof of the Hindman Theorem, so we prove the existence of idempotent ultrafilters with respect to suitable operation. Then we deduce partition theorems related to creature forcings.
We present a method to iterate finitely splitting lim-sup tree forcings along non-wellfounded linear orders. We apply this method to construct a forcing (without using an inaccessible or amalgamation) that makes all definable sets of reals measurable with respect to a certain (non-ccc) ideal.
We show the consistency of: the set of regular cardinals which are the character of some ultrafilter on omega can be quite chaotic, in particular not only can be not convex but can have many gaps. We also deal with the set of pi-characters of ultrafilters on omega.
Assume G.C.H. and kappa is the first uncountable cardinal such that there is a kappa-free abelian group which is not a Whitehead (abelian) group. We prove that kappa is necessarily an inaccessible cardinal
The set of all transformation monoids on a fixed set of infinite cardinality λ, equipped with the order of inclusion, forms a complete algebraic lattice Mon(λ) with 2^λ compact elements. We show that this lattice is universal with respect to closed sublattices, i.e., the closed sublattices of Mon(λ) are, up to isomorphism, precisely the complete algebraic lattices with at most 2^λ compact elements.
In [Sh E46], Shelah obtained a non-forking relation for an AEC, (K,\preceq), with LST-number at most λ, which is categorical in λand λ^+ and has less than 2^{λ^+} models of cardinality λ^{++}, but at least one. This non-forking relation satisfies the main properties of the non-forking relation on stable first order theories, but only a weak version of the local character. Here, we improve this non-forking relation such that it satisfies the local character, too. Therefore it satisfies the main properties of the non-forking relation on superstable first order theories. We conclude that the function λ\to I(λ,K), which assigns to each cardinal λ, the number of models in K of cardinality λ, is not arbitrary.
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. This is a very concise paper. For a self-contained, complete, and extended treatment of the topic see math.GN/0604451
We show that that a certain class of semi-proper iterations does not add omega-sequences. As a result, starting from suitable large cardinals one can obtain a model in which the Continuum Hypothesis holds and every function from omega_1 to omega_1 is bounded by a canonical function on a club, and so omega_1 is the omega_2-nd canonical function.
It is consistent (relative to ZFC) that the union of max{b,g} many families in the Baire space which are not finitely dominating is not dominating. In particular, it is consistent that for each nonprincipal ultrafilter U, the cofinality of the reduced ultrapower w^w/U is greater than max{b,g}. The model is constructed by oracle chain condition forcing, to which we give a self-contained introduction.
For f,g∈ωω let cf,g∀ be the minimal number of uniform g-splitting trees needed to cover the uniform f-splitting tree, i.e., for every branch ν of the f-tree, one of the g-trees contains ν. Let cf,g∃ be the dual notion: For every branch ν, one of the g-trees guesses ν(m) infinitely often. We show that it is consistent that cfε,gε∃=cfε,gε∀=κε for continuum many pairwise different cardinals κε and suitable pairs (fε,gε). For the proof we introduce a new mixed-limit creature forcing construction.
Motivated by the minimal tower problem, an earlier work studied diagonalizations of covers where the covers are related to linear quasiorders (tau-covers). We deal with two types of combinatorial questions which arise from this study. 1. Two new cardinals introduced in the topological study are expressed in terms of well known cardinals characteristics of the continuum. 2. We study the additivity numbers of the combinatorial notions corresponding to the topological diagonalization notions. This gives new insights on the structure of the eventual dominance ordering on the Baire space, the almost inclusion ordering on the Rothberger space, and the interactions between them.
We prove, e.g., that if lambda=chi^+=2^chi and S subseteq {delta<lambda:cf(delta) neq cf(chi)} is stationary then diamondsuit_lambda holds true.
Let K be an abstract elementary class of models. Assume that there are less than the maximal number of models in K_{λ^{+n}} (namely models in K of power λ^{+n}) for all n. We provide conditions on K_λ, that imply the existence of a model in K_{λ^{+n}} for all n. We do this by providing sufficiently strong conditions on K_λ, that they are inherited by a properly chosen subclass of K_{λ^+}.
We consider the random graph M^n_{\bar{p}} on the set [n], were the probability of {x,y} being an edge is p_{|x-y|}, and \bar{p}=(p_1,p_2,p_3,...) is a series of probabilities. We consider the set of all \bar{q} derived from \bar{p} by inserting 0 probabilities to \bar{p}, or alternatively by decreasing some of the p_i. We say that \bar{p} hereditarily satisfies the 0-1 law if the 0-1 law (for first order logic) holds in M^n_{\bar{q}} for any \bar{q} derived from \bar{p} in the relevant way described above. We give a necessary and sufficient condition on \bar{p} for it to hereditarily satisfy the 0-1 law.
We prove in ZF that there is an inner product space, in fact, nicely definable with no orthonormal basis.
Our main theorem is about iterated forcing for making the continuum larger than aleph_2. We present a generalization of math.LO/0303294 which is dealing with oracles for random, etc., replacing aleph_1, aleph_2 by lambda,lambda^+ (starting with lambda=lambda^{<lambda}>aleph_1). Well, instead of properness we demand absolute c.c.c. So we get, e.g. the continuum is lambda^+ but we can get cov(meagre)=lambda. We give some applications. As in math.LO/0303294, it is a "partial" countable support iteration but it is c.c.c.
Answering a question of Juhasz, Soukup and Szentmiklóssy we show that it is consistent that some first countable space of uncountable weight does not contain an uncountable subspace which has an irreducible base.
We introduce several properties of forcing notions which imply that their lambda-support iterations are lambda-proper. Our methods and techniques refine those studied in math.LO/9906024, math.LO/0210205, math.LO/0508272 and math.LO/0605067, covering some new forcing notions (though the exact relation of the new properties to the old ones remains undecided).
We throw some light on the question: is there a MAD family (= a family of infinite subsets of N, the intersection of any two is finite) which is completely separable (i.e. any X subseteq N is included in a finite union of members of the family or include a member of the family). We prove that it is hard to prove the consistency of the negation: (a) if 2^{aleph_0} < aleph_omega, then there is such a family (b) if there is no such families then some situation related to pcf holds whose consistency is large.
We investigate the pressing down game and its relation to the Banach Mazur game. In particular we show: Consistently, there is a nowhere precipitous normal ideal I on ℵ2 such that player nonempty wins the pressing down game of length ℵ1 on I even if player empty starts.
A 27 years old and still open problem of Juhasz and van Mill asks whether there exists a cardinal kappa such that every regular dense in itself countably compact space has a dense in itself subset of cardinality at most kappa. We give a negative answer for the analogous question where_regular_ is weakened to_Hausdorff_, and_coutnably compact_ is strengthened to_sequentially compact_.
We prove that e.g. there is no omega_4-sequence in (omega_3)^{omega_3} increasing modulo the ideal of countable sets.
We deal with relatives of GCH which are provable. In particular we deal with rank version of the revised GCH. Our motivation was to find such results when only weak versions of the axiom of choice are assumed but some of the results gives us additional information even in ZFC.
We continue investigations of reasonable ultrafilters on uncountable cardinals defined in math.LO/0407498. We introduce stronger properties of ultrafilters and we show that those properties may be handled in lambda-support iterations of reasonably bounding forcing notions. We use this to show that consistently there are reasonable ultrafilters on an inaccessible cardinal lambda with generating system of size less than 2^lambda . We also show how reasonable ultrafilters can be killed by forcing notions which have enough reasonable completeness to be iterated with lambda-supports (and we show the appropriate preservation theorem).
Answering a problem of Eklof and Mekler, we show that there is a reflexive group of cardinality >= first measurable.
Working in the context of restricted forms of the Axiom of Choice, we consider the problem of splitting the ordinals below λ of cofinality θ into λ many stationary sets, where θ<λ are regular cardinals. This is a continuation of \cite{Sh835}.
Using the Continuum Hyporthesis, we prove that there is a Menger-bounded (also called o-bounded) subgroup of the Baer-Specker group Z^N, whose square is not Menger-bounded. This settles a major open problem concerning boundedness notions for groups, and implies that Menger-bounded groups need not be Scheepers-bounded. This also answers some questions of Banakh, Nickolas, and Sanchis.
We solve four out of the six open problems concerning critical cardinalities of topological diagonalization properties involving tau-covers, show that the remaining two cardinals are equal, and give a consistency result concerning this remaining cardinal. Consequently, 21 open problems concerning potential implications between these properties are settled. We also give structural results based on the combinatorial techniques.
The \emph{stationary set splitting game} is a game of perfect information of length ω1 between two players, \unspls and \spl, in which \unspls chooses stationarily many countable ordinals and \spls tries to continuously divide them into two stationary pieces. We show that it is possible in ZFC to force a winning strategy for either player, or for neither. This gives a new counterexample to Σ22 maximality with a predicate for the nonstationary ideal on ω1, and an example of a consistently undetermined game of length ω1 with payoff definable in the second-order monadic logic of order. We also show that the determinacy of the game is consistent with Martin's Axiom but not Martin's Maximum.
For cardinals lambda, kappa, theta we consider the class of graphs of cardinality lambda which has no subgraph which is (kappa, theta)-complete bipartite graph. The question is whether in such a class there is a universal one under (weak) embedding. We solve this problem completely under GCH. Under various assumptions mostly related to cardinal arithmetic we prove nonexistence of universals for this problem and some related ones.
A subset of a topological space is said to be \emph{universally measurable} if it is measured by the completion of each countably additive σ-finite Borel measure on the space, and \emph{universally null} if it has measure zero for each such atomless measure. In 1908, Hausdorff proved that there exist universally null sets of real numbers of cardinality ℵ1, and thus that there exist at least 2ℵ1 such sets. Laver showed in the 1970's that consistently there are just continuum many universally null sets of reals. The question of whether there exist more than continuum many universally measurable sets of reals was asked by Mauldin in 1978. We show that consistently there exist only continuum many universally measurable sets. This result also follows from work of Ciesielski and Pawlikowski on the iterated Sacks model. In the models we consider (forcing extensions by suitably-sized random algebras) every set of reals is universally measurable if and only if it and its complement are unions of ground model continuum many Borel sets.
Suppose we are given a family of choice functions on pairs from a given finite set. The set is considered as a set of alternatives (say candidates for an office) and the functions as potential "voters". The question is, what choice functions agree, on every pair, with the majority of some finite subfamily of the voters? For the problem as stated, a complete characterization was given in \citet{shelah2009mdp}, but here we allow each voter to abstain. There are four cases.
There is a proper countable support iteration of length ω adding no new reals at finite stages and adding a Sacks real in the limit.
For $f,g\inω\ho$ let $\mycfa_{f,g}$ be the minimal number of uniform g-splitting trees needed to cover the uniform f-splitting tree, i.e. for every branch ν of the f-tree, one of the g-trees contains ν. $\myc_{f,g}$ is the dual notion: For every branch ν, one of the g-trees guesses ν(m) infinitely often. It is consistent that $\myc_{f_ε,g_ε}=\mycfa_{f_ε,g_ε}=κ_ε$ for $\al1$ 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.
We prove a Theorem about the relationship between the Depth of the ultraproduct of Boolean algebras, divided by an ultrafilter, and the products of the depths of each component. This answers (partly) an open problem of Monk.
We continue investigations of reasonable ultrafilters on uncountable cardinals defined in Shelah math.LO/0407498 and studied also in math.LO/0605067. We introduce a general scheme of generating a filter on lambda from filters on smaller sets and we investigate the combinatorics of objects obtained this way.
There are Noetherian rings (in fact domains) with a free additive group, in every infinite cardinality. (This is an expanded version of [SgSh:217] which appears in the Abstracts of the American Mathematical Society 7 (1986): 369.)
We show that it is consistent with ordinary set theory ZFC and the generalized continuum hypothesis that there exist two separable abelian groups of cardinality aleph_1 which are filtration equivalent and one is a Whitehead group but the other is not. This solves one of the open problems of Eklof and Mekler.
Solovay's random-real forcing (1971) is the standard way of producing real-valued measurable cardinals. Following questions of Fremlin, by giving a new construction, we show that there are combinatorial, measure-theoretic properties of Solovay's model that do not follow from the existence of real-valued measurability.
We introduce more properties of forcing notions which imply that their lambda-support iterations are lambda-proper, where lambda is an inaccessible cardinal. This paper is a direct continuation of section A.2 of math.LO/0210205. As an application of our iteration result we show that it is consistent that dominating numbers associated with two normal filters on lambda are distinct.
It is shown to be consistent with set theory that the uniformity invariant for Lebesgue measure is strictly greater than the corresponding invariant for Hausdorff r-dimensional measure where 0<r<1.
We continue investigations of forcing notions with strong ccc properties introducing new methods of building sweet forcing notions. We also show that quotients of topologically sweet forcing notions over Cohen reals are topologically sweet while the quotients over random reals do not have to be such.
The main result of this paper is a partial answer to [math.LO/9909115, Problem 5.5]: a finite iteration of Universal Meager forcing notions adds generic filters for many forcing notions determined by universality parameters. We also give some results concerning cardinal characteristics of the sigma-ideals determined by those universality parameters.
Using forcing with measured creatures we build a universe of set theory in which: (a) every sup-measurable function f:RxR-->R is measurable, and (b) every function f:R-->R is continuous on a non-measurable set. This answers a question of Balcerzak, Ciesielski and Kharazishvili and von Weizsacker's problem (see Fremlin's list of problems).
We develop the theory of the forcing with trees and creatures for an inaccessible lambda continuing Rosłanowski and Shelah math.LO/9807172, math.LO/9909115. To make a real use of these forcing notions (that is to iterate them without collapsing cardinals) we need suitable iteration theorems, and those are proved as well. (In this aspect we continue Rosłanowski and Shelah math.LO/9906024.)
We show that the reduced cofinality of the nonstationary ideal NS_kappa on a regular uncountable cardinal kappa may be less than its cofinality, where the reduced cofinality of NS_kappa is the least cardinality of any family F of nonstationary subsets of kappa such that every nonstationary subset of kappa can be covered by less than κ many members of F.
We prove the following two results. Theorem A: Let alpha be a limit ordinal. Suppose that 2^{|alpha|}<aleph_alpha and 2^{|alpha|^+}<aleph_{|alpha|^+}, whereas aleph_alpha^{|alpha|}>aleph_{|alpha|^+}. Then for all n< omega and for all bounded X subset aleph_{|alpha|^+}, M_n^#(X) exists. Theorem B: Let kappa be a singular cardinal of uncountable cofinality. If {alpha<kappa| 2^alpha=alpha^+} is stationary as well as co-stationary then for all n< omega and for all bounded X subset kappa, M_n^#(X) exists. Theorem A answers a question of Gitik and Mitchell, and Theorem B yields a lower bound for an assertion discussed in Gitik, M., Introduction to Prikry type forcing notions, in: Handbook of set theory, Foreman, Kanamori, Magidor (see Problem 4 there). The proofs of these theorems combine pcf theory with core model theory. Along the way we establish some ZFC results in cardinal arithmetic, motivated by Silver's theorem and we obtain results of core model theory, motivated by the task of building a ``stable core model.'' Both sets of results are of independent interest.
The maximality of Abelian subgroups play a role in various parts of group theory. For example, Mycielski has extended a classical result of Lie groups and shown that a maximal Abelian subgroup of a compact connected group is connected and, furthermore, all the maximal Abelian subgroups are conjugate. For finite symmetric groups the question of the size of maximal Abelian subgroups has been examined by Burns and Goldsmith in 1989 and Winkler in 1993. We show that there is not much interest in generalizing this study to infinite symmetric groups; the cardinality of any maximal Abelian subgroup of the symmetric group of the integers is 2^{aleph_0}. Our purpose is also to examine the size of maximal Abelian subgroups for a class of groups closely related to the the symmetric group of the integers; these arise by taking an ideal on the integers, considering the subgroup of all permutations which respect the ideal and then taking the quotient by the normal subgroup of permutations which fix all integers except a set in the ideal. We prove that the maximal size of Abelian subgroups in such groups is sensitive to the nature of the ideal as well as various set theoretic hypotheses.
We generalize the main result of math.RA/9608214 concerning the convex embeddings of a chain Gamma in a lexicographic power Delta^Gamma. For a fixed nonempty chain Delta, we derive necessary and sufficient conditions for the existence of nonempty solutions Gamma to each of the lexicographic functional equations (Delta^Gamma)^{<=0} simeq Gamma, (Delta^Gamma) simeq Gamma, and (Delta^Gamma)^{<0} simeq Gamma.
We look for a parallel to the notion of ``proper forcing'' among lambda-complete forcing notions not collapsing lambda^+ . We suggest such a definition and prove that it is preserved by suitable iterations.
Let T be an abelian group and lambda an uncountable regular cardinal. We consider the question of whether there is a lambda-universal group G^* among all torsion-free abelian groups G of cardinality less than or equal to lambda satisfying Ext(G,T)=0. Here G^* is said to be lambda-universal for T if, whenever a torsion-free abelian group G of cardinality less than or equal to lambda satisfies Ext(G,T)=0, then there is an embedding of G into G^*. For large classes of abelian groups T and cardinals lambda it is shown that the answer is consistently no. In particular, for T torsion, this solves a problem of Kulikov.
The present paper has three themes. First, we continue the investigations started in Judah, Roslanowski and Shelah \math.LO/9310224 and Roslanowski and Shelah math.LO/9807172, math.LO/9703222, and we investigate the method of norms on possibilities in the context of ccc forcing notions, getting a number of constructions of nicely definable ccc forcings. The second theme of the paper is a part of the general program ``how special are random and Cohen forcing notions (or: the respective ideals)''. Shelah math.LO/9303208 shows that the two forcing notions may occupy special positions in the realm of nicely definable forcing notions. In this realm we may classify forcing notions using the methods of Shelah [Sh:630] (math.LO/9712283), [Sh:669] and, for example, declare that very Souslin (or generally omega-nw-nep) ccc forcing notions are really nice. Both the Cohen forcing notion and the random forcing notion and their FS iterations (and nice subforcings) are all ccc omega-nw-nep, and Problem 4.24 of math.LO/9906113 asked if we have more examples. It occurs that our method relatively easily results in very Souslin ccc forcing notions. The third theme is Sweet & Sour, and it is related to one of the most striking differences between the random and the Cohen forcing notions that appears when we consider the respective regularity properties of projective sets: the Lebesgue measurability of Sigma^1_3 sets implies aleph_1 is inaccessible in L, while one can construct (in ZFC) a forcing notion P which forces ``projective subsets of R have the Baire property'' (see Shelah [Sh:176]).
We investigate the structure of the lattice of clones on an infinite set X. We first observe that ultrafilters naturally induce clones; this yields a simple proof of Rosenberg's theorem: "there are 2^2^kappa many maximal (=precomplete) clones on a set of size kappa." The clones we construct here do not contain all unary functions. We then investigate clones that do contain all unary functions. Using a strong negative partition theorem we show that for many cardinals kappa there are 2^2^kappa many such clones on a set of size kappa. Finally, we show that on a weakly compact cardinal there are exactly 2 maximal clones which contain all unary functions.
The present paper addresses the problem of attainment of the supremums in various equivalent definitions of hereditary density hd and hereditary Lindelof degree hL of Boolean algebras. We partially answer two problems of J. Donald Monk (Problems 50 and 54 in his book "Cardinal Invariants on Boolean Algebras), showing consistency of different attainment behaviour and proving that (for the considered variants) this is the best result we can expect.
We show that, consistently, for some regular cardinals theta<lambda, there exists a Boolean algebra B such that B=lambda^+ and for every subalgebra B' of B of size lambda^+ we have Depth(B')=theta.
If G and X are groups and N is a normal subgroup of X, then the G-closure of N in X is the normal subgroup X^G= bigcap{kerphi|phi:X-> G, with N subseteq kerphi} of X . In particular, 1^G = R_G X is the G-radical of X. Plotkin calls two groups G and H geometrically equivalent, written G H, if for any free group F of finite rank and any normal subgroup N of F the G-closure and the H-closure of N in F are the same. Quasiidentities are formulas of the form (bigwedge_{i<=n}w_i=1 -> w =1) for any words w, w_i (i<=n) in a free group. Generally geometrically equivalent groups satisfy the same quasiidentiies. Plotkin showed that nilpotent groups G and H satisfy the same quasiidenties if and only if G and H are geometrically equivalent. Hence he conjectured that this might hold for any pair of groups. We provide a counterexample.
We will prove that there exists a model of ZFC+``c= omega_2'' in which every M subseteq R of cardinality less than continuum c is meager, and such that for every X subseteq R of cardinality c there exists a continuous function f:R-> R with f[X]=[0,1]. In particular in this model there is no magic set, i.e., a set M subseteq R such that the equation f[M]=g[M] implies f=g for every continuous nowhere constant functions f,g:R-> R .
We investigate the Whiteheadness of Borel abelian groups (aleph_1-free, wlog, as otherwise this is trivial). We show that CH (and even WCH) implies any such abelian group is free, and always aleph_2-free.
Let K be an abstract elementary class with amalgamation, and Lowenheim Skolem number LS(K). We prove that for a suitable Hanf number chi_0 if chi_0 < lambda_0 <= lambda_1, and K is categorical in lambda^+_1 then it is categorical in lambda_0 .
We investigate categoricity of abstract elementary classes without any remnants of compactness (like non-definability of well ordering, existence of E.M. models or existence of large cardinals). We prove (assuming a weak version of GCH around lambda) that if K is categorical in lambda, lambda^+, LS(K) <= lambda and 1 <= I(lambda^{++},K)< 2^{lambda^{++}} then K has a model in lambda^{+++} .
We prove that it is consistent that the covering of the ideal of measure zero sets has countable cofinality.
We address several questions of Donald Monk related to irredundance and spread of Boolean algebras, gaining both some ZFC knowledge and consistency results. We show in ZFC that irr(B_0 times B_1)= max(irr(B_0),irr(B_1)). We prove consistency of the statement ``there is a Boolean algebra B such that irr(B)<s(B otimes B)'' and we force a superatomic Boolean algebra B_* such that s(B_*)=inc(B_*)=kappa, irr(B_*)=Id(B_*)=kappa^+ and Sub(B_*)=2^(kappa^+). Next we force a superatomic algebra B_0 such that irr(B_0)<inc(B_0) and a superatomic algebra B_1 such that t(B_1)>Aut(B_1). Finally we show that consistently there is a Boolean algebra B of size lambda such that there is no free sequence in B of length lambda, there is an ultrafilter of tightness lambda (so t(B)=lambda) and lambda notin Depth_(Hs)(B).
We present a systematic study of the method of "norms on possibilities" of building forcing notions with keeping their properties under full control. This technique allows us to answer several open problems, but on our way to get the solutions we develop various ideas interesting per se.These include a new iterable condition for ``not adding Cohen reals'' (which has a flavour of preserving special properties of p-points), new intriguing properties of ultrafilters (weaker than being Ramsey but stronger than p-point) and some new applications of variants of the PP--property.
We deal with (< kappa)-supported iterated forcing notions which are (E_0,E_1)-complete, have in mind problems on Whitehead groups, uniformizations and the general problem. We deal mainly with the successor of a singular case. This continues [Sh:587]. We also deal with complimentary combinatorial results.
We discuss some problems posed by Ciesielski. For example we show that, consistently, d_c is a singular cardinal and e_c<d_c. Next we prove that the Martin Axiom for sigma --centered forcing notions implies that for every function f:R^2 ---> R there are functions g_n,h_n:R ---> R, n< omega, such that f(x,y)= sum_{n=0}^{infty} g_n(x)h_n(y). Finally, we deal with countably continuous functions and we show that in the Cohen model they are exactly the functions f with the property that (for all U in [R]^{aleph_1})(exists U^* in [U]^{aleph_1}) (f restriction U^* is continuous).
We study several cardinal, and ordinal--valued functions that are relatives of Hanf numbers. Let kappa be an infinite cardinal, and let T subseteq L_{kappa^+, omega} be a theory of cardinality <= kappa, and let gamma be an ordinal >= kappa^+. For example we look at (1) mu_{T}^*(gamma, kappa):= min {mu^* for all phi in L_{infinity, omega}, with rk(phi)< gamma, if T has the (phi, mu^*)-order property then there exists a formula phi'(x;y) in L_{kappa^+, omega}, such that for every chi >= kappa, T has the (phi', chi)-order property}; and (2) mu^*(gamma, kappa):= sup{mu_T^*(gamma, kappa)| T in L_{kappa^+,omega}}.
Suppose lambda is a singular cardinal of uncountable cofinality kappa. For a model M of cardinality lambda, let No(M) denote the number of isomorphism types of models N of cardinality lambda which are L_{infty lambda}-equivalent to M. In [Sh:189] inverse kappa-systems A of abelian groups and their certain kind of quotient limits Gr(A)/Fact(A) were considered. It was proved that for every cardinal mu there exists an inverse kappa-system A such that A consists of abelian groups having cardinality at most mu^kappa and card(Gr(A)/Fact(A))= mu. In [Sh:228] a strict connection between inverse kappa-systems and possible values of No was proved. In this paper we show: for every nonzero mu <= lambda^kappa there is an inverse kappa-system A of abelian groups having cardinality < lambda such that card(Gr(A)/Fact(A))= mu (under the assumptions 2^kappa < lambda and theta^{< kappa}< lambda for all theta < lambda when mu > lambda), with the obvious new consequence concerning the possible value of No. Specifically, the case No(M)= lambda is possible when theta^kappa < lambda for every theta < lambda.
We consider a finite universe U (more exactly - a family U of them) and second order quantifiers Q_K, where for each U this means quantifying over a family of n(K)-place relations closed under permuting U. We define some natural orders and shed some light on the classification problem of those quantifiers.
Based on computer simulations Wolfram presented in several papers conjectured classifications of cellular automata into 4 types. He distinguishes the 4 classes of cellular automata by the evolution of the pattern generated by applying a cellular automaton to a finite input. Wolfram's qualitative classification is based on the examination of a large number of simulations. In addition to this classification based on the rate of growth, he conjectured a similar classification according to the eventual pattern. We consider here one formalization of his rate of growth suggestion. After completing our major results (based only on Wolfram's work), we investigated other contributions to the area and we report the relation of some of them to our discoveries.
Assume V=L and lambda is regular smaller than the first weakly compact cardinal. Under those circumstances and with arbitrary requirements on the structure of Ext(G,Z) (under well known limitations), we construct an abelian group G of cardinality lambda such that for no G' subseteq G, |G'|< lambda is G/G' free and Ext(G,Z) realizes our requirements.
We introduce a large cardinal property which is consistent with L and show that for every superatomic Boolean algebra B and every cardinal lambda with the large cardinal property, if tightness^+(B) >= lambda^+, then depth (B) >= lambda. This improves a theorem of Dow and Monk.
We deal with several pcf problems; we characterize another version of exponentiation: number of kappa-branches in a tree with lambda nodes, deal with existence of independent sets in stable theories, possible cardinality of ultraproduct, the depth of ultraproducts of Boolean Algebras. Also we give cardinal invariant for each lambda with pcf restriction and investigate further T_D(f) .
The original theme of the paper is the existence proof of ``there is < eta_alpha : alpha < lambda > which is a (lambda,J)-sequence for < I_i:i<delta >, a sequence of ideals. This can be thought of as in a generalization to Luzin sets and Sierpinski sets, but for the product prod_{i< delta} Dom(I_i), the existence proofs are related to pcf. The second theme is when does a Boolean algebra B has free caliber lambda (i.e. if X subseteq B and |X|= lambda, then for some Y subseteq X with |Y|= lambda and Y is independent). We consider it for B being a Maharam measure algebra, or B a (small) product of free Boolean algebras, and kappa-cc Boolean algebras. A central case lambda = (beth_omega)^+ or more generally, lambda = mu^+ for mu strong limit singular of ``small'' cofinality. A second one is mu = mu^{< kappa}< lambda < 2^mu ; the main case is lambda regular but we also have things to say on the singular case. Lastly, we deal with ultraproducts of Boolean algebras in relation to irr(-) and s(-) etc.
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 orders which we call pseudo-product. Using such products, we give several generic extensions where some of these principles hold together with not 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 omega_1 together with not CH and Martin's Axiom for countable p.o.-sets.
A usual dichotomy is that in many cases, reasonably definable sets, satisfy the CH, i.e. if they are uncountable they have cardinality continuum. A strong dichotomy is when: if the cardinality is infinite it is continuum as in [Sh:273]. We are interested in such phenomena when lambda = aleph_0 is replaced by lambda regular uncountable and also by lambda = beth_omega or more generally by strong limit of cofinality aleph_0 .
A combinatorial principle CECA is formulated and its equivalence with GCH+ certain weakenings of Box_lambda for singular lambda is proved. CECA is used to show that certain ``almost point- < tau'' families can be refined to point- < tau families by removing a small set from each member of the family. This theorem in turn is used to show the consistency of ``every first countable T_1-space with a weakly uniform base has a point-countable base.''
Generalizing [ShSi:494], for every n< omega we construct a ZFC-model where the distributivity number of r.o. (P(omega)/fin)^{n+1}, h(n+1), is smaller than the one of r.o.(P(omega)/fin)^{n}. This answers an old problem of Balcar, Pelant and Simon. We also show that Laver and Miller forcing collapse the continuum to h(n) for every n<omega, hence by the first result, consistently they collapse it below h(n)
We argue that we solved Hilbert's first problem positively (after reformulating it just to avoid the known consistency results) and give some applications. Let lambda to the revised power of kappa, denoted lambda^{[kappa]}, be the minimal cardinality of a family of subsets of lambda each of cardinality kappa such that any other subset of lambda of cardinality kappa is included in the union of <kappa members of the family. The main theorem says that almost always this revised power is equal to lambda. Our main result is The Revised GCH Theorem: Assume we fix an uncountable strong limit cardinal mu (i.e., mu>aleph_0, (for all theta<mu)(2^theta<mu)), e.g. mu=beth_omega. Then for every lambda >= mu for some kappa<mu we have: (a) kappa <= theta < mu => lambda^{[theta]}= lambda and (b) there is a family P of lambda subsets of lambda each of cardinality < mu such that every subset of lambda of cardinality mu is equal to the union of < kappa members of P .
We consider the following property: (*) For every function f from R^2 to R there are functions g_n,h_n from R to R (for n<omega) such that for all real numbers x and y, f(x,y) = sum_{n<omega} g_n(x)h_n(y). We show that, despite some expectation suggested by [Sh:675], (*) does not imply MA(sigma-centered). Next, we introduce cardinal characteristics of the continuum responsible for the failure of (*).
The goal of this note is to construct a uniformly antisymmetric function f:R-> R with a bounded countable range. This answers Problem 1(b) of Ciesielski and Larson. (See also list of problems in Thomson and Problem 2(b) from Ciesielski's survey.) A problem of existence of uniformly antisymmetric function f:R-> R with finite range remains open.
We apply model theoretic methods to the problem of existence of countable universal graphs with finitely many forbidden connected subgraphs. We show that to a large extent the question reduces to one of local finiteness of an associated''algebraic closure'' operator. The main applications are new examples of universal graphs with forbidden subgraphs and simplified treatments of some previously known cases.
It is consistent that there is a partial order (P,<) of size aleph_1 such that every monotone (unary) function from P to P is first order definable in (P,<). The partial order is constructed in an extension obtained by finite support iteration of Cohen forcing. The main points is that (1) all monotone functions from P to P will (essentially) have countable range (this uses a Delta-system argument) and (2) that all countable subsets of P will be first order definable, so we have to code these countable sets into the partial order. Amalgamation of finite structures plays an essential role.
We address ZFC inequalities between some cardinal invariants of the continuum, which turned to be true in spite of strong expectations given by [RoSh:470].
We deal with some of problems posed by Monk and related to cardinal invariant of ultraproducts of Boolean algebras. We also introduce and investigate some new cardinal invariants.
It is shown that there exists a complete, atomless, sigma-centered Boolean algebra, which does not contain any regular countable subalgebra if and only if there exist a nowhere dense ultrafilter. Therefore the existence of such algebras is undecidable in ZFC.
This paper is concerned with certain generalizations of meagreness and their combinatorial equivalents. The simplest example, and the one which motivated further study in this area, comes about by considering the following definition: a set X subseteq R is said to be Q-nowhere dense if and only if for every rational q there exists and integer k such that the interval whose endpoints are q and q+1/k is disjoint from X. A set which is the union of countably many Q-nowhere dense sets will be called Q-very meagre. Steprans considered the least number of Q-meagre sets required to cover the real line and denoted by d_1. He showed that there is a continuous function H --- first constructed by Lebesgue --- such that the least number of smooth functions into which H can be decomposed is equal to d_1. This paper will further study d_1 and some of its generalizations. As well, an equivalence will be established between Q-meagreness and certain combinatorial properties of trees. This will lead to new cardinal invariants and various independence results about these will then be established.
Affirming a conjecture of Erdős and Renyi we prove that for any (real number) c_1>0 for some c_2>0, if a graph G has no c_1(log n) nodes on which the graph is complete or edgeless (i.e. G exemplifies |G| not-> (c_1 log n)^2_2) then G has at least 2^{c_2n} non-isomorphic (induced) subgraphs.
We present two different types of models where, for certain singular cardinals lambda of uncountable cofinality, lambda -> (lambda, omega+1)^2, although lambda is not a strong limit cardinal. We announce, here, and will present in a subsequent paper, that, for example, consistently, aleph_{omega_1} not-> (aleph_{omega_1}, omega+1)^2 and consistently, 2^{aleph_0} not-> (2^{aleph_0},omega +1)^2 .
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, and use just one simple lemma from there. Originally entangledness was introduced in order to get narrow Boolean algebras and examples of the nonmultiplicativity of c.c-ness. These applications became marginal when the hope to extract new such objects or strong colourings were not materialized, but after the pcf constructions which made their debut in [Sh:g] it seems that this notion gained independence. Generally we aim at characterizing the existence strong and weak entangled orders in cardinal arithmetic terms. In [Sh462] necessary conditions were shown for strong entangledness which in a previous version was erroneously proved to be equivalent to plain entangledness. In section 1 we give a forcing counterexample to this equivalence and in section 2 we get those results for entangledness (certainly the most interesting case). In section 3 we get weaker results for positively entangledness, especially when supplemented with the existence of a separating point. An antipodal case is defined and completely characterized. Lastly we outline a forcing example showing that these two subcases of positive entangledness comprise no dichotomy.
We prove in ZFC that for mu >= aleph_2 there is a sigma --ideal I on mu and a Boolean sigma --subalgebra B of the family of subsets of mu which includes I such that the natural homomorphism from B onto B/I cannot be lifted.
We present reasons for developing a theory of forcing notions which satisfy the properness demand for countable models which are not necessarily elementary submodels of some (H(chi), in). This leads to forcing notions which are ``reasonably'' definable. We present two specific properties materializing this intuition: nep (non-elementary properness) and snep (Souslin non-elementary properness). For this we consider candidates (countable models to which the definition applies), and the older Souslin proper. A major theme here is ``preservation by iteration'', but we also show a dichotomy: if such forcing notions preserve the positiveness of the set of old reals for some naturally define c.c.c. ideals, then they preserve the positiveness of any old positive set. We also prove that (among such forcing notions) the only one commuting with Cohen is Cohen itself.
We use the method of norms on possibilities to answer a question of Kunen and construct a ccc sigma --ideal on 2^omega with various closure properties and distinct from the ideal of null sets, the ideal of meager sets and their intersection.
We deal with the problem of preserving various versions of completeness in (< kappa) --support iterations of forcing notions, generalizing the case ``S --complete proper is preserved by CS iterations for a stationary co-stationary S subseteq omega_1''. We give applications to Uniformization and the Whitehead problem. In particular, for a strongly inaccessible cardinal kappa and a stationary set S subseteq kappa with fat complement we can have uniformization for < A_delta : delta in S'>, A_delta subseteq delta = sup A_delta, cf(delta)=otp(A_delta) and a stationary non-reflecting set S' subseteq S .
The Kalikow problem for a pair (lambda, kappa) of cardinal numbers, lambda > kappa (in particular kappa =2) is whether we can map the family of omega --sequences from lambda to the family of omega --sequences from kappa in a very continuous manner. Namely, we demand that for eta, nu in lambda^omega we have: eta, nu are almost equal if and only if their images are. We show consistency of the negative answer e.g. for aleph_omega but we prove it for smaller cardinals. We indicate a close connection with the free subset property and its variants.
If L is an order polynomially complete lattice, (that is: every monotone function from L^n to L is induced by a lattice-theoretic polynomial) then the cardinality of L is a strongly inaccessible cardinal. In particular, the existence of such lattices is not provable in ZFC, nor from ZFC+GCH. Although the problem originates in algebra, the proof is purely set-theoretical. The main tools are partition and canonisation theorems. It is still open if the existence of infinite o.p.c. lattices can be refuted in ZFC.
We continue the works of Gurevich-Shelah and Lifsches-Shelah by showing that it is consistent with ZFC that the first-order theory of random graphs is not interpretable in the monadic theory of all chains. It is provable from ZFC that the theory of random graphs is not interpretable in the monadic second order theory of short chains (hence, in the monadic theory of the real line).
Let K^0_lambda be the class of structures < lambda,<,A>, where A subseteq lambda is disjoint from a club, and let K^1_lambda be the class of structures < lambda,<,A>, where A subseteq lambda contains a club. We prove that if lambda = lambda^{< kappa} is regular, then no sentence of L_{lambda^+ kappa} separates K^0_lambda and K^1_lambda. On the other hand, we prove that if lambda = mu^+, mu = mu^{< mu}, and a forcing axiom holds (and aleph_1^L= aleph_1 if mu = aleph_0), then there is a sentence of L_{lambda lambda} which separates K^0_lambda and K^1_lambda .
We show that the assumption lambda > kappa^+ in the Trichotomy Theorem cannot be relaxed to lambda > kappa .
The Mycielski ideal M_k is defined to consist of all sets A subseteq k^omega such that {f restriction X: f in A} not= k^X for all X in [omega]^{aleph_0}. It will be shown that the covering numbers for these ideals are all equal. However, the covering numbers of the closely associated Roslanowski ideals will be shown to be consistently different.
For a free ultrafilter U on omega we study several cardinal characteristics which describe part of the combinatorial structure of U. We provide various consistency results; e.g. we show how to force simultaneously many characters and many pi --characters. We also investigate two ideals on the Baire space omega^omega naturally related to U and calculate cardinal coefficients of these ideals in terms of cardinal characteristics of the underlying ultrafilter.
We prove for any mu = mu^{< mu}< theta < lambda, lambda large enough (just strongly inaccessible Mahlo) the consistency of 2^mu = lambda-> [theta]^2_3 and even 2^mu = lambda-> [theta]^2_{sigma,2} for sigma < mu . The new point is that possibly theta > mu^+ .
We give some general criteria, when kappa-complete forcing preserves largeness properties -- like kappa-presaturation of normal ideals on lambda (even when they concentrate on small cofinalities). Then we quite accurately obtain the consistency strength ``NS_lambda is aleph_1-preserving'', for lambda > aleph_2 .
After the main gap theorem was proved (see [Sh:c]), in discussion, Harrington expressed a desire for a finer structure - of finitary character (when we have a structure theorem at all). I point out that the logic L_{infty,aleph_0}(d.q.) (d.q. stands for dimension quantifier) does not suffice: e.g., for T=Th(lambda x 2^ω,E_n)_{n<omega} where (alpha,eta)E_n(beta,nu) =: eta|n=nu|n and for a subset S of 2^omega we define M_S = M | {(alpha,eta): [eta in S -> alpha<omega_1] and [eta in 2^ωbackslash S -> alpha<omega]}. Hence, it seems to me we should try L_{infty,aleph_epsilon}(d.q.) (essentially, in C we can quantify over sets which are included in the algebraic closure of finite sets), and Harrington accepts this interpretation. Here the conjecture is proved for aleph_epsilon-saturated models. I.e., the main theorem is M equiv_{L_{infty,aleph_epsilon}(d.q.)} N iff M cong N for aleph_epsilon--saturated models of a superstable countable (first order) theory T without dop.
Let 0<n^*< omega and f:X-> n^*+1 be a function where X subseteq omega backslash (n^*+1) is infinite. Consider the following set S_f= {x subset aleph_omega : |x| <= aleph_{n^*} & (for all n in X)cf(x cap alpha_n)= aleph_{f(n)}}. The question, first posed by Baumgartner, is whether S_f is stationary in [alpha_omega]^{< aleph_{n^*+1}}. By a standard result, the above question can also be rephrased as certain transfer property. Namely, S_f is stationary iff for any structure A=< aleph_omega, ... > there's a B prec A such that |B|= aleph_{n^*} and for all n in X we have cf(B cap aleph_n)= aleph_{f(n)}. In this paper, we are going to prove a few results concerning the above question.
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 section 1 we prove that Loeb spaces are compact under various assumptions, and in section 2 we prove that Loeb spaces are not compact under various other assumptions. The results in section 1 and section 2 give a quite complete answer to a question of D. Ross.
Spencer and Shelah [ShSp:304] constructed for each irrational alpha between 0 and 1 the theory T^alpha as the almost sure theory of random graphs with edge probability n^{- alpha}. In [BlSh:528] we proved that this was the same theory as the theory T_alpha built by constructing a generic model in Baldwin and Shi. In this paper we explore some of the more subtle model theoretic properties of this theory. We show that T^alpha has the dimensional order property and does not have the finite cover property.
We continue the investigations in the author's book on cardinal arithmetic, assuming some knowledge of it. We deal with the cofinality of (S_{<= aleph_0}(kappa), subseteq) for kappa real valued measurable (Section 3), densities of box products (Section 5,3), prove the equality cov(lambda, lambda, theta^+,2)=pp(lambda) in more cases even when cf(lambda)= aleph_0 (Section 1), deal with bounds of pp(lambda) for lambda limit of inaccessible (Section 4) and give proofs to various claims I was sure I had already written but did not find (Section 6).
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 subseteq P(X) of size c, consisting of Borel sets which are not in I. Condition (M) states that there is a function f:X-> X with f^{-1}[{x}] notin I for each x in X. Provided that X is a group and I is invariant, condition (D) states that there exist a Borel set B notin I and a perfect set P subseteq X for which the family {B+x: x in 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 sigma-ideal on the Cantor group witnessing''(M) and not (D)'' (Section 2). A modified version of that sigma-ideal contains the whole space (Section 3). Some consistency results deriving (M) from (B) for''nicely'' defined ideals are established (Section 4). We show that both ccc and (M) can fail (Theorems 1.3 and 4.2). Finally, some sharp versions of (M) for invariant ideals on Polish groups are investigated (Section 5).
This paper investigates the class of k-universal finite graphs, a local analog of the class of universal graphs, which arises naturally in the study of finite variable logics. The main results of the paper, which are due to Shelah, establish that the class of k-universal graphs is not definable by an infinite disjunction of first-order existential sentences with a finite number of variables and that there exist k-universal graphs with no k-extendible induced subgraphs.
We address a number of problems on Boolean Algebras. For example, we construct, in ZFC, for any BA B, and cardinal kappa BAs B_1,B_2 extending B such that the depth of the free product of B_1,B_2 over B is strictly larger than the depths of B_1 and of B_2 than kappa. We give a condition (for lambda, mu and theta) which implies that for some BA A_theta there are B_1=B^1_{lambda, mu, theta} and B_2B^2_{lambda, mu, theta} such that Depth (B_t) <= mu and Depth (B_1 oplus_{A_theta} B_1) >= lambda. We then investigate for a fixed A, the existence of such B_1,B_2 giving sufficient and necessary conditions, involving consistency results. Further we prove that e.g. if B is a BA of cardinality lambda, lambda >= mu and lambda, mu are strong limit singular of the same cofinality, then B has a homomorphic image of cardinality mu (and with mu ultrafilters). Next we show that for a BA B, if d(B)^kappa <|B| then ind (B)> kappa or Depth (B) >= log (|B|). Finally we prove that if square_lambda holds and lambda = lambda^{aleph_0} then for some BAs B_n, Depth (B_n) <= lambda but for any uniform ultrafilter D on omega, prod_{n< omega} B_n/D has depth >= lambda^+ .
Monk asks (problems 13, 15 in his list; pi is the algebraic density):''For a Boolean algebra B, aleph_0 <= theta <= pi (B), does B have a subalgebra B' with pi (B')= theta ?'' If theta is regular the answer is easily positive, we show that in general it may be negative, but for quite many singular cardinals - it is positive; the theorems are quite complementary. Next we deal with pi-chi and we show that the pi-chi of an ultraproduct of Boolean algebras is not necessarily the ultraproduct of the pi-chi 's. We also prove that for infinite Boolean algebras A_i (i< kappa) and a non-principal ultrafilter D on kappa : if n_i< aleph_0 for i< kappa and mu = prod_{i< kappa} n_i/D is regular, then pi-chi(A) >= mu. Here A= prod_{i< kappa}A_i/D. By a theorem of Peterson the regularity of mu is needed.
We investigate sigma-entangled linear orders and narrowness of Boolean algebras. We show existence of sigma-entangled linear orders in many cardinals, and we build Boolean algebras with neither large chains nor large pies. We study the behavior of these notions in ultraproducts.
Let L contain only the equality symbol and let L^+ be an arbitrary finite symmetric relational language containing L . Suppose probabilities are defined on finite L^+ structures with ''edge probability'' n^{- alpha}. By T^alpha, the almost sure theory of random L^+-structures we mean the collection of L^+-sentences which have limit probability 1. T_alpha denotes the theory of the generic structures for K_alpha, (the collection of finite graphs G with delta_{alpha}(G)=|G|- alpha. | edges of G | hereditarily nonnegative.) THEOREM: T_alpha, the almost sure theory of random L^+-structures is the same as the theory T_alpha of the K_alpha-generic model. This theory is complete, stable, and nearly model complete. Moreover, it has the finite model property and has only infinite models so is not finitely axiomatizable.
We continue [Sh:b, Ch XIII] and [Sh:410]. Let W be an inner model of ZFC. Let kappa be a cardinal in V. We say that kappa-covering holds between V and W iff for all X in V with X subseteq ON and V models |X|< kappa, there exists Y in W such that X subseteq Y subseteq ON and V models |Y|< kappa. Strong kappa-covering holds between V and W iff for every structure M in V for some countable first-order language whose underlying set is some ordinal lambda, and every X in V with X subseteq lambda and V models |X|< kappa, there is Y in W such that X subseteq Y prec M and V models |Y|< kappa. We prove that if kappa is V-regular, kappa^+_V= kappa^+_W, and we have both kappa-covering and kappa^+-covering between W and V, then strong kappa-covering holds. Next we show that we can drop the assumption of kappa^+-covering at the expense of assuming some more absoluteness of cardinals and cofinalities between W and V, and that we can drop the assumption that kappa^+_W = kappa^+_V and weaken the kappa^+-covering assumption at the expense of assuming some structural facts about W (the existence of certain square sequences).
An omega-coloring is a pair <f,B> where f:[B]^{2} ---> omega. The set B is the field of f and denoted Fld(f). Let f,g be omega-colorings. We say that f realizes the coloring g if there is a one-one function k:Fld(g) ---> Fld(f) such that for all {x,y}, {u,v} in dom(g) we have f({k(x),k(y)}) not= f({k(u),k(v)}) => g({x,y}) not= g({u,v}). We write f~g if f realizes g and g realizes f. We call the ~-classes of omega-colorings with finite fields identities. We say that an identity I is of size r if |Fld(f)|=r for some/all f in I. For a cardinal kappa and f:[kappa]^2 ---> omega we define I(f) to be the collection of identities realized by f and I (kappa) to be bigcap {I(f)| f:[kappa]^2 ---> omega}. We show that, if ZFC is consistent then ZFC + 2^{aleph_0}> aleph_omega + I(aleph_2)=I(aleph_omega) is consistent.
We show that in a model obtained by forcing with a countable support iteration of length omega_2 of Mathias forcing h(2), the distributivity number of r.o.(P(omega)/fin)^2, is omega_1 but h, the one of P(omega)/fin, is omega_2.
Let G_<(n,p) denote the usual random graph G(n,p) on a totally ordered set of n vertices. We will fix p=1/2 for definiteness. Let L^< denote the first order language with predicates equality (x=y), adjacency (x~y) and less than (x<y). For any sentence A in L^< let f_A(n) denote the probability that the random G_<(n,p) has property A. It is known Compton, Henson and Shelah [CHSh:245] that there are A for which f_A(n) does not converge. Here we show what is called a very weak zero-one law (from [Sh 463]): THEOREM: For every A in language L^<, lim_{n-> infty}(f_A(n+1)-f_A(n))=0.
We prove that double exponentiation is an upper bound to Ramsey theorem for colouring of pairs when we want to predetermine the order of the differences of successive members of the homogeneous set.
We study the determinacy of the game G_kappa (A) introduced in [FKSh:549] for uncountable regular kappa and several classes of partial orderings A. Among trees or Boolean algebras, we can always find an A such that G_kappa (A) is undetermined. For the class of linear orders, the existence of such A depends on the size of kappa^{< kappa}. In particular we obtain a characterization of kappa^{< kappa}= kappa in terms of determinacy of the game G_kappa (L) for linear orders L .
A ZFC Dowker space is constructed which has cardinality ℵω+1. This provides a bound in ZFC to the first cardinal in which there is a ZFC Dowker space. The space we construct is a closed and cofinal subspace of M.~E.~Rudin's Dowker space from 1971. A theorem from pcf theory used in the proof, but otherwise the proof is elementary.
In the paper we probe the possibilities of creating a Kurepa tree in a generic extension of a model of CH plus no Kurepa trees by an omega_1-preserving forcing notion of size at most omega_1. In the first section we show that in the Levy model obtained by collapsing all cardinals between omega_1 and a strongly inaccessible cardinal by forcing with a countable support Levy collapsing order many omega_1-preserving forcing notions of size at most omega_1 including all omega-proper forcing notions and some proper but not omega-proper forcing notions of size at most omega_1 do not create Kurepa trees. In the second section we construct a model of CH plus no Kurepa trees, in which there is an omega-distributive Aronszajn tree such that forcing with that Aronszajn tree does create a Kurepa tree in the generic extension. At the end of the paper we ask three questions.
We prove some consistency results about b(lambda) and d(lambda), which are natural generalisations of the cardinal invariants of the continuum b and d. We also define invariants b_cl(lambda) and d_cl(lambda), and prove that almost always b(lambda) = b_cl(lambda) and d(lambda)=d_cl(lambda)
It is consistent for every (1 <= n< omega) that (2^omega = omega_n) and there is a function (F:[omega_n]^{< omega}-> omega) such that every finite set can be written at most (2^n-1) ways as the union of two distinct monocolored sets. If GCH holds, for every such coloring there is a finite set that can be written at least (sum^n_{i=1}{n+i choose n}{n choose i}) ways as the union of two sets with the same color.
For a sequence p=(p(1),p(2), ...) let G(n,p) denote the random graph with vertex set {1,2, ...,n} in which two vertices i, j are adjacent with probability p(|i-j|), independently for each pair. We study how the convergence of probabilities of first order properties of G(n,p), can be affected by the behaviour of p and the strength of the language we use.
Complete Boolean algebras proved to be an important tool in topology and set theory. Two of the most prominent examples are B(kappa), the algebra of Borel sets modulo measure zero ideal in the generalized Cantor space {0,1}^kappa equipped with product measure, and C(kappa), the algebra of regular open sets in the space {0,1}^kappa, for kappa an infinite cardinal. C(kappa) is much easier to analyse than B(kappa) : C(kappa) has a dense subset of size kappa, while the density of B(kappa) depends on the cardinal characteristics of the real line; and the definition of C(kappa) is simpler. Indeed, C(kappa) seems to have the simplest definition among all algebras of its size. In the Main Theorem of this paper we show that in a certain precise sense, C(aleph_1) has the simplest structure among all algebras of its size, too. MAIN THEOREM: If ZFC is consistent then so is ZFC + 2^{aleph_0}= aleph_2 +``for every complete Boolean algebra B of uniform density aleph_1, C(aleph_1) is isomorphic to a complete subalgebra of B''.
Let kappa be an uncountable cardinal and the edges of a complete graph with kappa vertices be colored with aleph_0 colors. For kappa >2^{aleph_0} the Erdős-Rado theorem implies that there is an infinite monochromatic subgraph. However, if kappa <= 2^{aleph_0}, 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 kappa <= 2^{aleph_0}. In particular, we are concerned with the case aleph_1 <= kappa <= aleph_omega
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 [EM],(p.453). There, in pp. 241-242, this is discussed and proved in some cases. The existence of strongly lambda-free ones was proved earlier by the criteria in [Sh:161] in [MkSh:251]. We can apply a similar proof to a large class of other varieties in particular to the variety of (non-commutative) groups.
We are proving the following: (1) If $\kap$ is a weakly inaccessible then $NS_\kap$ is not $\kap^+$-saturated. (2) If $\kap$ is a weakly inaccessible and $\tet <\kap$ is regular then $NS^\tet_\kap$ is not $\kap^+$-saturated. (3) If $\kap$ is singular then $NS^{cf\kap}_{\kap^+}$ is not $\kap^{++}$-saturated. Combining this with previous results of Shelah, one obtains the following: (A) If $\kap >\aleph_1$ then $NS_\kap$ is not $\kap^+$-saturated. (B) If $\tet^+<\kap$ then $NS^\tet_\kap$ is not $\kap^+$-saturated.
In the present paper we are interested in properties of forcing notions which measure in a sense the distance between the ground model reals and the reals in the extension. We look at the ways the ``new'' reals can be aproximated by ``old'' reals. We consider localizations for infinite subsets of omega. Though each member of [omega]^omega can be identified with its increasing enumeration, the (standard) localizations of the enumeration does not provide satisfactory information on successive points of the set. They give us ``candidates'' for the n-th point of the set but the same candidates can appear several times for distinct n. That led to a suggestion that we should consider disjoint subsets of omega as sets of ``candidates'' for successive points of the localized set. We have two possibilities. Either we can demand that each set from the localization contains a limited number of members of the localized set or we can postulate that each intersection of that kind is large. Localizations of this kind are studied in section 1. In the second section we investigate localizations of infinite subsets of omega by sets of integers from the ground model. These localizations might be thought as localizations by partitions of omega into successive intervals.
Generalizing some earlier techniques due to the second author, we show that Menas' theorem which states that the least cardinal kappa which is a measurable limit of supercompact or strongly compact cardinals is strongly compact but not 2^kappa supercompact is best possible. Using these same techniques, we also extend and give a new proof of a theorem of Woodin and extend and give a new proof of an unpublished theorem due to the first author.
Answering two questions of D. Fremlin [Real-valued measurable cardinals, in Set Theory of the Reals, H. Judah ed. 1993, 151-305 ] we show the following: (1) If c is real-valued measurable then the Maharam type of (c,P(c),sigma) is 2^c. (2) It is consistent to have k real-valued measurable but for every submodel V_1 with k measurable in it there are no k reals which are random over V_1.
It is unprovable that every complete subalgebra of a countably closed complete Boolean algebra is countably closed.
A Gross space is a vector space E of infinite dimension over some field F, which is endowed with a symmetric bilinear form Phi:E^2 -> F and has the property that every infinite dimensional subspace U subseteq E satisfies dim U^perp < dim E. Gross spaces over uncountable fields exist (in certain dimensions). The existence of a Gross space over countable or finite fields (in a fixed dimension not above the continuum) is independent of the axioms of ZFC. Here we continue the investigation of Gross spaces. Among other things we show that if the cardinal invariant b equals omega_1 a Gross space in dimension omega_1 exists over every infinite field, and that it is consistent that Gross spaces exist over every infinite field but not over any finite field. We also generalize the notion of a Gross space and construct generalized Gross spaces in ZFC.
Suppose that lambda = mu^+. We consider two aspects of the square property on subsets of lambda. First, we have results which show e.g. that for aleph_0 <= kappa =cf (kappa)< mu, the equality cf([mu]^{<= kappa}, subseteq)= mu is a sufficient condition for the set of elements of lambda whose cofinality is bounded by kappa, to be split into the union of mu sets with squares. Secondly, we introduce a certain weak version of the square property and prove that if mu is a strong limit, then this weak square property holds on lambda without any additional assumptions
We show that supercompactness and strong compactness can be equivalent even as properties of pairs of regular cardinals. Specifically, we show that if V models ZFC + GCH is a given model (which in interesting cases contains instances of supercompactness), then there is some cardinal and cofinality preserving generic extension V[G] models ZFC + GCH in which, (a) (preservation) for kappa <= lambda regular, if V models ``kappa is lambda supercompact'', then V[G] models ``kappa is lambda supercompact'' and so that, (b) (equivalence) for kappa <= lambda regular, V[G] models ``kappa is lambda strongly compact'' iff V[G] models ``kappa is lambda supercompact'', except possibly if kappa is a measurable limit of cardinals which are lambda supercompact.
A partial ordering P is said to have the weak Freese-Nation property (WFN) if there is a mapping f:P ---> [P]^{<= aleph_0} such that, for any a, b in P, if a <= b then there exists c in f(a) cap f(b) such that a <= c <= b. In this note, we study the WFN and some of its generalizations. Some features of the class of BAs with the WFN seem to be quite sensitive to additional axioms of set theory: e.g., under CH, every ccc cBA has this property while, under b >= aleph_2, there exists no cBA with the WFN.
The bounded proper forcing axiom BPFA is the statement that for any family of aleph_1 many maximal antichains of a proper forcing notion, each of size aleph_1, there is a directed set meeting all these antichains. A regular cardinal kappa is called {Sigma}_1-reflecting, if for any regular cardinal chi, for all formulas phi, ``H(chi) models `phi ' '' implies ``exists delta < kappa, H(delta) models `phi ' '' We show that BPFA is equivalent to the statement that two nonisomorphic models of size aleph_1 cannot be made isomorphic by a proper forcing notion, and we show that the consistency strength of the bounded proper forcing axiom is exactly the existence of a Sigma_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.
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 maybe large while the covering for measure is small.
The essentially non-free spectrum is the class of uncountable cardinals kappa in which there is an essentially non-free algebra of cardinality kappa which is almost free. In L, the essentially non-free spectrum of a variety is entirely determined by whether or not the construction principle holds. In ZFC may be more complicated. For some varieties, such as groups, abelian groups or any variety of modules over a non-left perfect ring, the essentially non-free spectrum contains not only aleph_1 but aleph_n for all n>0. The reason for this being true in ZFC (rather than under some special set theoretic hypotheses) is that these varieties satisfy stronger versions of the construction principle. We conjecture that the hierarchy of construction principles is strict, i.e., that for each n>0 there is a variety which satisfies the n-construction principle but not the n+1-construction principle. In this paper we will show that the 1-construction principle does not imply the 2-construction principle. We prove that, assuming the consistency of some large cardinal hypothesis, it is consistent that a variety has an essentially non-free almost free algebra of cardinality aleph_n if and only if it satisfies the n-construction principle.
Paul Erdős and Alfred Renyi considered the evolution of the random graph G(n,p) as p ``evolved'' from 0 to 1. At p=1/n a sudden and dramatic change takes place in G. When p=c/n with c<1 the random G consists of small components, the largest of size Theta(log n). But by p=c/n with c>1 many of the components have ``congealed'' into a ``giant component'' of size Theta (n). Erdős and Renyi called this the double jump, the terms phase transition (from the analogy to percolation) and Big Bang have also been proferred. Now imagine an observer who can only see G through a logical fog. He may refer to graph theoretic properties A within a limited logical language. Will he be able to detect the double jump? The answer depends on the strength of the language. Our rough answer to this rough question is: the double jump is not detectible in the First Order Theory of Graphs but it is detectible in the Second Order Monadic Theory of Graphs.
Let T be the family of open subsets of a topological space (not necessarily Hausdorff or even T_0). We prove that if T has a base of cardinality <= mu, lambda <= mu < 2^lambda, lambda strong limit of cofinality aleph_0, then T has cardinality <= mu or >= 2^lambda. This is our main conclusion. First we prove it under some set theoretic assumption, which is clear when lambda = mu ; then we eliminate the assumption by a theorem on pcf from [Sh 460] motivated originally by this. Next we prove that the simplest examples are the basic ones; they occur in every example (for lambda = aleph_0 this fulfill a promise from [Sh 454]). The main result for the case lambda = aleph_0 was proved in [Sh 454].
Let dec be the least cardinal kappa such that every function of first Baire class can be decomposed into kappa continuous functions. Cichon, Morayne, Pawlikowski and Solecki proved that cov(Meager) <= dec <= d and asked whether these inequalities could, consistently, be strict. By cov(Meager) is meant the least number of closed nowhere dense sets required to cover the real line and by d is denoted the least cardinal of a dominating family in omega^omega. Steprans showed that it is consistent that cov(Meager) not= dec. In this paper we show that the second inequality can also be made strict. The model where dec is different from d is the one obtained by adding omega_2 Miller - sometimes known as super-perfect or rational-perfect - reals to a model of the Continuum Hypothesis. It is somewhat surprising that the model used to establish the consistency of the other inequality, cov(Meager) not= dec, is a slight modification of the iteration of super-perfect forcing.
We answer three problems by J. D. Monk on cardinal invariants of Boolean algebras. Two of these are whether taking the algebraic density pi(A), resp. the topological density d(A), of a Boolean algebra A commutes with formation of ultraproducts; the third one compares the number of endomorphisms and of ideals of a Boolean algebra.
By an omega_1 --tree we mean a tree of size omega_1 and height omega_1. An omega_1 --tree is called a Kurepa tree if all its levels are countable and it has more than omega_1 branches. An omega_1 --tree is called a Jech--Kunen tree if it has kappa branches for some kappa strictly between omega_1 and 2^{omega_1}. A Kurepa tree is called an essential Kurepa tree if it contains no Jech--Kunen subtrees. A Jech--Kunen tree is called an essential Jech--Kunen tree if it contains no Kurepa subtrees. In this paper we prove that (1) it is consistent with CH and 2^{omega_1}> omega_2 that there exist essential Kurepa trees and there are no essential Jech--Kunen trees, (2) it is consistent with CH and 2^{omega_1}> omega_2 plus the existence of a Kurepa tree with 2^{omega_1} branches that there exist essential Jech--Kunen trees and there are no essential Kurepa trees. In the second result we require the existence of a Kurepa tree with 2^{omega_1} branches in order to avoid triviality.
A subgroup G \leq Z^omega exhibits the Specker phenomenon if every homomorphism G \to Z maps almost all unit vectors to 0. We give several combinatorial characterizations of the cardinal se, the size of the smallest G \leq Z^omega exhibiting the Specker phenomenon. We also prove the consistency of b < e, where b is the unbounding number and e the evasion number introduced recently by Blass. Finally we show that e \geq \min { aleph_0--e , cov(M) }, where aleph_0--e is the aleph_0--evasion number (the uniformity of the evasion ideal) and cov(M) is the covering number of the meager ideal. All these results can be dualized. They answer several questions addressed by Blass.
We show that every null-additive set is meager-additive, where: (1) a set X subseteq 2^omega is null-additive if for every Lebesgue null set A subseteq 2^omega, X+A is null too; (2) we say that X subseteq 2^omega is meager-additive if for every A subseteq 2^omega which is meager also X+A is meager.
Gregory McColm 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.
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 L^omega_{infty, omega} formula with counting quantifiers defines a linear order.
We describe some (countably many) classes K^{n,e} of finite graphs and prove that if lambda^{aleph_0}= lambda then every lambda^+-chromatic graph of cardinal lambda^+ contains, for some n, e, all members of K^{n,e} as subgraphs. On the other hand, it is consistent for every regular infinite cardinal kappa that there is a kappa^+-chromatic graph on kappa^+ that contains finite subgraphs only from K^{n,e} .
There exists a family {Bα}α<ω1 of sets of countable ordinals such that o maxBα=α, o if α∈Bβ then Bα⊆Bβ, o if λ≤α and λ is a limit ordinal then Bα∩λ is not in the ideal generated by the Bβ, β<α, and by the bounded subsets of λ, o there is a partition {An}n=0∞ of ω1 such that for every α and every n, Bα∩An is finite.
CWH, CWN stand for collectionwise Hausdorff and collectionwise normal respectively. We analyze the statement "there is a lambda-CWH not CWH first countable (Hausdorff topological) space". We prove the existence of such a space under various conditions, show its equivalence to: there is a lambda-CWN not CWN first countable space and give an equivalent set theoretic statement; the nicest version we can obtain is in \S4. The author had a flawed proof of the existence of such spaces in ZFC, for some lambda > aleph_1, in June of 1992; still we decided that there is some interest in the correct part and some additions.
A group G that is not finitely generated can be written as the union of a chain of proper subgroups. The cofinality spectrum of G, written CF(S), is the set of regular cardinals lambda such that G can be expressed as the union of a chain of lambda proper subgroups. The cofinality of G, written c(G), is the least element of CF(G). We show that it is consistent that CF(S) is quite a bizarre set of cardinals. For example, we prove Theorem (A): Let T be any subset of omega setminus {0}. Then it is consistent that aleph_n in CF(S) if and only if n in T . One might suspect that it is consistent that CF(S) is an arbitrarily prescribed set of regular uncountable cardinals, subject only to the above mentioned constraint. This is not the case. Theorem (B): If aleph_n in CF(S) for all n in omega setminus {0}, then aleph_{omega +1} in CF(S) .
We lay the combinatorial foundations for [ShSt:340] 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.
We deal with consistency results for the existence of universal models in natural classes of models (more exactly--a somewhat weaker version). We apply a result on quite general family to T_feq and to the class of triangle-free graphs.
We examine the existence of universal elements in classes of infinite abelian groups. The main method is using group invariants which are defined relative to club guessing sequences. We prove, for example: Theorem: For n≥2, there is a purely universal separable p-group in ℵn if, and only if, $\cont\le \aleph_n$.
We investigate a notion called uniqueness in power kappa that is akin to categoricity in power kappa, but is based on the cardinality of the generating sets of models instead of on the cardinality of their universes. The notion is quite useful for formulating categoricity-like questions regarding powers below the cardinality of a theory. We prove, for (uncountable) universal theories T, that if T is kappa-unique for one uncountable kappa, then it is kappa-unique for every uncountable kappa ; in particular, it is categorical in powers greater than the cardinality of T.
By an omega_1 --tree we mean a tree of power omega_1 and height omega_1. We call an omega_1 --tree a Jech--Kunen tree if it has kappa --many branches for some kappa strictly between omega_1 and 2^{omega_1}. In this paper we construct the models of CH plus 2^{omega_1}> omega_2, in which there are Jech--Kunen trees and there are no Kurepa trees.
In the literature two notions of the word problem for a variety occur. A variety has a decidable word problem if every finitely presented algebra in the variety has a decidable word problem. It has a uniformly decidable word problem if there is an algorithm which given a finite presentation produces an algorithm for solving the word problem of the algebra so presented. A variety is given with finitely many axioms having a decidable, but not uniformly decidable, word problem. Other related examples are given as well.
A theorem of Galvin asserts that if the unordered pairs of reals are partitioned into finitely many Borel classes then there is a perfect set P such that all pairs from P lie in the same class. The generalization to n-tuples for n >= 3 is false. Let us identify the reals with 2^omega ordered by the lexicographical ordering and define for distinct x,y in 2^omega, D(x,y) to be the least n such that x(n) not= y(n). Let the type of an increasing n-tuple {x_0, ... x_{n-1}}_< be the ordering <^* on {0, ...,n-2} defined by i<^*j iff D(x_i,x_{i+1})< D(x_j,x_{j+1}). Galvin proved that for any Borel coloring of triples of reals there is a perfect set P such that the color of any triple from P depends only on its type. Blass proved an analogous result is true for any n. As a corollary it follows that if the unordered n-tuples of reals are colored into finitely many Borel classes there is a perfect set P such that the n-tuples from P meet at most (n-1)! classes. We consider extensions of this result to partitions of infinite increasing sequences of reals. We show, that for any Borel or even analytic partition of all increasing sequences of reals there is a perfect set P such that all strongly increasing sequences from P lie in the same class.
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 C and D, either C <= D or D <= C. However, in ZF this is no longer so. For a given infinite set A consider Seq(A), the set of all sequences of A without repetition. We compare |Seq(A)|, the cardinality of this set, to |P(A)|, 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 |- for all A: |Seq(A)| not= |P(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)|<|P(B)|, even though the existence for some infinite set B^* of a function f from fin(B^*) onto P(B^*) is consistent with ZF.
A graph is called dominating if its vertices can be labelled with integers in such a way that for every function f: omega-> omega the graph contains a ray whose sequence of labels eventually exceeds f. We obtain a characterization of these graphs by producing a small family of dominating graphs with the property that every dominating graph must contain some member of the family.
We show that if 2^{aleph_0} Cohen reals are added to the universe, then for every reduced non-free torsion-free abelian group A of cardinality less than the continuum, there is a prime p so that Ext_p(A, Z) not= 0. In particular if it is consistent that there is a supercompact cardinal, then it is consistent (even with weak CH) that every coseparable group is free. The use of some large cardinal hypothesis is needed.
We give a model where there is a ccc Souslin forcing which does not satisfy the Knaster condition. Next, we present a model where there is a sigma-linked not sigma-centered Souslin forcing such that all its small subsets are sigma-centered but Martin Axiom fails for this order. Furthermore, we construct a totally nonhomogeneous Souslin forcing and we build a Souslin forcing which is proper but not ccc that does not contain a perfect set of mutually incompatible conditions. Finally we show that ccc Sigma^1_2-notions of forcing may not be indestructible ccc.
A forcing extension may create new isomorphisms between two models of a first order theory. Certain model theoretic constraints on the theory and other constraints on the forcing can prevent this pathology. A countable first order theory is classifiable if it is superstable and does not have either the dimensional order property or the omitting types order property. Shelah [Sh:c] showed that if a theory T is classifiable then each model of cardinality lambda is described by a sentence of L_{infty, lambda}. In fact this sentence can be chosen in the L^*_{lambda}. (L^*_{lambda} is the result of enriching the language L_{infty, beth^+} by adding for each mu < lambda a quantifier saying the dimension of a dependence structure is greater than mu .) The truth of such sentences will be preserved by any forcing that does not collapse cardinals <= lambda and that adds no new countable subsets of lambda. Hence, if two models of a classifiable theory of power lambda are non-isomorphic, they are non-isomorphic after a lambda-complete forcing. Here we show that the hypothesis of the forcing adding no new countable subsets of lambda cannot be eliminated. In particular, we show that non-isomorphism of models of a classifiable theory need not be preserved by ccc forcings.
The feeling that those two forcing notions-Cohen and Random-(equivalently the corresponding Boolean algebras Borel(R)/(meager sets), Borel(R)/(null sets)) are special, was probably old and widespread. A reasonable interpretation is to show them unique, or ``minimal'' or at least characteristic in a family of ``nice forcing'' like Borel. We shall interpret ``nice'' as Souslin as suggested by Judah Shelah [JdSh 292]. We divide the family of Souslin forcing to two, and expect that: among the first part, i.e. those adding some non-dominated real, Cohen is minimal (=is below every one), while among the rest random is quite characteristic even unique. Concerning the second class we have weak results, concerning the first class, our results look satisfactory. We have two main results: one (1.14) says that Cohen forcing is ``minimal'' in the first class, the other (1.10) says that all c.c.c. Souslin forcing have a property shared by Cohen forcing and Random real forcing, so it gives a weak answer to the problem on how special is random forcing, but says much on all c.c.c. Souslin forcing.
It is proved that -- consistently -- there can be no ccc closed P-sets in the remainder space omega^* .
It is proved consistent with either CH or the negation of CH that there is an aleph_1-separable group of cardinality aleph_1 which does not have a coherent system of projections. It had previously been shown that it is consistent with not CH that every aleph_1-separable group of cardinality aleph_1 does have a coherent system of projections.
Let s(A) denote the number of automorphisms of a model A of power omega_1. We derive a necessary and sufficient condition in terms of trees for the existence of an A with omega_1 < s(A) < 2^{omega_1}. We study the sufficiency of some conditions for s(A)=2^{omega_1}. These conditions are analogous to conditions studied by D.Kueker in connection with countable models.
We show that there is always a uniformly antisymmetric f:A-> {0,1} if A subset R is countable. We prove that the continuum hypothesis is equivalent to the statement that there is an f:R-> omega with |S_x| <= 1 for every x in R. If the continuum is at least aleph_n then there exists a point x such that S_x has at least 2^n-1 elements. We also show that there is a function f:Q-> {0,1,2,3} such that S_x is always finite, but no such function with finite range on R exists
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 show here that it is consistent that there is no interpretation even in the monadic second-order theory of all chains.
We show that if we enrich first order logic by allowing quantification over isomorphisms between definable ordered fields the resulting logic, L(Q_{Of}), is fully compact. In this logic, we can give standard compactness proofs of various results. Next, we attempt to get compactness results for some other logics without recourse to diamond, i.e., all our results are in ZFC. We get the full result for the language where we quantify over automorphisms (isomorphisms) of ordered fields in Theorem 6.4. Unfortunately we are not able to show that the language with quantification over automorphisms of Boolean algebras is compact, but will have to settle for a close relative of that logic. This is theorem 5.1. In section 4 we prove we can construct models in which all relevant automorphism are somewhat definable: 4.1, 4.8 for BA, 4.13 for ordered fields. We also give a new proof of the compactness of another logic -- the one which is obtained when a quantifier Q_{Brch} is added to first order logic which says that a level tree (definitions will be given later) has an infinite branch. This logic was previously shown to be compact, but our proof yields a somewhat stronger result and provides a nice illustration of one of our methods.
It is shown to be consistent that there is a non-trivial autohomeomorphism of beta N while all such autohomeomorphisms are trivial on some open set. The model used is one due to Velickovic in which, coincidentally, Martin's Axiom also holds.
A canary tree is a tree of cardinality the continuum which has no uncountable branch, but gains a branch whenever a stationary set is destroyed (without adding reals). Canary trees are important in infinitary model theory. The existence of a canary tree is independent of ZFC + GCH.
We prove that in the product of kappa many Boolean algebras we cannot find an independent set of more than 2^kappa elements solving a problem of Monk (earlier it was known that we cannot find more than 2^{2^kappa} but can find 2^kappa).
We give some existence/nonexistence statements on universal graphs, which under GCH give a necessary and sufficient condition for the existence of a universal graph of size lambda with no K(kappa), namely, if either kappa is finite or cf(kappa)>cf(lambda). (Here K(kappa) denotes the complete graph on kappa vertices.) The special case when lambda^{< kappa}= lambda was first proved by F. Galvin. Next, we investigate the question that if there is no universal K(kappa)-free graph of size lambda then how many of these graphs embed all the other. It was known, that if lambda^{< lambda}= lambda (e.g., if lambda is regular and the GCH holds below lambda), and kappa = omega, then this number is lambda^+. We show that this holds for every kappa <= lambda of countable cofinality. On the other hand, even for kappa = omega_1, and any regular lambda >= omega_1 it is consistent that the GCH holds below lambda, 2^{lambda} is as large as we wish, and the above number is either lambda^+ or 2^{lambda}, so both extremes can actually occur.
We show in section 1 that the Ax-Kochen isomorphism theorem requires the continuum hypothesis. Most of the applications of this theorem are insensitive to set theoretic considerations. (A probable exception is the work of Moloney.) In section 2 we give an unrelated result on cuts in models of Peano arithmetic which answers a question on the ideal structure of countable ultraproducts of Z. In section 1 we also answer a question of Keisler and Schmerl regarding Scott complete ultrapowers of R .
Assuming 0^sharp does not exist, kappa is an uncountable cardinal and for all cardinals lambda with kappa <= lambda < kappa^{+ omega}, 2^lambda = lambda^+, we present a ``mini-coding'' between kappa and kappa^{+ omega}. This allows us to prove that any subset of kappa^{+ omega} can be coded into a subset, W of kappa^+ which, further, ``reshapes'' the interval [kappa, kappa^+), i.e., for all kappa < delta < kappa^+, kappa = (card delta)^{L[W cap delta]}. We sketch two applications of this result, assuming 0^sharp does not exist. First, we point out that this shows that any set can be coded by a real, via a set forcing. The second application involves a notion of abstract condensation, due to Woodin. Our methods can be used to show that for any cardinal mu, condensation for mu holds in a generic extension by a set forcing.
In this work we use a notion of rank first introduced by James Baumgartner and Peter Dordal and later developed independently by the third author to show that adding a Hechler real has strong combinatorial consequences. We prove: 1) assuming omega_1^V = omega_1^L, there is no real in V[d] which is eventually different from the reals in L[d], where d is Hechler over V; 2) adding one Hechler real makes the invariants on the left-hand side of Cicho'n's diagram equal omega_1 and those on the right-hand side equal 2^omega and produces a maximal almost disjoint family of subsets of omega of size omega_1; 3) there is no perfect set of random reals over V in V[r][d], where r is random over V and d Hechler over V[r], thus answering a question of the first and second authors. As an intermediate step in the proof of 3) we show that given models M subseteq N of ZFC such that there is a perfect set of random reals in N over M, either there is a dominating real in N over M or mu (2^omega cap M) = 0 in N.
For g < f in omega^omega we define c(f,g) be the least number of uniform trees with g-splitting needed to cover a uniform tree with f-splitting. We show that we can simultaneously force aleph_1 many different values for different functions (f,g). In the language of Blass: There may be aleph_1 many distinct uniform Pi^0_1 characteristics.
Various questions posed by P. Nyikos concerning ultrafilters on ω and chains in the partial order (ω,<∗) are answered. The main tool is the oracle chain condition and variations of it.
By an omega_1--tree we mean a tree of power omega_1 and height omega_1. Under CH and 2^{omega_1}> omega_2 we call an omega_1--tree a Jech--Kunen tree if it has kappa many branches for some kappa strictly between omega_1 and 2^{omega_1}. In this paper we prove that, assuming the existence of one inaccessible cardinal, (1) it is consistent with CH plus 2^{omega_1}> omega_2 that there exist Kurepa trees and there are no Jech--Kunen trees, (2) it is consistent with CH plus 2^{omega_1}= omega_4 that only Kurepa trees with omega_3 many branches exist.
In a series of papers, 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 subseteq [0,1]^2 such that whenever D subseteq [0,1] has outer measure 1 then the set Q^{-1}[D]= {x:(exists y in D)((x,y) in Q)} has inner measure 1.
It is shown that if T is stable unsuperstable, and aleph_1< lambda =cf(lambda)< 2^{aleph_0}, or 2^{aleph_0} < mu^+< lambda =cf(lambda)< mu^{aleph_0} then T has no universal model in cardinality lambda, and if e.g. aleph_omega < 2^{aleph_0} then T has no universal model in aleph_omega. These results are generalized to kappa =cf(kappa) < kappa (T) in the place of aleph_0. Also: if there is a universal model in lambda >|T|, T stable and kappa < kappa (T) then there is a universal tree of height kappa +1 in cardinality lambda .
The connections between Whitehead groups and uniformization properties were investigated by the third author in [Sh:98]. In particular it was essentially shown there that there is a non-free Whitehead (respectively, aleph_1-coseparable) group of cardinality aleph_1 if and only if there is a ladder system on a stationary subset of omega_1 which satisfies 2-uniformization (respectively, omega-uniformization). These techniques allowed also the proof of various independence and consistency results about Whitehead groups, for example that it is consistent that there is a non-free Whitehead group of cardinality aleph_1 but no non-free aleph_1-coseparable group. However, some natural questions remained open, among them the following two: (i) Is it consistent that the class of W-groups of cardinality aleph_1 is exactly the class of strongly aleph_1-free groups of cardinality aleph_1 ? (ii) If every strongly aleph_1-free group of cardinality aleph_1 is a W-group, are they also all aleph_1-coseparable? In this paper we use the techniques of uniformization to answer the first question in the negative and give a partial affirmative answer to the second question.
We show that the ordering of the Hanf number of L_{omega, omega}(wo) (well ordering), L^c_{omega, omega} (quantification on countable sets), L_{omega, omega}(aa) (stationary logic) and second order logic, have no more restraints provable in ZFC than previously known (those independence proofs assume CON(ZFC) only). We also get results on corresponding logics for L_{lambda, mu} .
This is the second in a series of articles developing abstract classification theory for classes that have a notion of prime models over independent pairs and over chains. It deals with the problem of smoothness and establishing the existence and uniqueness of a `monster model'. We work here with a predicate for a canonically prime model.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.