Квазиупорядочение - Википедия - Well-quasi-ordering

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

Мотивация

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

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

А хорошо квазиупорядоченный на съемочной площадке ${ displaystyle X}$ это квазиупорядочение (т.е. рефлексивный, переходный бинарное отношение ) такой, что любой бесконечный последовательность элементов ${ Displaystyle x_ {0}, x_ {1}, x_ {2}, ldots}$ из ${ displaystyle X}$ содержит возрастающую пару ${ displaystyle x_ {i} leq x_ {j}}$ с ${ displaystyle i$ . Набор ${ displaystyle X}$ как говорят квазиупорядоченный, или в ближайшее время wqo.

А ну частичный порядок, или wpo, является wqo, которое является правильным отношением упорядочения, т.е. антисимметричный.

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

Примеры

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

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

Рис.3: Диаграмма Хассе

{ Displaystyle mathbb {N} ^ {2}}

с покомпонентным порядком

${ Displaystyle ( mathbb {N}, leq)}$ , множество натуральных чисел со стандартным порядком, является вполне частичным порядком (фактически, в порядке ). Тем не мение, ${ Displaystyle ( mathbb {Z}, leq)}$ , множество положительных и отрицательных целых чисел, есть нет вполне квазипорядком, потому что он не обоснован (см. рис.1).

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

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

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

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

${ Displaystyle (Х ^ { omega}, leq)}$ , множество бесконечных последовательностей над хорошо квазипорядком ${ Displaystyle (Х, leq)}$ , упорядоченный по вложению, является нет ну-квазипорядок в целом. То есть лемма Хигмана не переносится на бесконечные последовательности. Лучше квазиупорядочения были введены для обобщения леммы Хигмена на последовательности произвольной длины.

Вложение между конечными деревьями с узлами, помеченными элементами wqo ${ Displaystyle (Х, leq)}$ это wqo (Теорема Крускала о дереве ).

Вложение между бесконечными деревьями с узлами, помеченными элементами wqo ${ Displaystyle (Х, leq)}$ это wqo (Нэш-Вильямс теорема).

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

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

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

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

Сравнение WQO с частичными заказами

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

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

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

Если ${ Displaystyle (Х, leq)}$ равно wqo, то каждая бесконечная последовательность ${ 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}$ ). Такую подпоследовательность иногда называют идеально.Это может быть доказано Аргумент Рамси: заданная последовательность ${ Displaystyle (х_ {я}) _ {я}}$ , рассмотрим множество ${ displaystyle I}$ индексов ${ displaystyle i}$ такой, что ${ displaystyle x_ {i}}$ не имеет большего или равного ${ displaystyle x_ {j}}$ справа, т.е. с ${ displaystyle i$ . Если ${ displaystyle I}$ бесконечно, то ${ displaystyle I}$ -выделенная подпоследовательность противоречит предположению, что ${ displaystyle X}$ это wqo. Так ${ displaystyle I}$ конечно, и любое ${ displaystyle x_ {n}}$ с ${ displaystyle n}$ больше любого индекса в ${ displaystyle I}$ может использоваться как начальная точка бесконечной возрастающей подпоследовательности.

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

Свойства wqos

Учитывая квазиупорядочение ${ Displaystyle (Х, leq)}$ квазиупорядочивание ${ Displaystyle (П (Х), leq ^ {+})}$ определяется ${ displaystyle A leq ^ {+} B iff forall a in A, существует b in B, a leq b}$ обоснованно тогда и только тогда, когда ${ Displaystyle (Х, leq)}$ это wqo.^[4]

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

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

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

Примечания

^ Здесь Икс < у средства: ${ displaystyle x leq y}$ и ${ displaystyle y nleq x.}$

^ Гасарх, В. (1998), "Обзор рекурсивной комбинаторики", Справочник по рекурсивной математике, Vol. 2, Stud. Логика найдена. Математика, 139, Амстердам: Северная Голландия, стр. 1041–1176, Дои:10.1016 / S0049-237X (98) 80049-9, МИСТЕР 1673598. См., В частности, страницу 1160.
^ Нешетржил, Ярослав; Оссона де Мендес, Патрис (2012), «Лемма 6.13», Разреженность: графики, структуры и алгоритмы, Алгоритмы и комбинаторика, 28, Гейдельберг: Springer, стр. 137, Дои:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, МИСТЕР 2920058.
^ Дамашке, Питер (1990), "Индуцированные подграфы и хорошо квазиупорядочение", Журнал теории графов, 14 (4): 427–435, Дои:10.1002 / jgt.3190140406, МИСТЕР 1067237.
^ Форстер, Томас (2003). «Лучше-квазиупорядочение и коиндукция». Теоретическая информатика. 309 (1–3): 111–123. Дои:10.1016 / S0304-3975 (03) 00131-2.

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

[1] Гасарх, В. (1998), "Обзор рекурсивной комбинаторики", Справочник по рекурсивной математике, Vol. 2, Stud. Логика найдена. Математика, 139, Амстердам: Северная Голландия, стр. 1041–1176, Дои:10.1016 / S0049-237X (98) 80049-9, МИСТЕР 1673598. См., В частности, страницу 1160.

[2] Нешетржил, Ярослав; Оссона де Мендес, Патрис (2012), «Лемма 6.13», Разреженность: графики, структуры и алгоритмы, Алгоритмы и комбинаторика, 28, Гейдельберг: Springer, стр. 137, Дои:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, МИСТЕР 2920058.

[3] Дамашке, Питер (1990), "Индуцированные подграфы и хорошо квазиупорядочение", Журнал теории графов, 14 (4): 427–435, Дои:10.1002 / jgt.3190140406, МИСТЕР 1067237.

[forster-4] Форстер, Томас (2003). «Лучше-квазиупорядочение и коиндукция». Теоретическая информатика. 309 (1–3): 111–123. Дои:10.1016 / S0304-3975 (03) 00131-2.

[1]

[1]

[2]

[3]

[4]