Введение в теорию множеств

Счетные множества

Разбить на страницы
Показывать лекцию целиком

Множество называется счетным, если оно равномощно множеству $$\bb N$$ натуральных чисел, то есть если его можно представить в виде $$\{x_0,x_1,x_2,\dots\}$$ (здесь $$x_i$$ - элемент, соответствующий числу $$i$$ ; соответствие взаимно однозначно, так что все $$x_i$$ различны).

Например, множество целых чисел $$\mathbb{Z}$$ счетно, так как целые числа можно расположить в последовательность $$0$$, $$1$$, $$-1$$, $$2$$, $$-2$$, $$3$$, $$-3$$, $$\ldots$$

Теорема 2.

(а) Подмножество счетного множества конечно или счетно.

(б) Всякое бесконечное множество содержит счетное подмножество.

(в) Объединение конечного или счетного числа конечных или счетных множеств конечно или счетно.

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

(а) Пусть $$B$$ - подмножество счетного множества $$A\hm=\{a_0,a_1,a_2,\dots\}$$. Выбросим из последовательности $$a_0, a_1, \dots$$ те члены, которые не принадлежат $$B$$ (сохраняя порядок оставшихся). Тогда оставшиеся члены образуют либо конечную последовательность (и тогда $$B$$ конечно), либо бесконечную (и тогда $$B$$ счетно).

(б) Пусть $$A$$ бесконечно. Тогда оно непусто и содержит некоторый элемент $$b_0$$. Будучи бесконечным, множество $$A$$ не исчерпывается элементом $$b_0$$ - возьмем какой - нибудь другой элемент $$b_1$$, и т.д. Получится последовательность $$b_0, b_1, \dots$$ ; построение не прервется ни на каком шаге, поскольку $$A$$ бесконечно. Теперь множество $$B\hm=\{b_0,b_1,\dots\}$$ и будет искомым счетным подмножеством. (Заметим, что $$B$$ вовсе не обязано совпадать с $$A$$, даже если $$A$$ счетно.)

(в) Пусть имеется счетное число счетных множеств $$A_1, A_2, \dots$$ Расположив элементы каждого из них слева направо в последовательность ( $$A_i\hm=\{a_{i0},a_{i1},\dots\}$$ ) и поместив эти последовательности друг под другом, получим таблицу$$\begin{array}{ccccc} a_{00} a_{01} a_{02} a_{03} \ldots \\ a_{10} a_{11} a_{12} a_{13} \ldots \\ a_{20} a_{21} a_{22} a_{23} \ldots \\ a_{30} a_{31} a_{32} a_{33} \ldots \\ \ldots \ldots \ldots \ldots \ldots \end{array}$$ Теперь эту таблицу можно развернуть в последовательность, например, проходя по очереди диагонали:$$a_{00},\ a_{01}, a_{10}, \ a_{02}, a_{11}, a_{20}, \ a_{03}, a_{12}, a_{21}, a_{30}, \ldots$$ Если множества $$A_i$$ не пересекались, то мы получили искомое представление для их объединения. Если пересекались, то из построенной последовательности надо выбросить повторения.

Если множеств конечное число или какие-то из множеств конечны, то в этой конструкции части членов не будет - и останется либо конечное, либо счетное множество.

29. Описанный проход по диагоналям задает взаимно однозначное соответствие между множеством всех пар натуральных чисел (которое обозначается $$\bbN\times\bbN$$ ) и $$\bbN$$. Любопытно, что это соответствие задается простой формулой (многочленом второй степени с рациональными коэффициентами). Укажите этот многочлен.

Замечание. В доказательстве утверждения (б) теоремы 2 есть тонкий момент: на каждом шаге мы должны выбрать один из оставшихся элементов множества $$A$$ ; такие элементы есть, но у нас нет никакого правила, позволяющего такой выбор описать. При более формальном построении теории множеств тут нужно сослаться на специальную аксиому, называемую аксиомой выбора. Законность этой аксиомы вызывала большие споры в начале 20-го века, но постепенно к ней привыкли, и эти споры сейчас почти не воспринимаются. В середине века великий логик Курт Гедель доказал, что аксиому выбора нельзя опровергнуть, пользуясь остальными аксиомами теории множеств, а в 1960-е годы американский математик Пол Дж.Коэн доказал, что ее нельзя и вывести из остальных аксиом. (Конечно, понимание этих утверждений требует подробного изложения теории множеств как аксиоматической теории.)

