Лемма Цорна - Википедия - Zorns lemma

Для фильма Холлис Фрэмптон см. Лемма Цорнса (фильм).

Лемму Цорна можно использовать, чтобы показать, что каждое связное график имеет остовное дерево. Множество всех подграфов, являющихся деревьями, упорядочено по включению, а объединение цепочки является верхней границей. Лемма Цорна утверждает, что должно существовать максимальное дерево, которое является остовным деревом, поскольку граф связен.[1] Лемма Цорна не нужна для конечных графов, подобных изображенному здесь.

Лемма Цорна, также известный как Лемма Куратовского – Цорна., после математиков Макс Зорн и Казимеж Куратовски, является предложением теория множеств. В нем говорится, что частично заказанный набор содержащий верхняя граница для каждого цепь (то есть каждый полностью заказанный подмножество ) обязательно содержит хотя бы один максимальный элемент.

Доказано Куратовским в 1922 году и независимо Цорном в 1935 году,[2] это лемма встречается в доказательствах нескольких важнейших теорем, например, Теорема Хана – Банаха в функциональный анализ, теорема о том, что каждый векторное пространство имеет основа,[3] Теорема Тихонова в топология заявляя, что каждый продукт компактные пространства компактно, а теоремы из абстрактная алгебра что в звенеть с тождеством каждый собственный идеал содержится в максимальный идеал и что каждый поле имеет алгебраическое замыкание.[4]

Лемма Цорна эквивалентна теорема о хорошем порядке а также к аксиома выбора, в том смысле, что любой из трех вместе с Аксиомы Цермело – Френкеля из теория множеств, достаточно для доказательства двух других.[5] Более ранняя формулировка леммы Цорна такова: Принцип максимума Хаусдорфа который утверждает, что каждое полностью упорядоченное подмножество данного частично упорядоченного множества содержится в максимальном полностью упорядоченном подмножестве этого частично упорядоченного набора.[6]

Мотивация

Чтобы доказать существование математического объекта, который можно рассматривать как максимальный элемент в некоторых посеть каким-то образом можно попытаться доказать существование такого объекта, предположив, что максимального элемента нет, и используя трансфинитная индукция и предположения ситуации, чтобы получить противоречие. Лемма Цорна приводит в порядок условия, которым должна удовлетворять ситуация, чтобы такой аргумент работал, и позволяет математикам не повторять аргумент трансфинитной индукции каждый раз вручную, а просто проверять условия леммы Цорна.

Если вы строите математический объект поэтапно и обнаруживаете, что (i) вы не закончили даже после бесконечного множества этапов, и (ii) кажется, что ничто не мешает вам продолжать строительство, то лемма Цорна вполне может помочь ты.

— Уильям Тимоти Гауэрс, "Как пользоваться леммой Цорна"[7]

Утверждение леммы

Лемму Цорна можно сформулировать так:

Лемма Цорна — Предположим, что частично заказанный набор п обладает тем свойством, что каждый цепь в п имеет верхняя граница в п. Тогда набор п содержит по крайней мере один максимальный элемент.

Иногда используются варианты этой формулировки, например, требующие, чтобы п и цепи непустые.[8]

Лемма Цорна (для непустых множеств) — Предположим, что непустое частично упорядоченное множество п обладает тем свойством, что каждая непустая цепочка имеет верхнюю границу в п. Тогда набор п содержит хотя бы один максимальный элемент.

Хотя эта формулировка кажется формально слабее (поскольку п дополнительное условие непустоты, но дает тот же вывод о п), на самом деле эти две формулировки эквивалентны. Чтобы проверить это, предположим сначала, что п удовлетворяет условию, что каждая цепь в п имеет верхнюю границу в п. Тогда пустое подмножество п цепь, так как она удовлетворяет определению бессмысленно; поэтому гипотеза предполагает, что это подмножество должно иметь верхнюю границу в п, и эта оценка сверху показывает, что п на самом деле не пусто. Наоборот, если п предполагается непустым и удовлетворяет гипотезе о том, что каждая непустая цепочка имеет верхнюю границу в п, тогда п также удовлетворяет условию, что каждый цепь имеет верхнюю границу, так как произвольный элемент п служит верхней границей для пустой цепочки (то есть пустого подмножества, рассматриваемого как цепочка).

