Задачка:

Счетно ли множество всех конечных подмножеств натуральных чисел?

Верно ли такое решение (ответ -- счетно):

Запишем каждое подмножество как последовательность из нулей и единиц так, что на месте чисел, лежащих в подмножестве, стоят 1, а на месте чисел, не лежащих в подмножестве, стоит 0.
Например, {1,2,5} -- 110010000...

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

0 -> 0000000...
1 -> 1000000...
10 -> 0100000...
11 -> 1100000...
100 -> 0010000...
101 -> 1010000...
110 -> 0110000...
111 -> 1110000...
...

Так рано или поздно мы доберемся до любой конечной последовательности из нулей и единиц. Именно, чтобы узнать номер данной последовательности, обрежем ее по последней единице, за которой начинается бесконечность нулей (мы знаем, когда начинаются нули, потому нам известно, что подмножество конечно, и значит, известен его последний элемент -- последняя единица в последовательности). Затем перевернем получившееся число -- это и будет номер последовательности в двоичной системе счисления.

Предъявлена биекция между множеством и натуральными числами в двоичной записи. Нужно что-то еще?

Сопоставляем каждому числу подмн-во, содержащее только его - инъекция из чисел в подмножества.
Сопоставляем каждому подмн-ву его двоичный код (как вы это сделали, а спереди дописываем единичку, чтобы разное кол-во нулей впереди различалось), получаем натуральное число в двоичной записи - инъекция из подмн-в в числа.

По теореме Кантора-Бернштейна они равномощны.

Так получается короче ^_^

Зачем единичку, не надо единичку: я ищу последнюю единицу в двоичной записи подмножества, обрезаю по ней, и переворачиваю число -- то есть у меня эта последняя единичка выходит первой слева в получившемся двоичном числе.

Кроме того, у меня одна биекция, а у вас две инъекции. Но все это, видимо, детали. Ответ на мой вопрос, как я понимаю, да (т. е. решение верное)?