Счетность и несчетность множеств. Равномощность множеств.

Литература: Сборник задач по математике. Часть 1. Под ред А. В. Ефимова, Б. П. Демидовича.

Множество $X$ называется счетным, если может быть установлено взаимно однозначное соответствие между элементами этого множества и элементами множества $N$ всех натуральных чисел (то есть элементы множества $X$ можно пронумеровать 1, 2, ...). 

Примеры.

Доказать, что следующие множества счетны:

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

Решение.

Установим взаимно однозначное соответствие между элементами этого множества и натуральными числами, например, упорядочив множество $\{n\in N\, |\, n=2k, \, k\in N \}$ следующим образом:

$$2, 4,  6, 8, ...$$ а затем каждому элементу множества поставив в соответствие его порядковый номер в этой последовательности $$1, 2, 3, 4, ... .$$ Таким образом заданное множество является счетным. 

Что и требовалось доказать.

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

Решение.

Множество $\{n\in N\, |\, n=2^k, \, k\in N \}$ упорядочим следующим образом:

$$2^1, 2^2,  2^3, 2^4, ...$$ далее каждому элементу множества поставив в соответствие его порядковый номер в этой последовательности. Таким образом, установлено взаимно однозначное соответствие между заданнім множеством и множеством натуральніх чисел. Следовательно, множество $$\{n\in N\, |\, n=2^k, \, k\in N \}$$ является счетным. 

Что и требовалось доказать.

1.68. Пусть $X_1, X_2, X_3, ... -$ счетные множества. Доказать, что их объеденение $\bigcup\limits_{n\in N} X_n-$ счетное множество.

Решение.

Пусть $X_n=\{x_{n, 1}, x_{n, 2}, ..., x_{n, l},... \}.$ Тогда элементы множества $\bigcup\limits_{n\in N} X_n$ можно записать в виде следующей таблицы:

$$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 $$

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

Занумеруем элементы этой таблицы следующим образом: в качестве первого элемента берем элемент $x_{1, 1},$ следующие два элемента -- элементы стоящие на диагонали $x_{1, 2}$ и $x_{2, 1},$ затем считаем три элемента стоящие на следующей диагонали $x_{3, 1},\,\, x_{2, 2}$ и $x_{1, 3}$ и так далее. Таким образом, каждому элементу множества $\bigcup\limits_{n\in N} X_n$ можно поставить в соответствие натуральное число (порядковый номер элемента, если их пересчитывать по указанной выше схеме). Следовательно, заданное множество счетное.

Что и требовалось доказать.

1.69.Используя результат задачи 1.68 доказать, что множество всех рациональных чисел $Q=\{x\in R\,|\, x=\frac{m}{n},\,\, n\neq 0,\,\, m,\, n \in Z \}.$

Решение.

Множество рациональных чисел можно представить как объединение счетных множеств $X_n=\{\frac{n}{k}\, | k\in N \}=\left\{\frac{n}{1},\frac{n}{2}, \frac{n}{3}, \cdots\right\}.$

Каждое множество $X_n$ счетное, поскольку каждому элементу можно поставить в соответствие натуральное число, стоящее в знаменателе. Тогда множество $$Q=\{x\in R\,|\, x=\frac{m}{n},\,\, n\neq 0,\,\, m,\, n \in Z \}=\bigcup\limits_{n\in N} X_n$$так же является счетным, как было доказано в задаче 1.68.

Что и требовалось доказать.

Множества $A$ и $B$ называются равномощными, если может быть установлено взаимно однозначное соответствие между элементами множества $A$ и элементами множества $B.$  (то есть каждому элементу множества $A$ можно поставить в соответствие один и только один элемент множеста $B,$ а каждому элементу множества $B$ можно поставить в соответствие один и только один элемент множеста $A.$)

Примеры:

1. Докажите, что отрезки $[0, 1]$ и $[0, 2]$ равномощны.

Доказательство. 

Каждому элементу $x\in [0, 1]$ поставим в соответствие число $2x.$ Очевидно $2x\in [0, 2].$ Аналонгично каждому элементу $y\in[0, 2]$ соответствует, и притом единственное, число $\frac{y}{2}\in\,[0, 1].$

Что и требовалось доказать.

2. Докажите, что интервалы $(a, b)$ и $(c, d)$ равномощны.

Доказательство.

Проведем доказательство в несколько этапов:

1) Заметим, что отображение $x\rightarrow x-a$ является взаимно однозначным соответствием между интервалами $(a, \, b)$ и $(0,\, b-a).$ 

2) Отображение $x\rightarrow\frac{(d-c)x}{b-a}$ взаимно однозначно отображает интервал $(0, b-a)$ на $(0, \, d-c).$

3) Отображение $x\rightarrow x+c$ взаимно однозначно отображает интервал $(0, d-c)$ на $(c, d).$

Композиция приведенных отображений $x\rightarrow\frac{(d-c)(x-a)}{b-a}+c$ является взаимно однозначным отображением между интервалами $(a,\, b)$ и $(c,\, d).$ Следовательно интервалы  $(a,\, b)$ и $(c,\, d)$  равномощны.

Что и требовалось доказать. 

Домашнее задание.

Доказать, что следующие множества счетны:

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

1.67. Доказать, что если множество $X$ счетно и $A\subset X$ его бесконечное подмонжество, то множество $A$ так же счето используя этот результат доказать, что множество $$n\in Z | n=k^2-k+1, k\in N$$ счетно.

1.70. Используя результат задачи 1.68, доказать, что множество всех точек плскости с рациональными координатами счетно.

1. Докажите, что полуинтервал $[0,\, 1)$ равномощен полуинтервалу  $(0,\, 1].$

2. Докажите, что интервал $(0, 1)$ и луч $(0, \, +\infty)$ равномощны.