Cardinality of a Set

Definition

Consider a set A. If A contains exactly n elements, where n ≥ 0, then we say that the set A is finite and its cardinality is equal to the number of elements n. The cardinality of a set A is denoted by |A|. For example,

\[A = \left\{ {1,2,3,4,5} \right\}, \Rightarrow \left| A \right| = 5.\]

Recall that we count only distinct elements, so |{1, 2, 1, 4, 2}| = 3.

The cardinality of the empty set is equal to zero:

\[{\left| \varnothing \right| = 0.}\]

The concept of cardinality can be generalized to infinite sets.

If no bijection exists from \(A\) to \(B,\) then the sets have unequal cardinalities, that is, \(\left| A \right| \ne \left| B \right|.\)

If sets \(A\) and \(B\) have the same cardinality, they are said to be equinumerous. In this case, we write \(A \sim B.\) More formally,

\[A \sim B \;\text{ iff }\; \left| A \right| = \left| B \right|.\]

Equinumerosity is an equivalence relation on a family of sets. The equivalence class of a set \(A\) under this relation contains all sets with the same cardinality \(\left| A \right|.\)

Examples of Sets with Equal Cardinalities

The Sets \(\mathbb{N}\) and \(\mathbb{O}\)

The mapping \(f : \mathbb{N} \to \mathbb{O}\) between the set of natural numbers \(\mathbb{N}\) and the set of odd natural numbers \(\mathbb{O} = \left\{ {1,3,5,7,9,\ldots } \right\}\) is defined by the function \(f\left( n \right) = 2n - 1,\) where \(n \in \mathbb{N}.\) This function is bijective. Therefore both sets \(\mathbb{N}\) and \(\mathbb{O}\) have the same cardinality: \(\left| \mathbb{N} \right| = \left| \mathbb{O} \right|.\)

Two Finite Intervals

Let \(\left( {a,b} \right)\) and \(\left( {c,d} \right)\) be two open finite intervals on the real axis. We show that any intervals \(\left( {a,b} \right)\) and \(\left( {c,d} \right)\) have the equal cardinality.

The mapping from \(\left( {a,b} \right)\) and \(\left( {c,d} \right)\) is given by the function

\[f(x) = c + \frac{{d - c}}{{b - a}}\left( {x - a} \right) = y,\]

