Счетность множеств (задачи из Давидовича)

[ewert]

А, на конечность я не обратил внимания. Впрочем, в тексте д-ва ничего менять не требуется, надо лишь добавить одну фразу.

[irod]

grizzly в сообщении #1121176 писал(а):

Вы нигде не использовали в доказательстве тот факт, что множества различны. Вы, возможно, считаете, что это вполне очевидно для читателя догадаться, где и как он использован. Это иллюзия.

Пусть мы с помощью алгоритма перебрали сколько-то множеств $A_i$, в которых было в сумме $n$ различных элементов. Существует лишь конечное число способов составить из этих $n$ элементов какие-то конечные множества так, чтобы ни одно из них полностью не совпало ни с одним из уже обработанных $A_i$-х. А у нас осталось обработать еще бесконечное (счетное) число следующих $A_i$-х. Следовательно, далее наш алгоритм гарантированно рано или поздно наткнется на ранее не встречавшийся элемент в каком-то из следующих $A_i$-х, и этот элемент будет добавлен в нашу последовательность.
Я понимаю, что некоторые из моих утверждений выше могут потребовать отдельного доказательства, просто хочу спросить в правильном ли направлении я иду?

grizzly в сообщении #1121182 писал(а):

А слово "последовательности" было неуместно.

Прошу прощения за наивный вопрос, а какое слово тогда лучше использовать? Полагаю, "ряды" тоже не подходит?

ewert в сообщении #1121184 писал(а):

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

Какую фразу?

[ewert]

irod в сообщении #1121212 писал(а):

Какую фразу?

Что объединение состоит из бесконечного количества элементов, т.к. иначе какие-либо множества совпадали бы.

[irod]

ewert
А, ясно, я выше как раз это и попытался расписать.

[grizzly]

irod в сообщении #1121212 писал(а):

Прошу прощения за наивный вопрос, а какое слово тогда лучше использовать?

Вообще, "последовательность" употребляется в контексте именно счётного (а значит, бесконечного) множества. Можно было сказать "конечные последовательности" (некая вольность речи, но она часто используется). Либо говорить про данные наборы / множества (пронумерованные).

irod в сообщении #1121212 писал(а):

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

Да, верно. В общем, такого рассуждения достаточно (его можно, наверное, оформить красивее, но не в этом здесь цель).

[ewert]

irod в сообщении #1121227 писал(а):

я выше как раз это и попытался расписать.

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

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

Что же до не очень приятной обязанности выкидывать какие-то элементы, то от неё очень легко отвертеться, поскольку любое счётное объединение можно представить как (не более чем) счётное объединение непересекающихся подмножеств исходных множеств. Рекомендую самостоятельно это доказать, т.к. этот факт довольно часто бывает полезен. Вообще полезно разбивать доказательство на условно независимые блоки.

[grizzly]

irod
При решении задачи 10 (про счётное объединение счётных множеств) Вас, наверное, уже насторожило замечание ewert'а к предыдущей задаче. Здесь я думаю нужно сразу дать подсказку: в данном случае действительно невозможно заполнить бесконечную таблицу счётным числом последовательностей, если использовать обычные алгоритмы нумерации / мат.индукцию. Проблема состоит в том, что Вы не сможете "замкнуть" нумерацию элементов всех множеств одновременно с нумерацией самих множеств.

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

[irod]

ewert в сообщении #1121236 писал(а):

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

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

Да, так короче чем у меня

ewert в сообщении #1121236 писал(а):

Что же до не очень приятной обязанности выкидывать какие-то элементы, то от неё очень легко отвертеться, поскольку любое счётное объединение можно представить как (не более чем) счётное объединение непересекающихся подмножеств исходных множеств. Рекомендую самостоятельно это доказать, т.к. этот факт довольно часто бывает полезен. Вообще полезно разбивать доказательство на условно независимые блоки.

Ок. Спасибо за помощь!

grizzly в сообщении #1121410 писал(а):

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

Неоднократно встречал упоминания про эту аксиому здесь на форуме, в том смысле что это очень важная штука, и часто требуется в доказательствах. Поэтому меня смущает что ее нет в Давидовиче. Но раз ее нет, то, возможно, эту задачу можно решить без нее?

grizzly в сообщении #1121410 писал(а):

При решении задачи 10 (про счётное объединение счётных множеств) Вас, наверное, уже насторожило замечание ewert'а к предыдущей задаче. Здесь я думаю нужно сразу дать подсказку: в данном случае действительно невозможно заполнить бесконечную таблицу счётным числом последовательностей, если использовать обычные алгоритмы нумерации / мат.индукцию. Проблема состоит в том, что Вы не сможете "замкнуть" нумерацию элементов всех множеств одновременно с нумерацией самих множеств.

Позвольте подставить под сомнение это Ваше утверждение Мне кажется у меня получилось придумать такой алгоритм, он похож на задачу 8.

10. Доказать, что объединение счетного числа счетных множеств счетно.

Доказательство.
Алгоритм построения пронумерованной последовательности из элементов $\bigcup\limits_{i=1}^{\infty} A_i$, где $A_i$ -- счетное множество:
Вход: пронумерованные последовательности $\{ a_1^i,a_2^i,\ldots \} = A_i$, где $A_i$ -- счетное множество;
Выход: пронумерованная последовательность из элементов $\bigcup\limits_{i=1}^{\infty} A_i$;
Для $i=1,2,\ldots$ цикл:
\begin{itemize} \item[] Для $j=1,2,\ldots,i$ цикл: \begin{itemize} \item[] Для $k=1,2,\ldots,i$ цикл: \begin{itemize} \item[] Если элемент $a_j^k$ ранее не был добавлен в формируемую последовательность из $\bigcup\limits_{i=1}^{\infty} A_i$: \begin{itemize} \item[] Добавляем $a_j^k$ в последовательность; \end{itemize} \item[] Конец если; \end{itemize} \item[] Конец цикла по $k$; \end{itemize} \item[] Конец цикла по $j$; \end{itemize}
Конец цикла по $i$;

