Аксиоматическая теория множеств

[Qlin]

Пусть $A$ является бесконечным множеством, и пусть $M$ является множеством всех его подмножеств $x$ заданной мощности: каждое $x$ имеет натуральную мощность $m$. Как доказать, что $M$ непусто ?

В наивной теории множеств вроде всё просто: сначала надо выбрать элемент $a_1$, затем выбрать элемент из оставшихся, затем продолжать этот процесс, пока не получим $x=\{a_1, \ldots, a_m \}$. Поскольку $x \in M$, то $M \neq \varnothing$.

А как получить этот результат в аксиоматической теории множеств ?

[Xaositect]

Аксиомой выделения из множества всех подмножеств.

[Someone]

Ну как…
$A\neq\varnothing$, потому что бесконечно, поэтому существует элемент $x_1\in A$.
Рассмотрим $A_1=A\setminus\{x_1\}$. $A_1\neq\varnothing$, так как в противном случае $A=\{x_1\}$ является конечным, поэтому…

А чего Вы испугались?

[xagiwo]

Точно так же? Показать, что такая последовательность $a : \{1,2,…,m\} \to A$ существует и взять за $x$ её образ

[Qlin]

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

Аксиомой выделения из множества всех подмножеств.

А почему не выделится пустое множество ?

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

А чего Вы испугались?

Мощности $m$. Для случая $m=1$ вы доказали теорему, а для произвольного $m$ нужна видимо какая-то индукция ?

[Someone]

Qlin в сообщении #1525003 писал(а):

Мощности $m$. Для случая $m=1$ вы доказали теорему, а для произвольного $m$ нужна видимо какая-то индукция ?

Ну, у Вас ведь число $m$ задано? Тогда просто $m$ раз выбираете по одному элементу.

А если нужно доказать "для каждого натурального $m$…", то без аксиомы выбора это недоказуемо. Из-за возможности бесконечных множеств, "конечных" по Дедекинду. Тут возникает парадоксальная ситуация, когда мы можем доказать утверждение отдельно для каждого натурального $m$, но не можем доказать его сразу для всех натуральных $m$.

[xagiwo]

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

без аксиомы выбора это недоказуемо

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

[Someone]

xagiwo в сообщении #1525017 писал(а):

Вроде хватает аксиомы выбора для конечных семейств множеств, которая доказывается в ZF?

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

xagiwo в сообщении #1525017 писал(а):

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

А вот рассуждения по индукции аксиому выбора используют.

К. Куратовский, А. Мостовский. Теория множеств. "Мир", Москва, 1970.
В главе III, § 2, рассмотрены различные схемы определений по индукции. В применении к задаче из данной темы Вам понадобится функция выбора для семейства $\{A\setminus M: M\text{ конечно}\}$.

[xagiwo]

Понял, спасибо. Извините, что влез.

[Qlin]

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

рассуждения по индукции аксиому выбора используют

Пусть множество $M$ содержит элемент $x$. Множество $A\setminus x$ является бесконечным, следовательно $\exists a' \in A\setminus x \ \ \exists A' \ \ (a'\in A' \land \forall a \ \ (a\in A' \longrightarrow a=a')) $
Обозначим выражение в скобках через $\varphi (a',A')$, тогда
$\exists a' \in A\setminus x \ \ \exists A' \ \ \exists x' \ \ (\varphi (a',A') \land x'=x \cup A') $
Разве где-то в этом индуктивном переходе нужна аксиома выбора ?

[xagiwo]

А, стоп. Определений по индукции вроде и не надо, достаточно принципа математической индукции (любое индуктивное множество — надмножество $\mathbb N$)
Доказывается, что есть инъекция $a: \{0,1,…, m-1\} \to A$ для $m = 0$ (здесь не надо аксиомы выбора) и доказывается, что если есть инъекция $f: \{0,1,…,m_0-1\} \to A$, то есть инъекция $g: \{0, 1, …, m_0\} \to A$: есть какое-то $t \in A \setminus f\{0,1,…,m_0-1\}$ (функция, выбирающая такие $t$, нам не нужна) и достаточно взять $g = f \cup \{(m_0, t)\}$. То есть множество всех $m$, для которых такая инъекция есть, индуктивно.

