Доказать, что не существует сюръекции из $%X \rightarrow 2^X$% и инъекции из $%2^X \rightarrow X$% Как решить задачу без теоремы Кантора или Кантора-Бернштейнв, в общем с минимумом техники

задан 5 Окт '15 3:45

изменен 6 Окт '15 15:16

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

Второе сводится к первому: по инъекции $%Y$% в $%X$% для непустого $%Y$% легко строится сюръекция $%X$% на $%Y$%. А именно, те элементы $%X$%, которые имеют прообраз, в него и переводим, а остальные переводим в фиксированный элемент множества $%Y$%.

Теперь достаточно проверить, что никакое отображение $%f\colon X\to2^X$% не сюръективно. Для этого достаточно построить подмножество, не принадлежащее образу. Пусть $%Z=\{x\in X\mid x\notin f(x)\}$%. Это элемент булеана. По построению, $%x\in Z$% равносильно $%x\notin f(x)$% для всех $%x\in X$%. Если допустить, что $%Z$% принадлежит образу $%f$%, то есть существует $%a\in X$% такой, что $%f(a)=Z$%, получается логическое противоречие: $%a\in f(a)$% равносильно своему отрицанию $%a\notin f(a)$%.

Это и есть прямое доказательство требуемого факта, то есть фактически теорема Кантора. А кто такой Торез? Я знаю только деятеля французской компартии с такой фамилией, но он вроде как математикой не занимался :)

ссылка

отвечен 5 Окт '15 4:31

1

@falcao спасибо! А Торез это автозамена слова "теорема")

(6 Окт '15 15:17) sapere aude

@sapere aude: никогда бы не догадался до причины! По идее, спелл-чекер слово "теорема" точно знает, но если там была опечатка (типа пропущенной случайно буквы "е"), но легко мог появиться и товарищ Торез! :)

(6 Окт '15 16:06) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×354
×144

задан
5 Окт '15 3:45

показан
1147 раз

обновлен
6 Окт '15 16:06

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

по почте:

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

по RSS:

Ответы

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

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