Лемма Цорна

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

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

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

Мотивация

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

Если вы строите математический объект поэтапно и обнаруживаете, что (i) вы не закончили даже после бесконечного числа этапов и (ii) кажется, что ничто не мешает вам продолжать строить, то лемма Цорна вполне может помочь. ты.
- Уильям Тимоти Гауэрс , «Как использовать лемму Цорна» ^[7]

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

Предварительные понятия:

Множество P, оснащенное бинарным отношением ≤, которое является рефлексивным ( x ≤ x для каждого x ), антисимметричным (если выполняются оба x ≤ y и y ≤ x , то x = y ) и транзитивным (если x ≤ y и y ≤ x ). z , то x ≤ z ) называется (частично) упорядоченным по ≤. Учитывая два элемента x и y из P с x ≤ y , говорят, что y больше или равен x . Слово «частичный» означает, что не каждая пара элементов частично упорядоченного множества должна быть сравнима по отношению порядка, то есть в частично упорядоченном множестве P с отношением порядка ≤ могут существовать элементы x и y . ни x ≤ y , ни y ≤ x . Упорядоченное множество, в котором каждая пара элементов сравнима, называется полностью упорядоченным .
Каждое подмножество S частично упорядоченного множества P само по себе можно рассматривать как частично упорядоченное, ограничивая отношение порядка, унаследованное от P , до S. Подмножество S частично упорядоченного множества P называется цепью (в P ), если оно полностью упорядочено в наследственном порядке.
Элемент m частично упорядоченного множества P с отношением порядка ≤ является максимальным (относительно ≤), если нет другого элемента P , большего, чем m , то есть если в P нет s с s ≠ m и m ≤ с . В зависимости от отношения порядка частично упорядоченное множество может иметь любое количество максимальных элементов. Однако полностью упорядоченное множество может иметь не более одного максимального элемента.
Учитывая подмножество S частично упорядоченного множества P , элемент u из P является верхней границей S , если он больше или равен каждому элементу S. Здесь S не обязательно должно быть цепью, а u должно быть сравнимо с каждым элементом S , но само не обязательно должно быть элементом S .

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

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

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

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

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

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

Примеры приложений

Каждое векторное пространство имеет базис.

Лемму Цорна можно использовать, чтобы показать, что каждое векторное пространство V имеет базис . ^[10]

Если V = {0} , то пустое множество является базисом V. Теперь предположим, что V ≠ {0} . Пусть P — множество, состоящее из всех линейно независимых подмножеств V . Поскольку V не является нулевым векторным пространством , существует ненулевой элемент v из V , поэтому P содержит линейно независимое подмножество { v }. Более того, P частично упорядочен включением множества (см. порядок включения ). Найти максимальное линейно независимое подмножество V — это то же самое, что найти максимальный элемент в P .

Чтобы применить лемму Цорна, возьмем цепь T из P (т. е. T — полностью упорядоченное подмножество P ). Если T — пустое множество, то { v } — верхняя граница T в P . Предположим тогда, что T непусто. Нам нужно показать, что T имеет верхнюю границу, то есть существует линейно независимое подмножество B из V , содержащее все члены T .

Возьмем B как объединение всех множеств из T. Мы хотим показать, что B является верхней границей T в P . Для этого достаточно показать, что B — линейно независимое подмножество V .

Предположим иначе, что B не является линейно независимым. Тогда существуют векторы v ₁ , v ₂ , ..., v _k ∈ B и скаляры a ₁ , a ₂ , ..., a _k , не все нули, такие, что

a_{1}\mathbf {v} _{1}+a_{2}\mathbf {v} _{2}+\cdots +a_{k}\mathbf {v} _{k}=\mathbf {0} .

Поскольку B — объединение всех множеств из T , существуют множества S1 _,S2 _, ..., Sk ∈ T _такие , что v i _∈ Si для каждого _{i = 1}, 2, ..., k . Поскольку T полностью упорядочен, одно из множеств S ₁ , S ₂ , ..., Sk должно содержать остальные, поэтому существует некоторый набор _Si, _{который} содержит все v ₁ , v ₂ , ..., v _k . Это говорит нам о наличии линейно зависимого набора векторов в Si , что противоречит тому, что _Siлинейно независимо (поскольку он является членом _P) .

Условие леммы Цорна проверено, и, таким образом, в P существует максимальный элемент , другими словами, максимальное линейно независимое подмножество B из V .

Наконец, мы покажем, что B действительно является базисом V . Достаточно показать, что B является охватывающим множеством V . Предположим, ради противоречия, что B не является охватывающим. Тогда существует некоторый v ∈ V , не покрытый промежутком B . Это говорит о том, что B ∪ { v } является линейно независимым подмножеством V , которое больше, чем B , что противоречит максимальности B . Следовательно, B является охватывающим множеством V и, следовательно, базисом V .

Каждое нетривиальное кольцо с единицей содержит максимальный идеал

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

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

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

