# Cardinality of a Set

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

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

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:

${\left| \varnothing \right| = 0.}$

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,

$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|.$