Квазиупорядочение скважин

В математике, в частности теории порядка, -квазиупорядочение или wqo - это квазиупорядочение, такое, что любая бесконечная последовательность элементов $x\; 0,\; x\; 1,\; x\; 2,\dots \; \{\backslash \; Displaystyle\; x\_\; \{0\},\; x\_\; \{1\},\; x\_\; \{2\},\; \backslash \; ldots\}$from $X\; \{\backslash \; displaystyle\; X\}$содержит возрастающую пару $xi\; \le \; xj\; \{\backslash \; displaystyle\; x\_\; \{i\}\; \backslash \; leq\; x\_\; \{j\}\}$с .

• 1 Мотивация
• 2 Формальное определение
• 3 Примеры
• 4 Сравнение частичных порядков WQO и скважин
• 5 Бесконечные возрастающие подпоследовательности
• 6 Свойства wqos
• 7 Примечания
• 8 Ссылки
• 9 См. Также

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

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

A хорошее квазиупорядочение на множестве $X\; \{\backslash \; displaystyle\; X\}$- это квазиупорядочение (т.е., рефлексивное, транзитивное бинарное отношение ) такое, что любая бесконечная последовательность элементов $x\; 0,\; x\; 1,\; x\; 2,\dots \; \{\backslash \; Displaystyle\; x\_\; \{0\},\; x\_\; \{1\},\; x\_\; \{2\},\; \backslash \; ldots\}$from $X\; \{\backslash \; displaystyle\; X\}$содержит возрастающую пару $xi\; \le \; xj\; \{\backslash \; displaystyle\; x\_\; \{i\}\; \backslash \; leq\; x\_\; \{j\}\}$с . Набор $X\; \{\backslash \; displaystyle\; X\}$называется хорошо квазиупорядоченным, или коротко wqo .

A хорошо частично упорядоченным, или a wpo - это wqo, которое является надлежащим отношением упорядочения, т. е. оно антисимметрично.

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

Рис.1: Целые числа с обычным порядком Рис.2: Диаграмма Хассе натуральных чисел, упорядоченных по делимости Рис.3: Диаграмма Хассе $N\; 2\; \{\backslash \; displaystyl\; e\; \backslash \; mathbb\; \{N\}\; ^\; \{2\}\}$с покомпонентным порядком

• $(N,\; \le )\; \{\backslash \; displaystyle\; (\backslash \; mathbb\; \{N\},\; \backslash \; leq)\}$, набор натуральных чисел со стандартным порядком, является хорошо частичным порядком (фактически, хорошим порядком ). Однако $(Z,\; \le )\; \{\backslash \; displaystyle\; (\backslash \; mathbb\; \{Z\},\; \backslash \; leq)\}$, набор положительных и отрицательных целых чисел, не хорошо- квазипорядок, потому что он не обоснован (см. рис.1).

• $(N,\; |)\; \{\backslash \; displaystyle\; (\backslash \; mathbb\; \{N\},\; |)\}$, множество естественных числа, упорядоченные по делимости, является не хорошо квазипорядком: простые числа представляют собой бесконечную антицепь (см. рис.2).

• $(N\; k,\; \le )\; \{\backslash \; displaystyle\; (\backslash \; mathbb\; \{\; N\}\; ^\; \{k\},\; \backslash \; leq)\}$, набор векторов $k\; \{\backslash \; displaystyle\; k\}$натуральных чисел (где $k\; \{\backslash \; displaystyle\; k\; \}$конечно) с покомпонентным упорядочением, является вполне частичным порядком (лемма Диксона ; см. Рис.3). В более общем смысле, если $(X,\; \le )\; \{\backslash \; displaystyle\; (X,\; \backslash \; leq)\}$хорошо квазипорядок, то $(X\; k,\; \le \; k)\; \{\backslash \; displaystyle\; (\; X\; ^\; \{k\},\; \backslash \; leq\; ^\; \{k\})\}$также является хорошо квазипорядком для всех $k\; \{\backslash \; displaystyle\; k\}$.

