Лемма Цорна

О фильме Холлиса Фрэмптона см. «Лемму Цорна» .

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

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

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

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

Мотивация

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

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

- Уильям Тимоти Гауэрс , «Как использовать лемму Цорна»

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

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

• Множество оснащенное P, бинарным отношением ≤, которое является рефлексивным ( x ≤ x для каждого x ), антисимметричным (если выполняются оба x ≤ y и y ≤ x , то x = y ) и транзитивным (если x ≤ y и y ≤ 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 нет s , то есть если в P с s ≠ m и m ≤ с . В зависимости от отношения порядка частично упорядоченное множество может иметь любое количество максимальных элементов. Однако полностью упорядоченное множество может иметь не более одного максимального элемента.
• Учитывая подмножество S частично упорядоченного множества P , элемент u из P является верхней границей S , если он больше или равен каждому S. элементу Здесь S не обязательно должно быть цепью, а u должно быть сравнимо с каждым элементом S , но само не обязательно должно быть элементом S .

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

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

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

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

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

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

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

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

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

Если 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 _k ,..., ∈ _такие T для , что i _∈ Si — _Sk каждого i = 1, 2, ... v . Поскольку 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 . Сначала мы покажем, что — идеал R. I Чтобы Я был идеалом, оно должно удовлетворять трем условиям:

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

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

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

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

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

#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 , нам нужно использовать аксиому выбора (явно: пусть $B(T)=\{b\in P:\forall t\in T,b\geq t\}$, то есть набор верхних границ для T . Аксиома выбора дает $b:b(T)\in B(T)$).

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

a i _P определяются с помощью рекурсии : мы выбираем a ₀ в 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 (что соответствует порядковый падеж преемника).

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

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

История

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

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

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

леммы

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

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

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

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

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

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

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

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

аксиомы

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

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

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

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

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

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

См. также

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

Ссылки

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

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

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