2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Мощность множества всех функций N^N или 2^N?
Сообщение07.08.2006, 13:41 
Аватара пользователя
Для любого конечного множества 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)? И что лучше почитать по этому поводу?

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

 
 
 
 Re: Мощность множества всех функций N^N или 2^N?
Сообщение07.08.2006, 15:17 
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}.$$

 
 
 
 Re: Мощность множества всех функций N^N или 2^N?
Сообщение07.08.2006, 16:07 
Аватара пользователя
Руст писал(а):
Замечание $$(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|?

 
 
 
 Re: Мощность множества всех функций N^N или 2^N?
Сообщение07.08.2006, 17:32 
AlexDem писал(а):
Количество биективных отображений = N!, количество всех отображений = N^N:

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

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

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

 
 
 
 Re: Мощность множества всех функций N^N или 2^N?
Сообщение07.12.2006, 08:30 
Руст писал(а):
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} ?

 
 
 
 
Сообщение07.12.2006, 15:07 
Аватара пользователя
Да, если мощности множеств равны, то между их элементами можно установить взаимно однозначное соответствие. Например, рассмотрим множество рациональных чисел $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$

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

 
 
 
 
Сообщение07.12.2006, 17:03 
Аватара пользователя
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$ верно независимо от гипотез подобного рода (но аксиому выбора желательно сохранить, поскольку без неё кардинальная арифметика становится весьма запутанной).

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

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

Someone писал(а):
но аксиому выбора желательно сохранить

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

 
 
 
 
Сообщение07.12.2006, 21:38 
Аватара пользователя
AlexDem писал(а):
Someone писал(а):
но аксиому выбора желательно сохранить

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


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

 
 
 
 
Сообщение08.12.2006, 08:58 
Аксиома выбора эквивалентно возможности вполне упорядочить любое множество.

 
 
 
 
Сообщение08.12.2006, 10:14 
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] эквивалентно множеству функций
с той же областью определения, но принимающих только два
значения, то как построить взаимно-однозначное
соответствие между ними?

 
 
 
 
Сообщение08.12.2006, 14:19 
Аватара пользователя
По теореме Кантора-Бернштейна.

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

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

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

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

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

 
 
 
 
Сообщение08.12.2006, 18:14 
Аватара пользователя
Остался вопрос про аксиому выбора...

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

Договоримся о том, что элементы одного множества все-таки чем-либо отличаются между собой. Например, если рассматриваем множество светловолосых людей, то разные люди из этого множества будут отличаться отпечатками пальцев. В противном случае мы получим множество тождественных элементов - типа {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$... :)

 
 
 
 
Сообщение08.12.2006, 19:49 
Аватара пользователя
Руст писал(а):
Аксиома выбора эквивалентно возможности вполне упорядочить любое множество.


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

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

 
 
 [ Сообщений: 22 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group