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

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

| A | = | B | . {displaystyle |A|=|B|.}

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

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

История

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

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

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

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

Пусть

C 0 = A ∖ g ( B ) , {displaystyle C_{0}=Asetminus g(B),}

и

C n + 1 = g ( f ( C n ) ) {displaystyle C_{n+1}=g(f(C_{n}))quad } при n ⩾ 0 {displaystyle ngeqslant 0}

и

C = ⋃ n = 0 ∞ C n . {displaystyle C=igcup _{n=0}^{infty }C_{n}.}

Тогда для любого x ∈ A {displaystyle xin A} положим

h ( x ) = { f ( x ) if  x ∈ C g − 1 ( x ) if  x ∉ C {displaystyle h(x)=left{{egin{matrix}f(x)&,,{mbox{if }}xin Cg^{-1}(x)&{mbox{if }}x ot in Cend{matrix}} ight.}

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

Осталось проверить, что h : A → B {displaystyle h:A o B} — биекция.

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

Нужно доказать, что ∀ y ∈ B ∃ x ∈ A : h ( x ) = y {displaystyle forall yin Bexists xin A:h(x)=y}
∀ y ∈ B {displaystyle forall yin B}

I       {displaystyle mathrm {I} } Если y ∈ f ( C ) {displaystyle yin f(C)} , то ∃ x ∈ C f ( x ) = y {displaystyle exists xin Cf(x)=y} . Тогда h ( x ) = f ( x ) = y {displaystyle h(x)=f(x)=y}

I I y ∉ f ( C ) {displaystyle mathrm {II} ;y otin f(C)}
Пусть x = g ( y ) {displaystyle x=g(y)} . Предположим, x ∈ C {displaystyle xin C} . Тогда x ∈ C n {displaystyle xin C_{n}} , при n > 0 {displaystyle n>0} , значит x ∈ g ( f ( C n − 1 ) ) {displaystyle xin g(f(C_{n-1}))} ,
⇒ ∃ c ∈ C n − 1 x = g ( f ( c ) ) x = g ( y ) } ⇒ {displaystyle Rightarrow exists cin C_{n-1}{egin{matrix}x=g(f(c))x=g(y)end{matrix}}{Bigg }}Rightarrow } , так как g {displaystyle g} — инъекция, то y = f ( c ) ∈ f ( C ) {displaystyle y=f(c)in f(C)} , что противоречит предположению.
Значит x ∉ C {displaystyle x otin C} . Тогда h ( x ) = g − 1 ( x ) = g − 1 ( g ( y ) ) = y {displaystyle h(x)=g^{-1}(x)=g^{-1}(g(y))=y}

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

Нужно доказать, что h ( x 1 ) = h ( x 2 ) ⇒ x 1 = x 2 {displaystyle h(x_{1})=h(x_{2})Rightarrow x_{1}=x_{2}}

I x 1 , x 2 ∈ C {displaystyle mathrm {I} ;x_{1},x_{2}in C}
f ( x 1 ) = f ( x 2 ) ⇒ x 1 = x 2 {displaystyle f(x_{1})=f(x_{2})Rightarrow x_{1}=x_{2}} ( f {displaystyle f} — инъекция)

I I x 1 , x 2 ∉ C {displaystyle mathrm {II} ;x_{1},x_{2} otin C}
g − 1 ( x 1 ) = g − 1 ( x 2 ) ⇒ x 1 = g ( g − 1 ( x 1 ) ) = g ( g − 1 ( x 2 ) ) = x 2 {displaystyle g^{-1}(x_{1})=g^{-1}(x_{2})Rightarrow x_{1}=g(g^{-1}(x_{1}))=g(g^{-1}(x_{2}))=x_{2}}

I I I x 1 ∈ C , x 2 ∉ C {displaystyle mathrm {III} ;x_{1}in C,x_{2} otin C}
h ( x 1 ) = f ( x 1 ) , h ( x 2 ) = g − 1 ( x 2 ) {displaystyle h(x_{1})=f(x_{1}),h(x_{2})=g^{-1}(x_{2})}
h ( x 1 ) = h ( x 2 ) {displaystyle h(x_{1})=h(x_{2})}
x 2 = g ( h ( x 2 ) ) = g ( h ( x 1 ) ) = g ( f ( x 1 ) ) ∈ C {displaystyle x_{2}=g(h(x_{2}))=g(h(x_{1}))=g(f(x_{1}))in C} . Значит, этот случай невозможен.

Замечание

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