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

[irod]

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

Но дальше-то вы нигде бесконечность не использовали!

Почему же не использовал? Вот здесь использовал, не проговаривая это явно:

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

Т.к. $\forall b \in B: \ b \in A$, то существует биекция между $B$ и некоторыми натуральными числами: $b_n = a_{k_n} \overset{f}\mapsto k_n$, где $k_n \in \mathbb{N}$, $n = 1,2,\ldots$

Допустим самый простой случай: $B = A$, т.е. $B$ бесконечно (и счетно). Тогда $g$ будет тождественным отображением. Мое доказательство прекрасно отрабатывает этот частный случай с бесконечным $B$, разве не так?

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

То есть, если это доказательство, мы можем выкинуть «пусть $B$ не конечно» и получить тоже доказательство. Уже неверного факта, ну и это было бы не очень хорошо.

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

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

Предположим, что $B$ здесь может быть любым. Тогда все функции здесь определяются нормально, но $g$ не будет биекцией, а оттого и $g\circ f$. Т. е. надо доказать, что если $B$ бесконечно, $g$ биективна, и тогда доказательство спасено. Или это можно включить в круг очевидных вещей.

По-моему из моих рассуждений следует, что $g$ - это таки биекция, а значит после всех рассуждений $B$ не может быть любым, а может быть только счетным. Возможно, я плохо объяснил, почему $g$ должна обязательно быть биекцией? Я тогда подумаю как переписать это кусок. Но какая тут связь с конечностью/бесконечностью $B$ я пока не могу уловить.

[arseniiv]

Ну, например, $B$ могло бы быть бесконечным, но не счётным.

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

Допустим самый простой случай: $B = A$, т.е. $B$ бесконечно (и счетно). Тогда $g$ будет тождественным отображением. Мое доказательство прекрасно отрабатывает этот частный случай с бесконечным $B$, разве не так?

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

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

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

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

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

Возможно, я плохо объяснил, почему $g$ должна обязательно быть биекцией?

Не стану говорить от имени больше чем себя, а от своего ответить тоже не могу, потому что не знаю, насколько это соответствует уровню вашего источника.

-- Вт апр 19, 2016 16:24:16 --

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

Но какая тут связь с конечностью/бесконечностью $B$ я пока не могу уловить.

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

[grizzly]

(Оффтоп)

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

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

Доказательство. Пусть $A$ - счетное множество с биекцией $a_n \overset{f}\mapsto n$, где $a_n \in A$, $n = 1,2,\ldots$ Выделим из $A$ произвольное подмножество $B \subset A$. Пусть $B$ не конечно (иначе доказательство окончено). Т.к. $\forall b \in B: \ b \in A$, то существует биекция между $B$ и некоторыми натуральными числами: $b_n = a_{k_n} \overset{f}\mapsto k_n$, где $k_n \in \mathbb{N}$, $n = 1,2,\ldots$ Расставим эти натуральные числа по порядку и перенумеруем их:
$k_n \overset{g}\mapsto n$. Получили биекцию $b_n \overset{g \circ f}\mapsto n$.

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

Начну с мелочей. Насколько я понимаю формулировки ТС, во всех случаях, когда требуется обозначить последовательность, ТС подразумевает биекцию типа $f(a_n)=n$. В случае, когда речь идёт о заранее заданной последовательности, это можно оправдать (последовательность задана -- в какую сторону мы направим стрелку, неважно). Когда же речь идёт о необходимости задать новую последовательность, возникает эффект порочного круга, имхо (сама запись $f(a_n)$ в формуле $f(a_n)=n$ подразумевает (не)явно, что соответствие уже задано -- ещё до того, как мы доказали / проверили существование биекции). Когда же дело доходит до суперпозиции этих тонкостей, пропадает всякое желание отслеживать корректность окончательных формулировок :)

Теперь о главном.
Само утверждение задачи также не раскрыто и заменено другим утверждением:

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

Т.к. $\forall b \in B: \ b \in A$, то существует биекция между $B$ и некоторыми натуральными числами

Предложенный переход "так как, ... то ..." не является собственно рассуждением, а только маскирует его. Под таким переходом можно спрятать и совсем неправильное подробности типа "Расположим элементы $B$ (в случае подмножества рациональных чисел) в порядке возрастания, возьмём первый элемент и найдём его индекс среди $a_n$ и т.д.".

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

[irod]

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

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

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

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

