"Диагональное" доказательство теоремы Кантора

[Vladimir Pliassov]

mihaild в сообщении #1527560 писал(а):

Аналогично: существует биекция между четными натуральными числами и четными натуральными числами, $f(a) = a$. Какое четное число можно поставить в соответствие какому-нибудь нечетному числу после того, как биекция $f(a) = a$ уже задана?

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

Если имеется в виду не отображение, а функция из $\mathbb N$ в подмножество четных чисел, областью определения которой является также подмножество четных чисел, то и в этом случае никакие нечетные числа не могут отображаться в четные числа, потому что нечетные числа не входят в область определения.

Разумеется, эту функцию можно заменить на такую, при которой задается биекция между четными натуральными числами и четными натуральными числами и при этом в какое-то четное число отображается не только оно само, но еще и какое-то нечетное число, потому что после задания этой "четной" биекции у нас остается в множестве $\mathbb N$ сколько угодно свободных нечетных чисел (то есть все нечетные числа).

(При этом биекции не будет, правда, в другую сторону: эта функция может быть сюръективной и не может быть инъективной, в то время как отображение всех натуральных чисел во все подмножества $\mathbb N$ может быть инъективным и не может быть сюръективным.)

Что же касается биекции $ f(a)=\{a\}, \; a=1, 2, \ldots\; ,$ то при ней свободных натуральных чисел в множестве $\mathbb N$ совсем не остается, и нечего поставить в соответствие остальным (то есть не одноэлементным) подмножествам.

[xagiwo]

Vladimir Pliassov в сообщении #1527570 писал(а):

Если имеется в виду не отображение, а функция

Отображение и функция — синонимы

[mihaild]

Смотрите: вы пытаетесь доказать, что не существует биекции $\mathbb {N} \to \mathcal P(\mathbb N)$, потому что существует функция $f: \mathbb N \to \mathcal P(\mathbb N)$, $f(a) = \{a\}$, такая что в её образе не все подмножества $\mathbb N$, и оставшиеся "нечему сопоставить". Так?
Аналогично докажем, что не существует биекции $\mathbb N \to \mathbb Z$ (не будем заморачиваться с четными числами). Действительно, рассмотрим функцию $f: \mathbb N \to \mathbb Z$, $f(n) = n$. В её образе не все целые числа, и значит отрицательные числа нечему сопоставить.

Vladimir Pliassov в сообщении #1527570 писал(а):

то когда она уже задана, то свободных натуральных чисел в множестве $\mathbb N$ совсем не остается

Ну да, эта функция не задает биекцию. Ну и что, от нас же не требуют чтобы любая функция (и даже любая инъекция) из $\mathbb N$ в $\mathcal P(\mathbb N)$ была биекцией.

Давайте попробуем совсем на пальцах разобраться. Вы берете яблоки (натуральные числа) и раскладываете их по коробкам (подмножествам натуральных чисел). Вы можете разложить все яблоки так, что в каждой коробке лежит не больше одного яблока, и некоторые коробки пустые - всё хорошо. Но из этого еще не следует, что, раскладывая яблоки другим способом, не получится занять все коробки.

(Оффтоп)

А без аксиомы выбора возможны еще большие чудеса - в каждой коробке лежит несколько яблок, все яблоки разные, но всего яблок меньше, чем коробок.

[Vladimir Pliassov]

mihaild в сообщении #1527572 писал(а):

Аналогично докажем, что не существует биекции $\mathbb N \to \mathbb Z$ (не будем заморачиваться с четными числами). Действительно, рассмотрим функцию $f: \mathbb N \to \mathbb Z$, $f(n) = n$. В её образе не все целые числа, и значит отрицательные числа нечему сопоставить.

В этом Вы меня убедили, спасибо!

Но почему Вы говорите. что

mihaild в сообщении #1527572 писал(а):

эта функция не задает биекцию

