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

[Someone]

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

Основная идея - доказать отдельно 2 случая - когда $B$ счетно, и когда $B$ несчетно.

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

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

Мысль такая: использовать задачу 13 и выделить из $B$ счетное подмножество $C$, затем показать равномощность $C$ и $A \cup C$, используя пункт 1) выше. Потом говорю что множество $B \setminus C$ бесконечно и несчетно (если бы оно было счетным, то $(B \setminus C) \cup C = B$ было бы счетным согласно зад.7. Еще надо будет показать почему оно не может быть конечным). И в конце, используя все вышеперечисленное, как-то вывести что $|B| = |(B \setminus C) \cup C| = |(B \setminus C) \cup (A \cup C)| = |B \cup A|$.

Хороший путь?

Не знаю, что Вы со всем этим делать собираетесь. Нужно ведь предъявить взаимно однозначное отображение $A\cup B\to B$.

[irod]

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

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

Лемма 14.1. Объединение конечного и счетного множеств счетно.

Утверждение верно, но Вы его не доказали (оборвали доказательство на полумысли).

Добавлю фразу:
Из существования пронумерованной последовательности элементов $A \cup B$ следует счетность $A \cup B$.
Подобные доказательства уже были в этом листке, и я думаю излишне морочиться с указанием конкретной биекции, и так ведь все понятно, как считаете?

Someone да, кажется я зря так усложняю.

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

Лемма 14.1. Объединение конечного и счетного множеств счетно.

Лемму 14.1 я оставляю.
Теперь доказательство основного утверждения.

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

14. Пусть $A$ конечно или счетно, а $B$ бесконечно. Доказать, что $|A \cup B| = |B|$.

Для удобства введем множество $A_{\overline{B}} = A \setminus B$. Очевидно, оно конечно или счетно.
Согласно зад.13 из множества $B$ можно выделить счетное подмножество $C$. Множество $A_{\overline{B}} \cup C$ счетно (по зад.7 в случае счетного $A_{\overline{B}}$, и по лемме 14.1 в случае конечного $A_{\overline{B}}$). Таким образом, $|A_{\overline{B}} \cup C| = |C|$. Обозначим соответствующую биекцию $f : A_{\overline{B}} \cup C \to C$.
Отметим, что $A \cup B = (A_{\overline{B}} \cup C) \sqcup (B \setminus C)$ и $B = C \sqcup (B \setminus C)$.
Построим биекцию $A \cup B \to B$ следующим образом:
\begin{equation*} x \mapsto \begin{cases} f(x), & \text{если}\ x \in A_{\overline{B}} \cup C \\ x, & \text{иначе, если}\ x \in B \setminus C \end{cases} \end{equation*}



Из существования такой биекции следует, что $|A \cup B| = |B|$.

[grizzly]

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

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

Вот чем закончилось Ваше рассуждение:

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

$$ \{ c_1,c_2,\ldots,c_n,b_1,b_2,\ldots \} = C \cup B = A \cup B. $$

Но ведь выписана не биекция! Нельзя оборвать просто на этом месте. Можете не выписывать явную формулу со сдвигом или другим вариантом, но скажите, хотя бы в конце: "откуда очевидным образом получаем нужную биекцию".

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

[irod]

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

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

Ок

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

Вы просто хотели сказать, что эти множества не пересекаются?)

Да.

-- 22.05.2016, 15:06 --

(Оффтоп)

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

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

Спасибо за совет
Я параллельно с Давидовичем читаю учебник Пантаева "Матанализ с человеческим лицом". Не уверен что он подходит под определение "полноценного учебника", но там все на пальцах объясняется, и мне он нравится. Я сначала решаю листок из Давидовича, и только потом читаю соответствующую главу из Пантаева. После Пантаева я собираюсь взяться за Зорича и/ли Рудина, как я уже писал.

[irod]

(Оффтоп)

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

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

А как это лучше написать? Я думал дизъюнктное объединение и означает пустое пересечение, нет?

-- 25.05.2016, 20:02 --

15. Множество точек отрезка равномощно множеству точек интервала.

Доказательство.
Рассмотрим отрезок и интервал одинаковой длины, не считая концов отрезка (согласно задачам 12.а, 12.б и 1.3, мы можем рассматривать отрезки и интервалы любой удобной нам длины). Пусть $B$ -- множество точек интервала, а $A$ -- множество из двух точек -- концов отрезка. Согласно зад. 12.д, интервал равномощен прямой, а множество точек прямой, очевидно, бесконечно $\Rightarrow$ множество $B$ бесконечно. Тогда по зад. 14, $|A \cup B| = |B|$, т.е. отрезок равномощен интервалу.

[grizzly]

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

А как это лучше написать?

Да просто словами -- "... есть объединение непересекающихся множеств ... и ...". Не следует злоупотреблять формулами, если не уверены в их содержании.

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

Я думал дизъюнктное объединение и означает пустое пересечение, нет?

Я в таком контексте его никогда не встречал. Вот Вам первый попавшийся пример из Вики:

Disjoint union of sets $A_0 = \{1, 2, 3\}$ and $A_1 = \{1, 2\}$ can be computed by finding:
$A^*_0 = \{(1, 0), (2, 0), (3, 0)\}$
$A^*_1 & = \{(1, 1), (2, 1)\}$
so
$A_0 \sqcup A_1 = A^*_0 \cup A^*_1 = \{(1, 0), (2, 0), (3, 0), (1, 1), (2, 1)\} $