• Пусть $X\; \{\backslash \; displaystyle\; X\}$- произвольное конечное множество по крайней мере из двух элементов. Набор $X\; \ast \; \{\backslash \; displaystyle\; X\; ^\; \{*\}\}$ из слов над $X\; \{\backslash \; displaystyle\; X\}$упорядочен лексикографически (как в словаре) не квази-порядок, потому что он содержит бесконечную убывающую последовательность $b,\; ab,\; aab,\; aaab,\dots \; \{\backslash \; displaystyle\; b,\; ab,\; aab,\; aaab,\; \backslash \; ldots\}$. Точно так же $X\; \ast \; \{\backslash \; displaystyle\; X\; ^\; \{*\}\}$, упорядоченный по отношению префикса , является не квазипорядком, потому что предыдущая последовательность является бесконечной антицепью этого частичного порядка. Однако $X\; \ast \; \{\backslash \; displaystyle\; X\; ^\; \{*\}\}$, упорядоченный отношением подпоследовательности, является вполне частичным порядком. (Если $X\; \{\backslash \; displaystyle\; X\}$имеет только один элемент, эти три частичных порядка идентичны.)

• В более общем смысле, $(X\; \ast ,\; \le )\; \{\backslash \; displaystyle\; (X\; ^\; \{*\},\; \backslash \; leq)\}$, набор конечных $X\; \{\backslash \; displaystyle\; X\}$-последовательностей, упорядоченных с помощью встраивания, является хорошо- квазипорядок тогда и только тогда, когда $(X,\; \le )\; \{\backslash \; displaystyle\; (X,\; \backslash \; leq)\}$является квазипорядком (лемма Хигмана ). Напомним, что последовательность $u\; \{\backslash \; displaystyle\; u\}$встраивается в последовательность $v\; \{\backslash \; displaystyle\; v\}$путем нахождения подпоследовательности $v\; \{\backslash \; displaystyle\; v\}$, который имеет ту же длину, что и $u\; \{\backslash \; displaystyle\; u\}$, и доминирует в нем поэтапно. Когда $(X,\; =)\; \{\backslash \; displaystyle\; (X,\; =)\}$- неупорядоченный набор, $u\; \le \; v\; \{\backslash \; displaystyle\; u\; \backslash \; leq\; v\}$если и только если $u\; \{\backslash \; displaystyle\; u\}$является подпоследовательностью $v\; \{\backslash \; displaystyle\; v\}$.

• $(X\; \omega ,\; \le )\; \{\backslash \; displaystyle\; (X\; ^\; \{\backslash \; omega\},\; \backslash \; leq)\}$, набор бесконечных последовательностей в хорошо квазипорядке $(X,\; \le )\; \{\backslash \; displaystyle\; (X,\; \backslash \; leq)\}$, упорядоченный по встраиванию не в целом квазипорядок. То есть лемма Хигмана не переносится на бесконечные последовательности. Улучшенный квазипорядок был введен для обобщения леммы Хигмана на последовательности произвольной длины.

• Вложение между конечными деревьями с узлами, помеченными элементами wqo $(X,\; \le )\; \{\backslash \; displaystyle\; (X,\; \backslash \; leq)\}$- это wqo (Теорема Крускала о дереве ).

