Обсуждение книги Верещагина, Шена "Начала теории множеств"

[vego]

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

[vpb]

Уже было, см. тему О биекции отрезка на квадрат. Особенно самое последнее сообщение в той теме, там собственно ответ. Хоть это и есть указание готового решения (собственно, выше оно и так уже было указано...), но что ТС нашел бы его сам даже с подсказками, маловероятно; не зря в той теме неглупые участники шесть страниц вопрос мусолили.

-- 08.03.2021, 22:27 --

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

[vego]

Кантор, кстати, доказывал через цепные дроби

[Sinoid]

Кажется, сделал. Я надумал вот это:

Evgenii2012 в сообщении #1014617 писал(а):

Дорогие коллеги ! Большое спасибо за столь активное обсуждение. Я, естественно, согласен со всеми доводами. Сейчас я предложу другой вариант - давайте обсудим его.

Начало повторяется. Пусть у нас число $x\in [0,1]$ представляется бесконечной десятичной дробью вида $x=0,x_1x_2x_2\ldots .$ Бесконечные последовательности девяток, как и прежде, будем считать недопустимыми, за исключением случая $x_0=0,999\ldots ;$ В этом случае, сразу положим $f(x_0):=(1, 1).$ Далее, как и прежде, положим $f(0, x_1x_2x_3\ldots)=(0, x_1x_3x_5\ldots ; 0, x_2x_4x_6\ldots)$ в том и только том случае, если последовательность а) $x_i$ не является последовательностью вида $x=0,x_1\ldots x_{2k-1}9x_{2k+1}9x_{2k+3}9\ldots$ либо б) $x=0, x_1\ldots x_{2k}9x_{2k+2}9x_{2k+2}9\ldots$ (ведь именно эти последовательности дадут в образе "плохие" точки). Заметим, что множество тех $x=0,x_1x_2\ldots,$ для которых ни одно из условий а) и б) не выполнено, взаимнооднозначно отображается на $[0, 1)\times [0, 1).$

"Новая" часть. Если последовательность $x=0,x_1x_2\ldots x_{2n-1}9x_{2n+1}9x_{2n+3}9x_{2n+5}\ldots,$ где $n\geqslant 2,$то полагаем $f(x)=(1; 0, \underbrace{9\ldots 9}\limits_{2n-2}x_{2n-2}x_1x_2x_3\ldots x_{2n-5}x_{2n-4}x_{2n-3}x_{2n-1}x_{2n+1}x_{2n+3}\ldots)$ . Здесь стоит заметить, что $x_{2n-2}\ne 9$ по определению ! Далее, есть ещё точки вида $x=0,x_19x_39x_59\ldots$ . Возможны два случая: 1) $x_1\ne 9,$ тогда положим $f(x)=(1; x_1x_3x_5\ldots).$ 2) $x_1=9,$ тогда положим $f(x)=(1; 0, \underbrace{9\ldots 9}\limits_{2n-1}x_{2n+1}x_{2n+3}\ldots)$ , где $n$ соответствует наименьшему элементу $x_{2n+1},$ который отличен от числа 9. Указанное соотвествие переводит некоторое подмножество отрезка $[0, 1]$ на сторону квадрата $A_1=\{(1, x): x\in [0,1]\}$ и, вроде бы, оно взаимнооднозначно (Ваше мнение ?). С другой стороной квадрата - вполне аналогичная ситуация, когда девятки расположены на нечётных местах последовательности, соответствующей выбранному элементу $x\in [0, 1].$

