Задачи на счетность множеств

[Egornn]

Является ли счетным множество
а)Четных чисел кратных 9
б)целых чисел не кратных 3
в) рациональных чисел

[Виктор Викторов]

Да.

[caxap]

а, б) Составьте биекцию c $\mathbb N$
в) Составьте биекцию с $\mathbb Z\times \mathbb N\sim\mathbb N$.

[mihailm]

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

в) Составьте биекцию с $\mathbb Z\times \mathbb N\sim\mathbb N$.

там не биекция

[caxap]

Ага, извиняюсь. Тогда можно учесть, что множество несократимых дробей с данным знаменателем счётно.

-- 19 фев 2011, 23:25 --

Для явной биекции с $\mathbb N$ можно использовать дерево Штерна--Броко.

[Legioner93]

Можно так доказать счётность рациональных. Сначала покажем счётность неотрицательных рац. чисел. Высотой несократимой дроби (рац. числа) назовем сумму числителя и знаменателя. Очевидно, что кол-во неотрицательных рац. чисел с определенной высотой конечно, и что высота определятся однозначно для любого рационального числа. Тогда все неотрицательные рациональные числа можно упорядочить так: $\frac{0}{1}$ (высота 1); $\frac{1}{1}$ (высота 2); $\frac{1}{2}$, $\frac{2}{1}$ (высота 3); $\frac{1}{3}$, $\frac{3}{1}$ (высота 4); $\frac{1}{4}$, $\frac{2}{3}$, $\frac{3}{2}$, $\frac{4}{1}$ (высота 5); ...
Далее после каждого члена последовательности (кроме нуля) добавляем соответствующее отрицательное число. Q.E.D.