Возьмем I за объединение всех идеалов в T. Мы хотим показать, что I является верхней границей T в P . Сначала мы покажем, что I — идеал R. Чтобы Я был идеалом, оно должно удовлетворять трем условиям:

I — непустое подмножество R ,
Для каждого x , y ∈ I сумма x + y находится в I ,
Для каждого r ∈ R и каждого x ∈ I произведение rx находится в I.

#1 — I — непустое подмножество R.

Поскольку T содержит хотя бы один элемент, а этот элемент содержит как минимум 0, объединение I содержит как минимум 0 и не пусто. Каждый элемент T является подмножеством R , поэтому объединение I состоит только из элементов R.

#2 – Для каждых x , y ∈ I сумма x + y находится в I.

Предположим, x и y — элементы I. Тогда существуют два идеала J , K ∈ T такие, что x — элемент J , а y — элемент K. Поскольку T полностью упорядочен, мы знаем, что J ⊆ K или K ⊆ J . Не ограничивая общности , предположим первый случай. И x , и y являются членами идеала K , поэтому их сумма x + y является членом K , что показывает, что x + y является членом I.

#3 . Для каждого r ∈ R и каждого x ∈ I произведение rx находится в I.

Предположим, x является элементом I . Тогда существует идеал J ∈ T такой, что x принадлежит J . Если r ∈ R , то rx — элемент J и, следовательно , элемент I. Таким образом, I — идеал в R.

Теперь мы покажем, что Я — собственный идеал. Идеал равен R тогда и только тогда, когда он содержит 1. (Ясно, что если это R , то он содержит 1; с другой стороны, если он содержит 1 и r — произвольный элемент из R , то r 1 = r является элементом идеала, и поэтому идеал равен R .) Итак, если бы я был равен R , то он содержал бы 1, а это означает, что один из членов T содержал бы 1 и, таким образом, был бы равен к R – но R явно исключен из P .

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

Эскиз доказательства

Ниже приводится набросок доказательства леммы Цорна в предположении аксиомы выбора . Предположим, что лемма неверна. Тогда существует частично упорядоченное множество, или частично упорядоченное множество, P такое, что каждое полностью упорядоченное подмножество имеет верхнюю границу и что для каждого элемента в P существует другой элемент, больший его. Затем для каждого полностью упорядоченного подмножества T мы можем определить больший элемент b ( T ), поскольку T имеет верхнюю границу, а эта верхняя граница имеет больший элемент. Чтобы фактически определить функцию b , нам нужно использовать аксиому выбора (явно: пусть , то есть набор верхних границ для T . Аксиома выбора дает ). $B(T)=\{b\in P:\forall t\in T,b\geq t\}$ $b:b(T)\in B(T)$

Используя функцию b , мы собираемся определить элементы a ₀ < a ₁ < a ₂ < a ₃ < ... < a _ω < a _ω+1 <… в P . Эта неисчисляемая последовательность очень длинная : индексами являются не только натуральные числа , но и все порядковые номера . Фактически, последовательность слишком длинна для множества P ; ординалов слишком много ( собственный класс ), больше, чем элементов в любом наборе (другими словами, для любого набора ординалов существует больший ординал), и вскоре набор P будет исчерпан, и тогда мы натолкнуться на желаемое противоречие.

a _i определяются с помощью трансфинитной рекурсии : мы выбираем a ₀ в P произвольно (это возможно, поскольку P содержит верхнюю границу для пустого множества и, следовательно, не пусто), а для любого другого порядкового номера w мы устанавливаем a _w = b ( { а _v : v < ш }). Поскольку a v _{полностью} упорядочены, это определение вполне обосновано.

Приведенное выше доказательство можно сформулировать без явной ссылки на ординалы, рассматривая начальные сегменты { a _v : v < w } как подмножества P . Такие множества можно легко охарактеризовать как вполне упорядоченные цепи S ⊆ P , где каждый x ∈ S удовлетворяет условию x = b ({ y ∈ S : y < x }). Противоречие достигается, если отметить, что мы всегда можем найти «следующий» начальный сегмент либо путем объединения всех таких S (что соответствует предельному порядковому случаю), либо путем добавления b ( S ) к «последнему» S (что соответствует предельному порядковому случаю). порядковый падеж преемника). ^[11]

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

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

История

Принцип максимума Хаусдорфа — раннее утверждение, похожее на лемму Цорна.

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

Название «Лемма Цорна», по-видимому, принадлежит Джону Тьюки , который использовал его в своей книге «Сходимость и единообразие в топологии» в 1940 году. В «Теории ансамблей» Бурбаки 1939 года аналогичный максимальный принцип упоминается как «теорема Цорна». ^[14] Название «лемма Куратовского–Цорна» преобладает в Польше и России.

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

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

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

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

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

