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

Теорема Кантора — Бернштейна (також теорема Кантора — Бернштейна — Шредера), стосується теорії множин та стверджує, що якщо в множині A елементів не менше, ніж в множині B (тобто, якщо в множині A існує підмножина, рівнопотужна множині B), а в множині B елементів не менше, ніж в множині A, то насправді елементів порівну, тобто існує бієкція (взаємно однозначна відповідність) між множинами A та B. Тобто: що якщо існують ін'єктивні відображення

Теорема Кантора — Бернштейна — Шредера
Названо на честь	Фелікс Бернштейн, Ернст Шредер і Георг Кантор
Досліджується в	теорія множин
Твердження описує	ін'єкція
Ким доведено	Ріхард Дедекінд і Фелікс Бернштейн
Підтримується Вікіпроєктом	Вікіпедія:Проєкт:Математика
Теорема Кантора — Бернштейна — Шредера у Вікісховищі

${\displaystyle f:A\to B}$ і ${\displaystyle g:B\to A}$ між множинами ${\displaystyle A}$ і ${\displaystyle B}$, то існує бієкція ${\displaystyle h:A\to B}$. Іншими словами, потужності множин ${\displaystyle A}$ і ${\displaystyle B}$ збігаються:

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

Неформально, теорема стверджує наступне: Із ${\displaystyle \alpha \leqslant \beta }$ і ${\displaystyle \beta \leqslant \alpha }$, випливає, що ${\displaystyle \alpha }$ = ${\displaystyle \beta }$. В даних нерівностях ${\displaystyle \alpha }$ і ${\displaystyle \beta }$ є кардинальними числами.

Доведення

Нехай, без обмеження загальності, множини A та B не перетинаються. Для будь-яких a в A чи b в B, ми можемо сформувати унікальну двосторонню послідовність елементів, що поперемінно належать A та B, шляхом почергового застосування ${\displaystyle f}$ та ${\displaystyle g}$ йдучи вправо і ${\displaystyle g^{-1}}$ та ${\displaystyle f^{-1}}$ вліво (де вони визначені).

${\displaystyle \cdots \rightarrow f^{-1}(g^{-1}(a))\rightarrow g^{-1}(a)\rightarrow a\rightarrow f(a)\rightarrow g(f(a))\rightarrow \cdots }$

Для будь-якого конкретного a, ця послідовність може припинитися в точці, де ${\displaystyle f^{-1}}$ чи ${\displaystyle g^{-1}}$ не визначені або не закінчуватися, якщо вони всюди визначені.

Назвемо таку послідовність (та усі її елементи) A-стопор, якщо вона зупиняється на елементі з A, чи B-стопор якщо вона зупиняється на елементі з B. Інакше, назвемо її подвійно безмежною, якщо всі елементи різні чи циклічною, якщо вони повторюються.

У силу того, що ${\displaystyle f}$ та ${\displaystyle g}$ є ін'єктивними функціями, кожен елемент a в A та b в B буде зустрічатися лише в одній такій послідовності, оскільки якщо б елемент зустрічався в двох послідовностях, всі елементи зліва і справа повинні були б бути однакові в обох з них, за визначенням.

У силу вище сказаного описані послідовності формують розбиття об'єднання множин A і B. Для A-стопора функція ${\displaystyle f}$ є бієкцією між елементами множин A і B в цій послідовності. Для B-стопора функція ${\displaystyle g}$ є бієкцією між елементами множин B і A в цій послідовності. Для подвійно безмежної чи циклічної послідовності можна використати будь-яку з двох функцій.

Інше доведення

Нехай

${\displaystyle C_{0}=A\setminus g[B],\!}$

і

${\displaystyle C_{n+1}=g[f[C_{n}]]\quad {\mbox{ for }}n\geqslant 0}$

і

${\displaystyle C=\bigcup _{n=0}^{\infty }C_{n}.}$

Тоді, для довільного ${\displaystyle x\in A}$ візьмемо

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

Якщо x не лежить в C, тоді x повинен бути в g[B] (образі множини B під дією відображення g). І тоді існує g ⁻¹(x), і h коректно визначене взаємно однозначне відображення (бієкція).

Можна перевірити, що ${\displaystyle h:A\to B}$ і є шукане взаємооднозначне відображення.

Зауважимо, що це визначення відображення h неконструктивне в тому сенсі, що не існує загального алгоритму визначення за скінченне число кроків для будь-яких заданих множин A, B і ін'єкцій f, g, чи лежить деякий елемент x множини A в множині C чи ні. Хоча для деяких окремих випадків, такий алгоритм існує.

Історія

Як це часто буває в математиці, назва цієї теореми не правильно відображає її історію. Традиційна назва «Шредера-Бернштейна» ґрунтується на двох доказах, опублікованих в 1898 році незалежно один від одного. Кантора часто додають до назви тому, що він вперше сформулював теорему в 1895 році, в той час як ім'я Шредера часто опускається, тому що його доведення виявилося помилковим, а ім'я математика, який вперше довів це не пов'язано з теоремою взагалі. Насправді, історія була більш складною:

• 1887 — Ріхард Дедекінд доводить теорему, але не публікує її.
• 1895 — Георг Кантор подає твердження теореми у своїй першій роботі з теорії множин.
• 1896 — Ернст Шредер оголосив про доведення теореми.
• 1897 — Фелікс Бернштейн, молодий студент подав своє доведення на семінарі Кантора.
• 1897 — Після візиту Бернштейна до Дедекінда, останній самостійно доводить теорему вдруге.
• 1898 — Доведення Бернштейна публікує Еміль Борель у своїй книзі про функції.

Обидва доведення Дедекінда обґрунтовуються в його науковій статті «Was sind und was sollen die Zahlen?».

${\displaystyle A\subset B\subset C\quad {\textrm {and}}\quad |A|=|C|\qquad \Rightarrow \qquad |A|=|B|=|C|}$

Див. також

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

Література

• Олійник А.С., Петравчук А.П. (2024). Дискретна математика. Навчальний посібник для студентів механіко-математичного факультету (PDF). Київ: Видавничо-поліграфічний центр "Київський університет". с. 177.
• Андрійчук В.І., Комарницький М.Я., Іщук Ю.Б. (2003). Вступ до дискретної математики. Львів: Видавничий центр ЛНУ ім. І.Франка. с. 254.