Теорема Шредера – Бернштейна - Википедия - Schröder–Bernstein theorem

В теория множеств, то Теорема Шредера – Бернштейна. заявляет, что если существует инъективные функции ж : А → B и грамм : B → А между наборы А и B, то существует биективный функция час : А → B.

Что касается мощность из двух наборов это классически означает, что если |А| ≤ |B| и |B| ≤ |А|, тогда |А| = |B|; то есть, А и B находятся равномерный. Это полезная функция при заказе Количественные числительные.

Теорема названа в честь Феликс Бернштейн и Эрнст Шредер. Он также известен как Теорема Кантора – Бернштейна, или же Кантора – Шредера – Бернштейна, после Георг Кантор кто первым опубликовал его без доказательств.

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

Кенигское определение биекции час:А → B из данного примера инъекций ж:А → B и грамм:B → А. Элемент в А и B обозначается цифрой и буквой соответственно. Последовательность 3 → e → 6 → ... является А-стоппер, приводящий к определениям час(3) = ж(3) = е, час(6) = ж(6), .... Последовательность d → 5 → ж → ... это B-забойка, ведущая к час(5) = грамм−1(5) = d, .... Последовательность ... →а → 1 → c → 4 → ... вдвойне бесконечен, что приводит к час(1) = грамм−1(1) = а, час(4) = грамм−1(4) = c, .... Последовательность б → 2 → б циклический, что приводит к час(2) = грамм−1(2) = б.

Следующее доказательство приписывается Юлиус Кениг.[1]

Без ограничения общности предположим, что А и B находятся непересекающийся. Для любого а в А или же б в B мы можем сформировать уникальную двустороннюю последовательность элементов, которые попеременно находятся в А и B, многократно применяя и идти от А к B и и идти от B к А (где определено).

Для любого конкретного а, эта последовательность может заканчиваться влево или нет в точке, где или же не определено.

Тем, что и инъективные функции, каждая а в А и б в B находится ровно в одной такой последовательности с точностью до идентичности: если элемент встречается в двух последовательностях, все элементы слева и справа должны быть одинаковыми в обеих по определению последовательностей. Следовательно, последовательности образуют раздел (непересекающегося) объединения А и B. Следовательно, достаточно произвести взаимно однозначное соответствие между элементами А и B в каждой из последовательностей отдельно, а именно:

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

  • Для Стопор, функция есть взаимно однозначное соответствие между его элементами в А и его элементы в B.
  • Для B-стопор, функция есть взаимно однозначное соответствие между его элементами в B и его элементы в А.
  • Для вдвойне бесконечный последовательность или циклический последовательность, либо или же Сделаю ( используется на картинке).

История

Традиционное название «Шредер-Бернштейн» основано на двух доказательствах, опубликованных независимо в 1898 году. Кантора часто добавляют, потому что он впервые сформулировал теорему в 1887 году, в то время как имя Шредера часто опускается, потому что его доказательство оказалось ошибочным, в то время как имя Ричард Дедекинд, который первым доказал это, не связано с теоремой. Согласно Бернштейну, Кантор предложил название теорема эквивалентности (Äquivalenzsatz).[2]

