Перестановкой множества называется любое биективное отображение этого множества на себя. Доказать,что множество всех перестановок множества $%{\mathbb N}$% имеет мощность $%c$%. Можно поподробнее.

задан 29 Апр '13 12:21

изменен 29 Апр '13 16:19

falcao's gravatar image


193k1632

10|600 символов нужно символов осталось
1

Рассмотрим перестановки такого вида, когда числа $%2n-1$% и $%2n$% либо переходят каждое в себя, либо переставляются между собой. В первом случае положим $%a_n=0$%, а во втором $%a_n=1$%. Тем самым имеется биекция между некоторым подмножеством множества перестановок на $%{\mathbb N}$%, и множеством бесконечных двоичных последовательностей, которое имеет мощность континуума. Из этого следует, что перестановок имеется не меньше континуума.

Обратно, рассмотрим произвольную перестановку $%f$% на $%{\mathbb N}$%. Ей соответствует последовательность натуральных чисел $%f(1)$%, $%f(2)$%, ..., $%f(n)$%, ... . Запишем каждое из этих чисел в двоичной системе, начиная с младшего разряда, дополняя строку нулями. Например, числу $%19$% будет соответствовать запись $%110010000\ldots$%. Из этих строк сформируем матрицу бесконечного размера, а потом прочтём её элементы по диагоналям, двигаясь по каждой из диагоналей в заданном направлении (скажем, сверху вниз). Это даст нам одну бесконечную двоичную последовательность, по которой мы однозначно сможем восстановить матрицу, а по ней -- исходную перестановку. Из этого рассуждения следует, что перестановок имеется не больше, чем бесконечных двоичных последовательностей, то есть не больше континуума.

Остаётся сослаться на теорему Кантора - Бернштейна, из которой будет следовать, что мощность множества перестановок равна мощности континуума.

Добавление. Во второй части рассуждения можно поступить несколько проще. А именно, вместо составления матрицы, записать каждое число тем количеством единиц, которому оно равно, и разделить числа нулями. Получится бесконечная двоичная последовательность, Например, строка $%110111110111011111110\ldots$% будет означать, что мы закодировали последовательность $%2,5,3,7,\ldots$%, то есть в перестановке на первом месте стоит $%2$%, на втором $%5$% и так далее.

ссылка

отвечен 29 Апр '13 13:36

изменен 29 Апр '13 16:23

10|600 символов нужно символов осталось
0

Множество всех подмножеств натуральных чисел имеет мощность $%c=2^N$%. Мощность всех перестановок натурального ряда чисел имеет мощность не меньше мощности множества всех подмножеств натуральных чисел (для конечного множества, состоящего из $%n$% элементов, $%n!>2^n\quad,n>4$%). С другой стороны мощность подстановок равна мощности некоторого множества действительных чисел из промежутка $%(0;1)$%. Из вышеприведенных соображений, следует, что мощность множества перестановок натуральных чисел равна $%c.$%

Дополнение.Можно также аккуратным образом каждому подмножеству натуральных чисел поставить в соответствие некоторую подстановку натуральных чисел так, что разным подмножествам будут соответствовать разные подстановки.

ссылка

отвечен 29 Апр '13 19:40

изменен 30 Апр '13 13:40

Первое соображение, основанное на неравенстве $%n! > 2^n$%, не может иметь следствием тот факт, что перестановок на $%{\mathbb N}$% не меньше, чем подмножеств. Сам факт, разумеется, верен, но таким способом его нельзя обосновать. Это рассуждение выглядит некорректным. Из анализа конечных подмножеств здесь ничего не следует.

Для доказательства того, что подстановок не меньше, чем вещественных чисел, надо построить соответствующее инъективное отображение. Это можно сделать многими способами, но без явного построения такой факт всё-таки нельзя считать полностью очевидным.

(29 Апр '13 19:51) falcao

Но, если брать ряд первых $%n$% натуральных чисел, при этом $%n$% может быть как угодно большим, то где может наступить "сбой"?

(29 Апр '13 20:05) Anatoliy

Здесь просто нет соответствия между одним и другим. Подмножеству в $%{\mathbb N}$% можно сопоставить последовательность его "срезов" в виде пересечений с $%\{1,2,..,n\}$%. Но что делать с перестановками? Они ведь не оставляют инвариантными начальные отрезки натурального ряда. Вот возьмём для примера какое-то подмножество -- например, простых чисел. Ему соответствуют какие-то "срезы". Как по ним построить перестановку всего натурального ряда, чтобы она соответствовала этим "срезам"?

(29 Апр '13 20:25) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×134

задан
29 Апр '13 12:21

показан
2013 раз

обновлен
30 Апр '13 13:40

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru