# Nested Subsets

Every infinite set contains uncountably many nested subsets

Yes, this is true even for a countable set: every countable set contains uncountably many nested subsets.

The result may sound stunning, even implausible, when you first hear it, however, there is in fact not much of a surprise. Indeed, the power set (the set of all subsets) of a countable set is a continuum. So every countable set contains uncountably many subsets. The point of the assertion is that a significant part of those subsets, i.e., uncountably many of them, form a totally ordered set.

Also, since every infinite set contains a countable subset, the problem only needs to be solved for countable sets.

What else? All countable sets admit a 1-1 correspondence with the set of natural numbers and, therefore, between themselves as well. There is a 1-1 correspondence between any two countable sets, implying that, when choosing a countable subset of a given infinite set, we may imagine this countable subset to be any one of the better known countable sets.

To say any more is to give away the solution.

|Contact| |Front page| |Contents| |Algebra| |Did you know?|

Copyright © 1996-2018 Alexander BogomolnyThe claim holds for the set Q of rational numbers. Indeed, for every real α define _{α} = {r∈Q: r < α},_{α} are indexed by real numbers and are all distinct, they are also nested: _{α} is a proper subset of A_{β}

### References

- B. Bollobás,
*The Art of Mathematics: Coffee Time in Memphis*, Cambridge University Press, 2006, pp. 61-62

|Contact| |Front page| |Contents| |Algebra| |Did you know?|

Copyright © 1996-2018 Alexander Bogomolny