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

$\require{AMSsymbols}{\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|.$

## Solved Problems

Click or tap a problem to see the solution.

### Example 1

Show that the sets $$\mathbb{R}$$ and $$\left( {0,1} \right)$$ have the same cardinality.

### Example 2

Show that the sets $$\mathbb{R}$$ and $$\left( {1,\infty} \right)$$ have the same cardinality.

### Example 3

Prove that the intervals $$\left( {0,1} \right]$$ and $$\left( {0,1} \right)$$ have the same cardinality.

### Example 4

Prove that any two disks have the same cardinality.

### Example 5

Show that the sets $$\mathbb{N}^2$$ and $$\left\{ {n,m \in {\mathbb{N}^2} \;\bigg|\; n \lt m}\right\}$$ have the same cardinality.

### Example 1.

Show that the sets $$\mathbb{R}$$ and $$\left( {0,1} \right)$$ have the same cardinality.

Solution.

We need to find a bijective function between the two sets.

Let’s take the inverse tangent function $$\arctan x$$ and modify it to get the range $$\left( {0,1} \right).$$ The initial range is given by

$– \frac{\pi }{2} \lt \arctan x \lt \frac{\pi }{2}.$

We divide all terms of the inequality by $${\pi }$$ and add $$\large{\frac{1}{2}}\normalsize:$$

${- \frac{1}{2} \lt \frac{1}{\pi }\arctan x \lt \frac{1}{2},}\;\; \Rightarrow {0 \lt \frac{1}{\pi }\arctan x + \frac{1}{2} \lt 1.}$

Make sure that the function $$y = f\left( x \right) = \large{\frac{1}{\pi }}\normalsize \arctan x + \large{\frac{1}{2}}\normalsize$$ is bijective.

Assume that $${x_1} \ne {x_2}$$ but $$f\left( {{x_1}} \right) = f\left( {{x_2}} \right).$$ Then

${\frac{1}{\pi }\arctan {x_1} + \frac{1}{2} }={ \frac{1}{\pi }\arctan {x_2} + \frac{1}{2},}\;\; \Rightarrow {\frac{1}{\pi }\arctan {x_1} = \frac{1}{\pi }\arctan {x_2},}\;\; \Rightarrow {\arctan {x_1} = \arctan {x_2},}\;\; \Rightarrow {\tan \left( {\arctan {x_1}} \right) = \tan \left( {\arctan {x_2}} \right),}\;\; \Rightarrow {{x_1} = {x_2},}$

which is a contradiction. Hence, the function $$f$$ is injective.

Prove that $$f$$ is surjective. Take an arbitrary value $$y$$ in the interval $$\left( {0,1} \right)$$ and find its preimage $$x:$$

${y = f\left( x \right) = \frac{1}{\pi }\arctan x + \frac{1}{2},}\;\; \Rightarrow {y – \frac{1}{2} = \frac{1}{\pi }\arctan x,}\;\; \Rightarrow {\pi y – \frac{\pi }{2} = \arctan x,}\;\; \Rightarrow {x = \tan \left( {\pi y – \frac{\pi }{2}} \right) }={ – \cot \left( {\pi y} \right).}$

Check that $$f\left( x \right) = y:$$

${f\left( x \right) = \frac{1}{\pi }\arctan x + \frac{1}{2} }={ \frac{1}{\pi }\arctan \left[ {\tan \left( {\pi y – \frac{\pi }{2}} \right)} \right] + \frac{1}{2} }={ \frac{1}{\pi }\left( {\pi y – \frac{\pi }{2}} \right) + \frac{1}{2} }={ y – \cancel{\frac{1}{2}} + \cancel{\frac{1}{2}} }={ y.}$

Thus, the function $$f$$ is surjective. Since $$f$$ is both injective and surjective, it is bijective. Therefore, the sets $$\mathbb{R}$$ and $$\left( {0,1} \right)$$ have equal cardinality:

$\left| \mathbb{R} \right| = \left| {\left( {0,1} \right)} \right|.$

### Example 2.

Show that the sets $$\mathbb{R}$$ and $$\left( {1,\infty} \right)$$ have the same cardinality.

Solution.

We already know from the previous example that there is a bijection from $$\mathbb{R}$$ to $$\left( {0,1} \right).$$ So, if we find a bijection from $$\left( {0,1} \right)$$ to $$\left( {1,\infty} \right),$$ we prove that the sets $$\mathbb{R}$$ and $$\left( {1,\infty} \right)$$ have equal cardinality since equinumerosity is an equivalence relation, and hence, it is transitive.

One of the simplest functions that maps the interval $$\left( {0,1} \right)$$ to $$\left( {1,\infty} \right)$$ is the reciprocal function $$y = f\left( x \right) = \large{\frac{1}{x}}.$$

To see that the function $$f$$ is injective, we take $${x_1} \ne {x_2}$$ and suppose that $$f\left( {{x_1}} \right) = f\left( {{x_2}} \right).$$ This yields:

${f\left( {{x_1}} \right) = f\left( {{x_2}} \right),}\;\; \Rightarrow {\frac{1}{{{x_1}}} = \frac{1}{{{x_2}}},}\;\; \Rightarrow {{x_1} = {x_2}.}$

This contradiction shows that $$f$$ is injective.

To see that $$f$$ is surjective, we choose an arbitrary value $$y$$ in the codomain $$\left( {1,\infty} \right).$$ Solving the equation $$y = \large{\frac{1}{x}}\normalsize,$$ we get $$x = \large{\frac{1}{y}}\normalsize$$ where $$x$$ always lies in the domain $$\left( {0,1} \right).$$ Then

$f\left( x \right) = \frac{1}{{\left( {\frac{1}{y}} \right)}} = y.$

As it can be seen, the function $$f\left( x \right) = \large{\frac{1}{x}}\normalsize$$ is injective and surjective, and therefore it is bijective. So,

$\left| R \right| = \left| {\left( {1,\infty } \right)} \right|.$

### Example 3.

Prove that the intervals $$\left( {0,1} \right]$$ and $$\left( {0,1} \right)$$ have the same cardinality.

Solution.

To build a bijection from the half-open interval $$\left( {0,1} \right]$$ to the open interval $$\left( {0,1} \right),$$ we choose an infinite sequence $$\left\{ {{x_n}} \right\}$$ such that all its elements belong to $$\left( {0,1} \right].$$ We can choose, for example, the sequence $$\left\{ {{x_n}} \right\} = \large{\frac{1}{n}}\normalsize,$$ where $$n \ge 1.$$

The mapping between the two sets is defined by the function $$f:\left( {0,1} \right] \to \left( {0,1} \right)$$ that maps each term of the sequence to the next one:

${f\left( {{x_n}} \right) = {x_{n + 1}},\;\text{ or }\;}\kern0pt{\frac{1}{n} \to \frac{1}{{n + 1}}.}$

For example,

${f\left( {{x_1}} \right) = f\left( 1 \right) = {x_2} = \frac{1}{2},\;\;}\kern0pt{f\left( {{x_2}} \right) = f\left( {\frac{1}{2}} \right) = {x_3} = \frac{1}{3}, \ldots }$

All other values of $$x$$ different from $$x_n$$ do not change. Thus, the mapping function is given by

$f\left( x \right) = \left\{ {\begin{array}{*{20}{l}} {\frac{1}{{n + 1}}} &{\text{if }\; x = \frac{1}{n}}\\ {x} &{\text{if }\; x \ne \frac{1}{n}} \end{array}} \right.,$

where $$n \in \mathbb{N}.$$

The function $$f$$ is bijective. Hence,

$\left| {\left( {0,1} \right]} \right| = \left| {\left( {0,1} \right)} \right|.$

### Example 4.

Prove that any two disks have the same cardinality.

Solution.

Consider two disks with radii $$R_1$$ and $$R_2$$ centered at the origin. An arbitrary point $$M$$ inside the disk with radius $$R_1$$ is given by the polar coordinates $$\left( {r,\theta } \right)$$ where $$0 \le r \le {R_1},$$ $$0 \le \theta \lt 2\pi .$$

The mapping function $$f$$ between the disks is defined by

$f\left( {r,\theta } \right) = \left( {\frac{{{R_2}r}}{{{R_1}}},\theta } \right).$

It matches up the points $$\left( {r,\theta } \right)$$ in the $$1\text{st}$$ disk with the points $$\left( {\large{\frac{{{R_2}r}}{{{R_1}}}}\normalsize,\theta } \right)$$ of the $$2\text{nd}$$ disk.

Show that the function $$f$$ is injective. Let $$\left( {{r_1},{\theta _1}} \right) \ne \left( {{r_2},{\theta _2}} \right)$$ but $$f\left( {{r_1},{\theta _1}} \right) = f\left( {{r_2},{\theta _2}} \right).$$ Then

${\left( {\frac{{{R_2}{r_1}}}{{{R_1}}},{\theta _1}} \right) = \left( {\frac{{{R_2}{r_2}}}{{{R_1}}},{\theta _2}} \right),}\;\; \Rightarrow {\left\{ {\begin{array}{*{20}{l}} {\frac{{{R_2}{r_1}}}{{{R_1}}} = \frac{{{R_2}{r_2}}}{{{R_1}}}}\\ {{\theta _1} = {\theta _2}} \end{array}} \right.,}\;\; \Rightarrow {\left\{ {\begin{array}{*{20}{l}} {{r_1} = {r_2}}\\ {{\theta _1} = {\theta _2}} \end{array}} \right.,}\;\; \Rightarrow {\left( {{r_1},{\theta _1}} \right) = \left( {{r_2},{\theta _2}} \right).}$

This is a contradiction. Hence, the function $$f$$ is injective.

To see that $$f$$ is surjective, we take an arbitrary point $$\left( {a,b} \right)$$ in the $$2\text{nd}$$ disk and find its preimage in the $$1\text{st}$$ disk.

${f\left( {r,\theta } \right) = \left( {\frac{{{R_2}r}}{{{R_1}}},\theta } \right) = \left( {a,b} \right),}\;\; \Rightarrow {\left\{ {\begin{array}{*{20}{l}} {\frac{{{R_2}r}}{{{R_1}}} = a}\\ {\theta = b} \end{array}} \right.,}\;\; \Rightarrow {\left\{ {\begin{array}{*{20}{l}} {r = \frac{{{R_1}a}}{{{R_2}}}}\\ {\theta = b} \end{array}} \right..}$

Check that with these values of $$r$$ and $$\theta,$$ we have $$f\left( {r,\theta } \right) = \left( {a,b} \right):$$

${f\left( {r,\theta } \right) = \left( {\frac{{{R_2}r}}{{{R_1}}},\theta } \right) }={ \left( {\frac{{\cancel{R_2}}}{{\cancel{R_1}}}\frac{{\cancel{R_1}}}{{\cancel{R_2}}}a,b} \right) }={ \left( {a,b} \right).}$

Thus, the function $$f$$ is injective and surjective. Hence, there is a bijection between the two sets. This means that any two disks have equal cardinalities.

### Example 5.

Show that the sets $$\mathbb{N}^2$$ and $$\left\{ {n,m \in {\mathbb{N}^2} \;\bigg|\; n \lt m}\right\}$$ have the same cardinality.

Solution.

To prove equinumerosity, we need to find at least one bijective function between the sets. We can choose, for example, the following mapping function:

$f\left( {n,m} \right) = \left( {n – m,n + m} \right),$

where $$n,m \in \mathbb{N}.$$

To see that $$f$$ is injective, we suppose (by contradiction) that $$\left( {{n_1},{m_1}} \right) \ne \left( {{n_2},{m_2}} \right),$$ but $$f\left( {{n_1},{m_1}} \right) = f\left( {{n_2},{m_2}} \right).$$ Then we have

${\left( {{n_1} – {m_1},{n_1} + {m_1}} \right) }={ \left( {{n_2} – {m_2},{n_2} + {m_2}} \right),}\;\; \Rightarrow {\left\{ {\begin{array}{*{20}{l}} {{n_1} – {m_1} = {n_2} – {m_2}}\\ {{n_1} + {m_1} = {n_2} + {m_2}} \end{array}} \right..}$

To eliminate the variables $$m_1,$$ $$m_2,$$ we add both equations together. This gives us:

${2{n_1} = 2{n_2},}\;\; \Rightarrow {{n_1} = {n_2}.}$

Similarly, subtract the $$2\text{nd}$$ equation from the $$1\text{st}$$ one to eliminate $$n_1,$$ $$n_2:$$

${ – 2{m_1} = – 2{m_2},}\;\; \Rightarrow {{m_1} = {m_2}.}$

Thus, we get a contradiction: $$\left( {{n_1},{m_1}} \right) = \left( {{n_2},{m_2}} \right),$$ which means that the function $$f$$ is injective.

To see that $$f$$ is surjective, we take an arbitrary ordered pair of numbers $$\left( {a,b} \right) \in \text{cod}\left( f \right)$$ and find the preimage $$\left( {n,m} \right)$$ such that $$f\left( {n,m} \right) = \left( {a,b} \right).$$

${f\left( {n,m} \right) = \left( {a,b} \right),}\;\; \Rightarrow {\left( {n – m,n + m} \right) = \left( {a,b} \right),}\;\; \Rightarrow {\left\{ {\begin{array}{*{20}{l}} {n – m = a}\\ {n + m = b} \end{array}} \right..}$

Solving the system for $$n$$ and $$m$$ by elimination gives:

$\left( {n,m} \right) = \left( {\frac{{a + b}}{2},\frac{{b – a}}{2}} \right).$

Check the mapping with these values of $$n,m:$$

${f\left( {n,m} \right) = f\left( {\frac{{a + b}}{2},\frac{{b – a}}{2}} \right) }={ \left( {\frac{{a + b}}{2} – \frac{{b – a}}{2},\frac{{a + b}}{2} + \frac{{b – a}}{2}} \right) }={ \left( {\frac{{a + \cancel{b} – \cancel{b} + a}}{2},\frac{{\cancel{a} + b + b – \cancel{a}}}{2}} \right) }={ \left( {a,b} \right).}$

Hence, the function $$f$$ is surjective. Since $$f$$ is both injective and surjective, it is bijective. This means that both sets have the same cardinality.