Теорема Кантора о несчетности последовательностей 1 и 0

[Mikhail_K]

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

Я думаю, что невозможно построить биекцию между $\mathbb{N}$ и множеством описанных в первоначальном сообщении классов.

Я не уверен, что правильно понял Ваше первое сообщение. Но Вы там пишете, что строите сначала два класса, затем ещё четыре, затем ещё восемь, и так далее. Тогда можно первым двум классам присвоить номера 1 и 2, следующим четырём - номера 3,4,5,6, следующим восьми - номера 7,8,9,10,11,12,13,14, и так далее. Тогда каждый класс получит свой натуральный номер, и, стало быть, будет построена биекция между $\mathbb{N}$ и множеством классов.

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

По-моему, в "диагональном" доказательстве предпринимается попытка построить не-биекцию и на основании этой не-биекции утверждается, что нет биекции. Или нет?

Нет. В диагональном доказательстве берётся произвольное отображение между $\mathbb{N}$ и множеством последовательностей нулей и единиц, и доказывается, что это отображение - точно не биекция (а именно, указывается последовательность, которая точно не соответствует никакому натуральному числу). Если любое отображение - не биекция, значит, биекций нет.

[svv]

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

Попытаюсь сделать это на свежую голову.

Лучше не надо. Вдруг у Вас получится биекция, и теория множеств рухнет? А на ней столько всего держится.

[Vladimir Pliassov]

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

Лучше не надо. Вдруг у Вас получится биекция, и теория множеств рухнет? А на ней столько всего держится.

[Vladimir Pliassov]

Привожу обсуждаемое доказательство.

Цитата:

Теорема 7 (Кантора). Множество бесконечных последовательностей нулей и единиц несчётно.

$\rhd$ Предположим, что оно счётно. Тогда все последовательности нулей и единиц можно перенумеровать: $\alpha_0, \alpha_1, \ldots$ Составим бесконечную вниз таблицу, строками которой будут наши последовательности:

$$\begin {matrix} \alpha_0=&\alpha_{00}&\alpha_{01}&\alpha_{02}&\ldots\\ \alpha_1=&\alpha_{10}&\alpha_{11}&\alpha_{12}&\ldots\\ \hdotsfor [1.5] {5} \\ \alpha_2=&\alpha_{20}&\alpha_{21}&\alpha_{22}&\ldots\\ \end {matrix} $$

(через $\alpha_{ij}$ мы обозначаем $j$-й член $i$-й последовательности). Теперь рассмотрим последовательность, образованную стоящими на диагонали членами $\alpha_ {00}, \alpha_ {11}, \alpha_ {22}, \ldots ;$ её $i$-й член есть $\alpha_{ii}$ и совпадает с $i$-м членом $i$-й последовательности. Заменив все члены на противоположные, мы получим последовательность $\beta$, у которой

$$\beta_i=1-\alpha_{ii},$$

так что последовательность $\beta$ отличается от любой из последовательностей $\alpha_i$ (в позиции $i$) и потому отсутствует в таблице. Это противоречит нашему предположению о том, что таблица включает в себя все последовательности. $\lhd$

http://math-info.hse.ru/f/2014-15/CompL ... hestva.pdf стр. 26

А если так?

Множество элементов каждой последовательности находится в биекции с $\mathbb N$. Пусть множество всех последовательностей также находится в биекции с $\mathbb N$, тогда множество элементов каждой последовательности находится в биекции с множеством всех последовательностей.

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

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

[mihaild]

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

Множество элементов каждой последовательности находится в биекции с $\mathbb N$

Уточните, что вы понимаете под "множеством элементов последовательности".
И выражение "одно множество находится в биекции с другим" тоже выглядит весьма странно. Если вам нужна конкретная биекция - обозначьте её как-нибудь, если нет - то, видимо, то что вам нужно называется равномощностью.

[Doctor Boom]

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

Привожу обсуждаемое доказательство.

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

[eugensk]

Doctor Boom в сообщении #1567790 писал(а):

..., только почему его все хейтят?

"Все" откуда? "Все" без уточнения может оказаться "практически никто", знаете ли.

(потенциальные хейтеры)

На основании проведенных исследований в наблюдаемой Вселенной существуют следующие континуумы:
- Абсолютный континуум;
- качественный континуум, представляющий собой ряды натуральных чисел;
- количественный континуум, представляющий собой качественные числа и монады.
- внутренний континуум, качественно-количественных чисел и объектов, составленных из этих чисел.
...Физика исследует движение качественно-количественных объектов, двигающихся, либо в Абсолютном пространстве, либо в пространстве чистого количества.

[Vladimir Pliassov]

Doctor Boom в сообщении #1567790 писал(а):

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

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

Цитата:

Потенциальная и актуальная бесконечность

Бесконечность может рассматриваться как неограниченность некоторого процесса, например, когда во втором постулате Евклида утверждается возможность продолжить бесконечно и непрерывно любую прямую, то имеется в виду, что процесс можно непрерывно продолжать, но существование такого самостоятельного объекта, как бесконечная прямая, из него не следует. Такого рода процессы и совокупности объектов, их описывающие, характеризуют как потенциальную бесконечность (в схоластике используется термин «синкатегорематическая бесконечность»), потенциально бесконечное не подразумевает целостных бесконечных предметов и явлений, в каждой фазе бесконечного процесса рассматриваются лишь конечные сущности, то есть [ потенциально бесконечное -- вставка моя] является лишь частичным отрицанием конечного[1]. (Википедия)

