Рассмотрим отношение $%R$% на множества подмножеств N; $% (A,B) \in R$% $% \leftrightarrow$% А отличается от В на конечное число элементов. Доказать, что $%R$% - отношение эквивалетности. Верно ли, что в каждом классе эквивалентности счетное число элементов? Верно ли, самих классов счетное количество?

задан 30 Сен '15 1:02

10|600 символов нужно символов осталось
1

Прежде всего, удобно дать определение понятия "множества $%A$% и $%B$% отличаются элементом $%n$%". Это значит, что либо $%n\in A$% и $%n\notin B$%, либо $%n\in B$% и $%n\notin A$%. Соответственно, "множества $%A$% и $%B$% не отличаются элементом $%n$%" означает, что $%n\in A\Leftrightarrow n\in B$%.

Отношение здесь задаётся условием, что симметрическая разность $%A\Delta B=(A\setminus B)\cup(B\setminus A)$% конечна. Рефлексивность и симметричность очевидны, а для проверки транзитивности надо заметить, что если $%A$% и $%C$% отличаются элементом $%n$%, то верно хотя бы одно из условий $%n\in A\Delta B$% или $%n\in B\Delta C$%. В противном случае $%n\in A\Leftrightarrow n\in B\Leftrightarrow n\in C$%, то есть $%A$% и $%C$% этим элементом не отличаются. Из сказанного следует, что имеет место включение $%A\Delta C\subseteq(A\Delta B)\cup(B\Delta C)$%, и потому $%A\Delta C$% конечно.

То, что класс эквивалентности каждого множества $%A$% счётен, верно. Для начала проверим, что он бесконечен. Множество $%A$% или бесконечно, или обладает бесконечным дополнением. В первом случае из $%A$% можно исключить элемент бесконечным числом способов, и при этом получаются разные эквивалентные ему множества. Во втором случае в $%A$% бесконечным числом способов можно включить один новый элемент.

Счётность класса вытекает из того, что эквивалентное данному множество $%B$% однозначно восстанавливается по упорядоченной паре $%(A\setminus B,B\setminus A)$% двух конечных множеств. Хорошо известно, что множество конечных подмножеств в $%\mathbb N$% счётно (здесь имеется простое и естественное кодирование), а декартово произведение счётных множеств счётно.

Самих классов имеется континуум, что достаточно просто доказывается. Но в задаче достаточно показать, что это множество несчётно. Это делается от противного: если множество разбито на счётное число счётных классов эквивалентности, то оно само счётно как счётное объединение счётных множеств. А наше множество равно $%{\cal P}(\mathbb N)$%, и потому континуально.

ссылка

отвечен 30 Сен '15 1:36

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,500
×83

задан
30 Сен '15 1:02

показан
1151 раз

обновлен
30 Сен '15 1:36

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru