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

[Someone]

(Оффтоп)

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

А мы и осуществляем его лишь конечное к-во раз. Собственно, ровно один раз. На каждом шаге.

А шагов у нас бесконечно много. Занумерованных всеми натуральными числами.

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

Там же нет никакого наперёд заданного набора множеств. Пусть даже и счётного. Из которого следовало бы выбирать.

Собственно, на первом шаге выбираем $x_1\in A$, на втором — $x_2\in A\setminus\{x_1\}$, на третьем — $x_3\in A\setminus\{x_1,x_2\}$, …, на $k$-м — $x_k\in A\setminus\{x_1,x_2,\ldots,x_{k-1}\}$, …

Xaositect в сообщении #1124440 писал(а):

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

Э-э-э… Я не знаю, что такое "экспоненты" и "однородный выбор". Зато я знаю, что без аксиомы выбора теория ZF имеет модели, в которых существуют множества, конечные по Дедекинду.
Множество называется конечным по Дедекинду, если оно бесконечно (в том смысле, что не равномощно никакому натуральному числу), но не равномощно никакому собственному подмножеству.
Такое множество обладает странным свойством: из него можно выбрать любое конечное число попарно различных элементов, но нельзя выбрать бесконечную последовательность попарно различных элементов.

P.S. Мне в своё время пришлось приложить определённые усилия, чтобы научиться распознавать применение аксиомы выбора.

[ewert]

(Оффтоп)

Someone в сообщении #1124454 писал(а):

Собственно, на первом шаге выбираем $x_1\in A$, на втором — $x_2\in A\setminus\{x_1\}$, на третьем — $x_3\in A\setminus\{x_1,x_2\}$, …, на $k$-м — $x_k\in A\setminus\{x_1,x_2,\ldots,x_{k-1}\}$, …

Ну и что тут задано наперёд?...

