Хорошо-квази-упорядочение

Математическая концепция сравнения объектов

В математике , в частности в теории порядка , вполне квазиупорядоченный или wqo на множестве — это квазиупорядоченный набор, для которого каждая бесконечная последовательность элементов из содержит возрастающую пару с ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle x_{0},x_{1},x_{2},\ldots }$ ${\displaystyle X}$ ${\displaystyle x_{i}\leq x_{j}}$ ${\displaystyle i<j.}$

Мотивация

Хорошо обоснованная индукция может быть использована на любом множестве с хорошо обоснованным отношением , таким образом, нас интересует, когда квазипорядок хорошо обоснован. (Здесь, злоупотребляя терминологией, квазипорядок называется хорошо обоснованным, если соответствующий строгий порядок является хорошо обоснованным отношением.) Однако класс хорошо обоснованных квазипорядков не замкнут относительно определенных операций — то есть, когда квазипорядок используется для получения нового квазипорядка на множестве структур, полученных из нашего исходного множества, этот квазипорядок оказывается не хорошо обоснованным. Накладывая более жесткие ограничения на исходный хорошо обоснованный квазипорядок, можно надеяться гарантировать, что наши производные квазипорядки по-прежнему будут хорошо обоснованными. ${\displaystyle \leq }$ ${\displaystyle x\leq y\land y\nleq x}$

Примером этого является операция степенного множества . При наличии квазиупорядочения для множества можно определить квазиупорядочение на степенном множестве , установив тогда и только тогда, когда для каждого элемента из можно найти некоторый элемент из , который больше его относительно . Можно показать, что это квазиупорядочение на не обязательно должно быть хорошо обоснованным, но если принять исходное квазиупорядочение за хорошо квазиупорядоченное, то оно таковым является. ${\displaystyle \leq }$ ${\displaystyle X}$ ${\displaystyle \leq ^{+}}$ ${\displaystyle X}$ ${\displaystyle P(X)}$ ${\displaystyle A\leq ^{+}B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \leq }$ ${\displaystyle P(X)}$

Формальное определение

Вполне квазиупорядоченное множество — это квазиупорядоченное множество (т. е. рефлексивное транзитивное бинарное отношение ), такое, что любая бесконечная последовательность элементов из содержит возрастающую пару с . Множество называется вполне квазиупорядоченным , или коротко wqo . ${\displaystyle X}$ ${\displaystyle x_{0},x_{1},x_{2},\ldots }$ ${\displaystyle X}$ ${\displaystyle x_{i}\leq x_{j}}$ ${\displaystyle i<j}$ ${\displaystyle X}$

Частичный порядок ( wpo ) — это wqo, который является отношением правильного упорядочения, т. е. он антисимметричен .

Среди других способов определения wqo, можно сказать, что они являются квазипорядками, которые не содержат бесконечных строго убывающих последовательностей (вида ) ^[1] или бесконечных последовательностей попарно несравнимых элементов. Следовательно, квазипорядок ( X , ≤) является wqo тогда и только тогда, когда ( X , <) является обоснованным и не имеет бесконечных антицепей . ${\displaystyle x_{0}>x_{1}>x_{2}>\cdots }$

Порядковый тип

Пусть будет хорошо частично упорядоченным. (Необходимо конечная) последовательность элементов из , которая не содержит пары с , обычно называется плохой последовательностью . Дерево плохих последовательностей — это дерево, которое содержит вершину для каждой плохой последовательности и ребро, соединяющее каждую непустую плохую последовательность с ее родителем . Корень из соответствует пустой последовательности. Поскольку не содержит бесконечной плохой последовательности, дерево не содержит бесконечного пути, начинающегося с корня. ^{[ требуется ссылка ]} Следовательно, каждая вершина из имеет порядковую высоту , которая определяется трансфинитной индукцией как . Порядковый тип из , обозначаемый , является порядковой высотой корня из . ${\displaystyle X}$ ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$ ${\displaystyle X}$ ${\displaystyle x_{i}\leq x_{j}}$ ${\displaystyle i<j}$ ${\displaystyle T_{X}}$ ${\displaystyle (x_{1},\ldots ,x_{n-1},x_{n})}$ ${\displaystyle (x_{1},\ldots ,x_{n-1})}$ ${\displaystyle T_{X}}$ ${\displaystyle X}$ ${\displaystyle T_{X}}$ ${\displaystyle v}$ ${\displaystyle T_{X}}$ ${\displaystyle o(v)}$ ${\displaystyle o(v)=\lim _{w\mathrm {\ child\ of\ } v}(o(w)+1)}$ ${\displaystyle X}$ ${\displaystyle o(X)}$ ${\displaystyle T_{X}}$