30. Такой же тонкий момент (хотя и менее очевидный) есть и в доказательстве утверждения (в). Можете ли вы догадаться, где он? (Ответ: мы знаем, что множества $$A_i$$ счетны, то есть что существует взаимно однозначное соответствие между $$\bbN$$ и $$A_i$$. Но нужно выбрать и фиксировать эти соответствия, прежде чем удастся построить соответствие между объединением всех $$A_i$$ и $$\bbN$$.)

Еще несколько примеров счетных множеств:

  • Множество $$\bbQ$$ рациональных чисел счетно. В самом деле, рациональные числа представляются несократимыми дробями с целым числителем и знаменателем. Множество дробей с данным знаменателем счетно, поэтому $$\bbQ$$ представимо в виде объединения счетного числа счетных множеств. Забегая вперед (см. лекцию 4), отметим, что множество $$\bbR$$ всех действительных чисел несчетно.
  • Множество $$\bbN^k$$, элементами которого являются наборы из $$k$$ натуральных чисел, счетно. Это легко доказать индукцией по $$k$$. При $$k\hm=2$$ множество $$\bbN^2\hm=\bbN\hm\times\bbN$$ пар натуральных чисел разбивается на счетное число счетных множеств $$\{0\}\hm\times\bbN, \{1\}\hm\times\bbN, \dots$$ (элементами $$i$$ -го множества будут пары, первый член которых равен $$i$$ ). Поэтому $$\bbN^2$$ счетно. Аналогичным образом множество $$\bbN^3$$ троек натуральных чисел разбивается на счетное число множеств $$\{i\}\hm\times\bbN\hm\times\bbN$$. Каждое из них состоит из троек, первый член которых фиксирован и потому равномощно множеству $$\bbN^2$$, которое счетно. Точно так же можно перейти от счетности множества $$\bbN^k$$ к счетности множества $$\bbN^{k+1}$$.
  • Множество всех конечных последовательностей натуральных чисел счетно. В самом деле, множество всех последовательностей данной длины счетно (как мы только что видели), так что интересующее нас множество разбивается на счетное число счетных множеств.
  • В предыдущем примере не обязательно говорить о натуральных числах - можно взять любое счетное (или конечное) множество. Например, множество всех текстов, использующих русский алфавит (такой текст можно считать конечной последовательностью букв, пробелов, знаков препинания и т.п.), счетно; то же самое можно сказать о множестве (всех мыслимых) компьютерных программ и т.д.
  • Число называют алгебраическим, если оно является корнем ненулевого многочлена с целыми коэффициентами. Множество алгебраических чисел счетно, так как многочленов счетное число (многочлен задается конечной последовательностью целых чисел - его коэффициентов), а каждый многочлен имеет конечное число корней (не более $$n$$ для многочленов степени $$n$$ ).
  • Множество периодических дробей счетно. В самом деле, такая дробь может быть записана как конечная последовательность символов из конечного множества (запятая, цифры, скобки); например, дробь $$0{,}16666{\dots}$$ можно записать как $$0{,}1(6)$$. А таких последовательностей счетное множество.
  • 31. Докажите, что любое семейство непересекающихся интервалов на прямой конечно или счетно. (Указание: в каждом интервале найдется рациональная точка.)

    32. (а) Докажите, что любое множество непересекающихся восьмерок на плоскости конечно или счетно. (Восьмерка - объединение двух касающихся окружностей любых размеров.) (б) Сформулируйте и докажите аналогичное утверждение для букв "Т".

    33. Докажите, что множество точек строгого локального максимума любой функции действительного аргумента конечно или счетно.

    Докажите, что множество точек разрыва неубывающей функции Действительного аргумента конечно или счетно.

    Теорема 3. Если множество $$A$$ бесконечно, а множество $$B$$ конечно или счетно, то объединение $$A\hm\cup B$$ равномощно $$A$$.

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

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

    Выделим в $$A$$ счетное подмножество $$P$$ ; остаток обозначим через $$Q$$. Тогда нам надо доказать, что $$B\hm+P\hm+Q$$ равномощно $$P\hm+Q$$ (знак $$+$$ символизирует объединение непересекающихся множеств). Поскольку $$B\hm+P$$ и $$P$$ оба счетны, между ними существует взаимно однозначное соответствие. Его легко продолжить до соответствия между $$B\hm+P\hm+Q$$ и $$P\hm+Q$$ (каждый элемент множества $$Q$$ соответствует сам себе).

    35. Примените эту конструкцию и явно укажите соответствие между отрезком $$[0,1]$$ и полуинтервалом $$[0,1)$$.

    36. Теорема 3 показывает, что добавление счетного множества к бесконечному не меняет его мощности. Можно ли сказать то же самое про удаление? Докажите, что если $$A$$ бесконечно и не является счетным, а $$B$$ конечно или счетно, то $$A\setminus B$$ равномощно $$A$$.

    37. Немецкий математик Р.Дедекинд предложил такое определение бесконечного множества: множество бесконечно, если оно равномощно некоторому своему подмножеству, не совпадающему со всем множеством. Покажите, что указанное Дедекиндом свойство действительно определяет бесконечные множества.

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

    38. Укажите взаимно однозначное соответствие между множеством $$[0,1]\hm\cup[2,3]\hm\cup[4,5]\cup\ldots$$ и отрезком $$[0,1]$$.

    39. Докажите, что множество всех прямых на плоскости равномощно множеству всех точек на плоскости. (Указание: и точки, и прямые задаются парами чисел - за небольшими исключениями.)

    40. Докажите, что полуплоскость (точки плоскости, лежащие по одну сторону от некоторой прямой) равномощна плоскости. (Это верно независимо от того, включаем мы граничную прямую в полуплоскость или нет.)

    Теорема 4. Отрезок $$[0,1]$$ равномощен множеству всех бесконечных последовательностей нулей и единиц.

    Доказательство. В самом деле, каждое число $$x\hm\in[0,1]$$ записывается в виде бесконечной двоичной дроби. Первый знак этой дроби равен $$0$$ или $$1$$ в зависимости от того, попадает ли число $$x$$ в левую или правую половину отрезка. Чтобы определить следующий знак, надо выбранную половину поделить снова пополам и посмотреть, куда попадет $$x$$, и т.д.

    Это же соответствие можно описать в другую сторону: последовательности $$x_0x_1x_2\dots$$ соответствует число, являющееся суммой ряда$$\frac{x_0}{2} + \frac{x_1}{4} + \frac{x_2}{8} + \ldots$$ (В этом построении мы используем некоторые факты из математического анализа, что не удивительно - нас интересуют свойства действительных чисел.)

    Описанное соответствие пока что не совсем взаимно однозначно: двоично-рациональные числа (дроби вида $$m/2^n$$ ) имеют два представления. Например, число $$3/8$$ можно записать как в виде $$0{,}011000{\dots}$$, так и в виде $$0{,}010111{\dots}$$ Соответствие станет взаимно однозначным, если отбросить дроби с единицей в периоде (кроме дроби $$0{,}1111\ldots$$, которую надо оставить). Но таких дробей счетное число, поэтому на мощность это не повлияет.

    Какая двоичная дробь соответствует числу $$1/3$$?

    В этом доказательстве можно было бы использовать более привычные десятичные дроби вместо двоичных. Получилось бы, что отрезок $$[0,1]$$ равномощен множеству всех бесконечных последовательностей цифр $$0,1,\dots,9$$. Чтобы перейти отсюда к последовательностям нулей и единиц, можно воспользоваться приемом, описанным ранее.

    Теперь все готово для доказательства такого удивительного факта:

    Теорема 5. Квадрат (со внутренностью) равномощен отрезку.

    Доказательство. Квадрат равномощен множеству $$[0,1]\hm\times [0,1]$$ пар действительных чисел, каждое из которых лежит на отрезке $$[0,1]$$ (метод координат). Мы уже знаем, что вместо чисел на отрезке можно говорить о последовательностях нулей и единиц. Осталось заметить, что паре последовательностей нулей и единиц $$\langle x_0x_1x_2\ldots, y_0y_1y_2\ldots\rangle$$ можно поставить в соответствие последовательность-смесь $$x_0y_0x_1y_1x_2y_2\ldots$$ и что это соответствие будет взаимно однозначным.

    Этот результат был получен в 1877 году немецким математиком Георгом Кантором и удивил его самого, поскольку противоречил интуитивному ощущению " размерности" (квадрат двумерен, поэтому вроде бы должен содержать больше точек, чем одномерный отрезок). Вот что Кантор писал Дедекинду (20 июня 1877 года), обсуждая вопрос о равномощности пространств разного числа измерений: " Как мне кажется, на этот вопрос следует ответить утвердительно, хотя на протяжении ряда лет я придерживался противоположного мнения".

    В одном из ответных писем Дедекинд отмечает, что результат Кантора не лишает смысла понятие размерности, поскольку можно рассматривать лишь непрерывные в обе стороны соответствия, и тогда пространства разной размерности можно будет различить. Эта гипотеза оказалось верной, хотя не такой простой; первые попытки ее доказать, в том числе одна из статей Кантора, содержали ошибки, и только спустя тридцать лет голландский математик Л.Брауэр дал правильное доказательство. Впрочем, отсутствие непрерывного в обе стороны соответствия между отрезком и квадратом доказать несложно; трудности начинаются в больших размерностях. (Заметим также, что существует непрерывное отображение отрезка в квадрат, которое проходит через любую точку квадрата. Оно называется " кривой Пеано".)

    Из теоремы 5 легко получить много других утверждений про равномощность геометрических объектов: круг равномощен окружности, прямая равномощна плоскости и т.п.

    Можно также заметить, что пространство (точки которого задаются тремя координатами $$\langle x,y,z\rangle$$ ) равномощно плоскости (надо закодировать пару $$\langle x,y\rangle$$ одним числом), и, следовательно, прямой. То же самое можно проделать и для пространств большей размерности.

    42. Докажите, что множество всех конечных последовательностей действительных чисел равномощно $$\bbR$$ (множеству всех действительных чисел).

    43. Докажите, что множество всех бесконечных последовательностей действительных чисел равномощно $$\bbR$$.

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

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

    Страницы:

    Множество называется счетным, если оно равномощно множеству $$\bb N$$ натуральных чисел, то есть если его можно представить в виде $$\{x_0,x_1,x_2,\dots\}$$ (здесь $$x_i$$ - элемент, соответствующий числу $$i$$ ; соответствие взаимно однозначно, так что все $$x_i$$ различны).

    Например, множество целых чисел $$\mathbb{Z}$$ счетно, так как целые числа можно расположить в последовательность $$0$$, $$1$$, $$-1$$, $$2$$, $$-2$$, $$3$$, $$-3$$, $$\ldots$$

    Теорема 2.

    (а) Подмножество счетного множества конечно или счетно.

    (б) Всякое бесконечное множество содержит счетное подмножество.

    (в) Объединение конечного или счетного числа конечных или счетных множеств конечно или счетно.

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

    (а) Пусть $$B$$ - подмножество счетного множества $$A\hm=\{a_0,a_1,a_2,\dots\}$$. Выбросим из последовательности $$a_0, a_1, \dots$$ те члены, которые не принадлежат $$B$$ (сохраняя порядок оставшихся). Тогда оставшиеся члены образуют либо конечную последовательность (и тогда $$B$$ конечно), либо бесконечную (и тогда $$B$$ счетно).

    (б) Пусть $$A$$ бесконечно. Тогда оно непусто и содержит некоторый элемент $$b_0$$. Будучи бесконечным, множество $$A$$ не исчерпывается элементом $$b_0$$ - возьмем какой - нибудь другой элемент $$b_1$$, и т.д. Получится последовательность $$b_0, b_1, \dots$$ ; построение не прервется ни на каком шаге, поскольку $$A$$ бесконечно. Теперь множество $$B\hm=\{b_0,b_1,\dots\}$$ и будет искомым счетным подмножеством. (Заметим, что $$B$$ вовсе не обязано совпадать с $$A$$, даже если $$A$$ счетно.)

    (в) Пусть имеется счетное число счетных множеств $$A_1, A_2, \dots$$ Расположив элементы каждого из них слева направо в последовательность ( $$A_i\hm=\{a_{i0},a_{i1},\dots\}$$ ) и поместив эти последовательности друг под другом, получим таблицу$$\begin{array}{ccccc} a_{00} a_{01} a_{02} a_{03} \ldots \\ a_{10} a_{11} a_{12} a_{13} \ldots \\ a_{20} a_{21} a_{22} a_{23} \ldots \\ a_{30} a_{31} a_{32} a_{33} \ldots \\ \ldots \ldots \ldots \ldots \ldots \end{array}$$ Теперь эту таблицу можно развернуть в последовательность, например, проходя по очереди диагонали:$$a_{00},\ a_{01}, a_{10}, \ a_{02}, a_{11}, a_{20}, \ a_{03}, a_{12}, a_{21}, a_{30}, \ldots$$ Если множества $$A_i$$ не пересекались, то мы получили искомое представление для их объединения. Если пересекались, то из построенной последовательности надо выбросить повторения.

    Если множеств конечное число или какие-то из множеств конечны, то в этой конструкции части членов не будет - и останется либо конечное, либо счетное множество.

    29. Описанный проход по диагоналям задает взаимно однозначное соответствие между множеством всех пар натуральных чисел (которое обозначается $$\bbN\times\bbN$$ ) и $$\bbN$$. Любопытно, что это соответствие задается простой формулой (многочленом второй степени с рациональными коэффициентами). Укажите этот многочлен.

    Замечание. В доказательстве утверждения (б) теоремы 2 есть тонкий момент: на каждом шаге мы должны выбрать один из оставшихся элементов множества $$A$$ ; такие элементы есть, но у нас нет никакого правила, позволяющего такой выбор описать. При более формальном построении теории множеств тут нужно сослаться на специальную аксиому, называемую аксиомой выбора. Законность этой аксиомы вызывала большие споры в начале 20-го века, но постепенно к ней привыкли, и эти споры сейчас почти не воспринимаются. В середине века великий логик Курт Гедель доказал, что аксиому выбора нельзя опровергнуть, пользуясь остальными аксиомами теории множеств, а в 1960-е годы американский математик Пол Дж.Коэн доказал, что ее нельзя и вывести из остальных аксиом. (Конечно, понимание этих утверждений требует подробного изложения теории множеств как аксиоматической теории.)

    30. Такой же тонкий момент (хотя и менее очевидный) есть и в доказательстве утверждения (в). Можете ли вы догадаться, где он? (Ответ: мы знаем, что множества $$A_i$$ счетны, то есть что существует взаимно однозначное соответствие между $$\bbN$$ и $$A_i$$. Но нужно выбрать и фиксировать эти соответствия, прежде чем удастся построить соответствие между объединением всех $$A_i$$ и $$\bbN$$.)

    Еще несколько примеров счетных множеств:

  • Множество $$\bbQ$$ рациональных чисел счетно. В самом деле, рациональные числа представляются несократимыми дробями с целым числителем и знаменателем. Множество дробей с данным знаменателем счетно, поэтому $$\bbQ$$ представимо в виде объединения счетного числа счетных множеств. Забегая вперед (см. лекцию 4), отметим, что множество $$\bbR$$ всех действительных чисел несчетно.
  • Множество $$\bbN^k$$, элементами которого являются наборы из $$k$$ натуральных чисел, счетно. Это легко доказать индукцией по $$k$$. При $$k\hm=2$$ множество $$\bbN^2\hm=\bbN\hm\times\bbN$$ пар натуральных чисел разбивается на счетное число счетных множеств $$\{0\}\hm\times\bbN, \{1\}\hm\times\bbN, \dots$$ (элементами $$i$$ -го множества будут пары, первый член которых равен $$i$$ ). Поэтому $$\bbN^2$$ счетно. Аналогичным образом множество $$\bbN^3$$ троек натуральных чисел разбивается на счетное число множеств $$\{i\}\hm\times\bbN\hm\times\bbN$$. Каждое из них состоит из троек, первый член которых фиксирован и потому равномощно множеству $$\bbN^2$$, которое счетно. Точно так же можно перейти от счетности множества $$\bbN^k$$ к счетности множества $$\bbN^{k+1}$$.
  • Множество всех конечных последовательностей натуральных чисел счетно. В самом деле, множество всех последовательностей данной длины счетно (как мы только что видели), так что интересующее нас множество разбивается на счетное число счетных множеств.
  • В предыдущем примере не обязательно говорить о натуральных числах - можно взять любое счетное (или конечное) множество. Например, множество всех текстов, использующих русский алфавит (такой текст можно считать конечной последовательностью букв, пробелов, знаков препинания и т.п.), счетно; то же самое можно сказать о множестве (всех мыслимых) компьютерных программ и т.д.
  • Число называют алгебраическим, если оно является корнем ненулевого многочлена с целыми коэффициентами. Множество алгебраических чисел счетно, так как многочленов счетное число (многочлен задается конечной последовательностью целых чисел - его коэффициентов), а каждый многочлен имеет конечное число корней (не более $$n$$ для многочленов степени $$n$$ ).
  • Множество периодических дробей счетно. В самом деле, такая дробь может быть записана как конечная последовательность символов из конечного множества (запятая, цифры, скобки); например, дробь $$0{,}16666{\dots}$$ можно записать как $$0{,}1(6)$$. А таких последовательностей счетное множество.
  • 31. Докажите, что любое семейство непересекающихся интервалов на прямой конечно или счетно. (Указание: в каждом интервале найдется рациональная точка.)

    32. (а) Докажите, что любое множество непересекающихся восьмерок на плоскости конечно или счетно. (Восьмерка - объединение двух касающихся окружностей любых размеров.) (б) Сформулируйте и докажите аналогичное утверждение для букв "Т".

    33. Докажите, что множество точек строгого локального максимума любой функции действительного аргумента конечно или счетно.

    Докажите, что множество точек разрыва неубывающей функции Действительного аргумента конечно или счетно.

    Теорема 3. Если множество $$A$$ бесконечно, а множество $$B$$ конечно или счетно, то объединение $$A\hm\cup B$$ равномощно $$A$$.

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

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

    Выделим в $$A$$ счетное подмножество $$P$$ ; остаток обозначим через $$Q$$. Тогда нам надо доказать, что $$B\hm+P\hm+Q$$ равномощно $$P\hm+Q$$ (знак $$+$$ символизирует объединение непересекающихся множеств). Поскольку $$B\hm+P$$ и $$P$$ оба счетны, между ними существует взаимно однозначное соответствие. Его легко продолжить до соответствия между $$B\hm+P\hm+Q$$ и $$P\hm+Q$$ (каждый элемент множества $$Q$$ соответствует сам себе).

    35. Примените эту конструкцию и явно укажите соответствие между отрезком $$[0,1]$$ и полуинтервалом $$[0,1)$$.

    36. Теорема 3 показывает, что добавление счетного множества к бесконечному не меняет его мощности. Можно ли сказать то же самое про удаление? Докажите, что если $$A$$ бесконечно и не является счетным, а $$B$$ конечно или счетно, то $$A\setminus B$$ равномощно $$A$$.

    37. Немецкий математик Р.Дедекинд предложил такое определение бесконечного множества: множество бесконечно, если оно равномощно некоторому своему подмножеству, не совпадающему со всем множеством. Покажите, что указанное Дедекиндом свойство действительно определяет бесконечные множества.

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

    38. Укажите взаимно однозначное соответствие между множеством $$[0,1]\hm\cup[2,3]\hm\cup[4,5]\cup\ldots$$ и отрезком $$[0,1]$$.

    39. Докажите, что множество всех прямых на плоскости равномощно множеству всех точек на плоскости. (Указание: и точки, и прямые задаются парами чисел - за небольшими исключениями.)

    40. Докажите, что полуплоскость (точки плоскости, лежащие по одну сторону от некоторой прямой) равномощна плоскости. (Это верно независимо от того, включаем мы граничную прямую в полуплоскость или нет.)

    Теорема 4. Отрезок $$[0,1]$$ равномощен множеству всех бесконечных последовательностей нулей и единиц.

    Доказательство. В самом деле, каждое число $$x\hm\in[0,1]$$ записывается в виде бесконечной двоичной дроби. Первый знак этой дроби равен $$0$$ или $$1$$ в зависимости от того, попадает ли число $$x$$ в левую или правую половину отрезка. Чтобы определить следующий знак, надо выбранную половину поделить снова пополам и посмотреть, куда попадет $$x$$, и т.д.

    Это же соответствие можно описать в другую сторону: последовательности $$x_0x_1x_2\dots$$ соответствует число, являющееся суммой ряда$$\frac{x_0}{2} + \frac{x_1}{4} + \frac{x_2}{8} + \ldots$$ (В этом построении мы используем некоторые факты из математического анализа, что не удивительно - нас интересуют свойства действительных чисел.)

    Описанное соответствие пока что не совсем взаимно однозначно: двоично-рациональные числа (дроби вида $$m/2^n$$ ) имеют два представления. Например, число $$3/8$$ можно записать как в виде $$0{,}011000{\dots}$$, так и в виде $$0{,}010111{\dots}$$ Соответствие станет взаимно однозначным, если отбросить дроби с единицей в периоде (кроме дроби $$0{,}1111\ldots$$, которую надо оставить). Но таких дробей счетное число, поэтому на мощность это не повлияет.

    Какая двоичная дробь соответствует числу $$1/3$$?

    В этом доказательстве можно было бы использовать более привычные десятичные дроби вместо двоичных. Получилось бы, что отрезок $$[0,1]$$ равномощен множеству всех бесконечных последовательностей цифр $$0,1,\dots,9$$. Чтобы перейти отсюда к последовательностям нулей и единиц, можно воспользоваться приемом, описанным ранее.

    Теперь все готово для доказательства такого удивительного факта:

    Теорема 5. Квадрат (со внутренностью) равномощен отрезку.

    Доказательство. Квадрат равномощен множеству $$[0,1]\hm\times [0,1]$$ пар действительных чисел, каждое из которых лежит на отрезке $$[0,1]$$ (метод координат). Мы уже знаем, что вместо чисел на отрезке можно говорить о последовательностях нулей и единиц. Осталось заметить, что паре последовательностей нулей и единиц $$\langle x_0x_1x_2\ldots, y_0y_1y_2\ldots\rangle$$ можно поставить в соответствие последовательность-смесь $$x_0y_0x_1y_1x_2y_2\ldots$$ и что это соответствие будет взаимно однозначным.

    Этот результат был получен в 1877 году немецким математиком Георгом Кантором и удивил его самого, поскольку противоречил интуитивному ощущению " размерности" (квадрат двумерен, поэтому вроде бы должен содержать больше точек, чем одномерный отрезок). Вот что Кантор писал Дедекинду (20 июня 1877 года), обсуждая вопрос о равномощности пространств разного числа измерений: " Как мне кажется, на этот вопрос следует ответить утвердительно, хотя на протяжении ряда лет я придерживался противоположного мнения".

    В одном из ответных писем Дедекинд отмечает, что результат Кантора не лишает смысла понятие размерности, поскольку можно рассматривать лишь непрерывные в обе стороны соответствия, и тогда пространства разной размерности можно будет различить. Эта гипотеза оказалось верной, хотя не такой простой; первые попытки ее доказать, в том числе одна из статей Кантора, содержали ошибки, и только спустя тридцать лет голландский математик Л.Брауэр дал правильное доказательство. Впрочем, отсутствие непрерывного в обе стороны соответствия между отрезком и квадратом доказать несложно; трудности начинаются в больших размерностях. (Заметим также, что существует непрерывное отображение отрезка в квадрат, которое проходит через любую точку квадрата. Оно называется " кривой Пеано".)

    Из теоремы 5 легко получить много других утверждений про равномощность геометрических объектов: круг равномощен окружности, прямая равномощна плоскости и т.п.

    Можно также заметить, что пространство (точки которого задаются тремя координатами $$\langle x,y,z\rangle$$ ) равномощно плоскости (надо закодировать пару $$\langle x,y\rangle$$ одним числом), и, следовательно, прямой. То же самое можно проделать и для пространств большей размерности.

    42. Докажите, что множество всех конечных последовательностей действительных чисел равномощно $$\bbR$$ (множеству всех действительных чисел).

    43. Докажите, что множество всех бесконечных последовательностей действительных чисел равномощно $$\bbR$$.

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

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

    Вернуться к учебному плану