[Someone]

Qlin в сообщении #1525054 писал(а):

Разве где-то в этом индуктивном переходе нужна аксиома выбора ?

В этом переходе — не нужна. И в следующем не нужна. И в $4^{4^{4^4}}$-м не нужна. Но у Вас получается бесконечно длинное рассуждение, которое Вы никогда не закончите и, следовательно, требуемое утверждение никогда не докажете.

xagiwo в сообщении #1525064 писал(а):

есть какое-то $t \in A \setminus f\{0,1,…,m_0-1\}$ (функция, выбирающая такие $t$, нам не нужна)

Обратите внимание на предыдущее замечание. И укажите, пожалуйста, аксиомы теории множеств (ZFC, например), из которых следует, что совокупность выбранных таким образом элементов является множеством.

xagiwo в сообщении #1525064 писал(а):

Определений по индукции вроде и не надо, достаточно принципа математической индукции

Это, в общем-то, одно и то же. В одном случае Вы доказываете последовательность утверждений $P(n)$, параметризованную натуральными числами, а в другом случае Вы доказываете существование функции, доказывая аналогичную последовательность утверждений о значениях этой функции. В обоих случаях последовательность утверждений выглядит как некоторая формула с параметром.

[xagiwo]

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

И укажите, пожалуйста, аксиомы теории множеств (ZFC, например), из которых следует, что совокупность выбранных таким образом элементов является множеством.

Каких элементов? Различных $t$ при всех возможных $m_0$? Такое множество в доказательстве и не используется. Шаг индукции выглядит как $\forall m_0 \in \mathbb N\quad (\exists f: m_0 \to A)\rightarrow (\exists g: m_0+1 \to A)$ (здесь $f$ и $g$ — инъекции, я это пропустил, потому что в формуле некрасиво выглядит) . Мы имеем $\forall m_0 \in \mathbb N\quad \forall f\quad \exists t\quad t \in A \setminus f\{0, 1, …, m_0-1\}$ и из этого доказываем шаг индукции.

[Qlin]

Someone, возможно вы имеете в виду следующее:
https://ru.wikipedia.org/wiki/%D0%A2%D1 ... 0%B8%D1%8F

Цитата:

Математическая индукция является частным случаем трансфинитной индукции.

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

Аксиома выбора нужна, чтобы доказать, что обычную индукцию можно из арифметики перенести в ZFC. Но зачем она нужна для решения исходной задачи ? Есть база индукции, есть индуктивный переход, есть обычная схема аксиом индукции. Вроде всё получается?

[Someone]

Qlin в сообщении #1525083 писал(а):

Аксиома выбора нужна, чтобы доказать, что обычную индукцию можно из арифметики перенести в ZFC.

Совершенно не нужна. Загляните в главу III книжки Куратовского и Мостовского. Там все утверждения, для доказательства которых требуется аксиома выбора, отмечены значком "$^\circ$". Схемам индукции в арифметике посвящён § 2. Найдите там этот значок.

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

Аксиома выбора в обсуждаемой задаче нужна совсем в другом месте.

Ответ на ваш первоначальный вопрос я формулировал. Повторюсь.
1) Если задано конкретное натуральное $m$, то повторяете рассуждение с выбором одного элемента $m$ раз. Аксиома выбора не нужна.
2) Если нужно доказать утверждение для всех натуральных $m$, то предыдущее рассуждение не может закончиться, поэтому ничего не доказывает. Поэтому нужно использовать одну из схем индукции. Для использования схемы индукции требуется функция, выбирающая элементы из множеств, входящих в некоторое бесконечное семейство. Существование такой функции либо нужно доказать, используя свойства конкретного множества $A$, либо оно (существование) следует из аксиомы выбора, если $A$ — "абстрактное" множество, как в вашей задаче,