Линеаризация — это расширение частичного порядка до полного порядка. Легко проверить, что — верхняя граница порядкового типа каждой линеаризации . Де Йонг и Парих ^[1] доказали, что на самом деле всегда существует линеаризация , которая достигает максимального порядкового типа . ${\displaystyle X}$ ${\displaystyle o(X)}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle o(X)}$

Примеры

Рис.1: Целые числа в обычном порядке

Рис.2: Диаграмма Хассе натуральных чисел, упорядоченных по делимости

Рис.3: Диаграмма Хассе с покомпонентным порядком ${\displaystyle \mathbb {N} ^{2}}$

• ${\displaystyle (\mathbb {N} ,\leq )}$, множество натуральных чисел со стандартным порядком, является вполне частичным порядком (фактически, вполне порядком ). Однако, , множество положительных и отрицательных целых чисел, не является вполне квазипорядком, поскольку оно не является вполне обоснованным (см. рис. 1). ${\displaystyle (\mathbb {Z} ,\leq )}$
• ${\displaystyle (\mathbb {N} ,|)}$, множество натуральных чисел, упорядоченное по признаку делимости, не является вполне квазипорядком: простые числа представляют собой бесконечную антицепь (см. рис.2).
• ${\displaystyle (\mathbb {N} ^{k},\leq )}$, множество векторов натуральных чисел (где конечно) с покомпонентным порядком , является вполне частичным порядком ( лемма Диксона ; см. рис.3). В более общем случае, если является вполне квазипорядком, то также является вполне квазипорядком для всех . ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle (X,\leq )}$ ${\displaystyle (X^{k},\leq ^{k})}$ ${\displaystyle k}$
• Пусть будет произвольным конечным множеством с по крайней мере двумя элементами. Множество слов , упорядоченное лексикографически (как в словаре), не является вполне квазипорядком, поскольку содержит бесконечную убывающую последовательность . Аналогично, упорядочение по префиксному отношению не является вполне квазипорядком, поскольку предыдущая последовательность является бесконечной антицепью этого частичного порядка. Однако, упорядочение по отношению подпоследовательности является вполне частичным порядком. ^[2] (Если имеет только один элемент, эти три частичных порядка идентичны.) ${\displaystyle X}$ ${\displaystyle X^{*}}$ ${\displaystyle X}$ ${\displaystyle b,ab,aab,aaab,\ldots }$ ${\displaystyle X^{*}}$ ${\displaystyle X^{*}}$ ${\displaystyle X}$
• В более общем случае , множество конечных -последовательностей, упорядоченных вложением, является вполне квазипорядком тогда и только тогда, когда является вполне квазипорядком ( лемма Хигмана ). Напомним, что вложение последовательности в последовательность осуществляется путем нахождения подпоследовательности , которая имеет ту же длину, что и и которая доминирует над ней почленно. Когда является неупорядоченным множеством, тогда и только тогда, когда является подпоследовательностью . ${\displaystyle (X^{*},\leq )}$ ${\displaystyle X}$ ${\displaystyle (X,\leq )}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle (X,=)}$ ${\displaystyle u\leq v}$ ${\displaystyle u}$ ${\displaystyle v}$
• ${\displaystyle (X^{\omega },\leq )}$, множество бесконечных последовательностей над вполне квазипорядком , упорядоченное вложением, не является вполне квазипорядком в общем случае. То есть лемма Хигмана не переносится на бесконечные последовательности. Были введены более совершенные квазипорядки для обобщения леммы Хигмана на последовательности произвольной длины. ${\displaystyle (X,\leq )}$
• Вложение между конечными деревьями с узлами, помеченными элементами wqo, является wqo ( теорема Краскала о дереве ). ${\displaystyle (X,\leq )}$
• Вложение между бесконечными деревьями с узлами, помеченными элементами wqo, является wqo ( теорема Нэша-Вильямса ). ${\displaystyle (X,\leq )}$
• Вложение между счетными разбросанными линейными типами порядка является вполне квазипорядком ( теорема Лэйвера ).
• Вложение между счетными булевыми алгебрами является вполне квазипорядком. Это следует из теоремы Лэйвера и теоремы Кетонена.
• Конечные графы, упорядоченные с помощью понятия вложения, называемого « минор графа », являются вполне квазипорядком ( теорема Робертсона–Сеймура ).
• Графы конечной глубины дерева, упорядоченные отношением индуцированного подграфа, образуют вполне квазипорядок ^[3] , как и кографы, упорядоченные индуцированными подграфами ^{[4] .}

