2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Мощность множества всех функций N^N или 2^N?
Сообщение07.08.2006, 13:41 
Заблокирован
Аватара пользователя


07/08/06

3474
Для любого конечного множества 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 
Заслуженный участник


09/02/06
4382
Москва
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 
Заблокирован
Аватара пользователя


07/08/06

3474
Руст писал(а):
Замечание $$(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 
Заслуженный участник


09/02/06
4382
Москва
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 


19/10/06
24
Руст писал(а):
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 
Заблокирован
Аватара пользователя


07/08/06

3474
Да, если мощности множеств равны, то между их элементами можно установить взаимно однозначное соответствие. Например, рассмотрим множество рациональных чисел $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 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
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 
Заблокирован
Аватара пользователя


07/08/06

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

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

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

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

 Профиль  
                  
 
 
Сообщение07.12.2006, 21:38 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
AlexDem писал(а):
Someone писал(а):
но аксиому выбора желательно сохранить

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


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

 Профиль  
                  
 
 
Сообщение08.12.2006, 08:58 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение08.12.2006, 10:14 


19/10/06
24
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 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
По теореме Кантора-Бернштейна.

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

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

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

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

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

 Профиль  
                  
 
 
Сообщение08.12.2006, 18:14 
Заблокирован
Аватара пользователя


07/08/06

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

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

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


23/07/05
17973
Москва
Руст писал(а):
Аксиома выбора эквивалентно возможности вполне упорядочить любое множество.


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

 Профиль  
                  
 
 
Сообщение08.12.2006, 20:33 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group