From: ah170@FreeNet.Carleton.CA (David Libert) Subject: Re: combinatorial set theory question Date: 3 Aug 1999 06:38:48 GMT Newsgroups: sci.math Keywords: cardinality of a set of subsets of R David Bernier (bernier@my-deja.com) writes: > If A is a set with the properties: > > { (a) If x in A, then x is a subset of the real numbers. } > { (b) If x and y are in A, then the intersection of x and y } > { is finite or countably infinite. } > > then how big can |A| be? > > I can see that |A|=continuum is possible, e.g. let A= powerset of Z. > Clearly, |A| <= 2^continuum. > > David Bernier This is an interesting question. I haven't found a complete solution but do have some partial results. Claim: ZFC proves there is a set A as above of cardinality 2^aleph_1 . The proof below is similar to the usual construction of continuum many almost-disjoint subsets of w as branches through a countably branching tree. Proof of Claim: Using AC for a sequence s.t. for all alpha < aleph_1 f_alpha is a surjection from omega onto alpha. (This last step needed AC, ZF shows those surjections exist for each alpha but there is no canonical way to choose one f_alpha for each alpha, so AC provides the choice function.) For each set X a subset of aleph_1 (ie X a set of ordinals less than aleph_1 (using von Neumann ordinals identifying an ordinal with its set of predecessors)) we define a seq of aleph_1 many subsets of omega. Ie r(X, alpha) is a subset of omega. Define r(X, alpha) = (f_alpha)^(-1) " (X intersect alpha) . ie: restrict X to the ordinals below alpha, take the preimage of this set by f_alpha to induce a subset of omega. For X1, X2 distinct subsets of aleph_1, suppose they disagree on alpha < aleph_1, ie alpha is in the symmetric difference of X1 and X2. Then for beta s.t. alpha < beta < aleph_1, r(X1, beta) and r(X2, beta) disagree on their respective membership of any f_beta preimage of alpha. (Recall f_beta is surjective so such preimages exist.) So r(X1, beta) != r(X2, beta). To enforce further distinctions we make a new sequence building on those above where we tag items according to their location in the sequence. omega x omega (Cartesian product) is disjoint from omega. Use AC to form an omega sequence where s_alpha is a subset of omega x omega s.t. s_alpha is a total ordering on some subset of omega of order type alpha. Such s_alpha 's exist for each alpha using ZF only, we need AC to chose the s_alpha 's in an aleph_1 sequence. Finally for each X subset of aleph_1, define an aleph_1 sequence , where t(X, alpha) subset of omega x omega union omega: Define: t(X, alpha) = s_alpha union r(X, alpha). Subclaim: suppose X1, X2 are distinct subsets of aleph_1, then {t(X1, alpha) | alpha < aleph_1 } intersect {t(X1, alpha) | alpha < aleph_1 } is countable (ie finite or denumerable). Proof of subclaim: suppose alpha is in the symmetric difference of X1 and X2. Suppose t(X1, beta1) = t(X2, beta2), for some beta1, beta2 < aleph_1. Since omega x omega is disjoint from omega this forces agreement on the respective s and r parts. The s part forces beta1 = beta2. From the earlier discussion about r the r part forces beta1 <= alpha. So the intersection from the claim subset of {t(X1, beta) | beta <= alpha}, a countable set. QED subclaim. So {{t(X, alpha) | alpha < aleph_1 } | X subset of aleph_1} is a family of 2^aleph_1 many subsets of omega x omega union omega with pairwise countable intersections. Using a bijection of omega with omega x omega union omega this can induce a corresponding set of subsets of omega. Set theorists "know" that reals are subsets of omega :-). For "real" mathematicians who insist on some nonsense about equivalence classes of Cauchy sequences or Dedikind cuts the last construction can be pulled back by bijection to those. QED Claim. So ZFC gives us an A as required of size 2^aleph_1. David Bernier noted above the obvious upper bound on such A is 2^continuum. What can we say about the possible remaining gap? CH (continuum hypothesis) is aleph_1 = continuum so it says there is no gap. So if we like CH there is nothing more to settle. Even if we don't commit to CH this at least tells us (by Godel's relative consistency result) that we can't answer refute continuum sized A in ZFC alone. There are further ZFC models beyond CH ones where the above aleph_1 result gives a full settlement. Easton's result lets you produce models where cardinal exponentiation on regular cardinals can be made to order, subject to mild restrictions of non-decreasing and a Hartog's inequality condition on cofinalities. So for example if your favourite integers are 42 and 114, you could get a ZFC model where continuum = aleph_42 (certainly a failure of CH), but 2^aleph_1 = 2^continuum = aleph_114. No need to stick to the finite aleph's either, it can't be any aleph because of cofinality restrictions but for example 114 could be replaced by ordinals of various unbounded sizes. So these non-CH models still have my example 2^alpeh_1 attaining the upper bound 2^continuum and all is settled. Can we expect to prove continuum sized A in ZFC only? That possibility has not been ruled out above. Or a richer version of the same question: what results about this can be expected in ZFC + ~CH ? Conceivably ZFC could prove 2^aleph_1 is an upper bound on #A, and so ZFC + ~CH would prove there are no 2^continuum sized A's. I don't see how to settle these with forcing but here is my guess: ZFC + 2^aleph_1 < 2^continuum does not decide whether there are A's of size > 2^aleph_1. I believe the style of arguments producing continuum many almost-disjoint subsets of omega or producing the claim above are at their limits above. On the other hand, I would guess that the property under discussion is subtle enough that ZFC also can't resolve things the other way. -- David Libert (ah170@freenet.carleton.ca) 1. I used to be conceited but now I am perfect. 2. "So self-quoting doesn't seem so bad." -- David Libert 3. "So don't be a morron." -- Marek Drobnik bd308 rhetorical salvo IRC sig ============================================================================== From: "Brian M. Scott" Subject: Re: combinatorial set theory question Date: Tue, 03 Aug 1999 05:24:24 -0400 Newsgroups: sci.math David Bernier wrote: > If A is a set with the properties: > { (a) If x in A, then x is a subset of the real numbers. } > { (b) If x and y are in A, then the intersection of x and y } > { is finite or countably infinite. } > then how big can |A| be? > I can see that |A|=continuum is possible, e.g. let A= powerset of Z. > Clearly, |A| <= 2^continuum. In the complete binary tree of height w_1 (omega_1) there are 2^w nodes and 2^(w_1) branches. Distinct branches have only countably many nodes in common, so by identifying the set of nodes with the set of real numbers you get a family A of power 2^(w_1). Of course it's consistent that this is 2^c (= 2^(2^w)), but if I remember correctly it's only c under MA + ~CH. I'd guess that one can't construct a family A of power 2^c in ZFC, but I haven't thought too hard about it. Brian M. Scott ============================================================================== From: ah170@FreeNet.Carleton.CA (David Libert) Subject: Re: combinatorial set theory question Date: 3 Aug 1999 09:33:16 GMT Newsgroups: sci.math "Brian M. Scott" (BMScott@stratos.net) writes: [previous article quoted -- djr] I posted a short while ago a much longer proof of this same result about a 2^(w_1) sized solution. Brian's article above gives a clearer and more direct argument. It is also a more straightforward generalization of the similar result about a family of continuum many almost-disjoint subsets of omega, as branches through a tree of height omega. -- David Libert (ah170@freenet.carleton.ca) 1. I used to be conceited but now I am perfect. 2. "So self-quoting doesn't seem so bad." -- David Libert 3. "So don't be a morron." -- Marek Drobnik bd308 rhetorical salvo IRC sig ============================================================================== From: Fred Galvin Subject: Re: combinatorial set theory question Date: Wed, 4 Aug 1999 20:16:58 -0500 Newsgroups: sci.math On Tue, 3 Aug 1999, Brian M. Scott wrote: [see article, above -- djr] For each x in A, choose a subset f(x) of x so that (i) f(x) = x if x is finite or countably infinite, and (ii) |f(x)| = w_1 if x is uncountable. Note that the mapping f is one-to-one, and its range consists of subsets of R of cardinality at most w_1; hence |A| <= (2^w)^(w_1) = 2^(w_1). Thus the answer to the question, how big can |A| be, is 2^(w_1). Of course it is consistent with ZFC that 2^(w_1) = 2^(2^w), and it is also consistent with ZFC that 2^(w_1) = 2^w. ============================================================================== From: renfro@alpha.nslua.edu (Dave L. Renfro) Subject: Re: combinatorial set theory question Date: 4 Aug 1999 18:20:43 -0400 Newsgroups: sci.math NOTE: I wrote the following this morning, before I had a chance to access the internet and find that the original question generated some responses. In the event that there may be some interest in my comments, I'm posting them anyway. **************************************************** The type of question you're asking is related to the notion of an "almost disjoint collection of sets". DEFINITION: Let X be a set. A collection % of subsets of X is an almost disjoint collection for X if (a) the intersection of each pair elements from % has cardinality less than card(X), and (b) the cardinality of each element in % is equal to card(X). NOTATION: Let N* be the cardinality of the natural numbers and R* be the cardinality of the reals. Recall that 2^N* = R*. Let N** be the smallest uncountable cardinal number (i.e. the next largest infinity after N*). The continuum hypothesis (CH) is the statement N** = R*. CH is known to be independent of the ZFC axioms of set theory. THEOREM 1: If card(X) = N*, then there is an almost disjoint collection % in X such that card(%) = R*. PROOF: Two proofs are given later. Note, by the way, that we only need to satisfy condition (a) in the definition, since there are only countably many finite subsets of a countably infinite set. [If you can find R* many subsets of X having pairwise finite intersections (i.e. a collection of R* many sets in which (a) holds) then, by throwing out the countably many of these sets that are finite, you will still have R* many sets left, and all of the sets left will be infinite.] THEOREM 2: Assume CH holds. If card(X) = R*, then there is an almost disjoint collection % in X such that card(%) = 2^R*. In particular, there exists 2^R* subsets of the reals having pairwise countable intersection. [The pairwise intersections have cardinality less than R*, by the definition of "almost disjoint collection", and CH implies that "less than R*" is the same as "countable".] PROOF: This follows from theorem 1.3 on page 48 (with "kappa" chosen to be R* = N**) of Kenneth Kunen's book SET THEORY: An Introduction to Independence Proofs, Studies in Logic and the Foundations of Mathematics 102, North-Holland, 1980. [QA 248.K75] If CH fails, the situation becomes more complicated. For instance, it is possible for there to be more than N*, more than R*, or even more than 2^R* many distinct cardinal numbers lying between N* and R*, and also between R* and 2^R*. In fact, the number of cardinal numbers lying between N* and R* and the number of cardinal numbers lying between R* and 2^R* can be virtually anything. For instance, it is consistent with the ZFC axioms for there to be 38 cardinals between N* and R* and 19 cardinals between R* and 2^R*; or 559 cardinals between N* and R*, while none lie between R* and 2^R*; or more than 2^R* lying between N* and R* while 12 lie between R* and 2^R*. [However, it is known that there cannot be exactly N* distinct cardinals lying between N* and R*. This is why I used *virtually* in "virtually anything" above.] I don't know what is known about your specific question among the various possibilities I alluded to in my previous paragraph. I suspect that it is independent of the axioms of ZFC for there to be an almost disjoint collection of 2^R* many subsets of the reals, even when one assumes CH. [The CH assumption makes the pairwise intersection cardinality restriction (property (a) in the definition of "almost disjoint" above) be the same that you asked for, namely that each pairwise intersection be countable.] There are probably many results that are known which take the following form: "If there are such-and-such many cardinals lying between N* and R*, and this-and-that many cardinals lying between R* and 2^R*, then it is consistent with ZFC for there to be an almost disjoint collection of subsets of the reals with cardinality #, where # is some cardinal lying between R* and 2^R*." [The closer to 2^R* you can get # to be, the stronger the theorem.], but I don't know enough about these matters to be more specific. More than you'd probably ever want to know about these issues can be found in: Paul Erdos, Andras Hajnal, Attila Mate, and Richard Rado, COMBINATORIAL SET THEORY: PARTITION RELATIONS FOR CARDINALS, North-Holland, 1984. *********************************** TWO PROOFS OF THEOREM 1 PROOF (1): For each irrational number between 0 and 1 (note: there are R* many such numbers) we associate a subset of the natural numbers as follows. If x = .abcdefg..., where a, b, c, etc. are the digits of the decimal expansion of x, let N(x) be the set {a, ab, abc, abcd, ...}. For example, N(sqrt(1/2)) = {7, 70, 707, 7071, ...}. Then it is not difficult to check (i) N(x) is infinite for each irrational x in (0,1), (ii) the correspondence x <---> N(x) is one-to-one and onto (hence, there are R* many N(x)'s), and (iii) N(x) has finite intersection with N(y) whenever x is not equal to y. PROOF (2): It suffices to find such an almost disjoint collection in N x N (N = set of natural numbers; N x N is the Cartesian product of N with N), since any almost disjoint collection in N x N having cardinality R* can be identified (via any bijective mapping of N x N onto N) with an almost disjoint collection in N having cardinality R*. For each real number r between .9 and 1.1 let N(r) = {(m,n) in N x N : r*m - 2 < n < r*m + 2}. (Here I am using * for multiplication.) In other words, N(r) is the set of points in N x N lying between the lines y = r*x - 2 and y = r*x + 2. Then it is not difficult to check (i) N(r) is infinite for each real number r between .9 and 1.1, (ii) the correspondence r <---> N(r) is one-to-one and onto (hence, there are R* many N(r)'s), and (iii) N(r) has finite intersection with N(s) whenever r is not equal to s. {This neat geometric method (proof #2) is given in J. R. Buddenhagen, "Subsets of a countable set", The American Mathematical Monthly 78 (1971), 536-537. I don't know if this proof was previously known to anyone, but I wouldn't be surprised if it was.} P.S. Because I will be moving shortly, my present e-mail address will no longer be valid in about 2 weeks.