Теорема Кантора о несчетности множества точек отрезка [0, 1]

[Vladimir Pliassov]

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

Давайте возьмем произвольное множество $X$. Докажите, что существует индуктивное множество, содержащее $X$ (как подмножество).

По-моему, в ZF должна быть аксиома: "Существует, по крайней мере, одно множество," -- она есть? Я ее не нахожу. Если есть, можно сказать:

$\lhd$ Возьмем произвольное числовое множество $X$. Возьмем также множество $\{0\}$

(для этого нужно обоснование: "Существует более одного множества", -- или слова "по крайней мере" в аксиоме: "Существует, по крайней мере, одно множество," -- это и означают?)

и по аксиоме объединения объединим его с $X$, получим множество $X'$. Применим к каждому элементу $x\in X'$ операцию $S(a)=a+1$

(почему нельзя назвать эту операцию функцией? Ведь есть аксиома преобразования:

Цитата:

Схему преобразования можно сформулировать по-русски, а именно: "Любое множество можно преобразовать в [то же самое или другое] множество $d$, высказав функциональное суждение $\varphi$ обо всех элементах $b$ данного множества $a$." Википедия.

), к каждому полученному элементу снова применим операцию $S(a)$ и т. д., получим индуктивное множество $X''$, подмножеством которого будет $X$. $\rhd$

Здесь я применил прием, запрещенный в строгих доказательствах: прием "и так далее", но не знаю, как иначе доказать.

[dgwuqtj]

Vladimir Pliassov в сообщении #1615291 писал(а):

По-моему, в ZF должна быть аксиома: "Существует, по крайней мере, одно множество," -- она есть? Я ее не нахожу.

Там аж 2 такие аксиомы (пустого множества и бесконечности), ни одна из них не требуется для вашего "возьмём". Рассматривать можно и несуществующие объекты, в конце концов.

Vladimir Pliassov в сообщении #1615291 писал(а):

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

Потому что в схеме преобразования нет функций. В том числе $\varphi$ - это формула, а не функция. Если что, функция $f \colon X \to Y$ в ZF - это подмножество $X \times Y$ с какими-то свойствами, то есть тоже множество.

[mihaild]

Vladimir Pliassov в сообщении #1615291 писал(а):

По-моему, в ZF должна быть аксиома: "Существует, по крайней мере, одно множество," -- она есть?

Это правильное наблюдение. В ZF есть ровно одна аксиома, начинающаяся с квантора существования - как раз утверждение о существовании индуктивного множества. Существование пустого множества уже выводится из неё и аксиомы выделения. Иногда существование пустого множества делают отдельной аксиомой, но особого смысла в этом нет.

Vladimir Pliassov в сообщении #1615291 писал(а):

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

И там не просто так написано "функциональное суждение". Эта схема аксиом может быть нужна, в том числе, для доказательства существования функции - без неё может оказаться, что некоторых довольно естественных функций не существует.

Да, я сообразил, что построение индуктивного множества это слишком сложная задача. Есть трюк с формализацией "и так далее", но для него тоже нужен принцип индукции для натуральных чисел.
Т.е. идея у Вас правильная - возьмем $\mathbb N$, и для каждого $x \in X$ добавим $x, S(x), S^2(x), \ldots$. Это получится индуктивное множество. Его строгое описание получится сделать чуть позже, но для интуиции ИМХО должно помочь.
В предположении, что $X \nsubseteq \mathbb N$, покажите, что вот для получившегося множества (и вообще для любого индуктивного множества, отличного от $\mathbb N$) принцип индукции не выполнен - имея индуктивное множество $X \neq \mathbb N$, напишите формулу $P(x)$, такую что $P(0) \wedge (\forall n \in X: P(n) \rightarrow P(x + 1)) \wedge \exists y \in X: \neg P(y)$.

-- 30.10.2023, 18:20 --

Vladimir Pliassov в сообщении #1615291 писал(а):

Возьмем произвольное числовое множество $X$

Понятия "числовое множество" нет. Но оно Вам и не нужно.

[Vladimir Pliassov]

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

Давайте возьмем произвольное множество $X$. Докажите, что существует индуктивное множество, содержащее $X$ (как подмножество).

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

В ZF есть ровно одна аксиома, начинающаяся с квантора существования - как раз утверждение о существовании индуктивного множества.

