Мощность множества всех функций N^N или 2^N?

[AlexDem]

Для любого конечного множества N количество всех возможных отображений из N в N равно N^N. При определенном числе элементов исходного множества N можно записать, что N^N = (N)^N = (2^2^2...^2)^N = 2^(2^(...(2^N))).

При переходе от конечного к счетному множеству N получаем несуразицу - учитывая, что каждая степень 2^N дает множество более высокой мощности, а число скобок в выражении бесконечно, получаем, что мощность множества всех отображений из счетного множества N в N имеет мощность алеф-бесконечность.

В чем ошибка? И какую мощность на самом деле имеет множество всех отображений счетного множества (алеф-1 или алеф-2)? И что лучше почитать по этому поводу?

Спасибо откликнувшимся

[Руст]

AlexDem писал(а):

Для любого конечного множества N количество всех возможных отображений из N в N равно N^N. При определенном числе элементов исходного множества N можно записать, что N^N = (N)^N = (2^2^2...^2)^N = 2^(2^(...(2^N))).

При переходе от конечного к счетному множеству N получаем несуразицу - учитывая, что каждая степень 2^N дает множество более высокой мощности, а число скобок в выражении бесконечно, получаем, что мощность множества всех отображений из счетного множества N в N имеет мощность алеф-бесконечность.

В чем ошибка? И какую мощность на самом деле имеет множество всех отображений счетного множества (алеф-1 или алеф-2)? И что лучше почитать по этому поводу?

Спасибо откликнувшимся

Замечание

$$(a^b)^c\not =a^{b^c}.$$

[AlexDem]

Руст писал(а):

Замечание

$$(a^b)^c\not =a^{b^c}.$$

Да, заклинило чего-то, спасибо

Все-таки интересует литература или ссылки на примеры вычисления мощности отображений (всех и биективных). Количество биективных отображений = N!, количество всех отображений = N^N:

2^N < N! < N^N < (2^N)^N

Если |N^N| = |2^N|, значит и |N!| = |2^N|?

[Руст]

AlexDem писал(а):

Количество биективных отображений = N!, количество всех отображений = N^N:

2^N < N! < N^N < (2^N)^N

Если |N^N| = |2^N|, значит и |N!| = |2^N|?

Для бесконечных мощностей всюду равенства, вместе меньше.

[Agathis]

Руст писал(а):

AlexDem писал(а):

Количество биективных отображений = N!, количество всех отображений = N^N:

2^N < N! < N^N < (2^N)^N

Если |N^N| = |2^N|, значит и |N!| = |2^N|?

Для бесконечных мощностей всюду равенства, вместе меньше.

почему?
если, например, рассмотреть множество произвольных отображений [0,1] в себя, то мощность множества всех характеристических функций на [0,1] будет 2^R.
А область значений этих функций есть только две точки.
Значит, множество всех отображений [0,1] в себя эквивалентно множеству его отображений в конечное множество {0,1} ?

[AlexDem]

Да, если мощности множеств равны, то между их элементами можно установить взаимно однозначное соответствие. Например, рассмотрим множество рациональных чисел $Q$, между двумя целыми точками на числовой прямой рациональных чисел бесконечно много. И тем не менее, все рациональные числа можно занумеровать натуральными $N$, поскольку мощности обоих множеств совпадают. Точно так же можно установить соответствие между рассматриваемыми Вами множествами. Обычно это объясняется в разделе "Операции над мощностями". Например:
$\aleph_0 * \aleph_0 = \aleph_0$

${\aleph_1}^{\aleph_0} = (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 * \aleph_0} = 2^{\aleph_0} = \aleph_1$

(если где ошибся - пусть меня поправят)

[Someone]

AlexDem писал(а):

${\aleph_1}^{\aleph_0} = (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 * \aleph_0} = 2^{\aleph_0} = \aleph_1$

(если где ошибся - пусть меня поправят)

Это верно в предположении справедливости континуум-гипотезы, которая как раз в том и состоит, что $2^{\aleph_0}=\aleph_1$. Однако можно считать, что $2^{\aleph_0}>\aleph_1$.
Обычно кардинал $\mathfrak c=2^{\aleph_0}$ называют континуумом (это мощность множества действительных чисел), и для него действительно $\mathfrak c^{\aleph_0}=2^{\aleph_0}$ и $\mathfrak c^{\mathfrak c}=2^{\mathfrak c}$.
Разумеется, равенство ${\aleph_1}^{\aleph_0}=2^{\aleph_0}=\mathfrak c$ верно независимо от гипотез подобного рода (но аксиому выбора желательно сохранить, поскольку без неё кардинальная арифметика становится весьма запутанной).

[AlexDem]

Есть одна книжка - Гарднер "А ну-ка, догадайся!", где об этом и многом другом можно прочитать в очень доступной форме. Например, про бесконечность - глава "Числа", разделы "Гостиница Бесконечность" и "Лестница алефов".

Добавлено спустя 1 час 14 минут 5 секунд:

Someone писал(а):

