wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Another cardinality question
        
(Message started by: Deedlit on Apr 9^th, 2005, 11:34pm)

Title: Another cardinality question
Post by Deedlit on Apr 9^th, 2005, 11:34pm

We've been talking about cardinals, so here's a neat problem:

Define a family of sets to be "countably disjoint" if the intersection of any two sets in the family is countable. What is the largest cardinality a family of countably disjoint sets of reals can have?

Title: Re: Another cardinality question
Post by towr on Apr 10^th, 2005, 6:54am

[hideb]Infinitely many if f.i. you take just one element in each set.
An empty set seems countable to me anyway..

You could also take the sets Si = [i..i+1], i \in Z.
Then at least some intersections aren't empty.[/hideb]

Title: Re: Another cardinality question
Post by Eigenray on Apr 10^th, 2005, 8:40am

Does the answer depend on the continuum hypothesis? Assuming CH, it looks like [hide]beth₂[/hide], which, if you also assume GCH, is just [hide]aleph₂[/hide].

Title: Re: Another cardinality question
Post by Deedlit on Apr 10^th, 2005, 8:50pm

That's correct, but you can answer the question without reference to CH.

I'll edit the OP to specify cardinality.

Title: Re: Another cardinality question
Post by Eigenray on Apr 11^th, 2005, 3:50pm

So is it 2^omega_1 or 2^c?

Title: Re: Another cardinality question
Post by Deedlit on Apr 11^th, 2005, 4:41pm

It's 2^omega_1. I thought it was neat, since you had such an unusual cardinal as the answer to such a normal sounding question. (of course, the word "countable" is key here.)

Edit: first put the answer in hide, then realized how silly it was. :P

Title: Re: Another cardinality question
Post by Eigenray on Apr 12^th, 2005, 4:10pm

Well, here's why it's at least 2^omega_1:
First note that if X is the union, over a < [omega]₁, of binary a-sequences, then |X| = [omega]₁*|R|=|R|, so we can work with subsets of X instead. Now for each of the 2^omega_1 binary [omega]₁-sequences, associate to it the set of all its initial segments, which is a subset of X, and the intersection of any two such sets is countable, as two [omega]₁-sequences differ at some countable position < [omega]₁.

I can't think of a way to show it's no more than 2^omega_1 though.

Title: Re: Another cardinality question
Post by Deedlit on Apr 12^th, 2005, 6:19pm

Well done! For the upper bound, you can inject the set into another set whose cardinality is clearly 2^omega_1

Title: Re: Another cardinality question
Post by Deedlit on May 21^st, 2005, 3:40am

The solution for the other direction:

[hideb]
For any countably disjoint family of sets F, we can choose an function f: F -> P(R) such that every set f(S) is either S, or a subset of S of cardinality omega₁. (we use the axiom of choice here) Then f is an injection; if f(S) = f(T) is a countable set, then f(S) = S and f(T) = T, and S = T. If f(S) = f(T) is uncountable, than S and T agree on an uncountable set, so S = T again. But the number of subsets of R with cardinality at most omega₁ is 2^omega₁; this set is clearly injectable into the functions from omega₁ to R, and the number of such functions is (2^omega)^omega₁ = 2^omega₁.
[/hideb]

An interesting question is how much can be done without the axiom of choice. I'm pretty sure that |R| <= omega₁ doesn't necessarily hold without AC, so max |F| >= 2^omega₁ won't hold either. I have a feeling that (2^omega)^omega₁ = 2^omega₁ isn't necessarily true as well, so that would kill the above proof.