Конечно, нет необходимости в аксиоме существования множества вообще, если

1) есть аксиома существования индуктивного множества,

и при этом

2) любое множество является подмножеством индуктивного множества.

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

[mihaild]

Vladimir Pliassov в сообщении #1615320 писал(а):

любое множество является подмножеством индуктивного множества

Лучше такие вещи формулировать как "является подмножеством некоторого индуктивного множества". Потому что Ваша формулировка может означать и это, и существование некоторого универсального индуктивного множества, подмножеством которого является любое - что, конечно, не так.

Vladimir Pliassov в сообщении #1615320 писал(а):

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

Можно. Если строго, то нужно доказать: $\forall X \exists X': X \subseteq X' \wedge I(X')$, где $I(x)$ - формула, говорящая "$x$ - индуктивное множество".

[Vladimir Pliassov]

1.

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

В предположении, что $X \nsubseteq \mathbb N$, покажите, что вот для получившегося множества (и вообще для любого индуктивного множества, отличного от $\mathbb N$) принцип индукции не выполнен - имея индуктивное множество $X \neq \mathbb N$, напишите формулу $P(x)$, такую что $P(0) \wedge (\forall n \in X: P(n) \rightarrow P(x + 1)) \wedge \exists y \in X: \neg P(y)$.

Пусть $X$ -- индуктивное множество, и $\mathbb N \subsetneq X$, тогда $\exists y: y\in X \wedge y\notin \mathbb N$.

И пусть $P(a)=a\in \mathbb N$, тогда $P(0) \wedge (\forall x \in X: P(x) \rightarrow P(x + 1)) \wedge \exists y \in X: \neg P(y)$.

То есть для $X$ не выполняется $(P(0) \wedge \forall x \in X: P(x) \rightarrow P(S(x))) \rightarrow \forall x \in X: P(x)$, таким образом, для индуктивного множества, не равного $\mathbb N$, может не выполняться принцип индукции.

Теперь надо доказать,

a) что принцип индукции не выполняется для множеств, не равных $\mathbb N$, ни в каком случае -- если это так (?), --

b) и что он всегда выполняется для $\mathbb N$.

Вообще, как я понимаю, в индуктивном множестве, не равном $\mathbb N$, есть не только цепочка $0, S(0), S^2(0), \ldots \; ,$ но и другие цепочки предшественников-следователей, например, в $\mathbb R$ (которое является индуктивным множеством) мощность множества цепочек равна мощности полуоткрытого промежутка $[0, 1)$ или $(0, 1]$, и, наверное, для ограниченных снизу множеств можно было бы применять принцип индукции к каждой цепочке отдельно (тогда базой индукции должно быть не $P(0)$, а $P(d)$, где $d$ это наименьший элемент цепочки). Разумеется, для множеств c бесконечным количеством цепочек это невозможно, но возможно для множеств с конечным их количеством -- если их не слишком много, -- например, для множества $\mathbb N\cup \{3,2; S(3,2); S^2(3,2); \ldots \; ,\}$ (оно имеет всего две цепочки).

Однако так, я думаю, не делается: принцип индукции применяется только к одной цепочке, а именно, к $\mathbb N$.

2.

dgwuqtj в сообщении #1615292 писал(а):

Vladimir Pliassov в сообщении #1615291 писал(а):

По-моему, в ZF должна быть аксиома: "Существует, по крайней мере, одно множество," -- она есть? Я ее не нахожу.

Там аж 2 такие аксиомы (пустого множества и бесконечности), ни одна из них не требуется для вашего "возьмём". Рассматривать можно и несуществующие объекты, в конце концов.

Рассматривать несуществующие объекты, конечно, можно, но мне кажется, что в доказательстве как существования, так и несуществования некоторого объекта в данной теории, например, в ZF, опираются именно на те объекты, которые в ней существуют, а не на те, которые в ней не существуют.

[dgwuqtj]

Vladimir Pliassov в сообщении #1615463 писал(а):

Рассматривать несуществующие объекты, конечно, можно, но мне кажется, что в доказательстве как существования, так и несуществования некоторого объекта в данной теории, например, в ZF, опираются именно на те объекты, которые в ней существуют, а не на те, которые в ней не существуют.

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

[mihaild]

Vladimir Pliassov в сообщении #1615463 писал(а):

