| |||
|
|
Задачка: Счетно ли множество всех конечных подмножеств натуральных чисел? Верно ли такое решение (ответ -- счетно): Запишем каждое подмножество как последовательность из нулей и единиц так, что на месте чисел, лежащих в подмножестве, стоят 1, а на месте чисел, не лежащих в подмножестве, стоит 0. Например, {1,2,5} -- 110010000... Теперь занумеруем все подмножества. Рассмотрим запись целых чисел в двоичной системе счисления. Будем брать двоичное число, записывать его наоборот (младший разряд слева) и приписывать справа бесконечно много нулей. 0 -> 0000000... 1 -> 1000000... 10 -> 0100000... 11 -> 1100000... 100 -> 0010000... 101 -> 1010000... 110 -> 0110000... 111 -> 1110000... ... Так рано или поздно мы доберемся до любой конечной последовательности из нулей и единиц. Именно, чтобы узнать номер данной последовательности, обрежем ее по последней единице, за которой начинается бесконечность нулей (мы знаем, когда начинаются нули, потому нам известно, что подмножество конечно, и значит, известен его последний элемент -- последняя единица в последовательности). Затем перевернем получившееся число -- это и будет номер последовательности в двоичной системе счисления. Добавить комментарий: |
|||