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.

Related material

Math Curiosities

  • Infinity and Probability
  • Shuttle Puzzle Practice I
  • Ratchet Effect
  • Structural Constellation
  • Scrub Tile Puzzle
  • Possible or Impossible?
  • |Contact| |Front page| |Contents| |Algebra| |Did you know?|

    Copyright © 1996-2018 Alexander Bogomolny

    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.


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

    Copyright © 1996-2018 Alexander Bogomolny