переписать в строгом виде. Получилось вот что:
Начало повторяется. Пусть у нас число $x\in[0,1]$ представляется бесконечной десятичной дробью вида $x=\overline{0,x_{1}x_{2}x_{2}\ldots}$. Бесконечные последовательности девяток, как и прежде, будем считать недопустимыми, за исключением случая $x_{0}=\overline{0,999\ldots}$; В этом случае, сразу положим $f(x_{0}):=(1,\,1)$. Далее, как и прежде, положим $f(\overline{0,x_{1}x_{2}x_{3}\ldots})=(\overline{0,x_{1}x_{3}x_{5}\ldots}\,;\,\overline{0,x_{2}x_{4}x_{6}\ldots})$ в том и только том случае, если последовательность а) $x$ не имеет вид $x=\overline{0,\, x_{1}\ldots x_{2k+1}9x_{2k+3}9x_{2k+5}9\ldots}$‚ при этом цифра $x_{2k}$‚ если она существует‚ уже отлична от 9 ‚ либо б) $x$ не имеет вид $x=\overline{0,x_{1}\ldots x_{2k}9x_{2k+2}9x_{2k+2}9\ldots}$ ‚ при этом цифра $x_{2k-1}$ ‚ если она существует‚ уже отлична от 9. Ведь именно эти последовательности дадут в образе "плохие" точки. Отметим‚ что‚ как в а)‚ так и в б) $k$ может принимать значения‚ принадлежащему множеству натуральных чисел‚ начинающемуся‚ как и принято в обсуждаемой книге‚ с нуля‚ но тогда цифр перед девятками‚ если $x$ имеет вид пункта б)‚ не будет вовсе. Именно это соображение заставило нас в исходном представлении икса $x=\overline{0,x_{1}x_{2}x_{2}\ldots}$ цифры $x_{i}$ нумеровать не с 0‚ а с 1. И у нас получается, что множество тех $x=\overline{0,x_{1}x_{2}\ldots}$, для которых ни одно из условий а) и б) не выполнено, взаимно-однозначно отображается на $[0,1)\times[0,1)$. Пусть $x$ имеет вид‚ как в пункте а)‚ т. е.‚ $x=\overline{0,x_{1}x_{2}\ldots x_{2k+1}9x_{2k+3}9x_{2k+5}9x_{2k+7}\ldots}$, где пока $k\geqslant 1$, тогда полагаем $f(x)=(1;\,\overline{0,\underbrace{9\ldots9}\limits _{2k}x_{2k}x_{1}x_{2}x_{3}\ldots x_{2k-3}x_{2k-2}x_{2k-1}x_{2k+1}x_{2k+3}x_{2k+5}\ldots})$. В силу принятого пока соглашения о $k$‚ $2k\geqslant 2$ и поэтому цифра $x_{2k}$ существует и по определению отлична от 9. Далее, если же такой цифры нет‚ т. е. в случае $k=0$‚ то $x$ имеет вид: $x=\overline{0,x_{1}9x_{3}9x_{5}9\ldots}$. При этом возможны два случая: 1) $x_{1}\ne 9$, тогда положим $f(x)=(1;\,\overline{0,x_{1}x_{3}x_{5}\ldots})$. 2) $x_{1}=9$, тогда положим $f(x)=(1;\overline{0,\underbrace{9\ldots9}\limits _{2l+1}x_{2l+3}x_{2l+5}\ldots})$, где $l$ находится из уравнения $2l+3=2m+1$‚ при условии, что $x_{2m+1}$ - первая отличная от 9 цифра числа $x$ (в этом случае из-за самого вида числа $x$ она стоит в нечётном отрицвтельном разряде). Нужно еще учитывать‚ что‚ т. к. в этом случае $x_{1}=9$‚ то будет $2m+1\geqslant 3$‚ а‚ значит‚ решая уравнение $2l+3=2m+1$ относительно $l$‚ мы никогда не получим его отрицательным. Опять же‚ в этом случае будет и $2l+1\geqslant 1$‚ т. е. в ординате $f(x)$ сразу после запятой стоит как минимум одна девятка‚ что исключает совпадение $f(x)$‚ вычисленного в данном случае‚ с каким-нибудь $f(x)$‚ вычисленным в случае а). Указанное соответствие переводит некоторое подмножество отрезка $[0,\,1]$ на сторону квадрата $A_{1}=\{(1,x):x\in[0,1]\}$ и, вроде бы, оно взаимно-однозначно (Ваше мнение ?). С другой стороной квадрата - вполне аналогичная ситуация, когда девятки расположены на нечётных местах последовательности, соответствующей выбранному элементу $x\in[0,1]$.

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- результат переписывания совершенно нечитаем.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[svv]