5. Доказать, что всякое подмножество счетного множества конечно или счетно.

Пусть $B$ -- подмножество счетного множества $A$. По условию, существует биекция $f : \mathbb{N} \to A$ такая что $f(n) = a_n$. Расставим все элементы $A$ по возрастанию натуральных чисел, которым они соответствуют при отображении $f$, получив последовательность $\{ a_1, a_2, \ldots \}$, где $f(i) = a_i$, $i = 1,2,\ldots$. Выбросим из $\{ a_1, a_2, \ldots \}$ все элементы, которые не принадлежат $B$ (т.е. все элементы $A \setminus B$), сохраняя порядок оставшихся. Пошаговая процедура при этом следующая. Рассмотрим $a_1$: если он принадлежит $B$ присвоим ему номер (индекс) $1$ в новой нумерации $a_{k_1}$ иначе переходим к $a_2$ и т.д. Находя каждый следующий ($i$-й) элемент $B$, мы будем присваивать ему очередной индекс в новой нумерации -- $a_{k_i}$. Если после какого-то шага все элементы $B$ окажутся пронумерованы в новой нумерации, значит $B$ конечно. Иначе мы получим бесконечную подпоследовательность $\{ a_{k_1}, a_{k_2}, \ldots \}$, состоящую из всех элементов $B$ и только из них. Все члены этой новой последовательности пронумерованы, и мы можем обозначить биекцию $g : \mathbb{N} \to B$ такую что $g(k_i) = a_{k_i}$, где $k_i = i$, $i = 1,2,\ldots$. Это будет означать счетность $B$ по определению.

[grizzly]

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

мы можем обозначить биекцию $g : \mathbb{N} \to B$ такую что $g(k_i) = a_{k_i}$, где $k_i = i$, $i = 1,2,\ldots$.

Здесь какая-то ошибка. Вместо последней формулы должно быть просто $g(i)=(a_{k_i})=b_i, i=1,2,...$ -- это и было бы "по определению". А вообще такая идея решения меня бы уже убедила (раз уж я сам так посоветовал :)

-- 24.04.2016, 01:50 --

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

получим бесконечную подпоследовательность $\{ a_{k_1}, a_{k_2}, \ldots \}$, состоящую из всех элементов $B$

Ответьте, пожалуйста, Вы можете коротко / чётко доказать, что в эту последовательность попали все элементы $B$? (можно не доказывать, интересует степень Вашей уверенности.)

[irod]

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

Здесь какая-то ошибка. Вместо последней формулы должно быть просто $g(i)=(a_{k_i})=b_i, i=1,2,...$ -- это и было бы "по определению".

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

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

Ответьте, пожалуйста, Вы можете коротко / чётко доказать, что в эту последовательность попали все элементы $B$? (можно не доказывать, интересует степень Вашей уверенности.)

Не знаю насколько это будет коротко / четко, но попробую доказать. Изначально у нас последовательность только из элементов $A$. Затем мы выкидываем из нее все элементы $A \setminus B$:

$$A \setminus (A \setminus B) = $$ $$ \{ x \mid x \in A \land x \not\in \{ y \mid y \in A \land y \not\in B \} \} = $$ $$ \{ x \mid x \in A \land x \in \{ y \mid y \not\in A \lor y \in B \} \} = $$ $$ \{ x \mid x \in A \land (x \not\in A \lor x \in B) \} = $$ $$ \{ x \mid x \in A \land x \in B \} = $$ $$ \{ x \mid x \in B \} = B.$$

Предпоследнее равенство следует из того, что $\forall b \in B: \ b \in A$.

[grizzly]

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

Не знаю насколько это будет коротко / четко, но попробую доказать.
...

Это да. Но вопрос был в другом: доказать, что после полного выполнения описанной Вами процедуры любой элемент $b\in B$ получит некий номер $k_i$. Это нужно, чтобы убедиться в корректности выбранной процедуры для получения множества $A\setminus (A\setminus B)$.

[irod]

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

Это да. Но вопрос был в другом: доказать, что после полного выполнения описанной Вами процедуры любой элемент $b\in B$ получит некий номер $k_i$. Это нужно, чтобы убедиться в корректности выбранной процедуры для получения множества $A\setminus (A\setminus B)$.