? По-моему, $ f(a)=\{a\}, \; a=1, 2, \ldots$ это биекция:

инъекция: $f(a)=f(b)\to a=b$, сюръекция: пусть дано некоторое одноэлементное подмножество $\{a\}$, тогда для него имеется натуральное число $a$.

Или это не доказательство?

svv в сообщении #1527502 писал(а):

Рассуждая аналогично, можно прийти к выводу, что не существует биекции между множеством чётных натуральных чисел и $\mathbb N$. Но она существует.

Здесь то же самое, что и при "доказательстве" несуществования биекции между натуральными и целыми числами, но множеством-прообразом будет множество четных чисел (потому что их как бы "меньше")? Или можно все же "доказать" наоборот, отображая все натуральные числа в четные?

xagiwo в сообщении #1527571 писал(а):

Отображение и функция — синонимы

На это есть разные взгляды. Сейчас не могу найти, но видел где-то, что если при отображении множества отображается все множество, то это отображение, а если только не равное ему подмножество, то функция.

[svv]

Vladimir Pliassov в сообщении #1527593 писал(а):

Здесь то же самое, что и при "доказательстве" несуществования биекции между натуральными и целыми числами, но множеством-прообразом будет множество четных чисел (потому что их как бы "меньше")?

Да. Всё почти как в Вашей попытке доказательства тут, только $\mathbb N$ заменяем на «множество чётных натуральных чисел», а $\mathcal{P}(\mathbb N)$ заменяем на $\mathbb N$.

Ну, и биекция, которая всё рушит, очевидна. Каждому натуральному $n$ ставим в соответствие чётное натуральное $2n$.

Vladimir Pliassov в сообщении #1527593 писал(а):

(потому что их как бы "меньше")?

Это очень хороший признак — ироничное отношение к такой аргументации. Правда.

[Vladimir Pliassov]

Спасибо!

svv в сообщении #1527502 писал(а):

Вы показали, что сюръекцией не является Ваша $f$, но не любая инъекция из $\mathbb N$ в $\mathcal{P}(\mathbb N)$.

А как показать, что любая? То есть какие еще есть доказательства несчетности множества всех подмножеств, кроме этого:

Цитата:

$\eqno (0.1)$ Пусть $X$ --- произвольное множество, $\mathcal{P}(X)$ --- множество всех подмножеств $X$.
$\eqno (0.2)$ Пусть $f$ --- биекция $X$ на $\mathcal{P}(X)$. Требуется доказать или опровергнуть её существование.
$\eqno (1)$ Пусть $Y = \{ x \in X : x \not\in f(x) \} $.
$\eqno (2)$ $f$ --- биекция, потому $Y = f(y)$ для некоторого $y \in X$.
$\eqno (3)$ Если $y \in Y$, то $y \in f(y)$ и $y \not\in Y$.
$\eqno (4)$ Если $y \not\in Y$, то $y \not\in f(y)$ и $y \in Y$.
$\eqno (5)$ Противоречие --- $f$ не существует.

? Это пока что единственное, какое я знаю.

[svv]

Других, кроме этого и "диагонального", я не знаю. Но зато это доказательство я встречал в какой-то популярной книжке в наглядной форме (хотя кто знает, может, Вам больше по душе чёткая формальная запись, чем картинка?).

Пусть установлено взаимно однозначное соответствие между элементами некоторого множества $A$ и подмножествами $A$.
Возьмём какой-то элемент $A$. Принадлежит ли он подмножеству, поставленному ему в соответствие? Если принадлежит, покрасим этот элемент в синий цвет. Если нет — покрасим в красный. По этому правилу раскрасим все элементы $A$.
Пусть $R$ — это множество всех красных элементов $A$. Оно соответствует некоторому элементу $x$. Этот $x$ синий или красный?
Пусть $x$ синий. Тогда $x\in R$. Но это противоречит тому, что $R$ состоит только из красных элементов.
Пусть $x$ красный. Тогда $x\notin R$. Но это противоречит тому, что $R$ содержит все красные элементы.

