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

[Надин]

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

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

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

[Lapp]

Гость, что ты мудришь?.. Мне кажется, ты не только себя, ты всех запутал ).
Зачем какие-то p и q? Зачем их делить??.. При чем тут они вообще?
Доказательство я привел выше. Могу сделать еще несколько пояснений, если хочешь.

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

Так что осталось только доказать, что множество четверок натуральных чисел счетно. Доказать это нетрудно простым пересчетом. Я привел алгоритм пересчета выше. Он основывается на "змейке", которую легко продемонстрировать на "двойках" чисел, при этом ясно, что способ легко распространяется на "тройки", четверки" и вообще "n-ки" натуральных чисел. Пересчет "змейкой" начинается с элемента (1,1) и дальше идет серпантином (serpent - змея).

Код

11-12 13-14 15- ...
  /  /  /  /  /
21 22 23 24 25 ...
| /  /  /  /  /
31 32 33 34 35 ...
  /  /  /  /  /
41 42 43 44 45 ...
| /  /  /  /  /
51 52 53 54 55 ...
  /  /  /  /  /

то есть 11, 12, 21, 31, 22, 13, 14, 23, 32, 41, 51, 42, 33 ...
- это все не двузначные числа, а пары однозначных чисел; я не стал ставить разделители между цифрами, чтоб не загромождать картинку.

Для иллюстрации также можешь глянуть на мое фото http://forum.pascal.net.ru/index.php? s=&showtopic=6163&view=findpost&p=67617 . Кроме того, можешь посмотреть сюда: Математическая логика - и сюда: Биекция (в последней ссылке вариант змейки немного другой, но это несущественно).

Если еще что-то неясно - спрашивай .