множества - Доказать, что множество биекций $%N \rightarrow N$% имеет мощность континуум

Я не понял смысл приведённого рассуждения. Прежде всего, биекцию $%\mathbb N$% на $%\mathbb N$% мы записываем не в виде множества, а в виде последовательности. Берутся все натуральные числа и располагаются в определённом порядке: $%a_1$%, $%a_2$%, ... , $%a_n$%, ... , где каждое число встречается ровно один раз. Множество при этом всегда оно и то же -- это само $%\mathbb N$%. От перестановки элементов множество не меняется, а вот последовательность меняется, поэтому именно этот термин и должен использоваться.

Далее, я так понял, Вы хотите применить тот факт, что множество всех подмножеств $%\mathbb N$% имеет мощность континуума, причём брать можно только бесконечные подмножества, так как конечных подмножеств счётное количество. Это верно, но отсюда пока ещё не получается доказательство, так как подмножества -- это одно, а биекции -- совсем другое.

Мне кажется, здесь в доказательстве имеет смысл использовать теорему Кантора - Бернштейна, так как требуемую биекцию построить довольно сложно, и легче доказать два факта. Первый, что биекций $%\mathbb N$% на $%\mathbb N$% не меньше континуума, а второй -- что их не больше континуума.

Докажем первое утверждение. Будем опираться на то, что имеется континуум бесконечных двоичных последовательностей типа 01100010... . Это фактически то же самое, что числа промежутка $%[0;1)$%, записанные в двоичной форме с участием запятой в начале. При этом 1 не может возникать в периоде -- подобно тому, как 9 не бывает периодом десятичных дробей. И здесь возможна такая интерпретация: каждой последовательности нулей и единиц сопоставляем подмножество в $%\mathbb N$% по такому правилу. Если на $%n$%-м месте стоит цифра 0, то считаем, что $%n$% принадлежит нашему подмножеству, а если 1, то не принадлежит. Например, множество нечётных чисел будет закодировано как 010101..., множество чётных как 101010..., множество простых как 10010101110.. и тому подобное. Это взаимно-однозначное соответствие между двоичными последовательностями и подмножествами $%\mathbb N$%. Если 1 получается в периоде, то это в точности означает, что наше подмножество конечно. Такие последовательности можно не рассматривать. И тогда получается биекция между множеством бесконечных подмножеств $%\mathbb N$% и множеством вещественных чисел промежутка $%[0;1)$%. Последних имеется континуум, поэтому далее я буду рассматривать множество двоичных последовательностей как "образец" континуума.

Итак, сейчас мы хотим показать, что биекций $%\mathbb N$% на $%\mathbb N$% не меньше континуума. Для этого по каждой двоичной последовательности типа 011010001... строим свою биекцию по определённому правилу. Я возьму такое правило: все натуральные числа разобью на пары соседних: 1 и 2, 3 и 4, и так далее. В $%n$%-ю пару войдут $%2n-1$% и $%2n$%. Теперь я смотрю на последовательность из нулей и единиц, и начинаю располагать натуральные числа в определённой последовательности. Если я вижу на $%n$%-м месте 0, то числа $%2n-1$% располагаю по порядку. А если вижу 1, то беру эти числа в обратном порядке. По той последовательности, которую я написал чуть выше, у меня получится 1,2,4,3,6,5,7,8,10,9, .... и так далее. Это не что иное как биекция $%\mathbb N$% на $%\mathbb N$%, где 1 переходит в 1, 2 переходит в 2, 3 переходит в 4, 4 переходит в 3, и так далее. Разумеется, не каждая биекция имеет такой вид, но нам здесь важно, что для каждой двоичной последовательности получается биекция, причём своя. Это рассуждение обосновывает тот факт, что биекций $%\mathbb N$% на $%\mathbb N$% имеется по крайней мере континуум.

Теперь докажем второе утверждение: что биекций не больше континуума. Здесь удобно доказать более сильный факт, что вообще отображений $%\mathbb N$% в $%\mathbb N$% имеется не больше континуума. Каждое такое отображение есть последовательность натуральных чисел, где числа могут повторяться, могут отсутствовать и так далее.

Пусть у нас в последовательности натуральных чисел встретилось число $%k$%. Тогда мы пишем $%k$% нулей и одну единицу за ними. Скажем, 001000100101... будет кодом последовательности 2,3,2,1,... и так далее. Понятно, что каждая последовательность натуральных чисел получает при этом свой двоичный код, по которому её можно восстановить. Это задаёт инъекцию из множества всех отображений ($%\mathbb N$% в $%\mathbb N$%) в множество двоичных последовательностей, откуда можно сделать вывод, что таких отображений не больше континуума.