Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Section 13.3 More about relative sizes of sets

Question 13.3.1.

What is the “size” of \(\R\text{?}\)
We know \(\N\text{,}\) \(\Z\text{,}\) and \(\Q\) all have the same size (countably infinite). But \(\R\) is so large that it is uncountable, so it seems like \(\R\) should be “larger” than \(\N\text{,}\) \(\Z\text{,}\) and \(\Q\text{.}\)
larger set
set \(B\) is larger than set \(A\) if
  1. \(B\) has a subset the same size as \(A\text{,}\) and
  2. every subset of \(B\) which is the same size as \(A\) is proper
smaller set
if \(B\) is larger than \(A\text{,}\) then \(A\) is smaller than \(B\)

Remark 13.3.3.

  1. Matching up the parts of the Test with the parts of the definition of larger set:
    1. The existence of an injection \(\ifuncdef{f}{A}{B}\) demonstrates that \(B\) has a subset that is the same size as \(A\text{,}\) as restricting the codomain to \(\funcdef{f}{A}{f(A)}\) creates a bijection.
    2. By definition, a subset \(C \subseteq B\) has the same size as \(A\) when there exists a bijection \(A \to C\text{.}\) Enlarging the codomain, such a bijection can be thought of as an injection \(A \ifuncto B\) whose image is \(C \subseteq B\text{.}\) If no such injection can also be surjective, then \(C \subsetneqq B\text{,}\) i.e. \(C\) is a proper subset of \(B\text{.}\)
  2. In the second part of the test, one can simply show that every function \(A \to B\) cannot be a surjection, in which case surely every injection \(A \ifuncto B\) cannot be a surjection. It may seem like it should be more difficult to prove this more general statement, but if you will find that your argument that every injection cannot be a surjection does not actually rely on the injective assumption, then there is no need for that assumption.

Example 13.3.4.

Set \(\R\) is larger than each of the sets \(\N\text{,}\) \(\Z\text{,}\) and \(\Q\text{.}\)
Here follows an important comparison of set sizes.
Let \(A\) represent an arbitrary set. We will apply the Larger Set Test to demonstrate that \(\powset{A}\) is larger than \(A\text{.}\)
  1. There exists a natural injection
    \begin{align*} A \amp \ifuncto \powset{A}, \\ x \amp \mapsto \{x\}. \end{align*}
    (If \(A\) is empty, then this is just the empty function, which is always injective by Statement 1 of Proposition 12.1.6.)
  2. Suppose \(\funcdef{f}{A}{\powset{A}}\) is an arbitrary function. Using the Surjective Function Test, we will demonstrate that it cannot be surjective by exhibiting an element \(X \in \powset{A}\) for which no element \(a \in A\) satisfies \(f(a) = X\text{.}\) (We will not need to make the assumption that \(f\) is injective — see Statement 2 of Remark 13.3.3.)
    Note that for each \(a \in A\text{,}\) the image element \(f(a) \in \powset{A}\text{,}\) being a power set element, is a subset of \(A\text{.}\) So for each \(a \in A\) we can ask whether \(a\) is contained in the subset \(f(a)\) or not. Collecting together the “or not” answers, set
    \begin{equation*} X = \setdef{a \in A}{a \notin f(a)}. \end{equation*}
    Note that \(X\) is a subset of \(A\text{,}\) so again this means that it is also an element of \(\powset{A}\text{.}\)
    Could \(f(a) = X\) be possible for some \(a \in A\text{?}\) Since \(X \subseteq A\text{,}\) for each \(a \in A\) we have either \(a \in X\) or \(a \notin X\text{.}\)

    Case \(a \in X\).

    Then by definition of \(X\) above, we have \(a \notin f(a)\text{.}\) Since \(X\) contains element \(a\) but \(f(a)\) does not, sets \(X\) and \(f(a)\) cannot be equal.

    Case \(a \notin X\).

    Then by definition of \(X\) above, we must have \(a \in f(a)\text{,}\) since otherwise \(a\) would satisfy the condition to be in \(X\text{.}\) But now \(f(a)\) contains element \(a\) but \(X\) does not, so again sets \(X\) and \(f(a)\) cannot be equal.
    Since \(f(a) = X\) is not possible in all cases, we have found an element in \(\powset{A}\) that is not in the image \(f(A)\text{,}\) as required to demonstrate that \(f\) is not surjective.

Remark 13.3.6.

