[math-fun] Cardinality puzzle
Let a collection C of subsets of the integers be called an "antichain" if there exists no pair of sets X,Y in C such that X is a subset of Y. Puzzle: What is the largest cardinality that an antichain can have? --Dan
Nice problem! The answer is C, the order of the continuum. For each subset S of the integers, associate a set S'. For each n, if n is not in S, 2n is in S'; if n is in S, then 2n+1 is in S'. Then the collection of all the S' is an antichain. Franklin T. Adams-Watters -----Original Message----- From: dasimov@earthlink.net Let a collection C of subsets of the integers be called an "antichain" if there exists no pair of sets X,Y in C such that X is a subset of Y. Puzzle: What is the largest cardinality that an antichain can have? --Dan ___________________________________________________ Try the New Netscape Mail Today! Virtually Spam-Free | More Storage | Import Your Contact List http://mail.netscape.com
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.) Franklin T. Adams-Watters
The answer is C, the order of the continuum.
Right. Next: what's the largest a *chain* can be?
Obviously aleph-nought. At least one integer must be added at each step. ___________________________________________________ Try the New Netscape Mail Today! Virtually Spam-Free | More Storage | Import Your Contact List http://mail.netscape.com
participants (3)
-
dasimov＠earthlink.net -
franktaw＠netscape.net -
Gareth McCaughan