To prove this, recall first that there are as many rational numbers as there are naturals, and one can thus construct a bijection between one and the other. (Readers unfamiliar with this construction will find it a nice exercise to come up with such bijections.)
We can, therefore, think about S not as a set of subsets of the naturals with an ordering according to the subset relation, but as a set of subsets of the rationals with an ordering according to the subset relation.
One famous example of a set that has the properties we require of S is the Dedekind cuts. Simply stated, for every real number r, define an element of S to be the set of all rationals smaller than r.
Clearly, this definition of S satisfies all necessary criteria, and clearly it has as many elements as there are real numbers, so uncountably many.
I thank Zhengpeng Wu for pointing out Béla Bollobás's highly recommended "The Art of Mathematics: Coffee Time in Memphis" as a possible source for this riddle. On page 61, Bollobás writes "This was one of my standard questions for freshmen in Cambridge". For readers who enjoyed this challenge, Bollobás proposes another (according to him: simpler) variation on this riddle: design an uncountable collection of subsets of the naturals, such that each pair in the collection has only a finite intersection.
Back to riddle
Back to main page