Разница может показаться тонкой, но во многих доказательствах, использующих лемму Цорна, для получения верхней оценки используются объединения какого-либо типа, поэтому случай пустой цепочки может быть упущен; то есть проверка того, что все цепи имеют верхние границы, может иметь дело с пустыми и непустыми цепями отдельно. Так что многие авторы предпочитают проверять непустоту набора п вместо того, чтобы иметь дело с пустой цепочкой в ​​общих рассуждениях.[9]

Пример приложения

Лемму Цорна можно использовать, чтобы показать, что каждое нетривиальное кольцо р с единство содержит максимальный идеал.

Позволять п быть множеством, состоящим из всех (двусторонних) идеалы в р Кроме р сам. Идеал р был исключен, потому что максимальные идеалы по определению не равны р. С р нетривиально, множество п содержит тривиальный идеал {0}, поэтому п не пусто. Более того, п частично заказан установить включение (видеть порядок включения ). Найти максимальный идеал в р это то же самое, что найти максимальный элемент в п.

Чтобы применить лемму Цорна, возьмем цепь Т в п (то есть, Т это подмножество п это полностью заказано). Если Т - пустое множество, то тривиальный идеал {0} является верхней границей для Т в п. Предположим тогда, что Т не пусто. Необходимо показать, что Т имеет верхнюю границу, т.е. существует идеал я ⊆ р что больше, чем все члены Т но все же меньше чем р (иначе его не было бы в п). Брать я быть союз всех идеалов в Т. Мы хотим показать, что я это верхняя граница для Т в п. Сначала мы покажем, что я это идеал р, а затем что это правильный идеал р и так это элемент п. Поскольку каждый элемент Т содержится в я, это покажет, что я это верхняя граница для Т в п, как требуется.

Потому что Т содержит по крайней мере один элемент, и этот элемент содержит по крайней мере 0, объединение я содержит не менее 0 и не является пустым. Чтобы доказать, что я является идеалом, обратите внимание, что если а и б являются элементами я, то существует два идеала J, K ∈ Т такой, что а является элементом J и б является элементом K. С Т полностью заказан, мы знаем, что J ⊆ K или же K ⊆ J. В первом случае оба а и б являются членами идеального K, поэтому их сумма а + б является членом K, что показывает, что а + б является членом я. Во втором случае оба а и б являются членами идеального J, и поэтому а + б ∈ я. Кроме того, если р ∈ р, тогда ар и ра являются элементами J и, следовательно, элементы я. Таким образом, я идеал в р.

Теперь идеал равен р если и только если он содержит 1. (Понятно, что если он равен р, то он должен содержать 1; с другой стороны, если он содержит 1 и р является произвольным элементом р, тогда r1 = р является элементом идеала, поэтому идеал равен р.) Так что если я были равны р, тогда он будет содержать 1, а это означает, что один из членов Т будет содержать 1 и, следовательно, будет равно р - но р явно исключен из п.

Условие леммы Цорна проверено, и, значит, есть максимальный элемент в п, другими словами, максимальный идеал в р.

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

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

Набросок доказательства леммы Цорна следует в предположении аксиома выбора. Предположим, что лемма неверна. Тогда существует частично упорядоченное множество, или poset, п такое, что каждое полностью упорядоченное подмножество имеет верхнюю границу, и что для каждого элемента в п есть еще один элемент, который больше его. Для каждого полностью упорядоченного подмножества Т затем мы можем определить более крупный элемент б(Т), потому что Т имеет верхнюю границу, и эта верхняя граница имеет больший элемент. Чтобы действительно определить функция б, нам нужно воспользоваться аксиомой выбора.

Используя функцию б, мы собираемся определить элементы а0 < а1 < а2 < а3 <... в п. Эта последовательность очень долго: индексы - это не просто натуральные числа, но все порядковые. На самом деле, последовательность слишком длинная для набора п; слишком много ординалов (a правильный класс ), больше, чем элементов в любом наборе, и набор п скоро исчерпаемся, и тогда мы столкнемся с желаемым противоречием.