Потенциальная бесконечность это когда к конечному множеству всегда можно добавить еще один элемент.

Цитата:

Альтернативой является понятие актуальной бесконечности (в схоластике — «категорематическая бесконечность»), которая означает рассмотрение конечно неизмеримых объектов как данность, как реально существующих, но при этом как единых и целостных, с которыми возможно оперировать[1]. В таком ключе актуально бесконечное — как прямое и полное отрицание конечного — используют мистики для характеризации различных божественных категорий, математики современности оперируют с актуально бесконечными множествами[⇨] и актуально бесконечномерными пространствами[⇨]. Представления о допустимости и содержании актуальной бесконечности в философии, теологии, логике, математике, естествознании существенно менялись на протяжении всего времени рассмотрения вопроса. (Там же)

Я сам полтора года назад написал:

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

Вообще же, мне кажется, что доказательство, которое начинается словами: "Составим бесконечную таблицу," -- нельзя принимать всерьез, надо поискать какое-нибудь другое.

И тогда же я написал:

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

к любому натуральному числу можно добавить еще единицу, и хотя непонятно, как это может быть, но, не задаваясь этим вопросом, можно принять это как факт. Лично у меня это не вызывает возражений.

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

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

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

Рассуждать о бесконечных множествах, конечно же, можно, почти вся математика в этом и состоит.

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

[mihaild]

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

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

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

Я не видел особого хейта. В нём есть небольшая небрежность - начальное предположение "предположим, множество счетно" на самом деле не нужно, и доказательство имеет структуру "любая функция из натуральных чисел в последовательности - не биекция; значит, биекции нет", слегка замаскированную под "пусть биекция есть, тогда это не биекция, значит биекции нет", но эта маскировка часто сбивает неопытных людей.

[Doctor Boom]

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

Я не видел особого хейта.

Я помню читал одну тему, где Someone прям хейтит это док-во от противного, мол пальцем у виска коллеги будут крутить

[eugensk]

Doctor Boom
Да что же это такое... Я помню, как Someone разбирал критику доказательства Кантора, и действительно, находил в ней (критике) много несуразного.
Гугл вашей памяти в помощь.

[Vladimir Pliassov]

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

Уточните, что вы понимаете под "множеством элементов последовательности".

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

[mihaild]

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

Но как назвать то, что представляет собой все члены последовательности вместе?

А что именно вам нужно? Формально, последовательность нулей и единиц - это функция из натуральных чисел в $\{0, 1\}$. Дальше можете из этой функции делать что угодно, что вам нужно, только сформулировав, что вы делаете.

[Vladimir Pliassov]

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

А что именно вам нужно? Формально, последовательность нулей и единиц - это функция из натуральных чисел в $\{0, 1\}$.

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

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

И выражение "одно множество находится в биекции с другим" тоже выглядит весьма странно.

Может быть, Вы имеете в виду, что это выражение не подходит в контексте? Потому что вот здесь, например, сказано о биекции множества $X$ с множеством $\mathbb N$:

Цитата:

Счётное множество — бесконечное множество, элементы которого возможно пронумеровать натуральными числами. Более формально: множество $X$ является счётным, если существует биекция со множеством натуральных чисел: $X\leftrightarrow \mathbb N$. (Википедия)

Или Вы имеете в виду, что не следует употреблять выражение "одно множество находится в биекции с другим множеством", следует говорить: "существует биекция между множествами"?

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

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

Конкретная биекция не является моей целью, целью является равномощность, но если доказать существование или несуществование биекции, то из этого следует равномощность или неравномощность.

Конкретная биекция подмножества множества всех последовательностей и всех натуральных чисел не нужна: все равно в какие последовательности отображаются какие натуральные числа (и даже какие последовательности будут задействованы в отображении, а какие нет), важно только, чтобы было инъективное отображение $\mathbb N \to (\mathbb N\to \{0, 1\})$.

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

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

[mihaild]

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

При этом совокупность

Как правило, совокупность - это синоним "множества", используемый чтобы избежать фраз вида "множество всех множеств элементами которых являются такие-то множества".

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

членов последовательности

А вот член последовательности - это в данном случае число $0$ либо $1$.

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

взаимно-однозначное соответствие это биекция

Да, взаимно-однозначное соответствие и биекция - это одно и то же.

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

Или Вы имеете в виду, что не следует употреблять выражение "одно множество находится в биекции с другим множеством", следует говорить: "существует биекция между множествами"?

Да, именно так.

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

то конкретная биекция между совокупностью членов последовательности и $\mathbb N$ существует по определению последовательности

Нет, последовательность это не обязательно биекция. Почти никогда не биекция собственно.

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

то биекция возможна не только между множествами, но и между другими совокупностями элементов

В теории множеств ничего кроме множеств не бывает. И сама по себе биекция (любая конкретная) - это тоже просто множество определенного вида.