Введение

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

В математике, в частности в теории порядка, хорошее квазиупорядочение или wqo на множестве — это квазиупорядочение, для которого любая бесконечная последовательность элементов из содержит возрастающую пару с

Мотивация

Хорошо обоснованная индукция может быть применена к любому множеству с хорошо обоснованным отношением, поэтому возникает вопрос, когда квазипорядок является хорошо обоснованным. (Здесь, допуская некоторую вольность в терминологии, квазипорядок считается хорошо обоснованным, если соответствующий строгий порядок является хорошо обоснованным отношением.) Однако класс хорошо обоснованных квазипорядков не замкнут относительно некоторых операций — то есть, когда квазипорядок используется для получения нового квазипорядка на множестве структур, производном от исходного множества, этот квазипорядок может оказаться не хорошо обоснованным. Накладывая более строгие ограничения на исходный хорошо обоснованный квазипорядок, можно надеяться обеспечить, чтобы производные квазипорядки оставались хорошо обоснованными. Примером этого является операция взятия булеана (или подмножеств). Для заданного квазипорядка на множестве можно определить квазипорядок на булеане множества, установив , если и только если для каждого элемента из существует элемент из , который больше его относительно . Можно показать, что этот квазипорядок на булеане не обязательно является хорошо обоснованным, но если исходный квазипорядок является хорошо квазипорядком, то он таковым будет.

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

Хорошо квазиупорядоченное множество — это квазиупорядочение (то есть рефлексивное, транзитивное бинарное отношение), такое что любая бесконечная последовательность элементов из содержит возрастающую пару с . Множество называется хорошо квазиупорядоченным, или сокращенно wqo. Хорошо частичный порядок, или wpo, — это wqo, являющееся строгим отношением порядка, то есть антисимметричным. Среди других способов определения wqo можно сказать, что это квазиупорядочения, не содержащие бесконечных строго убывающих последовательностей (вида ) и бесконечных последовательностей попарно несравнимых элементов. Следовательно, квазиупорядочение (X, ≤) является wqo тогда и только тогда, когда (X, <) хорошо обосновано и не имеет бесконечных антицепей.

Обычный тип

Пусть задан хорошо частично упорядоченный набор . (Конечная) последовательность элементов из , не содержащая пары с , обычно называется плохой последовательностью. Дерево плохих последовательностей – это дерево, содержащее вершину для каждой плохой последовательности и ребро, соединяющее каждую непустую плохую последовательность с её родителем. Корень соответствует пустой последовательности. Поскольку не содержит бесконечной плохой последовательности, дерево не содержит бесконечного пути, начинающегося с корня. Следовательно, каждая вершина дерева имеет порядковую высоту , которая определяется трансфинитной индукцией как . Порядковый тип , обозначаемый , является порядковой высотой корня . Линеаризация – это расширение частичного порядка до полного порядка. Легко проверить, что является верхней гранью порядкового типа каждой линеаризации. Де Йонг и Парих доказали, что на самом деле всегда существует линеаризация, достигающая максимального порядкового типа .

Примеры

, множество натуральных чисел со стандартным упорядочением, является хорошо частичным порядком (в действительности, хорошо упорядоченным). Однако, множество целых чисел, состоящее из положительных и отрицательных чисел, не является хорошо квазипорядком, поскольку оно не является хорошо обоснованным (см. рис. 1). , множество натуральных чисел, упорядоченных по делимости, не является хорошо квазипорядком: простые числа образуют бесконечную антицепь (см. рис. 2). , множество векторов натуральных чисел (где конечно) с компонентным упорядочением, является хорошо частичным порядком (лемма Диксона; см. рис. 3). В более общем случае, если является хорошо квазипорядком, то также является хорошо квазипорядком для всех Пусть будет произвольным конечным множеством, содержащим не менее двух элементов. Множество слов над , упорядоченных лексикографически (как в словаре), не является хорошо квазипорядком, поскольку оно содержит бесконечную убывающую последовательность. Аналогично, множество, упорядоченное отношением префикса, не является хорошо квазипорядком, поскольку предыдущая последовательность является бесконечной антицепью этого частичного порядка. Однако, множество, упорядоченное отношением подпоследовательности, является хорошо частичным порядком. (Если содержит только один элемент, эти три частичных порядка совпадают.) В более общем случае, множество конечных последовательностей, упорядоченных вложением, является хорошо квазипорядком тогда и только тогда, когда является хорошо квазипорядком (лемма Хигмана). Напомним, что последовательность вкладывается в последовательность, находя подпоследовательность, которая имеет ту же длину, что и и доминирует над ней покомпонентно. Когда является неупорядоченным множеством, если и только если является подпоследовательностью , множество бесконечных последовательностей над хорошо квазипорядком , упорядоченных вложением, в общем случае не является хорошо квазипорядком. То есть, лемма Хигмана не переносится на бесконечные последовательности. Были введены более качественные квазипорядки для обобщения леммы Хигмана на последовательности произвольной длины. Вложение между конечными деревьями с узлами, помеченными элементами wqo, является wqo (теорема Крускала о деревьях). Вложение между бесконечными деревьями с узлами, помеченными элементами wqo, является wqo (теорема Нэша Уильямса). Вложение между счетными рассеянными линейными типами порядка является хорошо квазипорядком (теорема Лавера). Вложение между счетными булевыми алгебрами является хорошо квазипорядком. Это следует из теоремы Лавера и теоремы Кетонена. Конечные графы, упорядоченные понятием вложения, называемым "минором графа", являются хорошо квазипорядком (теорема Робертсона — Сеймура). Графы конечной глубины дерева, упорядоченные отношением индуцированного подграфа, образуют хорошо квазипорядок, как и кографы, упорядоченные индуцированными подграфами.

Создание новых WPO из данных

Пусть и будут два непересекающихся WPO-множества. Пусть , и определим частичный порядок на , полагая , если и только если для одного и того же . Тогда является WPO, и , где обозначает естественную сумму ординалов. Для заданного WPO-множества , пусть будет множеством всех конечных корневых деревьев, вершины которых помечены элементами . Определим частичный порядок на посредством отношения вложения деревьев. По теореме Крускала о деревьях, является WPO. Этот результат нетривиален даже для случая (который соответствует немаркированным деревьям), в котором случай равен малому ординалу Веблена. В общем случае, для счетного , у нас есть верхняя оценка в терминах функции коллапса ординалов. (Малый ординал Веблена равен в этой ординальной нотации.)

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

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

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

Если является wqo, то любая бесконечная последовательность содержит бесконечную возрастающую подпоследовательность (с ). Такая подпоследовательность иногда называется совершенной. Это можно доказать с помощью аргумента Рамзи: для данной последовательности , рассмотрим множество индексов таких, что не имеет большего или равного элемента справа, то есть с . Если бесконечно, то извлеченная подпоследовательность противоречит предположению, что является wqo. Следовательно, конечно, и любой с индексом, большим, чем любой индекс в , может быть использован в качестве начальной точки бесконечной возрастающей подпоследовательности. Существование таких бесконечных возрастающих подпоследовательностей иногда принимается за определение хорошо квази-упорядоченности, что приводит к эквивалентному понятию.

Свойства wqos

Для заданного квазипорядка квазипорядок, определяемый как , является хорошо обоснованным тогда и только тогда, когда является wqo.