1) все элементы $B$ принадлежат исходной последовательности $\{ a_1, a_2, \ldots \}$;
2) процедура перебирает все элементы из $\{ a_1, a_2, \ldots \}$, в том числе все входящие в эту последовательность элементы из $B$;
3) каждый обработанный процедурой элемент множества $B$ из $\{ a_1, a_2, \ldots \}$ получает свой номер.
Из 1),2),3) следует что любой элемент $b\in B$ получит некий номер.

[grizzly]

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

Пусть $A=\mathbb Q$ -- множество рациональных чисел. Пусть $B=\{1,1/2,1/4,1/8,...\}$. Выполняем Шаг за Шагом следующую процедуру:

1. $i:=1, j:=1$;
2. Шаг № $i$:

a. Выберем произвольный элемент $p\in A$;
b. Если $p\in B$, присвоим ему номер $j$ (то есть $b_j:=p$); $j:=j+1$
c. $A:=A\setminus \{p\}$ (удалили элемент из $A$).

3. $i:=i+1$
4. GOTO 2.

Вопрос тот же: будут ли после выполнения всех шагов (Шаг 1, Шаг 2, ...) пронумерованы все элементы множества $B$?

[irod]

(Оффтоп)

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

Я Вам (как программисту) опишу похожую процедуру псевдокодом.

Я как раз в следующих задачах этого листка планировал описывать подобные процедуры нумерации псевдокодом. Вы меня опередили

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

Вот другой пример.
...
Вопрос тот же: будут ли после выполнения всех шагов (Шаг 1, Шаг 2, ...) пронумерованы все элементы множества $B$?

Полагаю что нет, в Вашем примере все элементы $B$ не обязательно будут пронумерованы. Проблема в этой строке:

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

a. Выберем произвольный элемент $p\in A$;

а конкретно в слове "произвольный". Можно ведь "произвольно" выбирать рац.числа все время только из интервала $(1/2,1)$, их там бесконечное количество, и в итоге ни один элемент из $B$ никогда так и не будет пронумерован.
Если я правильно Вас понял, то мне надо дополнить свое доказательство выше следующим образом:
процедура перебирает все элементы из $\{ a_1, a_2, \ldots \}$ последовательно без пропусков, начиная с $a_1$, следовательно ни один элемент из $B$ не будет пропущен и рано или поздно будет пронумерован.
Верно?

[grizzly]

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

Полагаю что нет, в Вашем примере все элементы $B$ не обязательно будут пронумерованы. Проблема в этой строке:
...

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

(Нужно доказать, что любой элемент из $B$ будет пронумерован).
Выберем произвольный элемент $b\in B$. Тогда $b\in A = \{a_1,a_2,...\}$. То есть, для некоторого $k\in \mathbb N$ выполнено $b=a_k$. Но наша процедура гарантирует, что элемент $a_k$ будет рассмотрен через $k$ шагов и, следовательно, выбранный элемент $b$ будет пронумерован через $k$ шагов.

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

[irod]

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

[irod]

6. Доказать, что если $X$ счетно, а $Y$ конечно и непусто, то $X \times Y$ счетно.

Доказательство.
Пусть $n \in \mathbb{N}$ и пусть $f : \mathbb{N} \to X$, $g : \{ 1,2,\ldots,n \} \to Y$ -- биекции. Расставим элементы из $X$ и $Y$ по порядку, получив соответствующие последовательности $\{ x_1,x_2,\ldots \}$, $\{ y_1,y_2,\ldots,y_n \}$, где $f(i) = x_i$, $g(j) = y_j$, $i \in \mathbb{N}$, $j = 1,2,\ldots,n$.
Построим пронумерованную последовательность (в псевдокоде ниже она обозначена как $A$) из элементов $X \times Y$ с помощью следующей процедуры:

1. $i:=1$, $k:=1$, $A:=\text{пустая последовательность}$;
2. Цикл по $i$:
3. $j:=1$;
4. Пока $j \leq n$:
5. Добавляем пару $(x_i,y_j)$ в $A$ под номером $k$;
6. $k:=k+1$;
7. $j:=j+1$;
8. Конец цикла по $j$;
9. $i:=i+1$;
10.Конец цикла по $i$;

В итоге последовательность $A$ будет иметь вид:

$$A = \{ (x_1,y_1), (x_1,y_2), \ldots, (x_1,y_n), (x_2,y_1), (x_2,y_2), \ldots, (x_2,y_n), \ldots \}.$$