Первое утверждение теоремы Кантора (1887 г.)[3]
  • 1887 Кантор публикует теорему, но без доказательства.[3][2]
  • 1887 11 июля Дедекинд доказывает теорему (не полагаясь на аксиома выбора )[4] но не публикует своих доказательств и не сообщает об этом Кантору. Эрнст Цермело открыл доказательство Дедекинда и в 1908 г.[5] он публикует собственное доказательство, основанное на теория цепей из статьи Дедекинда Was sind und was sollen die Zahlen?[2][6]
  • 1895 Кантор утверждает теорему в своей первой статье по теории множеств и трансфинитным числам. Он получает это как простое следствие линейного порядка кардинальных чисел.[7][8][9] Однако он не смог доказать последнюю теорему, которая, как было показано в 1915 году, эквивалентна аксиома выбора к Фридрих Мориц Хартогс.[2][10]
  • 1896 Шредер объявляет доказательство (как следствие теоремы Джевонс ).[11]
  • 1897 Бернштейн, 19-летний студент семинара Кантора, представляет свое доказательство.[12][13]
  • 1897 Почти одновременно, но независимо Шредер находит доказательство.[12][13]
  • 1897 После визита Бернштейна, Дедекинд самостоятельно доказывает теорему второй раз.
  • 1898 Бернштейнаs доказательство (не опирающееся на аксиому выбора) опубликовано Эмиль Борель в своей книге о функциях.[14] (Сообщение Кантора в 1897 г. Международный конгресс математиков в Цюрихе.) В том же году доказательство также появляется в Бернштейнас диссертацией.[15][2]
  • 1898 Шредер публикует свои доказательства[16] который, однако, оказывается неисправным Алвин Рейнхольд Корсельт в 1902 году (незадолго до смерти Шредера),[17] (подтверждено Шредером),[2][18], но статья Корсельта опубликована только в 1911 году.

Оба доказательства Дедекинда основаны на его знаменитых мемуарах 1888 года. Was sind und was sollen die Zahlen? и вывести его как следствие предложения, эквивалентного утверждению C в статье Кантора,[7] который читает А ⊆ B ⊆ C и |А| = |C| подразумевает |А| = |B| = |C|, Кантор наблюдал это свойство еще в 1882/83 г. во время своих исследований теории множеств и трансфинитных чисел и поэтому (неявно) полагался на Аксиома выбора.

Предпосылки

Доказательство 1895 г. Кантор полагался, по сути, на аксиома выбора выводя результат как следствие из теорема о хорошем порядке.[8][9] Однако доказательство Кенига, приведенное над показывает, что результат может быть доказан и без использования аксиомы выбора.

С другой стороны, доказательство Кёнига использует принцип исключенный средний, чтобы провести анализ по случаям, поэтому это доказательство не работает в конструктивная теория множеств. Более того, никакое доказательство не может существовать только на основе одной конструктивной теории множеств (т.е. без принципа исключенного третьего), поскольку теорема Шредера – Бернштейна подразумевает принцип исключенного третьего.[19] Следовательно, интуиционисты не принимаю теорему.[20]

Также есть доказательство, использующее Теорема Тарского о неподвижной точке.[21]

Смотрите также

