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,\dots \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,\dots$. 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 $f\left(1\right)=0.58109205$ and change the $1\text{st}$ decimal place value to something different, say $5\to 9.$ Similarly, take the second number $f\left(2\right)=5.30159257$ and change the $2\text{nd}$ decimal place: $0\to 6.$ Continue this process for all $n\in \mathbb{N}.$ The number $b=0.96\dots$ 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