Счётность конечных подмножеств

[Manticore]

Задание: Докажите, что множество всех конечных подмножеств данного счётного множество счётно.

Вообще, я хочу понять, какое решение самое простое. Мне говорили, что можно через индукцию, но у меня почему-то не вышло. Моё же решение не принимают, и хотел спросить у вас, как его можно подправить (если вообще можно).
Я решал так:
$A=\{a_1, a_2,...,a_n,...\}$ - исходное счётное множество (будем считать, что это натуральный ряд).
$B \subset A$, $B=\{a_{k1}, a_{k2},..., a_{km}\}$, где $a_{ki} \in A$
Будем определять подмножество $B$ так: пусть $a_{ki}$ входит в данное подмножество, тогда на его месте будем писать $1$, в противном случае - $0$. Получатся последовательности вида:
$B'_1=(1,1,0,...,1)$
$B'_2=(1,0,1,...,0)$ и так далее.
Получаем наборы из нулей и единиц - двоичный код переводим в десятичную систему счисления, и тогда получится, что каждому конечному подмножеству соответствует натуральное число.
Мы не можем получить несколько одинаковых последовательностей, потому что количество элементов последовательности равно значению последнего элемента подмножества. Например: $B_1=\{4,7,8\}$, тогда $B'_1=(0,0,0,1,0,0,1,1)$
Но тут возникает проблема: возьмём какое-нибудь $B_2=\{1,4,5\}, B'_2=(1,0,0,1,1)$, т.е. $B_1$ и $B_2$ соответствуют одинаковые натуральные числа
Может, нужно "закодировать" длину? Например, пусть будут упорядоченные пары $<a,b>$ такие, что $a$ - двоичная последовательность, $b$ - количество элементов соответствующего подмножества (натуральное число). Тогда инвертируем последовательность в десятичную систему счисления и приписываем число, соответствующее числу элементов. Или так нельзя?
Подскажите, пожалуйста.

[arseniiv]

А вы не можете использовать теорему о том, что объединение счётного числа не более чем счётных множеств не более чем счётно?

[mihailm]

Считаем все подмножества натурального ряда.
Начинаем считать те подмножества сумма элементов которых равна 1 (таких немного), потом тех у которых соответствующая сумма 2 и т.д. - все пересчитали, все доказано

[Manticore]

arseniiv
В списке есть задание - доказать как раз эту теорему, я не сообразил, что здесь она легко применяется. Спасибо большое.
mihailm
И Вам спасибо за ответ!

[iifat]

Пишите ваши наборы 0/1 справа налево.

[Manticore]

iifat в сообщении #770939 писал(а):

Пишите ваши наборы 0/1 справа налево.

Те, которые совпадают? Т.е. один набор - слева направо, другой - наоборот.
Но всё равно могут совпасть.

[Null]

Manticore в сообщении #771007 писал(а):

iifat в сообщении #770939 писал(а):

Пишите ваши наборы 0/1 справа налево.

Те, которые совпадают? Т.е. один набор - слева направо, другой - наоборот.
Но всё равно могут совпасть.

Все наборы.

[Manticore]

Null в сообщении #771008 писал(а):

Все наборы.

Всё, понял. Спасибо за помощь.