# 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,

Recall that we count only distinct elements, so |{1, 2, 1, 4, 2}| = 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