Построенная последовательность будет иметь вид:

$$\{ a_1^1, a_2^1, a_1^2, a_2^2, a_3^2,a_1^3, a_2^3, a_3^3, \ldots \}.$$

В случае ненулевого пересечения каких-то $A_i$-х повторы их общих элементов будут отсутствовать в последовательности, но общий порядок сохранится. Если все исходные множества $A_i$ совпадают, то последовательность будет совпадать с последовательностью $\{ a_1^1,a_2^1,\ldots \} = A_1$, и также будет счетной.

[grizzly]

irod в сообщении #1121526 писал(а):

Поэтому меня смущает что ее нет в Давидовиче.

Почему нет? Давидович говорит в комментариях к этим (основным) листкам, что она всегда держится в уме, как и аксиомы ZF. Также он говорит, что аксиоматический подход был бы здесь совершенно неуместен.

irod в сообщении #1121526 писал(а):

возможно, эту задачу можно решить без нее?

Увы, нет.

irod в сообщении #1121526 писал(а):

Мне кажется у меня получилось придумать такой алгоритм
...
Вход: пронумерованные последовательности $\{ a_1^i,a_2^i,\ldots \} = A_i$, где $A_i$ -- счетное множество;

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

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

[arseniiv]

(Аксиома выбора)

У аксиомы выбора есть много довольно прозрачных эквивалентных формулировок:
• $\prod_{i\in I} A_i\ne\varnothing$ для любого семейства непустых множеств $A_i$, индексированного элементами любого множества $I$. Для конечных $I$ это утверждение можно вывести из других аксиом ZF, а вот для остальных — нет.
• У любой сюръекции существует хотя бы одно сечение. (Эту на форуме как раз недавно вспоминали.)
• И много других, например, [1], [2].

Правда, бесконечное декартово произведение в терминах упорядоченных пар выразить, как конечные, не получится. Зато под элементами $\prod_{i\in I} A_i$ можно понимать всевозможные функции $f\colon I\to\bigcup_{i\in I} A_i$ такие, что $\forall i\in I.\,f(i)\in A_i$. Так это декартово произведение для общего случая и определяют, и мы приходим к обычной формулировке аксиомы выбора, которая говорит о существовании хотя бы одной такой функции.

Это всё к тому, что она не такая страшная, и пытаться обойтись без неё не обязательно. (Вот с континуум-гипотезой дело другое.)

[grizzly]

irod в сообщении #1121526 писал(а):

Алгоритм построения пронумерованной последовательности

Алгоритм у Вас не особенно оптимальный, да и на выходе получается не совсем та последовательность, которую Вы указали. Вы всякий раз переходя к новому $i$ начинаете всю таблицу перебирать заново. Это баг или фича?

[irod]

arseniiv, спасибо, я поразбираюсь с этим.

grizzly в сообщении #1121531 писал(а):

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

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

grizzly в сообщении #1121531 писал(а):

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

Ок, согласен.

grizzly в сообщении #1121598 писал(а):

Алгоритм у Вас не особенно оптимальный, да и на выходе получается не совсем та последовательность, которую Вы указали. Вы всякий раз переходя к новому $i$ начинаете всю таблицу перебирать заново. Это баг или фича?

Это фича Я над оптимальностью не заморачивался совсем, у нас ведь тут математическое доказательство, а не задача по программированию. Тем более смысла оптимизировать этот алгоритм нет никакого, потому что самый внешний цикл (по $i$) все равно останется бесконечным, и никогда не будет полностью выполнен ни на одном компе.
С итоговой последовательностью я действительно ошибся, она получится вот такая:

$$\{ a_1^1, a_1^2, a_2^1, a_2^2, a_1^3,a_2^3, a_3^1, a_3^2, a_3^3, \ldots \}.$$

[grizzly]

irod в сообщении #1121800 писал(а):

А почему этот нюанс всплыл только сейчас?

Может и не стоило вовсе упоминать. Но вот мне было жаль, что я узнал об этой аксиоме уже после курса матана, в котором она используется на полную катушку. Какое-то читерство получается. Так что упомянуть я счёл должным, но дальше углубляться не стану -- arseniiv объясняет эти вопросы намного лучше (можете также поискать на форуме, тема много раз обсуждалась).

irod в сообщении #1121800 писал(а):

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

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

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

[arseniiv]

(Оффтоп)

grizzly в сообщении #1121811 писал(а):

arseniiv объясняет эти вопросы намного лучше

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

[irod]

grizzly в сообщении #1121811 писал(а):

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

Ок

Двигаюсь дальше.

11. Доказать, что следующие множества счетны:
а) множество всевозможных конечных последовательностей нулей и единиц;
б) множество всевозможных русских "слов".

Доказательство.
(Здесь используем без доказательства тот факт, что число всевозможных последовательностей нулей и единиц длины $n$, рАвно как и число всевозможных русских "слов" длины $n$, конечно.)
а) Множество всевозможных конечных последовательностей нулей и единиц можно представить как объединение счетного числа различных конечных множеств последовательностей нулей и единиц определенной длины:

$$ \bigcup\limits_{n=1}^{\infty} A_n, $$

где $A_n$ -- конечное множество различных последовательностей нулей и единиц длины $n$.
Из задачи 9 этого листка следует, что такое объединение счетно.

б) Аналогично пункту а), представляем множество всех возможных "слов" как объединение счетного числа конечных множеств "слов" длины $n$, $\forall n \in \mathbb{N}$, и применяем задачу 9.