Author |
Topic: Another cardinality question (Read 1457 times) |
|
Deedlit
Senior Riddler
Posts: 476
|
 |
Another cardinality question
« on: Apr 9th, 2005, 11:34pm » |
 Quote  Modify
|
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?
|
| « Last Edit: Apr 10th, 2005, 8:51pm by Deedlit » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Another cardinality question
« Reply #1 on: Apr 10th, 2005, 6:54am » |
Quote Modify
|
| hidden: | 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. |
|
| « Last Edit: Apr 10th, 2005, 6:55am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Another cardinality question
« Reply #2 on: Apr 10th, 2005, 8:40am » |
Quote Modify
|
Does the answer depend on the continuum hypothesis? Assuming CH, it looks like beth2, which, if you also assume GCH, is just aleph2.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another cardinality question
« Reply #3 on: Apr 10th, 2005, 8:50pm » |
Quote Modify
|
That's correct, but you can answer the question without reference to CH.
I'll edit the OP to specify cardinality.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Another cardinality question
« Reply #4 on: Apr 11th, 2005, 3:50pm » |
Quote Modify
|
So is it 2omega_1 or 2c?
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another cardinality question
« Reply #5 on: Apr 11th, 2005, 4:41pm » |
Quote Modify
|
It's 2omega_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. 
|
| « Last Edit: Apr 11th, 2005, 4:43pm by Deedlit » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Another cardinality question
« Reply #6 on: Apr 12th, 2005, 4:10pm » |
Quote Modify
|
Well, here's why it's at least 2omega_1:
First note that if X is the union, over a < [omega]1, of binary a-sequences, then |X| = [omega]1*|R|=|R|, so we can work with subsets of X instead. Now for each of the 2omega_1 binary [omega]1-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]1-sequences differ at some countable position < [omega]1.
I can't think of a way to show it's no more than 2omega_1 though.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another cardinality question
« Reply #7 on: Apr 12th, 2005, 6:19pm » |
Quote Modify
|
Well done! For the upper bound, you can inject the set into another set whose cardinality is clearly 2omega_1
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Another cardinality question
« Reply #8 on: May 21st, 2005, 3:40am » |
Quote Modify
|
The solution for the other direction:
| hidden: |
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 omega1. (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 omega1 is 2omega1; this set is clearly injectable into the functions from omega1 to R, and the number of such functions is (2omega)omega1 = 2omega1.
|
An interesting question is how much can be done without the axiom of choice. I'm pretty sure that |R| <= omega1 doesn't necessarily hold without AC, so max |F| >= 2omega1 won't hold either. I have a feeling that (2omega)omega1 = 2omega1 isn't necessarily true as well, so that would kill the above proof.
|
| « Last Edit: May 21st, 2005, 3:41am by Deedlit » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print