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

Теорема Кантора — Бернштейна (в англ. литературе теорема Кантора — Бернштейна — Шрёдера), утверждает, что если существуют инъективные отображения <math>f:A\to B</math> и <math>g:B\to A</math> между множествами <math>A</math> и <math>B</math>, то существует взаимооднозначное отображение <math>h:A\to B</math>. Другими словами, что мощности множеств <math>A</math> и <math>B</math> совпадают:

<math>|A|=|B|.</math>

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

Из <math>\mathfrak{a} \leqslant \mathfrak{b}</math> и <math>\mathfrak{b} \leqslant \mathfrak{a}</math> следует, что <math>\mathfrak{a} = \mathfrak{b},</math> где <math>\mathfrak{a}, \mathfrak{b}</math> — кардинальные числа.

История

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

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

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

Доказательство

Пусть

<math>C_0=A\setminus g[B],</math>

и

<math>C_{n+1}=g[f[C_n]]\quad</math> при <math>n\geqslant 0</math>

и

<math>C=\bigcup_{n=0}^\infty C_n.</math>

Тогда, для любого <math>x\in A</math> положим

<math>

h(x)=\left\{ \begin{matrix} f(x) & \,\,\mbox{if }x\in C \\ g^{-1}(x) & \mbox{if }x\not\in C \end{matrix} \right. </math>

Если <math>x</math> не лежит в <math>C</math>, тогда <math>x</math> должен быть в <math>g[B]</math> (образе множества <math>B</math> под действием отображения <math>g</math>). И тогда существует <math>g^{-1}(x)</math>, и <math>h</math> отображение.

Осталось проверить, что <math>h:A\to B</math> - биекция.

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

Нужно доказать, что <math>\forall y \in B \exists x \in A: h(x)=y </math>
<math>\forall y \in B</math>

<math>\mathrm{I} \ \ \ </math> Если <math>y \in f(C)</math>, то <math>\exists x \in C f(x) = y </math>. Тогда <math>h(x)=f(x)=y</math>

<math>\mathrm{II}\; y \notin f(C)</math>
Пусть <math>x=g(y)</math>. Предположим, <math>x \in C</math>. Тогда <math>x \in C_n</math>, при <math>n>0</math>, значит <math>x \in g(f(C_{n-1}))</math>,
<math>\Rightarrow \exists c \in C_{n-1} \begin{matrix} x=g(f(c))\\ x=g(y) \end{matrix} \Bigg\} \Rightarrow </math>, т. к. <math>g</math> - инъекция, то <math>y=f(c) \in f(C)</math>, что противоречит предположению.
Значит <math>x \notin C</math>. Тогда <math>h(x)=g^{-1}(x)=g^{-1}(g(y))=y</math>

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

Нужно доказать, что <math> h(x_1) = h(x_2) \Rightarrow x_1 = x_2</math>

<math>\mathrm{I}\; x_1,x_2 \in C</math>
<math> f(x_1)=f(x_2) \Rightarrow x_1=x_2</math> ( <math>f</math> - инъекция)

<math>\mathrm{II}\; x_1,x_2 \notin C</math>
<math> g^{-1}(x_1)=g^{-1}(x_2) \Rightarrow x_1=g(g^{-1}(x_1))=g(g^{-1}(x_2))=x_2</math>

<math>\mathrm{III}\; x_1 \in C,x_2 \notin C</math>
<math> h(x_1)=f(x_1), h(x_2)=g^{-1}(x_2)</math>
<math>h(x_1)=h(x_2)</math>
<math>x_2=g(h(x_2))=g(h(x_1))=g(f(x_1))\in C </math> Значит этот случай невозможен.

Замечание

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

См. также

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

Литература

• Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств.

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

Отрывок, характеризующий Теорема Кантора — Бернштейна

Один из докторов, в окровавленном фартуке и с окровавленными небольшими руками, в одной из которых он между мизинцем и большим пальцем (чтобы не запачкать ее) держал сигару, вышел из палатки. Доктор этот поднял голову и стал смотреть по сторонам, но выше раненых. Он, очевидно, хотел отдохнуть немного. Поводив несколько времени головой вправо и влево, он вздохнул и опустил глаза.
– Ну, сейчас, – сказал он на слова фельдшера, указывавшего ему на князя Андрея, и велел нести его в палатку.
В толпе ожидавших раненых поднялся ропот.
– Видно, и на том свете господам одним жить, – проговорил один.
Князя Андрея внесли и положили на только что очистившийся стол, с которого фельдшер споласкивал что то. Князь Андрей не мог разобрать в отдельности того, что было в палатке. Жалобные стоны с разных сторон, мучительная боль бедра, живота и спины развлекали его. Все, что он видел вокруг себя, слилось для него в одно общее впечатление обнаженного, окровавленного человеческого тела, которое, казалось, наполняло всю низкую палатку, как несколько недель тому назад в этот жаркий, августовский день это же тело наполняло грязный пруд по Смоленской дороге. Да, это было то самое тело, та самая chair a canon [мясо для пушек], вид которой еще тогда, как бы предсказывая теперешнее, возбудил в нем ужас.
В палатке было три стола. Два были заняты, на третий положили князя Андрея. Несколько времени его оставили одного, и он невольно увидал то, что делалось на других двух столах. На ближнем столе сидел татарин, вероятно, казак – по мундиру, брошенному подле. Четверо солдат держали его. Доктор в очках что то резал в его коричневой, мускулистой спине.
– Ух, ух, ух!.. – как будто хрюкал татарин, и вдруг, подняв кверху свое скуластое черное курносое лицо, оскалив белые зубы, начинал рваться, дергаться и визжат ь пронзительно звенящим, протяжным визгом. На другом столе, около которого толпилось много народа, на спине лежал большой, полный человек с закинутой назад головой (вьющиеся волоса, их цвет и форма головы показались странно знакомы князю Андрею). Несколько человек фельдшеров навалились на грудь этому человеку и держали его. Белая большая полная нога быстро и часто, не переставая, дергалась лихорадочными трепетаниями. Человек этот судорожно рыдал и захлебывался. Два доктора молча – один был бледен и дрожал – что то делали над другой, красной ногой этого человека. Управившись с татарином, на которого накинули шинель, доктор в очках, обтирая руки, подошел к князю Андрею. Он взглянул в лицо князя Андрея и поспешно отвернулся.
– Раздеть! Что стоите? – крикнул он сердито на фельдшеров.
Самое первое далекое детство вспомнилось князю Андрею, когда фельдшер торопившимися засученными руками расстегивал ему пуговицы и снимал с него платье. Доктор низко нагнулся над раной, ощупал ее и тяжело вздохнул. Потом он сделал знак кому то. И мучительная боль внутри живота заставила князя Андрея потерять сознание. Когда он очнулся, разбитые кости бедра были вынуты, клоки мяса отрезаны, и рана перевязана. Ему прыскали в лицо водою. Как только князь Андрей открыл глаза, доктор нагнулся над ним, молча поцеловал его в губы и поспешно отошел.