Построение новых wpo из имеющихся

Пусть и будут двумя непересекающимися множествами wpo. Пусть , и определяют частичный порядок на , допуская, что если и только если для тех же и . Тогда есть wpo, и , где обозначает натуральную сумму ординалов. ^[1] ${\displaystyle X_{1}}$ ${\displaystyle X_{2}}$ ${\displaystyle Y=X_{1}\cup X_{2}}$ ${\displaystyle Y}$ ${\displaystyle y_{1}\leq _{Y}y_{2}}$ ${\displaystyle y_{1},y_{2}\in X_{i}}$ ${\displaystyle i\in \{1,2\}}$ ${\displaystyle y_{1}\leq _{X_{i}}y_{2}}$ ${\displaystyle Y}$ ${\displaystyle o(Y)=o(X_{1})\oplus o(X_{2})}$ ${\displaystyle \oplus }$

Для заданных множеств wpo и , определяем частичный порядок декартова произведения , допуская тогда и только тогда, когда и . Тогда есть wpo (это обобщение леммы Диксона ), и , где обозначает натуральное произведение ординалов. ^[1] ${\displaystyle X_{1}}$ ${\displaystyle X_{2}}$ ${\displaystyle Y=X_{1}\times X_{2}}$ ${\displaystyle (a_{1},a_{2})\leq _{Y}(b_{1},b_{2})}$ ${\displaystyle a_{1}\leq _{X_{1}}b_{1}}$ ${\displaystyle a_{2}\leq _{X_{2}}b_{2}}$ ${\displaystyle Y}$ ${\displaystyle o(Y)=o(X_{1})\otimes o(X_{2})}$ ${\displaystyle \otimes }$

При наличии множества wpo пусть будет множеством конечных последовательностей элементов , частично упорядоченных отношением подпоследовательности. Это означает, что пусть тогда и только тогда, когда существуют индексы такие, что для каждого . По лемме Хигмана есть wpo. Порядковый тип равен ^[1] [ ^5] ${\displaystyle X}$ ${\displaystyle X^{*}}$ ${\displaystyle X}$ ${\displaystyle (x_{1},\ldots ,x_{n})\leq _{X^{*}}(y_{1},\ldots ,y_{m})}$ ${\displaystyle 1\leq i_{1}<\cdots <i_{n}\leq m}$ ${\displaystyle x_{j}\leq _{X}y_{i_{j}}}$ ${\displaystyle 1\leq j\leq n}$ ${\displaystyle X^{*}}$ ${\displaystyle X^{*}}$ $${\displaystyle o(X^{*})={\begin{cases}\omega ^{\omega ^{o(X)-1}},&o(X){\text{ finite}};\\\omega ^{\omega ^{o(X)+1}},&o(X)=\varepsilon _{\alpha }+n{\text{ for some }}\alpha {\text{ and some finite }}n;\\\omega ^{\omega ^{o(X)}},&{\text{otherwise}}.\end{cases}}}$$

