Теорема расширения Шпильрайна

Математический результат по порядковым отношениям

В теории порядка теорема о расширении Шпильрайна ( также называемая принципом расширения порядка ), доказанная Эдвардом Шпильрайном в 1930 году, ^[1] утверждает, что каждый частичный порядок содержится в полном порядке . Интуитивно теорема гласит, что любой метод сравнения элементов, который оставляет некоторые пары несравнимыми, может быть расширен таким образом, что каждая пара станет сравнимой. Теорема является одним из многих примеров использования аксиомы выбора в форме леммы Цорна для нахождения максимального множества с определенными свойствами.

Определения и утверждения

Бинарное отношение на множестве формально определяется как набор упорядоченных пар элементов и часто сокращается до ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle (x,y)}$ ${\displaystyle X,}$ ${\displaystyle (x,y)\in R}$ ${\displaystyle xRy.}$

Отношение рефлексивно, если выполняется для каждого элемента , оно транзитивно , если выполняется для всех, оно антисимметрично, если выполняется для всех , и является отношением коннекса , если выполняется для всех . Частичный порядок по определению является рефлексивным, транзитивным и антисимметричным отношением. Полный порядок — это частичный порядок, который является коннексом. ${\displaystyle xRx}$ ${\displaystyle x\in X;}$ ${\displaystyle xRy{\text{ and }}yRz}$ ${\displaystyle xRz}$ ${\displaystyle x,y,z\in X;}$ ${\displaystyle xRy{\text{ and }}yRx}$ ${\displaystyle x=y}$ ${\displaystyle x,y\in X;}$ ${\displaystyle xRy{\text{ or }}yRx}$ ${\displaystyle x,y\in X.}$

Отношение содержится в другом отношении, когда все упорядоченные пары в также присутствуют в , то есть, следует для всех Теорема о расширении утверждает, что каждое отношение , которое является рефлексивным, транзитивным и антисимметричным (то есть частичным порядком), содержится в другом отношении , которое является рефлексивным, транзитивным, антисимметричным и коннексным (то есть полным порядком). ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle S;}$ ${\displaystyle xRy}$ ${\displaystyle xSy}$ ${\displaystyle x,y\in X.}$ ${\displaystyle R}$ ${\displaystyle S}$

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

Теорема доказывается в два шага. Во-первых, показывается, что если частичный порядок не сравнивает некоторые два элемента, то его можно расширить до порядка с надмножеством сравнимых пар. Максимальный частичный порядок не может быть расширен по определению, поэтому из этого шага следует, что максимальный частичный порядок должен быть полным порядком. На втором шаге лемма Цорна применяется для нахождения максимального частичного порядка, который расширяет любой заданный частичный порядок.

Для первого шага предположим, что заданный частичный порядок не сравнивается и . Тогда порядок расширяется путем первого добавления пары к отношению, что может привести к нетранзитивному отношению, а затем восстановления транзитивности путем добавления всех пар, таких что Это создает отношение, которое по-прежнему является рефлексивным, антисимметричным и транзитивным и которое строго содержит исходное. Из этого следует, что если расширяющиеся частичные порядки сами частично упорядочены расширением, то любой максимальный элемент этого порядка расширения должен быть полным порядком. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle xRy}$ ${\displaystyle qRp}$ ${\displaystyle qRx{\text{ and }}yRp.}$ ${\displaystyle R}$

Далее показано, что частично упорядоченное множество частичных порядков , расширяющихся , упорядоченных расширением, имеет максимальный элемент. Существование такого максимального элемента доказывается применением леммы Цорна к этому частично упорядоченному множеству. Лемма Цорна утверждает, что частично упорядоченное множество, в котором каждая цепь имеет верхнюю границу, имеет максимальный элемент. Цепь в этом частично упорядоченном множестве представляет собой множество отношений, в котором для любых двух отношений одно расширяет другое. Верхняя граница для цепи может быть найдена как объединение отношений в цепи, . Это объединение является отношением, которое расширяет , поскольку каждый элемент из является частичным порядком, имеющим в качестве подмножества. Далее показано, что является транзитивным отношением. Предположим, что и находятся в , так что существуют такие, что и . Поскольку является цепью, одно из или должно расширять другое и содержать как и , и в силу своей транзитивности оно также содержит , как и объединение. Аналогично можно показать, что является антисимметричным. Таким образом, является расширением , поэтому оно принадлежит к частично упорядоченному множеству расширений и является верхней границей для . ${\displaystyle R}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle \textstyle \bigcup {\mathcal {C}}}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle R}$ ${\displaystyle \textstyle \bigcup {\mathcal {C}}}$ ${\displaystyle (x,y)}$ ${\displaystyle (y,z)}$ ${\displaystyle \textstyle \bigcup {\mathcal {C}},}$ ${\displaystyle S,T\in {\mathcal {C}}}$ ${\displaystyle (x,y)\in S}$ ${\displaystyle (y,z)\in T}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle (x,y)}$ ${\displaystyle (y,z)}$ ${\displaystyle (x,z)}$ ${\displaystyle \textstyle \bigcup {\mathcal {C}}}$ ${\displaystyle \textstyle \bigcup {\mathcal {C}}}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {C}}}$

