# Using your Head is Permitted

## May 2015 solution

Yes, *S* can have uncountably many elements.
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