Теорема о продолжении Шпильрайна
В теории порядка ( теорема расширения Шпильрайна также называемая принципом расширения порядка ), доказанная Эдвардом Шпильрайном в 1930 году, [1] утверждает, что каждый частичный порядок содержится в общем порядке . Интуитивно, теорема гласит, что любой метод сравнения элементов, который оставляет некоторые пары несравнимыми, может быть расширен таким образом, чтобы каждая пара стала сравнимой. Теорема является одним из многих примеров использования аксиомы выбора в форме леммы Цорна для поиска максимального множества с определенными свойствами.
Определения и утверждения [ править ]
Бинарное отношение на съемочной площадке формально определяется как набор упорядоченных пар элементов и часто сокращается как
Отношение является рефлексивным, если выполняется для каждого элемента транзитивно , если подразумевать для всех оно антисимметрично, если подразумевать для всех и это отношение связи, если держится для всех Частичный порядок по определению является рефлексивным, транзитивным и антисимметричным отношением. Полный порядок — это частичный порядок, который связан.
Отношение содержится в другом отношении когда все упорядоченные пары в также появляются в то есть, подразумевает для всех Теорема о расширении утверждает, что каждое отношение рефлексивное, транзитивное и антисимметричное (то есть частичный порядок), содержится в другом отношении который является рефлексивным, транзитивным, антисимметричным и связным (то есть тотальным порядком).
Доказательство [ править ]
Теорема доказывается в два этапа. Во-первых, показано, что если частичный порядок не сравнивает какие-то два элемента, его можно расширить до порядка с надмножеством сравнимых пар. Максимальный частичный порядок не может быть расширен по определению, поэтому из этого шага следует, что максимальный частичный порядок должен быть полным порядком. На втором этапе лемма Цорна применяется для нахождения максимального частичного порядка, расширяющего любой заданный частичный порядок.
Для первого шага предположим, что данный частичный порядок не сравнивается и . Затем порядок расширяется путем добавления пары к отношению, что может привести к нетранзитивному отношению, а затем восстановить транзитивность, добавив все пары такой, что Это создает отношение, которое все еще является рефлексивным, антисимметричным и транзитивным и строго содержит исходное. Отсюда следует, что если частичные порядки, распространяющиеся сами частично упорядочены по расширению, то любой максимальный элемент этого порядка расширения должен быть полным порядком.
Далее показано, что ЧУМ частичных порядков, простирающихся , упорядоченный по расширению, имеет максимальный элемент. Существование такого максимального элемента доказывается применением к этому частичному множеству леммы Цорна . Лемма Цорна утверждает, что частичный порядок, в котором каждая цепь имеет верхнюю границу, имеет максимальный элемент. Цепочка в этом ЧУМ представляет собой набор отношений, в котором для каждых двух отношений одно расширяет другое. Верхняя граница для цепи можно найти как объединение отношений в цепи, . Этот союз представляет собой отношение, распространяющееся , поскольку каждый элемент представляет собой частичный порядок, имеющий как подмножество. Далее показано, что является транзитивным отношением. Предположим, что и находятся в так что существуют такой, что и . Потому что это цепочка, одна из или должен расширять другой и содержать оба и ,и в силу своей транзитивности оно также содержит , как и профсоюз. Аналогично можно показать, что является антисимметричным. Таким образом, является продолжением , поэтому он принадлежит частичному множеству расширений , и является верхней границей для .
Этот аргумент показывает, что лемма Цорна может быть применена к множеству расширений , производя максимальный элемент . На первом этапе этот максимальный элемент должен быть полным порядком, что завершает доказательство.
Сила [ править ]
Некоторая форма аксиомы выбора необходима для доказательства теоремы о расширении Шпильрайна. Теорема о расширении подразумевает аксиому конечного выбора : если объединению семейства конечных множеств задан пустой частичный порядок и он расширен до полного порядка, расширение определяет выбор из каждого конечного множества, его минимальный элемент в полный порядок. Хотя конечный выбор является слабой версией аксиомы выбора, он не зависит от теории множеств Цермело – Френкеля без выбора. [2]
Теорему о расширении Шпильрайна вместе с другим следствием аксиомы выбора, принципом, согласно которому каждый общий порядок имеет конфинальный хороший порядок , можно объединить, чтобы доказать полную аксиому выбора. С этими предположениями можно выбрать элемент из любого заданного набора, расширив его пустой частичный порядок, найдя конфинальный хороший порядок и выбрав минимальный элемент из этого хорошего порядка. [3]
Другие продолжении теоремы о
Эрроу заявил, что каждый предварительный порядок (рефлексивное и транзитивное отношение) может быть расширен до полного предпорядка (транзитивное и связное отношение). [4] Позже это утверждение было подтверждено Ханссоном. [5] [6]
Судзумура доказал, что бинарное отношение может быть расширено до полного предпорядка тогда и только тогда, когда оно согласовано по Судзумуре , а это означает, что не существует цикла элементов такого, что для каждой пары последовательных элементов и существует некоторая пара последовательных элементов в цикле, для которого не держит. [6]
Ссылки [ править ]
- ^ Шпильрайн, Эдвард (1930), «Sur l'extension de l'ordre partiel» (PDF) , Fundamentals of Mathematics (на французском языке), 16 : 386–389, doi : 10.4064/fm-16-1-386-389
- ^ Мур, Грегори Х. (1982), Аксиома выбора Цермело: ее истоки, развитие и влияние , Исследования по истории математики и физических наук, том. 8, Нью-Йорк: Springer-Verlag, с. 222, номер домена : 10.1007/978-1-4613-9478-5 , ISBN. 0-387-90670-3 , МР 0679315
- ^ Ховард, Пол; Рубин, Жан Э. (1998), «Примечание 121», Последствия аксиомы выбора , Математические обзоры и монографии, том. 59, Провиденс, Род-Айленд: Американское математическое общество, с. 299, номер домена : 10.1090/surv/059 , ISBN 0-8218-0977-6 , МР 1637107
- ^ Эрроу, Кеннет Дж. (2012), «IV.3: Квазиупорядочения и совместимые слабые порядки», Социальный выбор и индивидуальные ценности (3-е изд.), Yale University Press, стр. 64, ISBN 978-0-300-18698-7
- ^ Ханссон, Бенгт (1968), «Структуры выбора и отношения предпочтений», Synthese , 18 (4): 443–458, doi : 10.1007/BF00484979 , JSTOR 20114617 ; см. лемму 3
- ^ Jump up to: Перейти обратно: а б Катон, Сусуму (август 2011 г.), «Шпильрайн, Эрроу и Судзумура: краткие доказательства теорем расширения и расширения», Metro Economica , 63 (2): 235–249, doi : 10.1111/j.1467-999x.2011.04130.x