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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

|A|=|B|.

Неформально, теорема стверджує наступне:

Із \alpha \leqslant \beta і \beta\leqslant\alpha, випливає, що \alpha = \beta. В даних нерівностях \alpha і \beta є кардинальними числами.

Доведення[ред.ред. код]

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

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

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

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

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

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

Інше доведення[ред.ред. код]

Нехай

C_0=A\setminus g[B],\!

і

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

і

C=\bigcup_{n=0}^\infty C_n.

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


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 -1(x), і h коректно визначене взаємно однозначне відображення (бієкція).

Можна перевірити, що 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?".


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

Див. також[ред.ред. код]

Література[ред.ред. код]

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