[mihaild]

Vladimir Pliassov в сообщении #1527593 писал(а):

моему, $ f(a)=\{a\}, \; a=1, 2, \ldots$ это биекция

Биективность функции зависит от того, с каким кодоменом (областью значений) мы её рассматриваем. Любая инъекция является биекцией между своей областью определения и своим образом. Ваша $f$ является биекцией между натуральными числами и одноэлементными подмножествами, но является только инъекцией, а не биекцией, из натуральных чисел во все подмножества.
Я имел в виду "эта функция не задает биекцию между $\mathbb N$ и $\mathcal P (\mathbb N)$.

Vladimir Pliassov в сообщении #1527608 писал(а):

То есть какие еще есть доказательства несчетности множества всех подмножеств, кроме этого:

Например через анализ: показать, что отрезок $[0, 1]$ равномощен множеству всех подмножеств (мы уже показали, что множество всех подмножеств натуральных чисел равномощно множеству двоичных последовательностей, а это уже почти что отрезок). Ну а отрезок несчетен - иначе возьмем нумерацию точек отрезка, построим последовательность вложенных отрезков, $n$-й из которых не содержит $n$-ю точку - их пересечение непусто по лемме о вложенных отрезках, но не может содержать ни одну из пронумерованных точек, потому что все пронумерованные точки мы выкинули.
Но это очень дурное рассуждение.

[Vladimir Pliassov]

svv в сообщении #1527609 писал(а):

(хотя кто знает, может, Вам больше по душе чёткая формальная запись, чем картинка?).

Ваш "раскрашенный" вариант доказательства мне еще помог, спасибо, я вообще всегда за картинки, и это доказательство я для себя иллюстрировал в виде диаграммы Венна (подмножество $Y$ внутри множества $X$, стрелки-отображения от элементов в подмножество и из подмножества в его дополнение), иначе гораздо труднее было бы понять.

mihaild в сообщении #1527618 писал(а):

Vladimir Pliassov в сообщении #1527593 писал(а):

моему, $ f(a)=\{a\}, \; a=1, 2, \ldots$ это биекция

Биективность функции зависит от того, с каким кодоменом (областью значений) мы её рассматриваем. Любая инъекция является биекцией между своей областью определения и своим образом. Ваша $f$ является биекцией между натуральными числами и одноэлементными подмножествами, но является только инъекцией, а не биекцией, из натуральных чисел во все подмножества.
Я имел в виду "эта функция не задает биекцию между $\mathbb N$ и $\mathcal P (\mathbb N)$.

Спасибо, это понятно.

mihaild в сообщении #1527618 писал(а):

Vladimir Pliassov в сообщении #1527608 писал(а):

То есть какие еще есть доказательства несчетности множества всех подмножеств, кроме этого:

Например через анализ: показать, что отрезок $[0, 1]$ равномощен множеству всех подмножеств (мы уже показали, что множество всех подмножеств натуральных чисел равномощно множеству двоичных последовательностей, а это уже почти что отрезок). Ну а отрезок несчетен - иначе возьмем нумерацию точек отрезка, построим последовательность вложенных отрезков, $n$-й из которых не содержит $n$-ю точку - их пересечение непусто по лемме о вложенных отрезках, но не может содержать ни одну из пронумерованных точек, потому что все пронумерованные точки мы выкинули.
Но это очень дурное рассуждение.

Я читал об этом. Если взять случай, когда обе последовательности -- справа и слева -- имеют один и тот же предел, то эта точка (предел) и есть пересечение всех вложенных отрезков (при этом их должно быть бесконечно много). Но я пока не понимаю, как это и то, что крайние точки отрезков выбрасываются, доказывает несчетность множества этих отрезков. Ведь тут доказывается только то, что предельная точка последовательности не является одним из ее членов.

