Re: [math-fun] Cardinality puzzle - answer
Franklin wrote: << Here's a related problem. Can you describe a *maximal* uncountable antichain?
<< More difficult: describe an (uncountable) maximal antichain where every set is infinite. (I don't know the answer to this second question. It might be: no, no such description is possible.)
The antichain A = { Z - {n} : n is in Z} is maximal and contains only infinite sets: (Any other proper subset of Z must be missing at least 2 integers m and n, so is a proper subset of Z - {n}, so cannot be added to A -- and of course Z can't either. ) << [Gareth wrote:]
. . . Next: what's the largest a *chain* [of subsets of Z] can be?
Obviously aleph-nought. At least one integer must be added at each step.
There is a subtle flaw in the argument here, which is why this is such a great puzzle. --Dan
Franklin wrote:
<< Here's a related problem. Can you describe a *maximal* uncountable antichain?
I do have a solution for this problem.
<< More difficult: describe an (uncountable) maximal antichain where every set is infinite. (I don't know the answer to this second question. It might be: no, no such description is possible.)
The antichain A = { Z - {n} : n is in Z} is maximal and contains only infinite sets:
OK, but now try it with the uncountable condition; this antichain is countable.
(Any other proper subset of Z must be missing at least 2 integers m and n, so is a proper subset of Z - {n}, so cannot be added to A -- and of course Z can't either. )
<< [Gareth wrote:]
. . . Next: what's the largest a *chain* [of subsets of Z] can be?
Obviously aleph-nought. At least one integer must be added at each step.
There is a subtle flaw in the argument here, which is why this is such a great puzzle.
You're right. C is again the answer. See Dedekind cuts. ___________________________________________________ Try the New Netscape Mail Today! Virtually Spam-Free | More Storage | Import Your Contact List http://mail.netscape.com
--- franktaw@netscape.net wrote:
Franklin wrote:
<< Here's a related problem. Can you describe a *maximal* uncountable antichain?
I do have a solution for this problem.
<< More difficult: describe an (uncountable) maximal antichain where every set is infinite. (I don't know the answer to this second question. It might be: no, no such description is possible.)
The antichain A = { Z - {n} : n is in Z} is maximal and contains only infinite sets:
OK, but now try it with the uncountable condition; this antichain is countable.
(Any other proper subset of Z must be missing at least 2 integers m and n, so is a proper subset of Z - {n}, so cannot be added to A -- and of course Z can't either. )
<< [Gareth wrote:]
. . . Next: what's the largest a *chain* [of subsets of Z] can be?
Obviously aleph-nought. At least one integer must be added at each step.
There is a subtle flaw in the argument here, which is why this is such a great puzzle.
You're right. C is again the answer. See Dedekind cuts.
Yes, that hint does it! For each real number t, let S[t] be the set of rationals less than t. So we have an uncountable chain of infinite sets. If t1 < t2, then when S[t1] is enlarged to S[t2], only a countable number of rationals are added. How can there be an uncountable number of distinct nested sets between S[t1] and S[t2] when there are only a countable number of elements available??? An uncountable antichain can be constructed the same way. Let A[t] be the set of rationals that are < t-1 or > t+1. This has been a very intuition-upsetting puzzle. Gene __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
participants (3)
-
dasimov＠earthlink.net -
Eugene Salamin -
franktaw＠netscape.net