12.3: Relative Sizes of Sets

We have defined a set \(A\) to be finite when we can count its elements by matching them bijectively with the elements of some counting set \(\mathbb{N}_{<m}\text{.}\) And in this case, by defining \(\vert A \vert = m\text{,}\) we are declaring that \(A\) has the same “size” as \(\mathbb{N}_{<m}\text{.}\)

Expanding on this idea, we can think of every bijection as using the elements of one set to “count” the elements of another.

Definition: Same Size

sets \(A\) and \(B\) for which there exists a bijection \(A \to B\)

Fact \(\PageIndex{1}\): Symmetry of size.

If \(B\) has the same size as \(A\text{,}\) then \(A\) has the same size as \(B\text{.}\)

Proof.

If \(f: A \rightarrow B\) is a bijection, then so is \(f^{-1} : B \rightarrow A\text{.}\)

Fact \(\PageIndex{2}\): Transitivity of size.

If \(A\) has the same size as \(B\) and \(B\) has the same size as \(C\text{,}\) then \(A\) has the same size as \(C\text{.}\)

Proof.

This is left to you as Exercise 12.6.5.

We expect our general notion of same size to match with just counting elements of finite sets and getting the same result.

Fact \(\PageIndex{3}\): Finite sets with equal cardinality have the same size.

Assume \(A\) and \(B\) are finite sets. Then \(\vert A \vert = \vert B \vert\) if and only if \(A\) and \(B\) have the same size.

Proof.

Assume equal cardinality, show same size.

Assume \(\vert A \vert = \vert B \vert = m\text{.}\) Then by definition there exist bijections \(f: \mathbb{N}_{<m} \rightarrow A\) and \(g: \mathbb{N}_{<m} \rightarrow B\text{.}\) Now \(g \circ f^{-1}\) is a bijection \(A \to B\text{,}\) so \(A\) and \(B\) have the same size according to the technical definition.

Assume same size, show equal cardinality.

Assume \(A\) and \(B\) have the same size. Then by definition there exists a bijection \(f: A \rightarrow B\text{.}\) Now, we have also assumed that \(A\) is finite, so there exists a bijection \(g: \mathbb{N}_{<m} \rightarrow A\text{,}\) where \(m = \vert A \vert\text{.}\) Then \(f \circ g: \mathbb{N}_{<m} \rightarrow B\) is a bijection that demonstrates \(\vert B \vert = m\) as well.

Warning

Your intuition may fail you when considering “sizes” of infinite sets. In particular, it is possible to have \(\vert A \vert = \vert B \vert = \infty\text{,}\) where \(A\) and \(B\) do not have the same size.

 

Example \(\PageIndex{1}\): Sets of integers and natural numbers have the same size.

Even though \(\mathbb{N} \subsetneqq \mathbb{Z}\text{,}\) \(\mathbb{N}\) and \(\mathbb{Z}\) have the same size! The following defines a bijection \(f: \mathbb{N} \rightarrow \mathbb{Z}\text{.}\)

\(n\)	\(0\)	\(1\)	\(2\)	\(3\)	\(4\)	\(\cdots\)
\(f(n)\)	\(0\)	\(-1\)	\(1\)	\(-2\)	\(2\)	\(\cdots\)

This bijection can be expressed by the formula

\begin{equation*} f(n) = \begin{cases} \dfrac{m}{2}, & m \text{ even}, \\ -\dfrac{m+1}{2}, & m \text{ odd}. \end{cases} \end{equation*}

Example \(\PageIndex{2}\): Sets of real numbers and natural numbers do not have the same size.

In Chapter 13, we will see that even though \(\vert \mathbb{N} \vert = \vert \mathbb{R} \vert = \infty\text{,}\) the sets \(\mathbb{N}\) and \(\mathbb{R}\) do not have the same size!

Example \(\PageIndex{3}\): Intervals of real numbers of different lengths have the same size.

Recall from first-year calculus that for \(a,b \in \mathbb{R}\) with \(a \lt b\text{,}\) we define the open interval from \(a\) to \(b\) to be the set of all real numbers strictly between \(a\) and \(b\text{:}\)

\begin{equation*} (a,b) = \{x \in \mathbb{R} \vert a \lt x \lt b\} \text{.} \end{equation*}

Figure \(\PageIndex{1}\): An interval on the real number line.

It turns out that, even though they may have different lengths, the interval \((a,b)\) and the unit interval \((0,1)\) have the same size! (That is, they somehow contain the same “number” of numbers.)

Construct a bijection \((0,1)\to(a,b)\) in two steps.

1. The map
   \begin{align*} f \colon (0,1) & \to (0,b-a), \\ x & \mapsto (b-a)x, \end{align*}
   is a bijection. (Check!)
2. The map
   \begin{align*} g \colon (0,b-a) & \to (a,b), \\ x & \mapsto x+a, \end{align*}
   is a bijection. (Check!)

Then \(g\circ f: (0,1) \rightarrow (a,b)\) is a bijection.

Figure \(\PageIndex{2}\): Scaling and translating the unit interval onto another interval.

Example \(\PageIndex{4}\): A punctured circle has the same size as \(\mathbb{R}\).

Define

\begin{align*} S & = \{(x,y) \in \mathbb{R}^2 \vert x^2 + (y-\dfrac{1}{2})^2 = \dfrac{1}{4} \} \text{,} & \hat{S} & = S \setminus \{(0,1)\}\text{.} \end{align*}
Here, \(S\) is a circle in the plane with radius \(\dfrac{1}{2}\) and centre \((0,\dfrac{1}{2})\text{,}\) and \(\hat{S}\) is the circle \(S\) “punctured” at the “north pole”.

We claim that \(\hat{S}\) has the same size as \(\mathbb{R}\text{.}\) Construct a bijection \(\hat{S}\to\mathbb{R}\) in two steps.

1. Let \(X\) represent the \(x\)-axis in the plane, i.e.

\begin{equation*} X = \{(x,0) \vert x \in \mathbb{R} \} \subseteq \mathbb{R}^2 \text{.} \end{equation*}
Let \(f: \hat{S} \rightarrow X\) be defined as follows: for \((x,y)\in \hat{S}\text{,}\) let \(f(x,y)\) be the \(x\)-intercept of the line through points \((0,1),(x,y)\text{.}\)

Figure \(\PageIndex{3}\): Projecting the punctured circle onto the real number line.

Then \(f\) is a bijection. (Check!)

2. We also have a bijection \(g: X \rightarrow \mathbb{R}\) by \(g(x,0) = x\text{.}\)

Therefore, the composition \(g\circ f : \hat{S} \rightarrow \mathbb{R}\) is a bijection.

Example \(\PageIndex{5}\): Every interval of real numbers has the same size as the entire set of real numbers.

Example \(\PageIndex{3}\) and Example \(\PageIndex{4}\) can be combined to demonstrate that every finite-length interval \((a,b)\) of real numbers has the same size as the entire set \(\mathbb{R}\) of real numbers. See Exercise 12.6.6.