Вряд ли Вы себе это так представляли.

-- 25.05.2016, 20:37 --

irod
В 15 всё правильно. Прямую можно было не привлекать -- бесконечность точек в интервале или на отрезке можно считать очевидным фактом (попробуйте, например, от противного -- делить пополам и выбирать ту часть отрезка, куда попало меньше половины точек; через несколько шагов сможем выделить объект неизвестной природы :)

[arseniiv]

Есть дизъюнктное объединение для любых семейств множеств — одним из недвусмысленных его названий будет tagged union. Но изредка, вроде, действительно, под ним понимается «прямое объединение», хотя проще о попарном непересечении интересующих множеств сказать явно. Или это я поддался словоупотреблению irod и тому, что есть дизъюнктное семейство множеств — в нём они как раз непересекающиеся попарно.

[grizzly]

arseniiv
Вопрос был в том, насколько уместно и понятно выглядит это место в доказательстве (2-е сообщение на этой странице) с применением " $\sqcup $ " в формулах:

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

Отметим, что $A \cup B = (A_{\overline{B}} \cup C) \sqcup (B \setminus C)$ и $B = C \sqcup (B \setminus C)$.

Я думаю, что такого значка в сколько-то похожем ТМ-контексте никогда не встречал. Ладно бы ещё то же словами сказать (употребление в таком смысле "дизъюнктного объединения" я встречал, но воспринимал как не совсем удачный жаргонизм) -- по крайней мере была бы понятна мысль, а за формулой поди знай, что там в голове.

[arseniiv]

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

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

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

[irod]

Перехожу к задачам со звездочкой. Начну с зад.17.
Использую рассуждения из своей первой попытки доказательства зад.14 с прошлой страницы.

17. Если $A$ несчетно, а $B$ счетно, то $A \setminus B$ равномощно $A$.

Доказательство.
Множество $A \setminus B$ не может быть счетным, т.к. иначе множество $(A \setminus B) \cup B = A$ было бы счетным согласно зад.7.
Множество $A \setminus B$ также не может быть конечным, т.к. иначе множество $(A \setminus B) \cup B = A$ было бы счетным по лемме 14.1.
Значит, множество $A \setminus B$ несчетно.

И вот тут у меня вопрос. Как я понимаю из несчетности обоих множеств - $A$ и $A \setminus B$ - вовсе не следует их равномощность, т.е. доказательство не законечно.
Верно?

[arseniiv]

Верно. Но, как вы уже доказали,

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

14. Пусть $A$ конечно или счетно, а $B$ бесконечно. Доказать, что $|A \cup B| = |B|$.

и это хорошо применимо к $(A\setminus B)\cup B$ здесь.

[irod]

arseniiv
Точно!
Блин, одного маленького шага не хватило

[irod]

Последняя оставшаяся задача в этом листке - задача 16.
Признаюсь, после нескольких дней ломания головы над ней я просто вспомнил прочитанную где-то когда-то идею доказательства - диагональный метод Кантора. Не уверен, что я бы сам до такого додумался. Идею я вспомнил, теперь постараюсь сам написать это строго.

16. Множество бесконечных последовательностей нулей и единиц несчетно.

Доказательство.
Очевидно, множество всех бесконечных строк из нулей и единиц бесконечно.

(Оффтоп)

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

Диагональный метод Кантора.
Пусть искомое множество счетно, и существует какая-то нумерация бесконечных строк нулей и единиц $A_1,A_2,A_3,\ldots$. Выпишем все строки по порядку одна под другой для наглядности:
$ A_1: \ a^1_1 a^1_2 a^1_3 a^1_4 \ldots $
$ A_2: \ a^2_1 a^2_2 a^2_3 a^2_4 \ldots $
$ A_3: \ a^3_1 a^3_2 a^3_3 a^3_4 \ldots $
$ \ldots $
Сформируем новую строку из нулей и единиц следующим образом. Берем первый элемент новой строки не равным первому элементу в $A_1$ (т.е. берем единицу при $a^1_1 = 0$ и берем ноль при $a^1_1 = 1$). Далее, второй элемент нашей строки берем не равным второму элементу в $A_2$, третий -- не равный третьему элементу в $A_3$ и т.д. Получаем бесконечную строку из нулей и единиц, не равную ни одному из $A_i$-х (из-за отличия, как минимум, диагональных элементов в выписанной выше таблице всех элементов), и таким образом отсутствующую в пронумерованной последовательности. Это противоречит исходному предположению о существовании такой пронумерованной последовательности. Следовательно, множество всех бесконечных строк из нулей и единиц несчетно.

[grizzly]

Да, всё хорошо.
Читая само доказательство, я споткнулся об этот момент:

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

существует какая-то нумерация бесконечных строк нулей и единиц $A_1,A_2,A_3,\ldots$. Выпишем все строки по порядку одна под другой для наглядности:
$ A_1: \ a^1_1 a^1_2 a^1_3 a^1_4 \ldots $

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

[irod]

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

Общая рекомендация: не вводите без особой необходимости новые сущности (см. бритва Оккама :)

Ок, я понял.

Итак, этот листок готов, и я перехожу к листку 6 про действительные числа.
Хочу в очередной раз сказать огромное спасибо grizzly и всем остальным, кто мне помогает на этом форуме: спасибо вам всем!