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

[mihaild]

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

Найдите там этот значок

Открыл издание 1970 года, не нашел в этом параграфе этого значка вообще (или на это и был намек?).
На всякий случай - вы же говорите, что утверждение $\forall A[ (\forall n: |A| \neq n) \rightarrow (\forall m \exists f: m \to A (f - \text{инъекция}))]$ требует аксиомы выбора?

[Qlin]

Someone, тогда я не понимаю, в чём проблема.
Вы доказали случай $m=1$:

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

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

Я построил индуктивный переход от случая $m$ к $m+1$. Значит, если у бесконечного множества есть подмножество мощности $m$, то существует подмножество мощности $m+1$:

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

Пусть множество $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') $

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

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

Значит я где-то что-то пропустил в доказательстве ? Хотелось бы знать где именно и что именно.

[Someone]

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

Открыл издание 1970 года, не нашел в этом параграфе этого значка вообще (или на это и был намек?).

Ага. Этот значок в главе III впервые появляется в § 4, где сформулирована и доказана теорема 13, помеченная этим значком. Удивительным образом утверждение теоремы 13 совпадает с тем, что сформулировал Qlin в стартовом сообщении. Схемы индукции по натуральным числам доказываются в § 2 без использования аксиомы выбора. Трансфинитная индукция (по ординалам) рассматривается в главе VII, обосновывается без аксиомы выбора и не используется в главе III.

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

вы же говорите, что утверждение $\forall A[ (\forall n: |A| \neq n) \rightarrow (\forall m \exists f: m \to A (f - \text{инъекция}))]$ требует аксиомы выбора?

Строго говоря, это зависит от множества $A$. Оно может быть таким, что можно определить функцию выбора на семействе его непустых подмножеств, не используя аксиому выбора. Но если это абстрактное множество, о котором ничего не известно, кроме того, что оно не равномощно никакому отрезку натурального ряда вида $[0,n-1]$, $n\geqslant 0$, то без аксиомы выбора не обойтись.

Исторически было два определения бесконечного множества: общепринятое (множество бесконечно, если оно не равномощно никакому натуральному числу) и определение Дедекинда (множество бесконечно, если оно содержит подмножество, равномощное натуральному ряду; эквивалентная формулировка: множество бесконечно если оно равномощно своему собственному (не совпадающему с ним самим) подмножеству). Если выполняется аксиома выбора, то оба определения (традиционное и Дедекинда) равносильны, а без аксиомы выбора могут появляться весьма странные множества. Например, бесконечные множества, конечные по Дедекинду. В таком множестве можно определить сколь угодно длинную последовательность попарно различных элементов, но нельзя определить бесконечную последовательность.

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

Значит я где-то что-то пропустил в доказательстве ? Хотелось бы знать где именно и что именно.

Пропустили Вы вообще всё доказательство. Вы же не записали своё рассуждение в виде одной из схем индукции.

[Qlin]

Someone, а как правильно доказать эту теорему?

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

Пропустили Вы вообще всё доказательство. Вы же не записали своё рассуждение в виде одной из схем индукции.

Можно записать так:
$(\exists x \subset A \ \ |x|=1 \land \forall m \in \mathbb{N}\ \ (\exists x \subset A \ \ |x|=m \longrightarrow \exists x \subset A \ \ |x|=m+1))\longrightarrow \forall m \in \mathbb{N} \ \ (\exists x \subset A \ \ |x|=m)$

[mihaild]

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

Удивительным образом утверждение теоремы 13 совпадает с тем, что сформулировал Qlin в стартовом сообщении

Я не понимаю, как из "непустоты множества всех подмножеств мощности $m$" следует бесконечность по Дедекинду, если эту непустоту формализовать как $\forall m \exists B \subset A(|B| = m)$. Вы как-то иначе формализуете эту непустоту, или для того чтобы доказать что это утверждение выполнено для любого бесконечного множества, нужна аксиома выбора?

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

Строго говоря, это зависит от множества $A$.

Записанное мной утверждение не может зависеть от $A$, потому что там по $A$ стоит квантор всеобщности.

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

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

Так ТС и просит сколь угодно длинные последовательности, а не бесконечные.

[Someone]

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

Можно записать так:
$(\exists x \subset A \ \ |x|=1 \land \forall m \in \mathbb{N}\ \ (\exists x \subset A \ \ |x|=m \longrightarrow \exists x \subset A \ \ |x|=m+1))\longrightarrow \forall m \in \mathbb{N} \ \ (\exists x \subset A \ \ |x|=m)$

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

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

Ёлки-палки! Только сейчас до меня дошло наконец, что Вы доказываете совсем не то утверждение, которое мне померещилось. Аберрация какая-то. Прошу прощения.

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

Я не понимаю, как из "непустоты множества всех подмножеств мощности $m$" следует бесконечность по Дедекинду, если эту непустоту формализовать как $\forall m \exists B \subset A(|B| = m)$. Вы как-то иначе формализуете эту непустоту, или для того чтобы доказать что это утверждение выполнено для любого бесконечного множества, нужна аксиома выбора?

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

[Qlin]

Someone Ну а с этим-то решением всё в порядке, надеюсь ?

И про какую задачу вы изначально подумали ? Тоже интересно же. Всю ответственность за оффтоп беру на себя.

[Someone]

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

И про какую задачу вы изначально подумали ?

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