• Вложение между бесконечными деревьями с узлами, помеченными элементами wqo $(X,\; \le )\; \{\backslash \; displaystyle\; (\; X,\; \backslash \; leq)\}$- это wqo (теорема Нэша-Вильямса ').

• Вложение между счетным рассеянным линейным порядком типы - это хороший квазипорядок (Теорема Лавера ).

• Вложение между счетными булевыми алгебрами - это хороший квазипорядок. Это следует из теоремы Лавера и теоремы Кетонена.

• Конечные графы, упорядоченные с помощью понятия вложения, называемого «второстепенный граф », являются хорошо квазипорядком (теорема Робертсона – Сеймура ).

• Графы конечной древовидной глубины упорядочены индуцированным отношением подграфа образуют квази-порядок, как и кографы упорядочивают d с помощью индуцированных подграфов.

На практике, wqo, которым манипулирует, довольно часто не являются порядками (см. примеры выше), и теория технически более гладкая, если мы не требуем антисимметрии, поэтому он построен с использованием wqo в качестве основного понятия. С другой стороны, согласно Милнеру 1985, нельзя получить реального выигрыша в общности, рассматривая квазипорядки, а не частичные порядки... это просто более удобно.

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

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

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

• Учитывая квазиупорядочение $(X,\; \le )\; \{\backslash \; displaystyle\; (X,\; \backslash \; leq)\}$квазиупорядочение $(P\; (X),\; \le \; +)\; \{\backslash \; displaystyle\; (P\; (X),\; \backslash \; leq\; ^\; \{+\})\}$, определенный как $A\; \le \; +\; B\; ⟺\; \forall \; a\; \in \; A,\; \exists \; b\; \in \; B,\; a\; \le \; b\; \{\; \backslash \; displaystyle\; A\; \backslash \; leq\; ^\; \{+\}\; B\; \backslash \; iff\; \backslash \; forall\; a\; \backslash \; in\; A,\; \backslash \; exists\; b\; \backslash \; in\; B,\; a\; \backslash \; leq\; b\}$является обоснованным тогда и только тогда, когда $(X,\; \le )\; \{\backslash \; displaystyle\; (X,\; \backslash \; leq)\}$является wqo.

• Квазиупорядочение является wqo тогда и только тогда, когда соответствующий частичный порядок (полученный путем частичного разделения по $x\; \sim \; y\; ⟺\; x\; \le \; y\; \wedge \; y\; \le \; x\; \{\backslash \; displaystyle\; x\; \backslash \; sim\; y\; \backslash \; iff\; x\; \backslash \; leq\; y\; \backslash \; land\; y\; \backslash \; leq\; x\}$) не имеет бесконечных убывающих последовательностей или антицепей. (Это можно доказать, используя аргумент Рамсея, как указано выше.)

• Учитывая хорошо квазиупорядочение $(X,\; \le )\; \{\backslash \; displaystyle\; (X,\; \backslash \; leq)\}$, любая последовательность замкнутых вверх подмножеств $S\; 0\; \subseteq \; S\; 1\; \subseteq \; \cdots \; \subseteq \; X\; \{\backslash \; displaystyle\; S\_\; \{0\}\; \backslash \; substeq\; S\_\; \{1\}\; \backslash \; substeq\; \backslash \; cdots\; \backslash \; substeq\; X\}$в конечном итоге стабилизируется (то есть существует $n\; \in \; N\; \{\backslash \; displaystyle\; n\; \backslash \; in\; \backslash \; mathbb\; \{N\}\}$такое, что $S\; n\; =\; S\; n\; +\; 1\; =\; \cdots \; \{\backslash \; displaystyle\; S\_\; \{n\; \}\; =\; S\_\; \{n\; +\; 1\}\; =\; \backslash \; cdots\}$; подмножество $S\; \subseteq \; X\; \{\backslash \; displaystyle\; S\; \backslash \; substeq\; X\}$называется восходящим- закрытым если $\forall \; x,\; y\; \in \; X,\; x\; \le \; y\; \wedge \; x\; \in \; S\; \Rightarrow \; y\; \in \; S\; \{\backslash \; displaystyle\; \backslash \; forall\; x,\; y\; \backslash \; in\; X,\; x\; \backslash \; leq\; y\; \backslash \; wedge\; x\; \backslash \; in\; S\; \backslash \; Rightarrow\; y\; \backslash \; in\; S\}$): предположим противное $\forall \; i\; \in \; N,\; \exists \; j\; \in \; N,\; j>i,\; \exists \; x\; \in \; S\; j\; \setminus \; S\; i\; \{\backslash \; displaystyle\; \backslash \; forall\; i\; \backslash \; in\; \backslash \; mathbb\; \{\; N\},\; \backslash \; существует\; j\; \backslash \; in\; \backslash \; mathbb\; \{N\},\; j>i,\; \backslash \; существует\; x\; \backslash \; in\; S\_\; \{j\}\; \backslash \; setminus\; S\_\; \{i\}\}$, противоречие достигается путем извлечения бесконечной невозрастающей подпоследовательности.

• Учитывая хорошо квазиупорядоченный $(X,\; \le )\; \{\backslash \; displaystyle\; (X,\; \backslash \; leq)\}$, любое подмножество $S\; \{\backslash \; displaystyle\; S\}$из $X\; \{\backslash \; displaystyle\; X\}$имеет конечное число минимальных элементов по отношению к $\le \; \{\backslash \; displaystyle\; \backslash \; leq\}$, иначе минимальные элементы $S\; \{\backslash \; displaystyle\; S\}$составили бы бесконечную антицепь.

^Здесь x < y means: $x\; \le \; y\; \{\backslash \; displaystyle\; x\; \backslash \; leq\; y\}$и $y\; \nleqq \; x.\; \{\backslash \; displaystyle\; y\; \backslash \; nleq\; x.\}$

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

• Лучшее квазиупорядочение
• Предварительное упорядочение
• Хороший порядок