Пусть $X$ -- индуктивное множество, и $\mathbb N \subsetneq X$

А откуда взялось $\mathbb N \subsetneq X$? У нас было только $X \neq \mathbb N$ (ну и что $X$ индуктивно).

Vladimir Pliassov в сообщении #1615463 писал(а):

например, в $\mathbb R$ (которое является индуктивным множеством)

Это зависит от того, как именно мы определяем $\mathbb R$. И при стандартных вариантах - не является.

Vladimir Pliassov в сообщении #1615463 писал(а):

что принцип индукции не выполняется для множеств, не равных $\mathbb N$, ни в каком случае

Вы это по сути доказали. Для формулы $P(n) := n \in \mathbb N$ принцип индукции выполнен только для $\mathbb N$.
И если подумать, то в чем-то аналогичное соображение показывает и что принцип индукции выполнен для $\mathbb N$.

[Vladimir Pliassov]

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

А откуда взялось $\mathbb N \subsetneq X$? У нас было только $X \neq \mathbb N$ (ну и что $X$ индуктивно).

Но это ведь и значит, что $\mathbb N \subsetneq X$? Поскольку $X$ индуктивно, $\mathbb N \subset X$, а поскольку $X \neq \mathbb N$ -- $\mathbb N \subsetneq X$.

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

Vladimir Pliassov в сообщении #1615463 писал(а):

например, в $\mathbb R$ (которое является индуктивным множеством)

Это зависит от того, как именно мы определяем $\mathbb R$. И при стандартных вариантах - не является.

Но ведь, как бы мы ни определяли $\mathbb R$, оно содержит $0$ и вместе с каждым числом $a$ содержит $a+1$? Наверное, имеется в виду, что на него смотрят в зависимости от его определения: то так, то так (но $0$ и $a+1$ оно содержит в любом случае, от этого никуда не деться?)

[mihaild]

Vladimir Pliassov в сообщении #1615660 писал(а):

Поскольку $X$ индуктивно, $\mathbb N \subset X$

Да, правильно.

Vladimir Pliassov в сообщении #1615660 писал(а):

Но ведь, как бы мы ни определяли $\mathbb R$, оно содержит $0$ и вместе с каждым числом $a$ содержит $a+1$?

В определении индуктивного множества нет $+1$, там $S(\cdot)$. Знак $+1$ вводится уже дальше, и в разных контекстах имеет разное значение.

[Vladimir Pliassov]

Из равенства

$$\frac {1}{1\cdot 2}+\frac {1}{2\cdot 3}+\frac {1}{3\cdot 4}+\ldots+\frac {1}{n(n+1)}=\frac {n}{n+1} \eqno (1)$$

видно, что

$$x_n=\frac {1}{1\cdot 2}+\frac {1}{2\cdot 3}+\frac {1}{3\cdot 4}+\ldots+\frac {1}{n(n+1)} \eqno (2)$$

и

$$x_n=\frac {n}{n+1} \eqno (3)$$

это одна и та же последовательность, и доказательство по индукции равенства (1) это доказательство того, что последовательность $x_n$ можно представить не только в виде (2), но и в виде (3). Именно в этом состоит утверждение $P(x)$ относительно элементов $x\in X$, где $X$ это множество всех членов последовательности $x_n$.

Поскольку элементы $X$ естественным образом перенумерованы, $P(x)$ можно обозначить как $P(x_n)$, и даже как $P(n)$, но при последнем обозначении все равно имеется в виду, что утверждение $P$ высказано об элементах $X$ (а не об элементах $\mathbb N$).

(Впрочем, при другом взгляде можно считать, что $P$ это утверждение об элементах $\mathbb N$. )

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

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

Правильно?

[mihaild]

Нет, по индукции (в рассматриваемой теме) доказываются утверждения о натуральных числах. Т.е. Ваше $\eqno (1)$, после записи в виде формулы ZF. Если чуть раскрыть, то получится что-то вроде "для любой функции $f: \mathbb N \to \mathbb R$, такой что $f(1) = \frac{1}{2}$, $f(S(n)) = f(n) \cdot \frac{1}{n(n + 1)}$, выполнено $\forall n: f(n) = \frac{n}{n + 1}$", где умножение и дроби тоже расписываются через теоретико-множественные символы.