Теорема Кантора — Бернштейна

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Cantor-Bernstein.jpg

Теорема Кантора — Бернштейна (в англ. литературе теорема Кантора — Бернштейна — Шрёдера), утверждает, что если существуют инъективные отображения и между множествами и , то существует взаимооднозначное отображение . Другими словами, что мощности множеств и совпадают:

Другими словами, теорема утверждает следующее:

Из и следует, что где кардинальные числа.

История[править | править вики-текст]

Теорема названа в честь Георга Кантора, Феликса Бернштейна и Эрнста Шрёдера.

Первоначальное доказательство использовало аксиому выбора, однако эта аксиома необязательна для доказательства данной теоремы.

Эрнст Шрёдер первым сформулировал теорему, но опубликовал неправильное доказательство. Независимо эта теорема была сформулирована Кантором.[источник не указан 2619 дней] Ученик Кантора Феликс Бернштейн опубликовал диссертацию, содержащую полностью корректное доказательство.

Доказательство[править | править вики-текст]

Пусть

и

при

и

Тогда, для любого положим

Если не лежит в , тогда должен быть в (образе множества под действием отображения ). И тогда существует , и отображение.

Осталось проверить, что - биекция.

Проверим, что h - сюрьекция.

Нужно доказать, что

Если , то . Тогда


Пусть . Предположим, . Тогда , при , значит ,
, т. к. - инъекция, то , что противоречит предположению.
Значит . Тогда

Проверим, что h - инъекция.

Нужно доказать, что


( - инъекция)






Значит этот случай невозможен.

Замечание[править | править вики-текст]

Определение отображения выше неконструктивно, то есть не существует алгоритма определения за конечное число шагов, лежит ли некоторый элемент множества в множестве или нет. Хотя для некоторых частных случаев такой алгоритм существует.

См. также[править | править вики-текст]

Литература[править | править вики-текст]

  • Ершов Ю. Л., Палютин Е. А. Математическая логика: Учебное пособие. — 3-е, стереотип. изд. — СПб.: «Лань», 2004. — 336 с.