Sinoid
Меня беспокоит, что Вы чувствуете необходимость расписывать доказательство теоремы 5 «более строго», чем это сделано у Верещагина—Шеня.

Уже доказано, что отрезок $[0,1]$ равномощен множеству бесконечных последовательностей нулей и единиц. А это множество (как показывает построение в теореме 5) равномощно множеству пар таких последовательностей.

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

[Sinoid]

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

Sinoid
Меня беспокоит, что Вы чувствуете необходимость расписывать доказательство теоремы 5 «более строго», чем это сделано у Верещагина—Шеня.

Уже доказано, что отрезок $[0,1]$ равномощен множеству бесконечных последовательностей нулей и единиц. А это множество (как показывает построение в теореме 5) равномощно множеству пар таких последовательностей.

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

Нет-нет-нет, я просто хочу все руками прощупать, чтобы был более-менее мощный фундамент для поднятия на следующий уровень. Применение новых теорем, естественно, упрощает решение задач. Но, смотрите, какую распространенную проблему мы осветили еще в одном месте и не только осветили, но и еще раз ее решили, подробно, во всех деталях. А такое "доказательство" теоремы 5 я вижу не только в обсуждаемой книге. Я такое же "доказательство" видел еще 20 лет назад, в раздобытом мной томе советской детской энциклопедии, посвященном математике. И помню, что тогда оно мне сильно не понравилось, прям сильно.

Еще буквально пару кульбитов и пойдем дальше.

-- 10.03.2021, 21:28 --

vpb в сообщении #1508404 писал(а):

Уже было, см. тему О биекции отрезка на квадрат.

Я там тоже не все понял, например, вот это или вот это. Но это сейчас и не так важно.

[mihaild]

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

[Sinoid]

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

Т.е. обозначив множество последовательностей за $\{0, 1\}^\omega$, мы строим биекцию по цепочке $[0, 1]^2 \leftrightarrow \left(\{0, 1\}^\omega\right)^2 \leftrightarrow \{0, 1\}^\omega \leftrightarrow [0, 1]$.
Вы же попытались биекцию $\left(\{0, 1\}^\omega\right)^2 \leftrightarrow \{0, 1\}^\omega$ непосредственно перенести на $[0, 1]^2 \leftrightarrow [0, 1]$, забыв как раз про технические детали.

Сейчас понял, что вы хотели сказать. Все, кульбитов не будет. Спасибо за разъяснение. С вашего разрешения я пойду дальше.

[arseniiv]

Можем ли мы сформулировать задачу seven trees in one в терминах, в которых Sinoid мог бы попробовать её решить? Надо ведь чтобы биекция была «структурной», а просто показать счётность обоих множеств слишком просто.

[Sinoid]

arseniiv в сообщении #1508597 писал(а):

в которых Sinoid мог бы попробовать её решить?

Стоп-стоп. А разве я ее еще не решил?

[arseniiv]

Не, это вполне определённая задача. Скажем так, у нас есть некоторые множества $T, A$ и биекция $f \colon T \to \{ \varnothing \} \cup A \times T^2$. Можно ли построить биекцию между $T$ и $T^7$ конструктивно, отталкиваясь от $f$? Где «конструктивно» означает, в частности, никаких других биекций без явного данного определения, кроме $f$, использовать нельзя, и никакой аксиомы выбора, то есть никакого $X \cong X \times X$ для бесконечных $X$. По идее эту формулировку должна немного спасать произвольность $A$ (оно может быть и пустым, и несчётным), но не особо.

[Sinoid]

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

[arseniiv]

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

-- Ср мар 10, 2021 23:26:29 --

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