мощность множества всех перестановок натурального ряда

[Dialectic]

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

[ИСН]

Вы как ставили в соответствие? Если получается биекция, то уже всё хорошо; а если нет, то обычная стратегия - попытаться доказать, что эти множества "больше друг друга". Это входит в то, а то входит в это. Тогда они не иначе как равны.

[caxap]

А если сравнить с $|2^\mathbb N|$ и $|\mathbb N^\mathbb N|$?

[Dialectic]

ИСН в сообщении #390019 писал(а):

Вы как ставили в соответствие? Если получается биекция, то уже всё хорошо;

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

ИСН в сообщении #390019 писал(а):

а если нет, то обычная стратегия - попытаться доказать, что эти множества "больше друг друга". Это входит в то, а то входит в это. Тогда они не иначе как равны.

Я не знаю как это сделать. Но меня интересует не то, как тут применять теорему Кантора -Бернштейна, а меня больше всего интересует явное построение как каждому элементу одного множества ставится в соответсвие другое. Это не учебная задача .Это мне нужно самому понять, как это можно проделать, я хочу понять логику как вот это делается. И мне мало "абстрактного доказательства" мне нужно шоб прямо было показано -"вот берём иррациональное число, и делаем с ним то-то и то-то, из чего следует, что для него существует перестановка". Я например могу доказать диагональным методом, шо множество перестановок имеет мощность большую чем счетное множество. С другой стороны я могу доказать, чт окаждой перестановке соответсвует иррациональное число. Но я не могу доказать, что нет множества промежуточной мощности между N и R.
Вообщем ИСН - помогите пожалуйста постоить явный пример биекции. Спасибо.

-- Ср дек 22, 2010 00:17:47 --

caxap в сообщении #390030 писал(а):

А если сравнить с $|2^\mathbb N|$ и $|\mathbb N^\mathbb N|$?

Как построить явный пример биекции? Вы не в курсе? Все эти игры со сравнениями - мне не по душе. Нет ли способа явно построить биекцию?

[ИСН]

Тогда плюньте на биекцию и переходите к плану Б. Думаете, его от хорошей жизни придумали? Или, может, сдуру?
Часто оказывается так, что биекция-то "есть", но её хрен построишь.

[Dialectic]

ИСН в сообщении #390034 писал(а):

Тогда плюньте на биекцию и переходите к плану Б. Думаете, его от хорошей жизни придумали? Или, может, сдуру?
Часто оказывается так, что биекция-то "есть", но её хрен построишь.

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

[ИСН]

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

[Joker_vD]

Dialectic в сообщении #390032 писал(а):

Но я не могу доказать, что нет множества промежуточной мощности между $\mathbb N$ и $\mathbb R$.

Правильно, и не докажете — континуум-гипотеза недоказуема и неопровергаема.

[Dialectic]

ИСН в сообщении #390041 писал(а):

У Вас в какую сторону уже есть екция?

У меня есть инекция S(N) в R.

-- Ср дек 22, 2010 00:36:20 --

Joker_vD в сообщении #390045 писал(а):

Dialectic в сообщении #390032 писал(а):

Но я не могу доказать, что нет множества промежуточной мощности между $\mathbb N$ и $\mathbb R$.

Правильно, и не докажете — континуум-гипотеза недоказуема и неопровергаема.

Так какой Вы метод решения предлагаете? Как доказать, что мощность R не больше мощности S(N)? (что не меньше - и так понятно).

[ИСН]

Запишем число в нашей родной десятичной системе. И построим по нему перестановку. Например, такую: если цифра 0, выписываем самое первое из оставшихся у нас натуральных чисел. Если цифра 1, то второе. Если 2, то третье. И так далее до упора.

-- Ср, 2010-12-22, 00:45 --

Ах да, так мы пропустим довольно много чисел. Ну значит, это всё ставим на нечётные номера, а остальные подряд - на чётные, делов-то.

[Dialectic]

ИСН в сообщении #390053 писал(а):

Запишем число в нашей родной десятичной системе. И построим по нему перестановку. Например, такую: если цифра 0, выписываем самое первое из оставшихся у нас натуральных чисел. Если цифра 1, то второе. Если 2, то третье. И так далее до упора.

Да ,похоже, спасибо. Действительно, любое подмножество N -имеет минимальный элемент.
Токо не могу явным образом доказать иньективность. Она точно есть?

-- Ср дек 22, 2010 00:51:41 --

ИСН в сообщении #390053 писал(а):

Ах да, так мы пропустим довольно много чисел. Ну значит, это всё ставим на нечётные номера, а остальные подряд - на чётные, делов-то.

Вот это я что-то не понял уже. Какие "остальные"?

[ИСН]

Если в десятичной записи с какого-то места идут сплошь большие цифры (скажем, 7,8,9), то несколько натуральных чисел в самом начале так и останутся неприкаянными: мы вечно будем их перепрыгивать. Поэтому всё, что я сказал, делаем только на нечётных местах. На чётных - всегда ставим первое из оставшихся чисел. Так уж точно прихватим все.

[Dialectic]

ИСН в сообщении #390066 писал(а):

Если в десятичной записи с какого-то места идут сплошь большие цифры (скажем, 7,8,9), то несколько натуральных чисел в самом начале так и останутся неприкаянными: мы вечно будем их перепрыгивать. Поэтому всё, что я сказал, делаем только на нечётных местах. На чётных - всегда ставим первое из оставшихся чисел. Так уж точно прихватим все.

Допустим есть число:
$A=0,a_1a_2a_3a_4a_5a_6...$
перестановку мы так строим:
$P=(min( N / a_1),a_2,min( N / a_1 / a_2),a_4,min( N /a_1 / a_2 /a_3)...$
или так:
$P=(min( N / a_1),min( N / a_1 / a_2),min( N /a_1 / a_2 /a_3)...$?
ПО-моему Вы изначально за второй вариант говорили. Почему он не проходит?Вроде все нормально.

?

[Профессор Снэйп]

Dialectic в сообщении #390008 писал(а):

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

Разбиваем натуральные числа на пары, каждой паре назначаем номер. Теперь для каждого $A \subseteq \mathbb{N}$ строим перестановку $\sigma_A$ порядка $2$, меняющую местами элементы пар, номера которых принадлежат $A$, и оставляющую остальные натуральные числа на месте. Получаем инъекцию $A \mapsto \sigma_A$, так что перестановок порядка $2$ уже континуум. Оценка в другую сторону вроде не вызывает затруднений: имеется ровно континуум всевозможных функций из $\mathbb{N}$ в $\mathbb{N}$, каждая перестановка является функцией...

-- Чт дек 23, 2010 02:17:37 --

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

[Padawan]

Профессор Снэйп в сообщении #390418 писал(а):

То, что у счётного множества ровно континуум подмножеств, считается известным или нет?

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