Примечания

  1. ^ Я. Кениг (1906). "Sur la théorie des ensembles". Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences. 143: 110–112.
  2. ^ а б c d е ж Феликс Хаусдорф (2002), Эгберт Брискорн; Сришти Д. Чаттерджи; и другие. (ред.), Grundzüge der Mengenlehre (1-е изд.), Берлин / Гейдельберг: Springer, стр. 587, г. ISBN  978-3-540-42224-2 – Первоначальное издание (1914 г.)
  3. ^ а б Георг Кантор (1887), "Mitteilungen zur Lehre vom Transfiniten", Zeitschrift für Philosophie und Philosophische Kritik, 91: 81–125
    Печатается на: Георг Кантор (1932), Адольф Френкель (Lebenslauf); Эрнст Цермело (ред.), Gesammelte Abhandlungen Mathematischen und Philophischen Inhalts, Берлин: Springer, стр. 378–439. Здесь: стр.413 внизу
  4. ^ Ричард Дедекинд (1932), Роберт Фрике; Эмми Нётер; Øystein Ore (ред.), Gesammelte Mathematische Werke, 3, Брауншвейг: Фридр. Vieweg & Sohn, стр. 447–449 (Глава 62)
  5. ^ Эрнст Цермело (1908), Феликс Кляйн; Вальтер фон Дейк; Дэвид Гильберт; Отто Блюменталь (ред.), "Untersuchungen über die Grundlagen der Mengenlehre I", Mathematische Annalen, 65 (2): 261–281, здесь: с.271–272, Дои:10.1007 / bf01449999, ISSN  0025-5831
  6. ^ Ричард Дедекинд (1888 г.), Was sind und was sollen die Zahlen? (2., без изменений (1893) изд.), Брауншвейг: Friedr. Vieweg & Sohn
  7. ^ а б Георг Кантор (1932), Адольф Френкель (Lebenslauf); Эрнст Цермело (ред.), Gesammelte Abhandlungen Mathematischen und Philophischen Inhalts, Берлин: Springer, стр. 285 ("Satz B")
  8. ^ а б Георг Кантор (1895). "Beiträge zur Begründung der transfiniten Mengenlehre (1)". Mathematische Annalen. 46 (4): 481–512 (теорему см. "Satz B", с.484). Дои:10.1007 / bf02124929.
  9. ^ а б (Георг Кантор (1897). "Beiträge zur Begründung der transfiniten Mengenlehre (2)". Mathematische Annalen. 49 (2): 207–246. Дои:10.1007 / bf01444205.)
  10. ^ Фридрих М. Хартогс (1915), Феликс Кляйн; Вальтер фон Дейк; Дэвид Гильберт; Отто Блюменталь (ред.), "Über das Problem der Wohlordnung", Mathematische Annalen, 76 (4): 438–443, Дои:10.1007 / bf01458215, ISSN  0025-5831
  11. ^ Эрнст Шредер (1896 г.). "Über G. Cantorsche Sätze". Jahresbericht der Deutschen Mathematiker-Vereinigung. 5: 81–82.
  12. ^ а б Оливер Дайзер (2010), Einführung in die Mengenlehre - Die Mengenlehre Georg Cantors und ihre Axiomatisierung durch Ernst Zermelo, Springer-Lehrbuch (3-е, исправленное издание), Berlin / Heidelberg: Springer, стр. 71, 501, Дои:10.1007/978-3-642-01445-1, ISBN  978-3-642-01444-4
  13. ^ а б Патрик Суппес (1972), Аксиоматическая теория множеств (1-е изд.), Нью-Йорк: Dover Publications, стр.95 ж, ISBN  978-0-486-61630-8
  14. ^ Эмиль Борель (1898), Leçons sur la théorie des fonctions, Paris: Gauthier-Villars et fils, стр. 103 и далее.
  15. ^ Феликс Бернштейн (1901), Untersuchungen aus der Mengenlehre, Галле а. С .: Buchdruckerei des Waisenhauses
    Печатается на: Феликс Бернштейн (1905), Феликс Кляйн; Вальтер фон Дейк; Дэвид Гильберт (ред.), "Untersuchungen aus der Mengenlehre", Mathematische Annalen, 61 (1): 117–155, (теорему см. "Satz 1" на стр.121), Дои:10.1007 / bf01457734, ISSN  0025-5831
  16. ^ Эрнст Шредер (1898), Kaiserliche Leopoldino-Carolinische Deutsche Akademie der Naturforscher (редактор), "Ueber zwei Definitionen der Endlichkeit und G. Cantor'sche Sätze", Nova Acta, 71 (6): 303–376 (доказательство: с.336–344)
  17. ^ Алвин Р. Корсельт (1911), Феликс Кляйн; Вальтер фон Дейк; Дэвид Гильберт; Отто Блюменталь (ред.), "Über einen Beweis des Äquivalenzsatzes", Mathematische Annalen, 70 (2): 294–296, Дои:10.1007 / bf01461161, ISSN  0025-5831
  18. ^ Корсельт (1911), стр. 295
  19. ^ Прадич, Пьер; Браун, Чад Э. (2019). «Кантор-Бернштейн подразумевает исключенное среднее». arXiv:1904.09193 [math.LO ].
  20. ^ Этторе Карруччо (2006). Математика и логика в истории и современной мысли. Издатели транзакций. п. 354. ISBN  978-0-202-30850-0.
  21. ^ Р. Уль "Теорема Тарского о неподвижной точке ", из MathWorld–– Интернет-ресурс Wolfram, созданный Эриком В. Вайсштейном. (Пример 3)

Рекомендации

внешняя ссылка