combinatorial set theory question
David Bernier
{ (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
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
David Libert
David Bernier (ber...@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 <f_alpha | alpha ordinal < aleph_1 > 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 <r(X, alpha) | alpha < aleph_1 > 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 <s_alpha | alpha < aleph_1 > 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
<t(X, alpha) | alpha < aleph_1 >, 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 (ah...@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
Brian M. Scott
> 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
David Libert
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.
Dave L. Renfro
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.
Fred Galvin
> 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.
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.
David Bernier
Fred Galvin <gal...@math.ukans.edu> wrote:
> On Tue, 3 Aug 1999, Brian M. Scott wrote:
>
> > 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)),
> 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.
Thanks for the responses. I can see that
CH ==> maximum value of |A| is 2^continuum. [using above in ZFC]
David Libert wrote:
@ 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.
[sorry if the display is soso..]
If I understand correctly, this means
~CH ==> 2^aleph_1 < 2^continuum
I don't see how this follows.
More generally, I'd like to know a bit more about kappa for which
ZFC + ~CH is consistent with 2^aleph_1 = kappa.
(I know about cofinality. I'm not sure if it's true or not
that cof(alpha) is always a cardinal?)
Fred Galvin
It doesn't. Could be that 2^aleph_0 = aleph_5, 2_aleph_1 = aleph_8, and
2_aleph_5 = aleph_8.
> More generally, I'd like to know a bit more about kappa for which
> ZFC + ~CH is consistent with 2^aleph_1 = kappa.
Pretty much anything goes; there is no necessary relationship between
2^aleph_0 and 2^aleph_1 except that the former can't be greater than the
latter. Or so I've been told.
> (I know about cofinality. I'm not sure if it's true or not
> that cof(alpha) is always a cardinal?)
Affirmatory on that.