но аксиому выбора желательно сохранить

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

[Someone]

AlexDem писал(а):

Someone писал(а):

но аксиому выбора желательно сохранить

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

Мешает отсутствие минимального элемента в некоторых линейно упорядоченных множествах. Насчёт возможности линейно упорядочить любое множество без аксиомы выбора - не помню.

[Руст]

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

[Agathis]

AlexDem писал(а):

Да, если мощности множеств равны, то между их элементами можно установить взаимно однозначное соответствие. Например, рассмотрим множество рациональных чисел $Q$, между двумя целыми точками на числовой прямой рациональных чисел бесконечно много. И тем не менее, все рациональные числа можно занумеровать натуральными $N$, поскольку мощности обоих множеств совпадают. Точно так же можно установить соответствие между рассматриваемыми Вами множествами. Обычно это объясняется в разделе "Операции над мощностями". Например:
$\aleph_0 * \aleph_0 = \aleph_0$

${\aleph_1}^{\aleph_0} = (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 * \aleph_0} = 2^{\aleph_0} = \aleph_1$

(если где ошибся - пусть меня поправят)

нет, ну понятно, что бесконечное множество содержет
эквиваленотное самому себе собственное подмножество -
это определение бесконечного множества.
А если поставить вопрос так: если множество всех
функций на [0,1] эквивалентно множеству функций
с той же областью определения, но принимающих только два
значения, то как построить взаимно-однозначное
соответствие между ними?

[PAV]

По теореме Кантора-Бернштейна.

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

Построим обратное вложение. Для этого заметим, что каждую функцию с двумя значениями можно интерпретировать как индикаторную функцию некоторого подмножества отрезка [0,1]. Т.е. есть естественное взаимно-однозначное соответствие между функциями и такими подмножествами.

Функция же с произвольными значениями суть множество пар $(x,f(x))$, где $x$ пробегает весь отрезок [0,1]. Т.е. каждой такой функции можно сопоставить некоторое подмножество точек на плоскости (правда, специального вида, т.е. не любое подмножество соответствует некоторой функции).

Теперь воспользуемся тем, что существует взаимно-однозначное соответствие между плоскостью и отрезком [0,1]. Т.е. указанное подмножество плоскости с помощью этого соответствия однозначно переводится в подмножество отрезка, а оно уже соответствует некоторой двузначной функции.

Т.е. мы каждой произвольной функции сопоставили некоторую двузначную. Ну а далее теорема Кантора-Бернштейна, если нужна обязательно биекция.

[AlexDem]

Остался вопрос про аксиому выбора...

Если я правильно понял, проблема касается не только бесконечных, но и конечных множеств. А именно - множество рассматривается как некий мешок с элементами, а как они там лежат - мы не знаем.

Договоримся о том, что элементы одного множества все-таки чем-либо отличаются между собой. Например, если рассматриваем множество светловолосых людей, то разные люди из этого множества будут отличаться отпечатками пальцев. В противном случае мы получим множество тождественных элементов - типа {2 2 2 2}, и нам будет все равно, какой из элементов будет выбран в качестве представителя.

Пусть есть некий Оракул, который умеет производить стандартные операции с множествами. Например, если мы ему дадим два множества и скажем "Объедини" - он выдаст нам один мешок с объединенным множеством. В том числе Оракул может по команде "Подмножество" собрать и отдать нам подмножество элементов, удовлетворяющих некоторому точно заданному критерию, - например выделить из множества светловолосых людей с голубыми глазами.

Пусть мы имеем множество $\{M\}$, элементами которого являются множества мощности $\mathfrak c$. Тогда мы можем взять числовую прямую $R$ и для каждого элемента $M \in \{M\}$ дать Оракулу следующие команды:

1) "Декартово произведение": $G = M \times R$

2) "Множество всех подмножеств": $F = \text{множество всех подмножеств } G$

3) "Подмножество": $E = \{f \in F| f = id_F\}$

4) "Подмножество": $Z = \{r \in R| r = 0\}$

5) "Прообраз": $S = \bigcup\limits_{e \in E} e^{-1}: Z \to M$

Объединение всех $S$ и даст искомое множество представителей, поскольку $|E| = 1$, так?
Какая тогда из команд Оракула неверна в отсутствие аксиомы выбора?

Добавлено спустя 32 минуты 21 секунду:

А, Оракул, пожалуй, не сможет найти $id_F$...

[Someone]

Руст писал(а):

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

Это я знаю. Я не помню, что там с линейной упорядоченностью. Возможно линейно упорядочить любое множество в системе $ZF$, то есть, без аксиомы выбора и без дополнительных аксиом? Это должен быть какой-то модельный результат (я ожидаю отрицательный ответ).

[Руст]

Этот вопрос скорее не представляет интереса и поэтому не изучен. Скорее всего ответ отрицателен. Даже, если на множестве M имеется линейный порядок, то для введения линейного порядка на 2^M (множестве подмножеств) требуется, чтобы M был вполне упорядочен (без этого лексикографический порядок не определяется).