[Vladimir Pliassov]

А если так?

Возьмем полуоткрытый промежуток $[a,b)$, перенумеруем все его точки, при этом из двух точек пусть точка, находящаяся правее, получит больший номер. Возьмем две точки $c$ и $d$, номера которых $n$ и $n+1$ соответственно. Между любыми двумя точками промежутка есть еще точка, поэтому между точками $c$ и $d$ есть точка $\lambda$, которая не имеет номера.

[Vladimir Pliassov]

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

mihaild в сообщении #1527618 писал(а):

это уже почти что отрезок)

Тогда точке $\lambda$ будет соответствовать последовательность, не имеющая номера.

[mihaild]

Vladimir Pliassov в сообщении #1527620 писал(а):

Ведь тут доказывается только то, что предельная точка последовательности не является одним из ее членов

Нет, тут доказывается совершенно другое - получившаяся из леммы о вложенных отрезках точка не обязана быть предельной точкой последовательности.
Тут берется произвольная последовательность точек отрезка, и доказывается, что отрезок содержит точку, не принадлежащую этой последовательности. Следовательно, отрезок несчетен (иначе была бы последовательность, содержащая все его точки).

Vladimir Pliassov в сообщении #1527637 писал(а):

перенумеруем все его точки, при этом из двух точек пусть точка, находящаяся правее, получит больший номер

Вот второе условие очень ограничивающее. Монотонно нельзя пронумеровать даже целые числа, и тем более рациональные. Но и тех и других - счетно.

[Vladimir Pliassov]

mihaild в сообщении #1527654 писал(а):

Vladimir Pliassov в сообщении #1527637 писал(а):

перенумеруем все его точки, при этом из двух точек пусть точка, находящаяся правее, получит больший номер

Вот второе условие очень ограничивающее. Монотонно нельзя пронумеровать даже целые числа, и тем более рациональные. Но и тех и других - счетно.

Понятно, спасибо, я и сам это подозревал.

mihaild в сообщении #1527654 писал(а):

Нет, тут доказывается совершенно другое - получившаяся из леммы о вложенных отрезках точка не обязана быть предельной точкой последовательности.
Тут берется произвольная последовательность точек отрезка, и доказывается, что отрезок содержит точку, не принадлежащую этой последовательности. Следовательно, отрезок несчетен (иначе была бы последовательность, содержащая все его точки).

Об этом (хотя не совсем так) есть статья https://en.wikipedia.org/wiki/Cantor%27 ... ty_theorem В ней доказывается теорема

Цитата:

Для любой последовательности действительных чисел $x_1, x_2, x_3, \ldots$

-- обозначим ее $X$ --

Цитата:

и любого отрезка $[a, b]$ существует число в $[a, b]$, которое не содержится в данной последовательности.

Чтобы найти число в $[a, b]$, которое не содержится в данной последовательности, постройте две последовательности действительных чисел следующим образом: Найдите первые два числа данной последовательности, которые находятся в открытом промежутке $(a, b)$.

(Если они есть. Если нет, то для этого случая теорема справедлива.)

Цитата:

Обозначим меньшее из этих двух чисел $a_1$, а большее - $b_1$. Подобным же образом найдите первые два числа заданной последовательности, которые находятся в $(a_1, b_1)$. Обозначим меньшее через $a_2$, а большее через $b_2$. Продолжение этой процедуры генерирует последовательность интервалов $(a_1, b_1), \; (a_2, b_2), \; (a_3, b_3), \; \ldots\; ,$ такую, что каждый интервал в последовательности содержит все последующие интервалы, то есть генерирует последовательность вложенных интервалов.

(Для этого последовательность $X$ должна быть такой, что ее члены приближаются к предельной точке то справа, то слева?)

Цитата:

Это означает, что последовательность $a_1, a_2, a_3, \ldots$ возрастает, а последовательность $b_1, b_2, b_3, \ldots$ убывает.

