Мощность множества функций и континуум-гипотеза

[gris]

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

[Mihr]

gris в сообщении #1100012 писал(а):

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

Континуум. Это, по сути, задача 80 из сборника Ю.С. Очан. Сборник задач по математическому анализу. 1981.

P.S. Прошу прощения, сразу не заметил: Anton_Peplov уже ответил. Но удалять это сообщение не буду ради ссылки на задачу.

[ellipse]

Mihr в сообщении #1100017 писал(а):

gris в сообщении #1100012 писал(а):

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

Континуум. Это, по сути, задача 80 из сборника Ю.С. Очан. Сборник задач по математическому анализу. 1981.

Извиняюсь, что не совсем по теме. А верно ли, что для произвольного множества $X$ множество функций из $X$ в $X$ имеет мощность $2^X$?

[Dan B-Yallay]

$|X|^{|X|}$

[Mihr]

ellipse в сообщении #1100032 писал(а):

А верно ли, что для произвольного множества $X$ множество функций из $X$ в $X$ имеет мощность $2^X$?

По крайней мере, для первых двух бесконечных мощностей (счётного множества и континуума) это так. Если обозначить
$a$ - мощность счётного множества,
$c$ - мощность континуума,
$f$ - мощность гиперконтинуума
(и если признавать справедливость континуум-гипотезы), то
$a^a=2^a=c$,
$c^c=2^c=f$.

(А вот верно ли, что для каждой бесконечной мощности $m$ справедливо равенство $m^m=2^m$, - не знаю. Надеюсь, кто-нибудь более сведущий ответит.)

-- 17.02.2016, 01:20 --

Заметил у себя ошибку:

Mihr в сообщении #1100017 писал(а):

Это, по сути, задача 80 из сборника Ю.С. Очан. Сборник задач по математическому анализу. 1981.

Не 80, а 81.

[quartermind]

ellipse в сообщении #1100032 писал(а):

А верно ли, что для произвольного множества $X$ множество функций из $X$ в $X$ имеет мощность $2^X$?

Да, для любого бесконечного $X$. Доказывается с помощью пары неравенств для кардиналов и равенства $\lvert X \times X \rvert = \lvert X \rvert$.

Mihr в сообщении #1100041 писал(а):

... для первых двух бесконечных мощностей (счётного множества и континуума)...

Первые две они, только если принять континуум-гипотезу. А для упомянутого тождества она не нужна, хотя, без аксиомы выбора, наверное, не получится. Можно даже поставить такой вопрос: влечёт ли в $\mathbf{ZF}$ утверждение о существовании биекции из множества функций $X \rightarrow X$ в множество подмножеств $X$ для всякого бесконечного $X$ аксиому выбора? Сравните с теоремой Тарского.

[Mihr]

quartermind в сообщении #1100052 писал(а):

А для упомянутого тождества она не нужна

Я имел в виду другое.

Mihr в сообщении #1100041 писал(а):

(и если признавать справедливость континуум-гипотезы), то
$a^a=2^a=c$,
$c^c=2^c=f$.

Правая часть верхнего двойного равенства - континуум-гипотеза "в чистом виде".
Правая часть нижнего - обобщённая континуум-гипотеза.

[quartermind]

Mihr в сообщении #1100091 писал(а):

Правая часть верхнего двойного равенства - континуум-гипотеза "в чистом виде".
Правая часть нижнего - обобщённая континуум-гипотеза.

Это не так. Континуум по определению есть мощность множества всех подмножеств счётного множества. Аналогично с гиперконтинуумом. Гипотеза континуума касается промежуточных мощностей. Почитайте где-нибудь.

[Mihr]

quartermind,
я следую определениям и обозначением книги: И.П. Натансон. Теория функций вещественной переменной. 3-е изд., 1999. На странице 30 автор определяет континуум как мощность числового отрезка $[0;1]$ (что, очевидно, эквивалентно определению континуума как мощности множества действительных чисел).
А мощность булеана счётного множества по определению есть $2^a$. Которая, как легко доказывается, не превосходит $c$. Континуум-гипотеза состоит в том, что выполняется именно равенство (а не просто нестрогое неравенство): $2^a=c$.

[Xaositect]

Mihr в сообщении #1100183 писал(а):

quartermind,
я следую определениям и обозначением книги: И.П. Натансон. Теория функций вещественной переменной. 3-е изд., 1999. На странице 30 автор определяет континуум как мощность числового отрезка $[0;1]$ (что, очевидно, эквивалентно определению континуума как мощности множества действительных чисел).
А мощность булеана счётного множества по определению есть $2^a$. Которая, как легко доказывается, не превосходит $c$. Континуум-гипотеза состоит в том, что выполняется именно равенство (а не просто нестрогое неравенство): $2^a=c$.

Нет. Легко доказывается, что $2^{\aleph_0} = \mathfrak{c}$ (каждой бесконечной двоичной дроби соответствует какое-то подмножество множества натуральных чисел, и надо сказать пару слов про то, что из-за дробей с единицами в конце не слишком много потеряем). Континуум-гипотеза говорит о том, что нет множеств с мощность, промежуточной между счетной и континуумом, то есть, если обозначить $\aleph_1$ минимальную мощность несчетного множества, то $\aleph_1 = \mathfrak{c} = 2^{\aleph_0}$.

[Mihr]

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

Нет. Легко доказывается, что $2^{\aleph_0} = \mathfrak{c}$ (каждой бесконечной двоичной дроби соответствует какое-то подмножество множества натуральных чисел, и надо сказать пару слов про то, что из-за дробей с единицами в конце не слишком много потеряем). Континуум-гипотеза говорит о том, что нет множеств с мощность, промежуточной между счетной и континуумом, то есть, если обозначить $\aleph_1$ минимальную мощность несчетного множества, то $\aleph_1 = \mathfrak{c} = 2^{\aleph_0}$.

Да, в этом я неправ. quartermind, Xaositect, спасибо за поправки.