Теория множеств, счетность и континуум Опции

[Надин]

Мне опять приходится обращаться к Вам за помощью. Чем ближе к сессии, тем глупее я себя чувствую, в голове либо слишком много всего, либо совсем пусто. Не знаю, что делать... Помогите, пожалуйста!!!! Мой препод по матлогу меня не любит и специально дает задачи, к которым я не знаю с какой стороны подступиться!!! ПОЖАЛУЙСТА!!!!!

1.Доказать, что множество всех типов вида n/(2)^k + m/(3)^r, где n,m,r,k-натуральные числа, счетно.
2.Доказать, что множество всех бесконечных неубывающих последовательностей натуральных чисел имеет мощность континуума.

На интуитивном уровне все дейтсвительно понятно, но как объяснить это преподу.

[Lapp]

кроме как множество всех чисел вида и т.д, ничего в голову не приходит.

Ну, если это просто числа такого вида, то все очень просто. Их можно отобразить на множество целых положительных точек в четырехмерном пространстве в декартовых координатах. Для начала представь себе двумерное (что, кстати, соответствует просчету пар, то есть доказывает счетность рациональных чисел). Это выглядит примерно так:

^
| . . . . . . . . .
| . . . . . . . . .
| . . . . . . . . .
| . . . . . . . . .
| . . . . . . . . .
| . . . . . . . . .
+------------------->

- их можно пересчитать с помощью уже известной тебе змейки. Попробуй представить себе, как ляжет змейка в трехмерном пространстве - это неплохая разминка для пространственого воображения. Далее, если преп поверит тебе на слово, что ты можешь сделать змейку в четырехмерном пространстве ("У каждой женщины должна быть змея.." © Аквариум), то все ок, если нет - то дай ему такой агоритм:

1 1 1 1
2 1 1 1
1 2 1 1
1 1 2 1
1 1 1 2
2 2 1 1
2 1 2 1
2 1 1 2
2 2 2 1
2 2 1 2
2 2 2 2
3 1 1 1
3 2 1 1
3 1 2 1
3 1 1 2
3 2 2 1
3 2 1 2
3 2 2 2
3 3 1 1
3 3 2 1
3 3 1 2
3 3 2 2
3 3 3 1
3 3 3 2
3 3 3 3
4 1 1 1
4 2 1 1
. . . .
- ой, я, кажется, увлекся.. Затягивает, как семечки
Короче, все это хозяйство пересчитывается легко.

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

А тут тебе нужно использовать Канторову диагональ, но несколько модифицированную. Начать надо с того, что сузить данное множество. Возьмем только те последовательности, которые не имеют предела (или их предел равен плюс бесконечности). Далее от противного: предположим, что их множество счетно. Расположим их в том порядке, в котором они просчитаны:

1.  a1  a2  a3  a4  a5  a6  a7  a8 ...
2.  b1  b2  b3  b4  b5  b6  b7  b8 ...
3.  c1  c2  c3  c4  c5  c6  c7  c8 ...
4.  d1  d2  d3  d4  d5  d6  d7  d8 ...
5.  e1  e2  e3  e4  e5  e6  e7  e8 ...
6.  ............
..........

Теперь составим номую последовательность {Xn}. Первый элемент возьмем такой
x1 = a1 + 1
Далее переходим ко второй последовательности, {Bn}, и действем по такому правилу:
- начинаем со второго элемента, b2.
- если он больше либо равен x1, то полагаем x2 = b2 + 1,
- если нет, то x2 = x1 и переходим к b3.
- так находим элемент последовательности {B}, больше либо равный x1, по пути заполняя пустые места значением x1. Означенный элемент должен найтись обязательно в соотвествии с определением предела (мы взяли только те последовательности, которые стремятся к бесконечности). Обозначим его номер в {B} как n2. Полагаем xn2=bn2+1.
- Теперь переходим к последовательности {C}, начав с элемента n2+1, и проводим с ней те же самые действия, найдя таким образом элемент n3, для которого cn3>=xn2, и полагаем xn3=cn3+1.
- Повторяем эту процедуру по порядку до бесконечности.

В результате мы получим последовательность {Xn}, которая, во-первых, неубывающая, а во-вторых она отличается от всех присутствующих в изначальном списке последовательностей (по построению), то есть она оказалась непросчитанной. Полученное противоречие доказывает несчетность множества стремящихся к бесконечности неубывающих последовательностей. А поскольку это есть подмножество данного нам множества, то заключаем, что оно также несчетно. Это оценка снизу.

Далее, данное множество в свою очередь является подмножеством множества всех последовательностей натуральных чисел, которое имеет мощность континуума. Это оценка сверху.

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