Этот аргумент показывает, что лемма Цорна может быть применена к частично упорядоченному множеству расширений , производя максимальный элемент . На первом шаге этот максимальный элемент должен быть полным порядком, что завершает доказательство. ${\displaystyle R}$ ${\displaystyle Q}$

Сила

Некоторая форма аксиомы выбора необходима для доказательства теоремы о расширении Шпильрайна. Теорема о расширении подразумевает аксиому конечного выбора : если объединению семейства конечных множеств дан пустой частичный порядок, и он расширен до полного порядка, расширение определяет выбор из каждого конечного множества, его минимальный элемент в полном порядке. Хотя конечный выбор является слабой версией аксиомы выбора, он независим от теории множеств Цермело–Френкеля без выбора. ^[2]

Теорема расширения Шпильрайна вместе с другим следствием аксиомы выбора, принципом, что каждый полный порядок имеет конфинальный полный порядок , может быть объединена для доказательства полной аксиомы выбора. С этими предположениями можно выбрать элемент из любого заданного множества, расширив его пустой частичный порядок, найдя конфинальный полный порядок и выбрав минимальный элемент из этого полного порядка. ^[3]

Другие теоремы расширения

Эрроу утверждал, что каждый предпорядок (рефлексивное и транзитивное отношение) может быть расширен до полного предпорядка (транзитивного и коннексного отношения). ^[4] Это утверждение было позже доказано Ханссоном. ^{[5] [6]}

Судзумура доказал, что бинарное отношение может быть расширено до полного предпорядка тогда и только тогда, когда оно является согласованным по Судзумуре , что означает, что не существует цикла элементов, такого что для каждой пары последовательных элементов и существует некоторая пара последовательных элементов в цикле, для которой не выполняется. ^[6] ${\displaystyle xRy}$ ${\displaystyle (x,y),}$ ${\displaystyle (x,y)}$ ${\displaystyle yRx}$

Ссылки

1. Шпильрайн, Эдвард (1930), "Sur l'extension de l'ordre partiel" (PDF) , Fundamenta Mathematicae (на французском языке), 16 : 386–389, doi : 10.4064/fm-16-1-386-389
2. Мур, Грегори Х. (1982), Аксиома выбора Цермело: ее происхождение, развитие и влияние, Исследования по истории математики и физических наук, т. 8, Нью-Йорк: Springer-Verlag, стр. 222, doi :10.1007/978-1-4613-9478-5, ISBN 0-387-90670-3, МР  0679315
3. Howard, Paul; Rubin, Jean E. (1998), "Note 121", Consequences of the Axiom of Choice , Mathematical Surveys and Monographs, т. 59, Providence, Rhode Island: American Mathematical Society, стр. 299, doi :10.1090/surv/059, ISBN 0-8218-0977-6, г-н  1637107
4. Эрроу, Кеннет Дж. (2012), «IV.3: Квазиупорядочения и совместимые слабые упорядочения», Социальный выбор и индивидуальные ценности (3-е изд.), Издательство Йельского университета, стр. 64, ISBN 978-0-300-18698-7
5. Ханссон, Бенгт (1968), «Структуры выбора и отношения предпочтения», Synthese , 18 (4): 443–458, doi :10.1007/BF00484979, JSTOR  20114617; см. лемму 3
6. Cato, Susumu (август 2011 г.), «Шпильрайн, Эрроу и Судзумура: краткие доказательства теорем о расширении и расширение», Metroeconomica , 63 (2): 235–249, doi :10.1111/j.1467-999x.2011.04130.x