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

[iifat]

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

Это не очень понятно: то, что можно выбрать конечное подмножество элементов, по-моему, следует непосредственно из того, что множество $M$ бесконечное

Неважно, из чего следует переход. Важно, чтобы он хоть из чего-то следовал.

[mihaild]

Нет, в этой части всё еще в порядке.
По индукции доказываются утверждения вида $\forall n: P(n)$. В данном случае, $P(n)$ - утверждение "существует $n$-элементное подмножество множества $M$". Докажите его, пользуясь непосредственно определением бесконечного множества (множество бесконечно, если оно неравномощно никакому отрезку натурального ряда). Постарайтесь обойтись записями без многоточий (как раз в них будет проблема дальше).

После этого у нас будет доказано утверждение "для любого $n$, существует $n$-элементное подмножество множества $n$". Пусть $A_n$ - это самое $n$-элементное подмножество, и $f_n$ - биекция между $A_n$ и $0, \ldots, n - 1$. Тогда $\cup A_n$ - счетное подмножество $A$.
Упорядочим элементы $A$ следующим образом: пусть $g(x) = \min \{i | x \in A_i\}$ - первое множество, в которое входит $x$; тогда $x < y$ если $g(x) < g(y)$ или $g(x) = g(y) = n$ и $f_n(x) < f_n(y)$ - т.е. если записать все $A_i$ по порядку, внутри упорядочивая в соответствии с $f_i$, то $x$ идет раньше $y$. Ну и теперь легко строится биекция $h: A \to \mathbb N$, $h(x) = |\{y \in A | y < x\}|$ - проверьте, что это биекция.

Попробуйте найти, где в этом рассуждении необоснованный переход (если я нигде не ошибся, он ровно один, и в довольно неожиданном месте).

[Vladimir Pliassov]

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

утверждение "существует $n$-элементное подмножество множества $M$". Докажите его

Было бы понятнее, если бы было: "для любого $n$ существует $n$-элементное подмножество множества $M$". Или в том, что нет слов "для любого" есть какой-то умысел?

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

"для любого $n$, существует $n$-элементное подмножество множества $n$"

Не понимаю, что значит "множество $n$", $n$ это ведь число.

[mihaild]

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

Или в том, что нет слов "для любого" есть какой-то умысел?

Есть. Это утверждение $P(n)$ - оно зависит от $n$.
А доказываем мы уже утверждение $\forall n: P(n)$ ("его" относилось вот к этой формуле).

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

Не понимаю, что значит "множество $n$", $n$ это ведь число

Опечатка, читать как "для любого $n$, существует $n$-элементное подмножество множества $M$".

[pppppppo_98]

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

Кстати существование счетного подмножества в бесконечном множестве - довольно тонкая штука.

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

[mihaild]

(Оффтоп)

pppppppo_98 в сообщении #1610771 писал(а):

а чем проблема счетное количество раз применить аксиому выбора

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

[pppppppo_98]

1

[Vladimir Pliassov]

iifat в сообщении #1610728 писал(а):

Неважно, из чего следует переход. Важно, чтобы он хоть из чего-то следовал.

Цитата:

Утверждение справедливо для всякого натурального $n$, если 1) оно справедливо для $n=1$ и из справедливости утверждения для какого-либо произвольного натурального $n=k$ следует его справедливость для $n=k+1$.

Соминский https://ikfia.ysn.ru/wp-content/uploads ... 1965ru.pdf

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

[mihaild]

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

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

Речь не об утверждении, которое доказывается, а о самом переходе, так называемом шаге индукции. Т.е. нужно, чтобы откуда-то следовало утверждение "если $P(n)$, то $P(n + 1)$".

[Vladimir Pliassov]

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

Речь не об утверждении, которое доказывается, а о самом переходе, так называемом шаге индукции. Т.е. нужно, чтобы откуда-то следовало утверждение "если $P(n)$, то $P(n + 1)$".

Кажется, понял. Спасибо!

[Vladimir Pliassov]

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

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

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

[mihaild]

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

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

Пустое множество считается отрезком натурального ряда. Отрезок натурального ряда - это множество, состоящее из натуральных чисел, ограниченное сверху и вместе с каждым числом содержащее все меньшие.

[Geen]

Мне как-то больше нравится "равномощно собственному подмножеству"

[mihaild]

Geen в сообщении #1611516 писал(а):

Мне как-то больше нравится "равномощно собственному подмножеству"

Это бесконечное по Дедекинду (равносильно "есть инъекция из $\mathbb N$ в наше множество"). Собственно обсуждаемая теорема утверждает, что всякое бесконечное множество бесконечно по Дедекинду. И она нетривиальна.

[Vladimir Pliassov]

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

Пустое множество считается отрезком натурального ряда. Отрезок натурального ряда - это множество, состоящее из натуральных чисел, ограниченное сверху и вместе с каждым числом содержащее все меньшие.

Я посмотрел и обнаружил, что не все так считают, некоторые (https://uchi.ru/otvety/questions/zapish ... kotorih-27) полагают, так же как и я до сих пор думал, что подобно отрезку вещественных чисел, отрезок натуральных чисел состоит из своих концов и всех чисел между ними, например, что отрезок натуральных чисел $[27;35]_\mathbb N$ состоит из чисел $27, 28, 29, 30, 31, 32, 33, 34, 35$, то есть что $[27;35]_\mathbb N=[27;35]\cap \mathbb N=\{27, 28, 29, 30, 31, 32, 33, 34, 35\}$.

Как я думаю, для доказательства утверждения "существует $n$-элементное подмножество множества $M$" это, разумеется, не важно, хотя и странно такое ограничение понятия отрезка натурального ряда, пусть это будет как Вы сказали и как написано здесь https://kto.guru/matematika/802-teoreti ... hisla.html:

Цитата:

Отрезком $N$ натурального ряда называется множество натуральных чисел, не превосходящих натурального числа $a$, т. е $N =\{x\; |\; x\in \mathbb N \wedge x\leqslant a\}$.

Например, $N$ это множество натуральных чисел, не превосходящих $7$, т.е. $N =\{1,2,3,4,5,6,7\}$.

(Тут, по-моему, надо было бы обозначить, о каком именно отрезке идет речь, например, при $N$ поставить индексы $a$ и $7$ -- $N_a$, $N_7$.) Но дальше там стоит:

Цитата:

1) Любой отрезок $N$ содержит единицу. Это свойство вытекает из определения отрезка натурального ряда.

Это значит (и мне тоже так кажется), что отрезок натурального ряда не может быть пустым множеством: независимо от того, включать нуль в натуральные числа или нет, этим отрезком будет либо $[0; 0]$, либо $[1; 1]$, -- в обоих случаях имеем непустое множество: либо $\{0, 0\}=\{0\}$, либо $\{1, 1\}=\{1\}$.

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

Цитата:

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

Я думаю, для доказательства утверждения "существует $n$-элементное подмножество множества $M$" не важно также и то, считать ли, что пустое множество является отрезком натурального ряда, но все же как можно так считать? Может быть, так, что множество натуральных чисел является множеством натуральных чисел, даже если оно пусто? И, вообще, пустое множество является пустым множеством элементов любой природы?

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

Можно предположить также, что "отрезок натурального ряда" это условный термин (по-моему, неудачный), который означает просто-напросто первые, скажем, $n$ натуральных чисел, тогда при $n=0$ множество этих чисел является пустым.