Cardinality of a Set

Solved Problems

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

We divide all terms of the inequality by \({\pi }\) and add \(\frac{1}{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

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

Check that \(f\left( x \right) = 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:

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

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:

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

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

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:

For example,

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

where \(n \in \mathbb{N}.\)

The function \(f\) is bijective. Hence,

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

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.

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

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.

Check that with these values of \(r\) and \(\theta,\) we have \(f\left( {r,\theta } \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.

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:

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

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

Similarly, subtract the \(2\text{nd}\) equation from the \(1\text{st}\) one to eliminate \(n_1,\) \(n_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).\)

Solving the system for \(n\) and \(m\) by elimination gives:

Check the mapping with these values of \(n,m:\)

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.