Calculus

Set Theory

Set Theory Logo

Cardinality of a Set

Solved Problems

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 \(\frac{1}{2}:\)

\[- \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) = \frac{1}{\pi } \arctan x + \frac{1}{2}\) 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) = \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 = \frac{1}{x},\) we get \(x = \frac{1}{y}\) 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) =\frac{1}{x}\) 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\} = \frac{1}{n},\) 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 }\;\frac{1}{n} \to \frac{1}{{n + 1}}.\]

For example,

\[f\left( {{x_1}} \right) = f\left( 1 \right) = {x_2} = \frac{1}{2},\;\;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( {\frac{{{R_2}r}}{{{R_1}}},\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.

Page 1 Page 2