Someone в [url=http://dxdy.ru/post1124454.html#p1124454]сообщении #1124454[читал:/url] писал(а):

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

Я в своё время тоже много читал: и "Степного волка", и "Игру в бисер". Первого осознал (там как-то), второго же не осилил решительно. За откровенной ненадобностью.

[Someone]

(Оффтоп)

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

Ну и что тут задано наперёд?...

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

Пусть $A$ -- бесконечное множество. Берем произвольный элемент из $A$ и присваиваем ему номер 1, за ним берем другой произвольный элемент из $A$ и присваиваем ему номер 2 и т.д., на $i$-м шаге присваиваем произвольному ранее не пронумерованному элементу из $A$ номер $i$.

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

За откровенной ненадобностью.

Это не означает, что всем остальным требуется то же, что и Вам.

[NSKuber]

Someone

(Оффтоп)

Аксиома выбора позволяет нам, имея семейство множеств, выбрать из каждого из них по одному элементу. Предъявите, пожалуйста, это самое семейство множеств (подмножеств $A$), к которому, по-вашему, применяется аксиома выбора в доказательстве irod.

[grizzly]

NSKuber

(Оффтоп)

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

[ewert]

(Оффтоп)

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

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

На каждом шаге д-ва производится выбор из 1 (одного) подмножества. И даже не подмножества, а просто множества. А один -- это всё-таки меньше бесконечности. Пусть и совсем не намного, но меньше.

[grizzly]

(Оффтоп)

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

На каждом шаге д-ва производится выбор из 1 (одного) подмножества. И даже не подмножества, а просто множества. А один -- это всё-таки меньше бесконечности. Пусть и совсем не намного, но меньше.

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

[NSKuber]

(Оффтоп)

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

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

Вот это хороший аргумент, спасибо, теперь верится.

[arseniiv]

(Оффтоп)

Аж стало интересно, какие у этого доказательства есть формализации (вдруг утверждение разбито на несколько) в Metamath.

[Xaositect]

Someone

(Оффтоп)

Someone в сообщении #1124454 писал(а):

Э-э-э… Я не знаю, что такое "экспоненты" и "однородный выбор". Зато я знаю, что без аксиомы выбора теория ZF имеет модели, в которых существуют множества, конечные по Дедекинду.
Множество называется конечным по Дедекинду
, если оно бесконечно (в том смысле, что не равномощно никакому натуральному числу), но не равномощно никакому собственному подмножеству.
Такое множество обладает странным свойством: из него можно выбрать любое конечное число попарно различных элементов, но нельзя выбрать бесконечную последовательность попарно различных элементов.

Да, Вы правы.

[RIP]

(Оффтоп)

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

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

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

На каждом шаге д-ва производится выбор из 1 (одного) подмножества. И даже не подмножества, а просто множества. А один -- это всё-таки меньше бесконечности. Пусть и совсем не намного, но меньше.

Таким образом получится доказать, что $A$ имеет сколь угодно большое конечное подмножество. Но требуется совсем не это. Для того, чтобы доказать существование бесконечного (счётного) подмножества, исходя только из аксиом теории множеств (пусть даже и ZFC), нужно повозиться.
Например, можно воспользоваться такой теоремой (не очень сложной, но и не тривиальной): Для любого множества $A$ и любой функции $g\colon\operatorname{Seq}(A)\to A$ (где $\operatorname{Seq}(A)=\cup_{n\in\mathbb{N}}A^{n}$ — множество всех конечных последовательностей на $A$) существует единственная такая последовательность $f\colon\mathbb{N}\to A$, что $f_{n}=g\bigl(\langle f_{0},\dotsc,f_{n-1}\rangle\bigr)$ для всех $n\in\mathbb{N}$.
Эта теорема формализует следующее рассуждение: берём $f_{0}=g(\varnothing)$, $f_{1}=g\bigl(\langle f_{0}\rangle\bigr)$, $f_{2}=g\bigl(\langle f_{0},f_{1}\rangle\bigr)$ и т.д. Дело в том, что нету такой аксиомы, которая позволяет говорить "и т.д."
Теорему можно применить следующим образом. Пусть $g$ — какая-то функция, такая что $g\bigl(\langle x_{0},\dotsc,x_{n-1}\rangle\bigr)\in A\setminus\{x_0,\dotsc,x_{n-1}\}$. Тогда множество $\{f_{n}\mid n\in\mathbb{N}\}$ — искомое счётное подмножество. Аксиома выбора (причём, полная версия, по-видимому) тут нужна для доказательства существования функции $g$. Наверное, можно как-то исхитриться, чтобы хватило лишь счётной аксиомы выбора.

[grizzly]

(Оффтоп)

RIP в сообщении #1124553 писал(а):

Наверное, можно как-то исхитриться, чтобы хватило лишь счётной аксиомы выбора.

UPD (зачёркнуто после сообщения ниже). Это вряд ли. Это означало бы как минимум, что мы где-то используем счётное семейство множеств, из которых осуществляется выбор. Но не похоже, что задача предъявить это счётное семейство чем-то проще изначальной задачи. (Зря я помянул выше СчАВ, пусть и с другой целью.)
P.S. Спасибо за понятные подробности.

[RIP]

(Оффтоп)

Кстати, в английской Вике показано, как доказать существование счётного подмножества, используя только счётный выбор.
https://en.wikipedia.org/wiki/Axiom_of_countable_choice
P.S. Только определение множеств $C_{n}$ там плохое, ибо существование такой последовательности требует доказательства, например, через теорему о рекурсии из моего предыдущего сообщения. Гораздо проще и естественнее положить $C_{n}=B_{n}\setminus\cup_{j<n}B_{j}$. Разумеется, получаются те же самые множества, но тут определение явное, без рекурсии.

[irod]

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

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

Ок.

-- 21.05.2016, 14:42 --

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

Полностью эту задачу я пока не сделал, но есть некоторые мысли. Дайте пожалуйста подсказку, в правильную ли сторону я иду.
Итак. Основная идея - доказать отдельно 2 случая - когда $B$ счетно, и когда $B$ несчетно.

Сначала докажем вспомогательное утверждение (лемму).

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

Доказательство леммы 14.1.
Пусть $A$ конечно, а $B$ счетно.
Выкинем из $A$ все элементы, которые встречаются в $B$ и обозначим оставшиеся в $A$ элементы как множество $C = A \setminus B$. Очевидно, множество $C$ конечно.
Составим пронумерованную последовательность из объединения последовательностей $\{ c_1,c_2,\ldots,c_n \} = C$ и $\{ b_1,b_2,\ldots \} = B$:

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

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

1) Пусть $B$ счетно.
а) Если $A$ счетно, то согласно зад.7 множество $A \cup B$ счетно $\Rightarrow$ $|A \cup B| = |B|$.
б) Если $A$ конечно, то множество $A \cup B$ счетно по лемме 14.1 $\Rightarrow$ $|A \cup B| = |B|$.

2) Пусть $B$ несчетно.
Вот этот пункт у меня пока не выходит. Вообще здесь мне впервые приходится работать с несчетным множеством. Мысль такая: использовать задачу 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|$.

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

-- 21.05.2016, 15:02 --

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

Таким образом Вы устанавливаете пока что всего лишь инъекцию с полуокружности.

А чем это принципиально отличается от предложенного grizzly:

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

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

Можете объяснить подробнее?

[grizzly]

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

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

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

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

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

Да, этим путём можно прийти к цели.

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

Можете объяснить подробнее?

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

(Оффтоп)

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