Покажем, что в процессе этой процедуры любой элемент $X \times Y$ будет пронумерован (т.е. окажется в $A$).
Выберем произвольный элемент $a \in X \times Y$. Тогда $a = (x_i,y_j)$ для какого-то $i \in \mathbb{N}$, $j \in [1,2,\ldots,n]$, где $x_i \in X = \{ x_1,x_2,\ldots \}$, $y_j \in Y = \{ y_1,y_2,\ldots,y_n \}$. Согласно нашей процедуре, пара $(x_i,y_j)$ гарантированно получит номер $k$ в последовательности $A$ через $k = n(i-1) + j$ шагов.
Из существования пронумерованной последовательности, состоящей из всех элементов $X \times Y$, следует счетность $X \times Y$.

-- 26.04.2016, 18:38 --

(Оффтоп)

Прошу прощения за такое оформление псевдокода, без отступов, пока не разобрался как в Latex красивый псевдокод делать.

-- 26.04.2016, 19:18 --

Подумал я еще, и понял что можно все это записать гораздо проще и короче.

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

6. Доказать, что если $X$ счетно, а $Y$ конечно и непусто, то $X \times Y$ счетно.

Новый вариант доказательства.
Аналогично предыдущей задаче (№5), расставим элементы из $X$ и из $Y$ по порядку, получив соответствующие последовательности $\{ x_1,x_2,\ldots \}$ и $\{ y_1,y_2,\ldots,y_n \}$, где $n \in \mathbb{N}$.
Построим пронумерованную последовательность из элементов $X \times Y$, в которой произвольная пара $(x_i,y_j)$ из элементов $x_i \in X = \{ x_1,x_2,\ldots \}$, $i \in \mathbb{N}$ и $y_j \in Y = \{ y_1,y_2,\ldots,y_n \}$, $j \in [1,2,\ldots,n]$, будет стоять на месте с номером $k = n(i-1) + j$.
Эта последовательность будет иметь вид:

$$\{ (x_1,y_1), (x_1,y_2), \ldots, (x_1,y_n), (x_2,y_1), (x_2,y_2), \ldots, (x_2,y_n), \ldots \}.$$

Из существования пронумерованной последовательности, состоящей из всех элементов $X \times Y$, следует счетность $X \times Y$.

[grizzly]

irod
Всё нормально и с первым и со вторым способом. Обычно принято вместо псевдокода рисовать табличку и показывать стрелками порядок нумерации. Но это только выбор наглядности -- не принципиально, как её оформить, лишь бы правильно / понятно (на экзамене было бы уместно нарисовать табличку, на LaTeX'е -- дать алгоритм или описание).

Чтобы решение обрело завершённость, не помешало бы в конце выписать биекцию в явном виде (просто $f(x_i,y_j)=n(i-1)+j$). Обратите внимание на два момента:
(а) здесь уже нет той проблемы "в какую сторону направлены стрелки" -- можно строить в любую сторону;
(б) Вы доказали, что каждому элементу будет присвоен номер. Но в правилах хорошего тона было бы ещё упомянуть, что все элементы получат разные номера. В данном случае можно сослаться на очевидность -- вряд ли кто-то будет спорить. Но иногда это не очевидно.

Отступ можно сделать с помощью тега "List".

[irod]

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

irod
Всё нормально и с первым и со вторым способом. Обычно принято вместо псевдокода рисовать табличку и показывать стрелками порядок нумерации. Но это только выбор наглядности -- не принципиально, как её оформить, лишь бы правильно / понятно (на экзамене было бы уместно нарисовать табличку, на LaTeX'е -- дать алгоритм или описание).

А не дадите ссылку на подобную табличку? Хотелось бы взглянуть. А то гугл выдает всякий мусор.
Я уже сделал все вплоть до 10 задачи, думаю теперь как красивее оформить алгоритмы в своих доказательствах. Уже столько времени пишу код, что совсем забыл как алгоритмы без кода оформлять
Вообще мои доказательства задач 5-10 этого листка (а может и следующих задач) очень похожи, у них одинаковая структура. Все они начинаются с того что мы берем упорядоченные последовательности из элементов исходных множеств и с помощью какого-то алгоритма составляем пронумерованную последовательность элементов искомого множества (счетность которого надо доказать). Т.е. различие между этими задачами только в алгоритме построения пронумерованной последовательности - именно он и является главной целью этих задач, я полагаю.
Вот эта часть во всех доказательствах 5-10:

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

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

будет одинаковой (кроме формулы биекции).