(Это соответствует тому, что последовательность $X$ такая, что ее члены приближаются к предельной точке то справа, то слева. Обозначим последовательность $a_1, a_2, a_3, \ldots$ через $A$, а последовательность $b_1, b_2, b_3, \ldots$ через $B$.)

Цитата:

Либо количество сгенерированных интервалов конечно, либо бесконечно. Если конечно, пусть $(a_L, b_L)$ будет последним интервалом.

(Так будет, если последовательность $X$ конечная или такая, что ее члены приближаются к предельной точке с одной стороны.)

Цитата:

Если бесконечно, возьмем пределы $a_\infty=\lim_{n\to \infty} a_n$ и $b_\infty = \lim_{n\to \infty} b_n$. Поскольку $a_n<b_n$ для всех $n$, либо $a_\infty = b_\infty$, либо $a_\infty < b_\infty$. Таким образом, следует рассмотреть три случая:

Случай 1: есть последний интервал $(a_L, b_L)$. Поскольку в этом интервале может быть не более одного $x_n$, каждый $y$ в этом интервале, кроме $x_n$ (если он существует), не содержится в данной последовательности.

[Как я понимаю, в случае 1, так же как и в остальных случаях, имеется в виду, что $x_n=a_n$, то есть для возрастающей последовательности $A$ обозначение $A=x_1, x_2, x_3, \ldots$ равноправно с обозначением $A=a_1, a_2, a_3, \ldots\; .$ (При этом для убывающей последовательности $B\colon B=b_1, b_2, b_3, \ldots$ подобная замена (скажем, $B=y_1, y_2, y_3, \ldots$) не предусмотрена, то есть последовательность $B$, сама по себе, не рассматривается.

На мой взгляд, то, что здесь индексы при $x$ и при $a$ обозначены одной и той же буквой, неудачно, так как номер $x$ как члена последовательности $X$ может не совпадать (и, предположительно, чаще всего не совпадает) с номером $x$ как члена последовательности $A$. Я думаю, было бы лучше в последовательности $A$ писать, например, $x_{m_n}=a_n$.

Соответственно, в последовательности $X$ (если бы пришлось) для общего обозначения индексов выбрать букву $m\colon X=x_1, x_2, x_3, \ldots=x_1, x_2, x_3, \ldots, x_m, \ldots\; .$ Вместо записи $A=x_1, x_2, x_3, \ldots$ употреблять запись $A=x_{m_1}, x_{m_2}, x_{m_3}, \ldots\; .$ Тогда не будет путаницы $A$ с $X$.]

Цитата:

Случай 2: $a_\infty = b_\infty$. Тогда $a_\infty$ не содержится в данной последовательности, поскольку для всех $n$: $a_\infty$ принадлежит интервалу $(a_n, b_n)$, но $x_n$ не принадлежит $(a_n, b_n)$. В символах: $a_\infty\in (a_n, b_n)$ , но $x_n\notin (a_n, b_n)$.

(Здесь, как я понимаю, имеется в виду, что ни при каком $n$ $a_\infty$ не может быть равно $a_n=x_n$.)

Цитата:

Случай 3: $a_\infty < b_\infty$. Тогда каждый $y$ из $[a_\infty, b_\infty]$ не содержится в данной последовательности, поскольку для всех $n$: $y$ принадлежит $(a_n, b_n)$, а $x_n$ нет.

Доказательство завершено, поскольку во всех случаях было найдено хотя бы одно действительное число в $[a, b]$ которое не содержится в данной последовательности.

mihaild в сообщении #1527654 писал(а):

получившаяся из леммы о вложенных отрезках точка не обязана быть предельной точкой последовательности.

Да, в общем случае не обязана, если имеется в виду последовательность $X$. Но эта точка является предельной для последовательности $A$ и для последовательности $B$ в случае 2, а также, наверное, и для последовательности $X$ в случае 2.

mihaild в сообщении #1527654 писал(а):

Тут берется произвольная последовательность точек отрезка, и доказывается, что отрезок содержит точку, не принадлежащую этой последовательности. Следовательно, отрезок несчетен (иначе была бы последовательность, содержащая все его точки).

Как видим, в приведенном доказательстве берется не произвольная последовательность точек отрезка, а просто произвольная последовательность. Но, как я понимаю, в самом деле, можно взять произвольную бесконечную последовательность точек отрезка (тогда она будет ограниченной, и ее предел будет находиться в отрезке, в частности, он может быть равен одной из крайних точек отрезка) -- эта последовательность может соответствовать последовательности $A$ или последовательности $B$ из приведенного доказательства для случая 2, а также объединению этих двух последовательностей в одну, -- и вместо того, чтобы привлекать вложенные отрезки, усмотреть простую вещь: поскольку предел последовательности не принадлежит последовательности и при этом принадлежит отрезку, то имеется точка отрезка, которая не принадлежит последовательности. И это доказывает несчетность точек отрезка.

Беру назад свое заявление:

Vladimir Pliassov в сообщении #1527620 писал(а):

Ведь тут доказывается только то, что предельная точка последовательности не является одним из ее членов.

То, что " предельная точка последовательности не является одним из ее членов", это само собой, но в доказательстве есть такой момент, что эта точка принадлежит отрезку (и не принадлежит последовательности).

Таким образом, мы имеем еще два доказательства несчетности множества бесконечных последовательностей нулей и единиц (если удастся показать, что оно находится в биекции с множеством действительных чисел отрезка -- это отдельный вопрос). Причем эти два доказательства не зависят от доказательства несчетности $\mathcal P (\mathbb N)$.

[Someone]

Vladimir Pliassov в сообщении #1527736 писал(а):

Об этом (хотя не совсем так) есть статья https://en.wikipedia.org/wiki/Cantor%27 ... ty_theorem В ней доказывается теорема

Цитата:

Для любой последовательности действительных чисел $x_1, x_2, x_3, \ldots$

-- обозначим ее $X$ --

Цитата:

и любого отрезка $[a, b]$ существует число в $[a, b]$, которое не содержится в данной последовательности.

Это первоначальная формулировка теоремы Кантора о несчётности множества действительных чисел (1874 год). И доказательство его же (с точностью до несущественных деталей).

Георг Кантор. Труды по теории множеств. Москва, "Наука", 1985. Вторая статья в этом сборнике.

[mihaild]

Vladimir Pliassov в сообщении #1527736 писал(а):

Для этого последовательность $X$ должна быть такой, что ее члены приближаются к предельной точке то справа, то слева?

Нет, неважно. Просто если на очередном этапе не получилось найти пару, то значит пронумерованы не все точки (т.к. очередной интервал содержит уж точно больше одной точки).

Vladimir Pliassov в сообщении #1527736 писал(а):

Это соответствует тому, что последовательность $X$ такая, что ее члены приближаются к предельной точке то справа, то слева

Нет конечно. Мы выбираем из $X$ какие-то члены. И даже разрешаем чтобы $a_3$ шло в последовательности после $b_3$.
Ну и дальше вы начали придумывать что-то странное, частично правильное, частично нет, но точно не нужное.

Vladimir Pliassov в сообщении #1527736 писал(а):

поскольку предел последовательности не принадлежит последовательности

Совершенно не обязательно. Например предел последовательности $0, \frac{1}{2}, \frac{1}{3}, \ldots, \frac{1}{n}, \ldots$ ей принадлежит.
Вообще, предельные точки последовательности не имеют никакого отношения к доказательству. Важно два факта: мы можем построить последовательность вложенных отрезков, такую что $n$-й элемент последовательности не принадлежит $n$-му отрезку, и что последовательность вложенных отрезков имеет непустое пересечение.