Теорема о расширении Банаха, которая используется для доказательства одного из наиболее фундаментальных результатов функционального анализа, теоремы Хана – Банаха.
Каждое векторное пространство имеет базис , являющийся результатом линейной алгебры (которой оно эквивалентно ^[17] ). В частности, действительные числа как векторное пространство над рациональными числами обладают базисом Гамеля.
Каждое коммутативное кольцо с единицей имеет максимальный идеал — результат теории колец, известный как теорема Крулля , которому эквивалентна лемма Цорна ^[18]
Теорема Тихонова в топологии (которой она также эквивалентна ^[19] )
Каждый правильный фильтр содержится в ультрафильтре , что приводит к теореме полноты логики первого порядка ^[20]

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

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

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

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

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

В честь леммы назван фильм 1970 года « Лемма Цорна» .

Лемма упоминалась в « Симпсонах» в эпизоде « Новый друг Барта ». ^[22]

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

Античейн - Подмножество несравнимых элементов
Теорема Бурбаки – Витта
Частичный порядок, полный по цепочке - частично упорядоченное множество, в котором каждая цепочка имеет наименьшую верхнюю границу.
Теорема о расширении Шпильрайна - Математический результат об отношениях порядка
Конечность Тарского - Математический набор, содержащий конечное число элементов.
Лемма Тейхмюллера – Тьюки (иногда называемая леммой Тьюки)

Примечания

^ Серр, Жан-Пьер (2003), Деревья , Монографии Спрингера по математике, Спрингер, стр. 23
^ Мур 2013, с. 168
^ Вилански, Альберт (1964). Функциональный анализ . Нью-Йорк: Блейсделл. стр. 16–17.
^ Джех 2008, гл. 2, §2 Некоторые приложения аксиомы выбора в математике
^ Джех 2008, с. 9
^ Мур 2013, с. 168
↑ Уильям Тимоти Гауэрс (12 августа 2008 г.). «Как использовать лемму Цорна».
^ Например, Ланг, Серж (2002). Алгебра . Тексты для аспирантов по математике. Том. 211 (пересмотренное 3-е изд.). Спрингер-Верлаг. п. 880. ИСБН 978-0-387-95385-4., Даммит, Дэвид С.; Фут, Ричард М. (1998). Абстрактная алгебра (2-е изд.). Прентис Холл. п. 875. ИСБН 978-0-13-569302-5.и Бергман, Джордж М. (2015). Приглашение к общей алгебре и универсальным конструкциям. Университетский текст (2-е изд.). Спрингер-Верлаг. п. 162. ИСБН 978-3-319-11477-4..
^ Бергман, Джордж М. (2015). Приглашение к общей алгебре и универсальным конструкциям. Университетский текст (Второе изд.). Спрингер-Верлаг. п. 164. ИСБН 978-3-319-11477-4.
^ Смитс, Тим. «Доказательство того, что каждое векторное пространство имеет основу» (PDF) . Проверено 14 августа 2022 г.
^ Левин, Джонатан В. (1991). «Простое доказательство леммы Цорна». Американский математический ежемесячник . 98 (4): 353–354. дои : 10.1080/00029890.1991.12000768.
^ Куратовский, Казимир (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 г.
^ Цорн, Макс (1935). «Замечание о методе трансфинитной алгебры». Бюллетень Американского математического общества . 41 (10): 667–670. дои : 10.1090/S0002-9904-1935-06166-X .
^ Кэмпбелл 1978, с. 82.
^ Кранц, Стивен Г. (2002), «Аксиома выбора», Справочник по логике и методам доказательства для информатики , Springer, стр. 121–126, doi : 10.1007/978-1-4612-0115-1_9, ISBN 978-1-4612-6619-8.
^ Дж. Л. Белл и А. Б. Сломсон (1969). Модели и ультрапродукты . Издательство Северной Голландии. Глава 5, Теорема 4.3, стр. 103.
^ Бласс, Андреас (1984). «Существование базисов подразумевает аксиому выбора». Аксиоматическая теория множеств . Современная математика. Том. 31. С. 31–33. doi : 10.1090/conm/031/763890. ISBN 9780821850268.
^ Ходжес, В. (1979). «Крулл подразумевает Цорна». Журнал Лондонского математического общества . с2-19(2): 285–287. дои : 10.1112/jlms/s2-19.2.285.
^ Келли, Джон Л. (1950). «Теорема Тихонова о произведении подразумевает аксиому выбора». Фундамента Математика . 37 : 75–76. дои : 10.4064/fm-37-1-75-76 .
^ Дж. Л. Белл и А. Б. Сломсон (1969). Модели и ультрапродукты . Издательство Северной Голландии.
^ Аб Волк, Эллиот С. (1983), «О принципе зависимого выбора и некоторых формах леммы Цорна», Canadian Mathematical Bulletin , 26 (3): 365–367, doi : 10.4153/CMB-1983-062-5
^ «Лемма Цорна | Симпсоны и их математические секреты».

Внешние ссылки

«Лемма Цорна», Математическая энциклопедия , EMS Press , 2001 [1994]
Лемма Цорна в ProvenMath содержит формальное доказательство до мельчайших деталей эквивалентности выбранной аксиомы и леммы Цорна.
Лемма Цорна в Metamath — еще одно формальное доказательство. (Версия Unicode для последних браузеров.)