Для заданного множества wpo пусть будет множеством всех конечных корневых деревьев, вершины которых помечены элементами из . Частично упорядочить отношением вложения деревьев . По теореме Краскала о дереве , есть wpo. Этот результат нетривиален даже для случая (который соответствует немаркированным деревьям), в котором равен малому ординалу Веблена . В общем случае для счетного мы имеем верхнюю границу в терминах функции коллапса ординала . (Малый ординал Веблена равен в этой ординальной нотации.) ^[6] ${\displaystyle X}$ ${\displaystyle T(X)}$ ${\displaystyle X}$ ${\displaystyle T(X)}$ ${\displaystyle T(X)}$ ${\displaystyle |X|=1}$ ${\displaystyle o(T(X))}$ ${\displaystyle o(X)}$ ${\displaystyle o(T(X))\leq \vartheta (\Omega ^{\omega }o(X))}$ ${\displaystyle \vartheta }$ ${\displaystyle \vartheta (\Omega ^{\omega })}$

Wqo против хорошо частичных заказов

На практике wqo's, которыми манипулируют, довольно часто не являются упорядочениями (см. примеры выше), и теория технически более гладкая ^{[ требуется цитата ]} , если мы не требуем антисимметрии, поэтому она строится с wqo's как с базовым понятием. С другой стороны, согласно Milner 1985, никакого реального выигрыша в общности не получается, если рассматривать квазипорядки вместо частичных порядков... это просто удобнее.

Обратите внимание, что wpo является wqo, и что wqo порождает wpo между классами эквивалентности, индуцированными ядром wqo. Например, если мы упорядочиваем по делимости, мы получаем тогда и только тогда, когда , так что . ${\displaystyle \mathbb {Z} }$ ${\displaystyle n\equiv m}$ ${\displaystyle n=\pm m}$ ${\displaystyle (\mathbb {Z} ,|)\approx (\mathbb {N} ,|)}$

Бесконечные возрастающие подпоследовательности

Если равно wqo, то каждая бесконечная последовательность содержит бесконечную возрастающую подпоследовательность (с ). Такая подпоследовательность иногда называется идеальной . Это можно доказать с помощью аргумента Рамсея : для некоторой последовательности рассмотрим множество индексов , такое, что не имеет большего или равного ей справа, т. е. с . Если равно бесконечности, то -извлеченная подпоследовательность противоречит предположению, что равно wqo. Поэтому равно конечно, и любой с большим, чем любой индекс в , может использоваться в качестве начальной точки бесконечной возрастающей подпоследовательности. ${\displaystyle (X,\leq )}$ ${\displaystyle x_{0},x_{1},x_{2},\ldots ,}$ ${\displaystyle x_{n_{0}}\leq x_{n_{1}}\leq x_{n_{2}}\leq \cdots }$ ${\displaystyle n_{0}<n_{1}<n_{2}<\cdots }$ ${\displaystyle (x_{i})_{i}}$ ${\displaystyle I}$ ${\displaystyle i}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle i<j}$ ${\displaystyle I}$ ${\displaystyle I}$ ${\displaystyle X}$ ${\displaystyle I}$ ${\displaystyle x_{n}}$ ${\displaystyle n}$ ${\displaystyle I}$

Существование таких бесконечно возрастающих подпоследовательностей иногда принимается за определение вполне квазиупорядоченного порядка, что приводит к эквивалентному понятию.

Свойства wqos

• При наличии квазипорядка квазипорядок, определяемый с помощью , является обоснованным тогда и только тогда, когда является wqo. ^[7] ${\displaystyle (X,\leq )}$ ${\displaystyle (P(X),\leq ^{+})}$ ${\displaystyle A\leq ^{+}B\iff \forall a\in A,\exists b\in B,a\leq b}$ ${\displaystyle (X,\leq )}$
• Квазиупорядочение является wqo тогда и только тогда, когда соответствующий частичный порядок (полученный путем факторизации по ) не имеет бесконечных нисходящих последовательностей или антицепей . (Это можно доказать с помощью аргумента Рамсея , как указано выше.) ${\displaystyle x\sim y\iff x\leq y\land y\leq x}$
• При условии полного квазиупорядочения любая последовательность замкнутых вверх подмножеств в конечном итоге стабилизируется (то есть существует такое, что ; подмножество называется замкнутым вверх, если ): если предположить противное , то противоречие достигается путем извлечения бесконечной невозрастающей подпоследовательности. ${\displaystyle (X,\leq )}$ ${\displaystyle S_{0}\subseteq S_{1}\subseteq \cdots \subseteq X}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle S_{n}=S_{n+1}=\cdots }$ ${\displaystyle S\subseteq X}$ ${\displaystyle \forall x,y\in X,x\leq y\wedge x\in S\Rightarrow y\in S}$ ${\displaystyle \forall i\in \mathbb {N} ,\exists j\in \mathbb {N} ,j>i,\exists x\in S_{j}\setminus S_{i}}$
• При условии полного квазиупорядочения любое подмножество имеет конечное число минимальных элементов относительно , ​​иначе минимальные элементы составляли бы бесконечную антицепь. ${\displaystyle (X,\leq )}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle \leq }$ ${\displaystyle S}$

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

