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?| |Store|

The claim holds for the set Q of rational numbers. Indeed, for every real α define A_α = {r∈Q: r < α}, the set of rational numbers that are less than α. Well, that's it. Not only the sets A_α are indexed by real numbers and are all distinct, they are also nested: α < β implies that A_α is a proper subset of A_β (A ⊂ B, A ≠ B) because between the real α and β there is a good deal of rational numbers.

References

1. 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?| |Store|