Cantor’s Theorem implies that there are an infinite number of “levels” of infinity! For, if \(A\) is an infinite set, then \(\powset{A}\) is a larger infinite set, and \(\powset{\powset{A}}\) is a still larger infinite set, and \(\powset{\powset{\powset{A}}}\) is a still larger infinite set, ….
The size of the set of natural numbers \(\N\) seems like the lowest possible level of infinity, since every subset of \(\N\) is either finite or has the same size as \(\N\text{.}\) (See Statement 1 of Proposition 13.2.1.) The set of real numbers \(\R\) is larger than \(\N\text{,}\) since it contains \(\N\) as a proper subset but is not itself the same size as \(\N\text{.}\) So writing \(\card{\N} = \infty\) is not the same as writing \(\card{\R} = \infty\text{,}\) as they are evidently different levels of infinity. Is there any level of infinity between these two?

Remark 13.3.8.

It is not known whether the Continuum Hypothesis is true! In fact, it has been proved that the Continuum Hypothesis can be neither proved nor disproved in certain common axiomatic systems for set theory!
We have seen that funny things can happen with sizes of infinite sets — for example, \(\N\) is an proper subset of \(\Z\text{,}\) but the two have the same size! This is not a defect in our definitions, it just demonstrates that for infinite sets, the subset relation is not a good measure of size. But it also demonstrates that we should be vigilant about other possible unintuitive consequences of our definitions, because they might reveal defects in our definitions. For example, from our definitions of smaller and larger sets, there is no obvious reason why there could not be some weird example of a pair of sets \(A\) and \(B\) with both \(B\) larger than \(A\) and \(A\) larger than \(B\text{.}\) Luckily, that cannot happen thanks to the following theorem.
Suppose \(\ifuncdef{f}{A}{B}\) and \(\ifuncdef{g}{B}{A}\) are injections. We need to exhibit a bijection from \(A\) to \(B\) (or vice versa, but we will construct one from \(A\) to \(B\)).
For every element \(a \in A\text{,}\) we can construct a chain of alternating elements from \(A\) and \(B\) as follows. Working forwards from \(a\text{,}\) the injection \(f\) maps \(a\) to some element of \(B\text{,}\) and the injection \(g\) maps that element of \(B\) to some element of \(A\text{,}\) which is mapped by \(f\) to some element of \(B\text{,}\) and so on.
\begin{align*} a_0 \amp = a, \\ b_0 \amp = f(a_0), \\ a_1 \amp = g(b_0), \\ b_1 \amp = f(a_1), \\ a_2 \amp = g(b_1), \\ \amp \phantom{=} \vdots \end{align*}
The chain will go on infinitely because the functions \(f\) and \(g\) always provide a next element.
We can also try to trace the chain backwards: starting at our original element \(a \in A\text{,}\) we can look for some element of \(B\) that \(g\) maps to \(a\text{,}\) though at first consideration it’s possible that none exists. If we do find such an element of \(B\text{,}\) we can then look for some element of \(A\) that \(f\) maps to it, and so on. While the chain extends infinitely in the forward direction, we cannot be sure at this point that it will extend infinitely in the backward direction.
Now, every element of \(A\) can be placed into such a chain, and because \(f\) and \(g\) are injective the chain in which we find an element \(a\) is always the same: the next element in the chain is always \(f(a)\text{,}\) and the element before \(a\) is always the unique \(b\) in \(B\) so that \(g(b) = a\) (if such an element exists). And the elements after \(f(a)\) and before \(b\) are also uniquely determined by the injectiveness of \(f\) and \(g\text{.}\) And so on.
So we end up finding every element of \(A\) in a unique alternating chain, and each chain has one of four patterns:
  • a chain with some element repeated, in which case we could force the chain to loop back on itself at the repetition to form a finite, circular chain;
  • a chain with no repetition and no end or start;
  • a chain with no repetition and no end, but the process to trace it backward failed at some point, and the last element in the “backward” direction (which we could view as the first element in the whole chain) is an element of \(A\text{;}\) and
  • a chain with no repetition and no end, but starts with an element of \(B\text{.}\)
Now that we have cut out possible repetition by creating circular chains, every element of \(A\) appears exactly once in a unique chain, and by symmetry the same can be said about \(B\text{.}\) We can then create a bijection from \(A\) to \(B\) by mapping every element of \(A\) to the element of \(B\) that follows it in the chain it appears in. Except for elements of \(A\) that appear in a chain that has a beginning with a starting element from \(B\) — instead each of those elements of \(A\) should be mapped to the element of \(B\) that precedes it in its chain. This will create a bijective correspondence between the elements of \(A\) and \(B\text{.}\)
<Prev^TopNext>