В ая определены трансфинитная рекурсия: мы выбираем а0 в п произвольно (это возможно, так как п содержит верхнюю границу для пустого множества и, следовательно, не является пустым) и для любого другого порядкового номера ш мы установили аш = б({аv : v < ш}). Поскольку аv полностью упорядочены, это вполне обоснованное определение.

Это доказательство показывает, что на самом деле верна немного более сильная версия леммы Цорна:

Лемма — Если п это посеть в котором каждый хорошо организованный подмножество имеет верхнюю границу, и если Икс любой элемент п, тогда п имеет максимальный элемент, больший или равный Икс. То есть есть максимальный элемент, который сравним с Икс.

История

В Принцип максимума Хаусдорфа является ранним утверждением, аналогичным лемме Цорна.

Казимеж Куратовски доказано в 1922 г.[10] версия леммы, близкая к ее современной формулировке (применяется к множествам, упорядоченным по включению и замкнутым относительно объединений хорошо упорядоченных цепей). По сути, та же формулировка (ослабленная использованием произвольных цепочек, а не только хорошо упорядоченных) была независимо дана Макс Зорн в 1935 г.,[11] кто предложил это как новое аксиома теории множеств, заменяющей теорему о хорошем упорядочивании, продемонстрировал некоторые из ее приложений в алгебре и пообещал показать ее эквивалентность выбранной аксиоме в другой статье, которая так и не появилась.

Название "лемма Цорна", по-видимому, связано с Джон Тьюки, который использовал это в своей книге Сходимость и единообразие топологии в 1940 г. Бурбаки с Теория ансамблей 1939 г. ссылается на такой же принцип максимума, как "le théorème de Zorn".[12] Название "Лемма Куратовского – Цорна. "преобладает в Польше и России.

Эквивалентные формы леммы Цорна

Смотрите также: Аксиома выбора § Эквиваленты

Лемма Цорна эквивалентна (в ZF ) к трем основным результатам:

  1. Принцип максимума Хаусдорфа
  2. Аксиома выбора
  3. Теорема о хорошем порядке.

Известная шутка, намекающая на эту эквивалентность (которая может противоречить человеческой интуиции), приписывается Джерри Бона: "Аксиома выбора, очевидно, верна, принцип правильного порядка явно неверен, и кто может сказать о лемме Цорна?"[13]

Лемма Цорна также эквивалентна сильной теореме о полноте логики первого порядка.[14]

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

  1. Теорема Банаха о расширении, которая используется для доказательства одного из самых фундаментальных результатов функционального анализа, Теорема Хана – Банаха
  2. Каждое векторное пространство имеет основа, результат линейной алгебры (которой он эквивалентен[15]). В частности, действительные числа как векторное пространство над рациональными числами обладают базисом Гамеля.
  3. Каждое коммутативное кольцо с единицей имеет максимальный идеал, результат теории колец
  4. Теорема Тихонова в топологии (что также эквивалентно[16])
  5. Каждый правильный фильтр содержится в ультрафильтр, что дает теорема полноты из логика первого порядка[17]

В этом смысле мы видим, как лемму Цорна можно рассматривать как мощный инструмент, особенно в смысле единой математики.[требуется разъяснение ].

Аналоги при ослаблении аксиомы выбора

Смотрите также: Аксиома зависимого выбора

Ослабленная форма леммы Цорна может быть доказана с помощью ZF + DC (теория множеств Цермело – Френкеля с заменой выбранной аксиомы на аксиома зависимого выбора ). Лемму Цорна можно выразить прямо, заметив, что множество, не имеющее максимального элемента, было бы эквивалентно утверждению, что отношение упорядочения множества было бы целым, что позволило бы нам применить аксиому зависимого выбора для построения счетной цепи. В результате любое частично упорядоченное множество с исключительно конечными цепями должно иметь максимальный элемент.[18]

В более общем плане усиление аксиомы зависимого выбора до более высоких порядковых чисел позволяет нам обобщить утверждение в предыдущем абзаце на более высокие мощности.[18] В пределе, когда мы допускаем сколь угодно большие ординалы, мы восстанавливаем доказательство полной леммы Цорна, используя аксиому выбора из предыдущего раздела.

В популярной культуре

Фильм 1970 года, Лемма Цорна, назван в честь леммы.

Ссылка на эту лемму Симпсоны в эпизоде ​​"Новый друг Барта ".[19]

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