• Лучший квазипорядок  – математическое отношениеPages displaying wikidata descriptions as a fallback
• Prewellordering  – Концепция теории множеств
• Вполне упорядоченный  – класс математических упорядочений

Примечания

^ Здесь x < y означает:и ${\displaystyle x\leq y}$ ${\displaystyle x\neq y.}$

Ссылки

1. de Jongh, Dick HG; Parikh, Rohit (1977). «Хорошо частичные упорядочения и иерархии». Indagationes Mathematicae (Proceedings) . 80 (3): 195–207. doi : 10.1016/1385-7258(77)90067-1 .
2. Gasarch, W. (1998), "Обзор рекурсивной комбинаторики", Handbook of Recursive Mathematics, Vol. 2 , Stud. Logic Found. Math., vol. 139, Amsterdam: North-Holland, стр. 1041–1176, doi :10.1016/S0049-237X(98)80049-9, MR  1673598. См. в частности страницу 1160.
3. Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), "Лемма 6.13", Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, т. 28, Гейдельберг: Springer, стр. 137, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, МР  2920058.
4. Дамашке, Питер (1990), «Индуцированные подграфы и хорошее квазиупорядочение», Журнал теории графов , 14 (4): 427–435, doi :10.1002/jgt.3190140406, MR  1067237.
5. Шмидт, Диана (1979). Хорошо частичные упорядочения и их максимальные типы порядка (Habilitationsschrift). Гейдельберг.Переиздано в: Schmidt, Diana (2020). «Well-partial orderings and their maximum order types». В Schuster, Peter M.; Seisenberger, Monika; Weiermann, Andreas (ред.). Well-Quasi Orders in Computation, Logic, Language and Reasoning . Trends in Logic. Vol. 53. Springer. pp. 351–391. doi :10.1007/978-3-030-30229-0_13.
6. Ратьен, Михаэль; Вайерманн, Андреас (1993). «Исследования теории доказательств по теореме Крускала». Annals of Pure and Applied Logic . 60 : 49–88. doi : 10.1016/0168-0072(93)90192-G .
7. Форстер, Томас (2003). «Лучшие квазиупорядочения и коиндукция». Теоретическая информатика . 309 (1–3): 111–123. doi :10.1016/S0304-3975(03)00131-2.

• Диксон, Л. Э. (1913). «Конечность нечетных совершенных и примитивных обильных чисел с r различными простыми множителями». American Journal of Mathematics . 35 (4): 413–422. doi :10.2307/2370405. JSTOR  2370405.
• Хигман, Г. (1952). «Упорядочение по делимости в абстрактных алгебрах». Труды Лондонского математического общества . 2 : 326–336. doi :10.1112/plms/s3-2.1.326.
• Kruskal, JB (1972). «Теория хорошего квазиупорядочения: часто встречающаяся концепция». Журнал комбинаторной теории . Серия A. 13 (3): 297–305. doi : 10.1016/0097-3165(72)90063-5 .
• Кетонен, Юсси (1978). «Структура счетных булевых алгебр». Annals of Mathematics . 108 (1): 41–89. doi :10.2307/1970929. JSTOR  1970929.
• Milner, EC (1985). "Basic WQO- and BQO-theory". В Rival, I. (ред.). Графы и порядок. Роль графов в теории упорядоченных множеств и ее приложениях . D. Reidel Publishing Co. стр. 487–502. ISBN 90-277-1943-8.
• Галлье, Жан Х. (1991). «Что такого особенного в теореме Крускала и ординале Γo? Обзор некоторых результатов в теории доказательств». Annals of Pure and Applied Logic . 53 (3): 199–260. doi :10.1016/0168-0072(91)90022-E.