Definition

Consider a set \(A.\) If \(A\) contains exactly \(n\) elements, where \(n \ge 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 \(\left| A \right|.\) For example,

Recall that we count only distinct elements, so \(\left| {\left\{ {1,2,1,4,2} \right\}} \right| = 3.\)

The cardinality of the empty set is equal to zero:

The concept of cardinality can be generalized to infinite sets.

Two infinite sets \(A\) and \(B\) have the same cardinality (that is, \(\left| A \right| = \left| B \right|\)) if there exists a bijection \(A \to B.\) This bijection-based definition is also applicable to finite sets. A bijection between finite sets \(A\) and \(B\) will exist if and only if \(\left| A \right| = \left| B \right| = n.\)

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,

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

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

Check the mapping of the endpoints:

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

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:\)

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

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:

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

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:

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