Примечания

  1. ^ Серр, Жан-Пьер (2003), Деревья, Монографии Спрингера по математике, Springer, p. 23
  2. ^ Мур 2013, п. 168
  3. ^ Виланский, Альберт (1964). Функциональный анализ. Нью-Йорк: Блейсделл. С. 16–17.
  4. ^ Jech 2008, гл. 2, §2 Некоторые приложения аксиомы выбора в математике
  5. ^ Jech 2008, п. 9
  6. ^ Мур 2013, п. 168
  7. ^ https://gowers.wordpress.com/2008/08/12/how-to-use-zorns-lemma/
  8. ^ Например, Ланг, Серж (2002). Алгебра. Тексты для выпускников по математике. 211 (Пересмотренное 3-е изд.). Springer-Verlag. п. 880. ISBN  978-0-387-95385-4., Даммит, Дэвид С .; Фут, Ричард М. (1998). Абстрактная алгебра (2-е изд.). Прентис Холл. п. 875. ISBN  978-0-13-569302-5., и Бергман, Джордж М (2015). Приглашение к общей алгебре и универсальным конструкциям. Университекст (2-е изд.). Springer-Verlag. п. 162. ISBN  978-3-319-11477-4..
  9. ^ Бергман, Джордж М (2015). Приглашение к общей алгебре и универсальным конструкциям. Universitext (Второе изд.). Springer-Verlag. п. 164. ISBN  978-3-319-11477-4.
  10. ^ Куратовский, Казимир (1922). "Une méthode d'élimination des nombres transfinis des raisonnements mathématiques" [Метод избавления от трансфинитных чисел математических рассуждений] (PDF). Fundamenta Mathematicae (На французском). 3: 76–108. Дои:10.4064 / fm-3-1-76-108. Получено 24 апреля 2013.
  11. ^ Цорн, Макс (1935). «Замечание о методе трансфинитной алгебры». Бюллетень Американского математического общества. 41 (10): 667–670. Дои:10.1090 / S0002-9904-1935-06166-X.
  12. ^ Кэмпбелл 1978, п. 82.
  13. ^ Кранц, Стивен Г. (2002), «Аксиома выбора», Справочник по логике и методам доказательства для компьютерных наук, Springer, стр. 121–126, Дои:10.1007/978-1-4612-0115-1_9, ISBN  978-1-4612-6619-8.
  14. ^ Дж. Л. Белл и А. Б. Сломсон (1969). Модели и продукты Ultra. Издательская компания Северной Голландии. Глава 5, теорема 4.3, стр. 103.
  15. ^ Бласс, Андреас (1984). «Существование основ подразумевает Аксиому выбора». Аксиоматическая теория множеств. Contemp. Математика. Современная математика. 31. С. 31–33. Дои:10.1090 / conm / 031/763890. ISBN  9780821850268.
  16. ^ Келли, Джон Л. (1950). «Из теоремы Тихонова о произведении следует аксиома выбора». Fundamenta Mathematicae. 37: 75–76. Дои:10.4064 / fm-37-1-75-76.
  17. ^ Дж. Л. Белл и А. Б. Сломсон (1969). Модели и продукты Ultra. Издательская компания Северной Голландии.
  18. ^ а б Волк, Эллиот С. (1983), О принципе зависимого выбора и некоторых формах леммы Цорна, 26 365-367, Canadian Mathematical Bulletin, стр. 1
  19. ^ "Лемма Цорна | Симпсоны и их математические секреты".

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

  • Кэмпбелл, Пол Дж. (Февраль 1978 г.). "Происхождение леммы Цорна'". Historia Mathematica. 5 (1): 77–89. Дои:10.1016/0315-0860(78)90136-2.
  • Цесельский, Кшиштоф (1997). Теория множеств для работающего математика. Издательство Кембриджского университета. ISBN  978-0-521-59465-3.
  • Jech, Thomas (2008) [1973]. Аксиома выбора. Минеола, Нью-Йорк: Dover Publications. ISBN  978-0-486-46624-8.
  • Мур, Грегори Х. (2013) [1982]. Аксиома выбора Цермело: ее происхождение, развитие и влияние. Dover Publications. ISBN  978-0-486-48841-7.

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