57 школа, 10 класс
23 сентября 2002 г.
Счётные множества

    Множество a называется счетным, если существует взаимно однозначное соответствие между  a и множеством натуральных чисел N. Другими словами, множество называется счётным, если все его элементы можно пересчитать, но для пересчёта придётся использовать не первые несколько натуральных чисел, как мы привыкли, а все натуральные числа.
    Если множество не конечно и не счётно, то оно называется несчётным.

1.    Счётно ли:
    а)    Множество целых чисел?
    б)    Множество конечных  последовательностей нулей и единиц?    
    в)    NxN?
    г)     Q?
    д)    Объединение счетного числа счетных множеств?
    е)    Множество конечных последовательностей целых чисел?
    ж)   Множество всех конечных подмножеств счётного множества?

2.    Можно ли утверждать, что бесконечное подмножество счётного множества счётно?

3.    Назовём последовательность двоичной, если каждый её член равен 0 или1.
    а)    Пусть А1, А2, ..., Аn, ... -- бесконечные двоичные последовательности. Докажите, что существует бесконечная двоичная последовательность А, не совпадающая ни с одной из последовательностей Аi.
    б)    Счётно ли множество бесконечных двоичных последовательностей?
    в)    Счётно ли множество всех подмножеств натурального ряда?

4.    Можно ли утверждать, что в каждом бесконечном множестве найдется счётное подмножество?

5.    а)    Существует ли несчётное семейство попарно не пересекающихся подмножеств N?
    б)    Существует ли несчётное семейство подмножеств N, каждые два из которых имеют не более одного общего элемента?
    в)    не более семи общих элементов?
    г)    Назовем два множества почти не пересекающимися, если их пересечение конечно. Существует ли несчётное семейство попарно почти не пересекающихся подмножеств N?
    
6.    Назовём два множества сравнимыми, если одно из них является подмножеством другого. Существует ли несчетное семейство попарно сравнимых подмножеств счетного множества?