Как доказать это или где можно почитать доказательство этого факта?

Question

[MuffinLover3]

Множество всех конечных подмножеств счётного множества счётно

Comments

[Lynn «Кофеман»]

https://ru.m.wikipedia.org/wiki/%D0%A1%D1%87%D1%91...

не более чем счётное (конечное или счётное) объединение не более чем счётных множеств является не более чем счётным множеством.

Доказать что множество всех подмножеств состоящих ровно из N элементов счётно оставляю как домашнее задание

Answer 1

[Wataru]

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

Так можно по номеру получить уникальное подмножество и любое подмножество имеет какой-то номер. Все. Вот мы и занумеровали множество всех подмножеств натуральными числами. Оно счетно.

Comments

[MuffinLover3]

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

[Wataru]

MuffinLover3, А как вы себе представляете, какой номер будет иметь число с бесконечным количеством единиц в двоичной записи? Подмножества конечные => конечное количество единиц => конечный номер у элемента. С бесконечными никакую нумерацию счетную не задать.