Countability and Uncountability of Sets. Equinumerosity of Sets.

Literature: Collection of problems in mathematics. Part 1. Edited by A.V. Efimov, B.P. Demidovich.

A set $X$ is called countable if a one-to-one correspondence can be established between the elements of this set and the elements of the set $N$ of all natural numbers (that is, the elements of the set $X$ can be numbered 1, 2, ...).

Examples.

Prove that the following sets are countable:

1.64. ${n\in \mathbb{N} ,|, n=2k, , k\in \mathbb{N} }.$

Solution.

Let's establish a one-to-one correspondence between the elements of this set and the natural numbers, for example, by ordering the set ${n\in \mathbb{N} ,|, n=2k, , k\in \mathbb{N} }$ as follows: $$2, 4, 6, 8, ...$$ and then assigning to each element of the set its ordinal number in this sequence $$1, 2, 3, 4, ... .$$ Thus, the given set is countable.

Which was to be proved.

1.66. $\{n\in N\, |\, n=2^k, \, k\in N \}.$

Solution.

We will order the set ${n\in \mathbb{N} ,|, n=2^k, , k\in \mathbb{N} }$ as follows:

$$2^1, 2^2, 2^3, 2^4, ...$$ Furthermore, by assigning each element of the set its ordinal number in this sequence, we establish a one-to-one correspondence between the given set and the set of natural numbers. Therefore, the set $$\{n\in N\, |\, n=2^k, \, k\in N \}$$ The set is countable.

This is what needed to be proven.

1.68. Let $X_1, X_2, X_3, ...$ be countable sets. Prove that their union $\bigcup\limits_{n\in N} X_n$ is a countable set.

Solution.

Let $X_n={x_{n, 1}, x_{n, 2}, ..., x_{n, l},... }$. Then the elements of the set $\bigcup\limits_{n\in N} X_n$ can be arranged in the following table:

$$x_{1, 1},\, x_{1, 2},\, x_{1, 3},\,\cdots, x_{1, l},\cdots $$

$$x_{2, 1},\, x_{2, 2},\, x_{2, 3},\, \cdots, x_{2, l},\cdots $$

$$x_{3, 1},\, x_{3, 2},\, x_{3, 3},\, \cdots, x_{3, l},\cdots $$

$$..........................$$

$$x_{n, 1},\, x_{n, 2},\, x_{n, 3},\, \cdots, x_{n, l},\cdots $$

$$..........................$$

Let's number the elements of this table as follows: we take $x_{1, 1}$ as the first element, the next two elements are the ones on the diagonal $x_{1, 2}$ and $x_{2, 1}$, then we count three elements on the next diagonal $x_{3, 1},,, x_{2, 2}$, and $x_{1, 3}$, and so on. Thus, each element of the set $\bigcup\limits_{n\in N} X_n$ can be associated with a natural number (the ordinal number of the element if they are counted according to the scheme described above). Therefore, the given set is countable.

This is what needed to be proven.

1.69. Using the result of problem 1.68, prove that the set of all rational numbers $Q={x\in R,|, x=\frac{m}{n},,, n\neq 0,,, m,, n \in Z }.$

Solution.

The set of rational numbers can be represented as the union of countable sets $X_n=\{\frac{n}{k}\, | k\in N \}=\left\{\frac{n}{1},\frac{n}{2}, \frac{n}{3}, \cdots\right\}.$

Each set $X_n$ is countable, as each element can be associated with a natural number in the denominator. Then the set $$Q=\{x\in R\,|\, x=\frac{m}{n},\,\, n\neq 0,\,\, m,\, n \in Z \}=\bigcup\limits_{n\in N} X_n$$Similarly, it is countable, as proven in problem 1.68.

This is what needed to be proven.

Sets $A$ and $B$ are said to be equipotent if a one-to-one correspondence can be established between the elements of set $A$ and the elements of set $B$ (meaning each element of set $A$ can be paired with exactly one element of set $B$, and vice versa).

Examples:

Prove that the intervals $[0, 1]$ and $[0, 2]$ are equipotent.

Proof.

To each element $x\in [0, 1]$, we associate the number $2x$. It is obvious that $2x\in [0, 2]$. Similarly, to each element $y\in[0, 2]$, a unique number $\frac{y}{2}\in,[0, 1]$ is associated.

This is what needed to be proven.

2.Prove that the intervals $(a, b)$ and $(c, d)$ are equipotent.

Proof.

Let's proceed with the proof in several stages:

Notice that the mapping $x\rightarrow x-a$ is a bijective correspondence between the intervals $(a, , b)$ and $(0,, b-a).$

The mapping $x\rightarrow\frac{(d-c)x}{b-a}$ bijectively maps the interval $(0, b-a)$ onto $(0, , d-c).$

The mapping $x\rightarrow x+c$ bijectively maps the interval $(0, d-c)$ onto $(c, d).$

The composition of these mappings, $x\rightarrow\frac{(d-c)(x-a)}{b-a}+c$, is a bijective mapping between the intervals $(a,, b)$ and $(c,, d)$. Hence, the intervals $(a,, b)$ and $(c,, d)$ are equipotent.

This concludes the proof.

Homework.

Prove that the following sets are countable:

1.65. $\{n\in N\, |\, n=k^2, \, k\in N \}.$

1.67. Prove that if the set $X$ is countable and $A \subset X$ is an infinite subset, then the set $A$ is also countable. Using this result, prove that the set $$n\in Z | n=k^2-k+1, k\in N$$ is countable.

1.70. Using the result from problem 1.68, prove that the set of all points in the plane with rational coordinates is countable.

1) Prove that the half-open interval $[0,, 1)$ is equipotent to the half-open interval $(0,, 1]$.

2) Prove that the interval $(0, 1)$ and the ray $(0, , +\infty)$ are equipotent.