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

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

Мотивация [ править ]

Хорошо обоснованная индукция может использоваться на любом множестве с хорошо обоснованным соотношением, поэтому каждый интересуется, когда квазипорядок хорошо обоснован. (Здесь, злоупотребляя терминологией, квазипорядок считается хорошо обоснованным, если соответствующий строгий порядок является хорошо обоснованным отношением.) Однако класс хорошо обоснованных квазипорядков не закрывается при определенных операциях, то есть когда квазипорядок используется для получения нового квазипорядка на множестве структур, производных от нашего первоначального набора, этот квазипорядок оказывается недостаточно обоснованным. Установив более строгие ограничения на исходный хорошо обоснованный квазипорядок, можно надеяться на то, что полученные нами квазиупорядочения будут по-прежнему хорошо обоснованными.${\ displaystyle \ leq}$${\ Displaystyle х \ leq 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 }$

Примеры [ править ]

Рис.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}$

• Позвольте быть произвольным конечным множеством по крайней мере с двумя элементами. Набор из слов над заказал лексикографическом (как в словаре) является не хорошо квазипорядком , поскольку она содержит бесконечную убывающую последовательность . Аналогичным образом , по заказу префикса отношения является не хорошо квазипорядок, потому что предыдущая последовательность является бесконечной антицепью этого частичного порядка. Однако упорядоченность по отношению подпоследовательности является вполне частичным порядком. ^[1] (Если имеется только один элемент, эти три частичных порядка идентичны.)${\displaystyle X}$ 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 )}$

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

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

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

• Графы конечной древовидной глубины, упорядоченные индуцированным отношением подграфов, образуют хорошо-квазипорядок ^[2], как и кографы, упорядоченные индуцированными подграфами. ^[3]

Wqo в сравнении с частичными порядками скважин [ править ]

На практике, wqo, которым манипулируют, довольно часто не является упорядочением (см. Примеры выше), и теория технически более гладкая ^{[ необходима цитата ],} если нам не требуется антисимметрия, поэтому она построена с использованием wqo в качестве основного понятия. С другой стороны, согласно Милнеру 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. So конечно, и любое значение с индексом больше любого может использоваться в качестве начальной точки бесконечной возрастающей подпоследовательности.${\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. ^[4]${\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}$

Примечания [ править ]

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

Ссылки [ править ]

• Диксон, Л. Е. (1913). «Конечность нечетных совершенных и примитивных избыточных чисел с r различными простыми множителями». Американский журнал математики . 35 (4): 413–422. DOI : 10.2307 / 2370405 . JSTOR  2370405 .
• Хигман, Г. (1952). «Упорядочение по делимости в абстрактных алгебрах». Труды Лондонского математического общества . 2 : 326–336. DOI : 10.1112 / ПНИЛИ / s3-2.1.326 .
• Kruskal, JB (1972). «Теория хорошо квазиупорядочения: часто обнаруживаемая концепция». Журнал комбинаторной теории . Серия А. 13 (3): 297–305. DOI : 10.1016 / 0097-3165 (72) 90063-5 .
• Кетонен, Юсси (1978). «Строение счетных булевых алгебр». Анналы математики . 108 (1): 41–89. DOI : 10.2307 / 1970929 . JSTOR  1970929 .
• Милнер, EC (1985). «Основы теории WQO и BQO». В « Сопернике», И. (ред.). Графики и порядок. Роль графов в теории упорядоченных множеств и ее приложениях . 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 .

См. Также [ править ]

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