Пример решения задания 3.4.

Доказать, что множество всех конечных последовательностей, составленных из элементов некоторого счётного множества, счётно.

Доказательство. Пусть множество счётно, . Обозначим через множество конечных последовательностей длины , составленных из элементов множества , . Покажем, что для любого натурального множество – счётно.

Пусть

– сумма индексов у равна ,

– сумма индексов у равна ,

– сумма индексов у равна и т.д.

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

Выпишем элементы множества в виде бесконечной таблицы, где (табл. 3).

Таблица 3

				. . .
				. . .
				. . .
. . .	. . .		. . .	. . .

Будем обходить таблицу по маршруту, помеченному стрелками. По мере движения по этому маршруту будем присваивать номера: , , 4 и т.д.

Имеем, что для любых индексов последовательность получит когда-нибудь единственный номер.

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