Calculus

Set Theory

Set Theory Logo

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

Cantor's Diagonal Argument
Figure 1.

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.}\]

Graph of the bijective function between R and (0,1).
Figure 2.

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}}.\)

Bijective function y=1/x to for the mapping of (0,1) to (1,infinity).
Figure 3.

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}.\)

Bijective mapping of half-open interval (0,1] to open interval (0,1).
Figure 4.

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.

Mapping between two disks.
Figure 5.

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.