where \(x \in \left( {a,b} \right)\) and \(y \in \left( {c,d} \right).

Check the mapping of the endpoints:

\[f\left( a \right) = c + \frac{{d - c}}{{b - a}}\left( {a - a} \right) = c + 0 = c,\]

\[\require{cancel}f\left( b \right) = c + \frac{{d - c}}{\cancel{b - a}}\cancel{\left( {b - a} \right)} = \cancel{c} + d - \cancel{c} = d.\]

Prove that the function \(f\) is injective. The contrapositive statement is \(f\left( {{x_1}} \right) = f\left( {{x_2}} \right)\) for \({x_1} \ne {x_2}.\) If so, then we have

\[f\left( {{x_1}} \right) = f\left( {{x_2}} \right),\;\; \Rightarrow c + \frac{{d - c}}{{b - a}}\left( {{x_1} - a} \right) = c + \frac{{d - c}}{{b - a}}\left( {{x_2} - a} \right),\;\; \Rightarrow \frac{{d - c}}{{b - a}}\left( {{x_1} - a} \right) = \frac{{d - c}}{{b - a}}\left( {{x_2} - a} \right),\;\; \Rightarrow {x_1} - a = {x_2} - a,\;\; \Rightarrow {x_1} = {x_2}.\]

This is a contradiction. Therefore the function \(f\) is injective.

Make sure that \(f\) is surjective. Take a number \(y\) from the codomain \(\left( {c,d} \right)\) and find the preimage \(x:\)

\[y = c + \frac{{d - c}}{{b - a}}\left( {x - a} \right),\;\; \Rightarrow \frac{{d - c}}{{b - a}}\left( {x - a} \right) = y - c,\;\; \Rightarrow x - a = \frac{{b - a}}{{d - c}}\left( {y - c} \right),\;\; \Rightarrow x = a + \frac{{b - a}}{{d - c}}\left( {y - c} \right).\]

The preimage \(x\) lies in the domain \(\left( {a,b} \right)\) and

\[f\left( x \right) = f\left( {a + \frac{{b - a}}{{d - c}}\left( {y - c} \right)} \right) = c + \frac{{d - c}}{{b - a}}\left( {\cancel{a} + \frac{{b - a}}{{d - c}}\left( {y - c} \right) - \cancel{a}} \right) = c + \frac{\cancel{d - c}}{\cancel{b - a}} \cdot \frac{\cancel{b - a}}{\cancel{d - c}}\left( {y - c} \right) = \cancel{c} + y - \cancel{c} = y.\]

We see that the function \(f\) is surjective. Since \(f\) is both injective and surjective, it is bijective. Hence, the intervals \(\left( {a,b} \right)\) and \(\left( {c,d} \right)\) are equinumerous.

The Sets \(\mathbb{N}\) and \(\mathbb{Z}\)

This canonical example shows that the sets \(\mathbb{N}\) and \(\mathbb{Z}\) are equinumerous. To prove this, we need to find a bijective function from \(\mathbb{N}\) to \(\mathbb{Z}\) (or from \(\mathbb{Z}\) to \(\mathbb{N}\)).

Let's arrange all integers \(z \in \mathbb{Z}\) in the following order:

\[0, - 1,1, - 2,2, - 3,3, - 4,4, \ldots \]

Now we numerate this sequence with natural numbers \(1,2,3,4,5,\ldots\). As a result, we get a mapping from \(\mathbb{Z}\) to \(\mathbb{N}\) that is described by the function

\[n = f\left( z \right) = \left\{ {\begin{array}{*{20}{l}} {2z + 1,} & {\text{if }\; z \ge 0}\\ {2\left| z \right|,} & {\text{if }\; z \lt 0} \end{array}} \right..\]

The function \(f\) is injective because \(f\left( {{z_1}} \right) \ne f\left( {{z_2}} \right)\) whenever \({z_1} \ne {z_2}.\) It is also surjective because, given any natural number \(n \in \mathbb{N},\) there is an integer \(z \in \mathbb{Z}\) such that \(n = f\left( z \right).\) Hence, the function \(f\) is bijective, which means that both sets \(\mathbb{N}\) and \(\mathbb{Z}\) are equinumerous:

\[\left| \mathbb{N} \right| = \left| \mathbb{Z} \right|.\]

Cardinality of the Sets \(\mathbb{N}\) and \(\mathbb{R}\)

It is interesting to compare the cardinalities of two infinite sets: \(\mathbb{N}\) and \(\mathbb{R}.\) It turns out that \(\left| \mathbb{N} \right| \ne \left| \mathbb{R} \right|.\) This was proved by Georg Cantor in \(1891\) who showed that there are infinite sets which do not have a bijective mapping to the set of natural numbers \(\mathbb{N}.\) This proof is known as Cantor's diagonal argument.

Consider an arbitrary function \(f: \mathbb{N} \to \mathbb{R}.\) Suppose the function has the following values \(f\left( n \right)\) for the first few entries \(n:\)

We now construct a diagonal that covers the \(n\text{th}\) decimal place of \(f\left( n \right)\) for each \(n \in \mathbb{N}.\) This diagonal helps us find a number \(b\) in the codomain \(\mathbb{R}\) that does not match any value of \(f\left( n \right).\)

Take, the first number \(\color{#006699}{f\left( 1 \right)} = 0.\color{#f40b37}{5}8109205\) and change the \(1\text{st}\) decimal place value to something different, say \(\color{#f40b37}{5} \to \color{blue}{9}.\) Similarly, take the second number \(\color{#006699}{f\left( 2 \right)} = 5.3\color{#f40b37}{0}159257\) and change the \(2\text{nd}\) decimal place: \(\color{#f40b37}{0} \to \color{blue}{6}.\) Continue this process for all \(n \in \mathbb{N}.\) The number \(b = 0.\color{blue}{96\ldots}\) will consist of the modified values in each cell of the diagonal. It is clear that \(f\left( n \right) \ne b\) for any \(n \in \mathbb{N}.\) This means that the function \(f\) is not surjective. Hence, there is no bijection from \(\mathbb{N}\) to \(\mathbb{R}.\) Therefore

\[\left| \mathbb{N} \right| \ne \left| \mathbb{R} \right|.\]

See solved problems on Page 2.

Calculus