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 Read more...
	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.

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

Copyright © 1996-2018 Alexander Bogomolny