2. Эквивалентность множеств. Счетные и несчетные множества

Определение. Мощностью конечного множества называется число элементов в этом множестве.

Обозначение. Мощность множества A будем обозначать N(A).

Любые два конечные множества можно сравнивать по их мощности.

Пример 1. Пусть A=\{5,4,3,2,1\}, B=\{2,4,6\}. Тогда N(A)>N(B), так как N(A)=5,N(B)=3.

Однако для бесконечных множеств такой способ сравнения не подходит (возьмем, например, множество прямоугольников и множество рациональных чисел).

Рассмотрим способ сравнения множеств, применимый как для конечных, так и для бесконечных множеств. Для этого нам понадобится следующее определение.

Определение. Говорят, что между множествами A и B установлено взаимно однозначное соответствие, если:

1) каждому элементу множества A соответствует только один элемент множества B;

2) каждый элемент множества B при этом соответствует некоторому элементу множества A;

3) разныи элементам множества A соответствуют разные элементы множества B.

Тогда можно определить и эквивалентные множества:

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

Таким образом, мы имеем теперь возможность сравнивать по количеству элементов как конечные, так и бесконечные множества.

Приведем несколько примеров.

Пример 2. Покажем, что множество натуральных чисел эквивалентно множеству четных положительных чисел. Для этого установим между этими множествами взаимно однозначное соответствие следующим образом:

\begin{array}{cccccc}<br />
1&2&3&\ldots&n&\ldots\\<br />
\updownarrow&\updownarrow&\updownarrow&&\updownarrow&\\<br />
2&4&6&\ldots&2n&\ldots<br />
\end{array}
иначе: каждому элементу n\in\mathbb{N} поставим в соответствие элемент 2n множества четных положительных чисел.

Так как множество четных положительных чисел является подмножеством множества натуральных чисел, то этот пример показывает, что бесконечное множество может быть эквивалентно своему подмножеству. В случае конечных множеств такая ситуация невозможна: между конечными множествами A и B можно установить взаимно однозначное соответствие тогда и только тогда, когда N(A)=N(B).

Пример 3. Покажем, что множество целых чисел \mathbb{Z} эквивалентно множеству натуральных чисел \mathbb{N}. Для этого установим между этими множествами взаимно однозначное соответствие следующим образом:

\begin{array}{ccrcrcccc}<br />
0&1&-1&2&-2&\ldots&n&-n&\ldots\\<br />
\updownarrow&\updownarrow&\updownarrow&\updownarrow&\updownarrow&&\updownarrow&\updownarrow&\\<br />
1&2&3&4&5&\ldots&2n&2n+1&\ldots<br />
\end{array}
иначе: каждому элементу n\in\mathbb{Z} поставим в соответствие элемент 2n, если n>0, и элемент -2n+1, если n\le0 множества натуральных чисел.

Определение. Множество называется счетным, если оно эквивалентно множеству натуральных чисел.

Иначе говоря, множество счетно, если все элементы этого множества можно занумеровать. Таким образом, множества четных положительных чисел и множество целых чисел счетны.

Пример 4. Покажем, что множество положительных рациональных чисел счетно. В самом деле, запишем каждое положительное рациональное число в виде несократимой дроби, запишем его в бесконечную таблицу, а затем перенумеруем числа в таблице способом, указанным на рис. 4:

счетность множества положительных рациональных чисел

Рис. 4

\begin{array}{cccccc}<br />
0&1&2&3&4&\ldots\\[2mm]<br />
\displaystyle\frac{1}{2}&\displaystyle\frac{3}{2}&\displaystyle\frac{5}{2}&\displaystyle\frac{7}{2}&\displaystyle\frac{9}{2}&\ldots\\[3mm]<br />
\displaystyle\frac{1}{3}&\displaystyle\frac{2}{3}&\displaystyle\frac{4}{3}&\displaystyle\frac{5}{3}&\displaystyle\frac{7}{3}&\ldots<br />
\end{array}

Пример 5. Множества

A=\displaystyle\left\{\frac{1}{2},\frac{1}{3},\frac{1}{4},\ldots,\frac{1}{n},\ldots\right\},\<br />
B=\displaystyle\left\{0,\frac{1}{2},\frac{1}{3},\ldots,\frac{1}{n},\ldots\right\}

счетны, а следовательно, эквивалентны. В самом деле, установим взаимно однозначное соответствие следующим образом:

\begin{array}{cccccccc}<br />
A&\displaystyle\frac{1}{2}&\displaystyle\frac{1}{3}&\displaystyle\frac{1}{4}&\ldots&\displaystyle\frac{1}{n}&\displaystyle\frac{1}{n+1}&\ldots\\[2mm]<br />
&\updownarrow&\updownarrow&\updownarrow&&\updownarrow&\updownarrow&\\<br />
\mathbb{N}&1&2&3&\ldots&n-1&n&\ldots\\<br />
&\updownarrow&\updownarrow&\updownarrow&&\updownarrow&\updownarrow&\\[2mm]<br />
B&0&\displaystyle\frac{1}{2}&\displaystyle\frac{1}{3}&\ldots&\displaystyle\frac{1}{n-1}&\displaystyle\frac{1}{n}&\ldots<br />
\end{array}

Пример 6. Любой отрезок [a,b],a\ne b эквивалентен отрезку [0,1]. Искомое взаимно однозначное соответствие можно установить как аналитически, например, формулой:

x\in[0,1],\ x\leftrightarrow y=(b-a)x+a,\ y\in[a,b],

так и геометрически (см. рис. 5):

Эквивалентность отрезков

Рис. 5

Пример 7. Установим взаимно однозначное соответствие между точками интервала (0,1) и точками полуинтервала [0,1). Заметим, что множество (0,1)\setminus A и множество [0,1)\setminus B равны (множества A и B определены в примере 4; обозначим C=(0,1)\setminus A=[0,1)\setminus B. Тогда (0,1)=A\cup C, [0,1)=B\cup C. Пусть x\in(0,1). Если x\in A, то поставим ему в соответствие y\in B по закону, описанному в примере 4; если же x\in C, то поставим ему в соответствие себя: y=x\in C. Таким образом, устанавливается взаимно однозначное соответствие между (0,1) и [0,1). Следовательно, множества (0,1) и [0,1) эквивалентны.

В заключение заметим, что не все бесконечные множества являются счетными. Так, например, можно доказать, что множество точек любого отрезка [a,b],a\ne b не является счетным.

Задачи.

1. Докажите, что множество рациональных чисел счетно.

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

3. Установите взаимно однозначное соответствие между элементами множеств (0,1) и [0,1].

Оставьте свой отзыв

Добавить изображение