Лучшее квазиупорядочение - Better-quasi-ordering

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

Мотивация

Хотя хорошо квазиупорядоченный привлекательное понятие, многие важные бесконечные операции не сохраняют хорошо квазиупорядоченность. Пример из-за Ричард Радо иллюстрирует это.^[1] В статье 1965 года Криспин Нэш-Уильямс сформулировал более сильное понятие лучший квазиупорядоченный чтобы доказать, что класс деревья высоты ω хорошо квазиупорядочен по топологический минор связь.^[2] С тех пор многие квазиупорядочения было доказано, что они хорошо квазиупорядочены, доказывая, что они лучше квазиупорядочения. Например, Ричард Лейвер установлен Теорема Лавера (ранее предполагалось Роланд Фраиссе ), доказав, что класс рассеянных линейный порядок типы лучше квазиупорядочены.^[3] Совсем недавно Карлос Мартинес-Ранеро доказал, что под аксиома правильного принуждения, класс Линии Ароншайна лучше квазиупорядочен по отношению вложимости.^[4]

Определение

В теории лучшего квазиупорядочения принято писать ${\displaystyle {_{*}}x}$ для последовательности ${\displaystyle x}$ с опущенным первым членом. Написать ${\displaystyle [\omega ]^{<\omega }}$ для множества конечных, строго возрастающих последовательности с условиями в ${\displaystyle \omega }$, и определим отношение ${\displaystyle \triangleleft }$ на ${\displaystyle [\omega ]^{<\omega }}$ следующим образом: ${\displaystyle s\triangleleft t}$ Если там есть ${\displaystyle u\in [\omega ]^{<\omega }}$ такой, что ${\displaystyle s}$ является строгим начальным отрезком ${\displaystyle u}$ и ${\displaystyle t={}_{*}u}$. Соотношение ${\displaystyle \triangleleft }$ не является переходный.

А блокировать ${\displaystyle B}$ это бесконечное подмножество ${\displaystyle [\omega ]^{<\omega }}$ содержащий начальный сегмент^{[требуется разъяснение ]} каждого бесконечного подмножества ${\displaystyle \bigcup B}$. Для квази-порядка ${\displaystyle Q}$, а ${\displaystyle Q}$-шаблон это функция из некоторого блока ${\displaystyle B}$ в ${\displaystyle Q}$. А ${\displaystyle Q}$-шаблон ${\displaystyle f\colon B\to Q}$ как говорят Плохо если ${\displaystyle f(s)\not \leq _{Q}f(t)}$^{[требуется разъяснение ]} для каждой пары ${\displaystyle s,t\in B}$ такой, что ${\displaystyle s\triangleleft t}$; в противном случае ${\displaystyle f}$ является хороший. Квазиупорядочение ${\displaystyle Q}$ называется лучший квазиупорядоченный если нет плохого ${\displaystyle Q}$-шаблон.

Чтобы упростить работу с этим определением, Нэш-Вильямс определяет барьер быть блоком, элементы которого попарно несравненный по отношению включения ${\displaystyle \subset }$. А ${\displaystyle Q}$-множество это ${\displaystyle Q}$-шаблон, домен которого является барьером. Заметив, что каждый блок содержит барьер, можно увидеть, что ${\displaystyle Q}$ квазиупорядочение лучше тогда и только тогда, когда нет плохих ${\displaystyle Q}$-множество.

Альтернативное определение Симпсона

Симпсон представил альтернативное определение лучший квазиупорядоченный с точки зрения Борелевские функции ${\displaystyle [\omega ]^{\omega }\to Q}$, где ${\displaystyle [\omega ]^{\omega }}$, множество бесконечных подмножеств ${\displaystyle \omega }$, дается обычный топология продукта.^[5]

Позволять ${\displaystyle Q}$ быть квази-упорядочивающим и наделять ${\displaystyle Q}$ с дискретная топология. А ${\displaystyle Q}$-множество является борелевской функцией ${\displaystyle [A]^{\omega }\to Q}$ для некоторого бесконечного подмножества ${\displaystyle A}$ из ${\displaystyle \omega }$. А ${\displaystyle Q}$-множество ${\displaystyle f}$ является Плохо если ${\displaystyle f(X)\not \leq _{Q}f({_{*}}X)}$ для каждого ${\displaystyle X\in [A]^{\omega }}$;${\displaystyle f}$ является хороший в противном случае. Квазиупорядочение ${\displaystyle Q}$ это лучший квазиупорядоченный если нет плохого ${\displaystyle Q}$-массив в этом смысле.

Основные теоремы

Многие важные результаты в теории лучшего квазиупорядочения являются следствиями леммы о минимальном плохом массиве, которая появляется в статье Симпсона.^[5] следующим образом. См. Также статью Лейвера,^[6] где в результате впервые была сформулирована лемма о минимальном плохом массиве. Этот метод был представлен в оригинальной статье Нэша-Вильямса 1965 года.

Предположим ${\displaystyle (Q,\leq _{Q})}$ это квазипорядок.^{[требуется разъяснение ]} А частичное ранжирование ${\displaystyle \leq '}$ из ${\displaystyle Q}$ это обоснованный частичный заказ из ${\displaystyle Q}$ такой, что ${\displaystyle q\leq 'r\to q\leq _{Q}r}$. Для плохого ${\displaystyle Q}$-массивы (в смысле Симпсона) ${\displaystyle f\colon [A]^{\omega }\to Q}$ и ${\displaystyle g\colon [B]^{\omega }\to Q}$, определять:

${\displaystyle g\leq ^{*}f{\text{ if }}B\subseteq A{\text{ and }}g(X)\leq 'f(X){\text{ for every }}X\in [B]^{\omega }}$

${\displaystyle g<^{*}f{\text{ if }}B\subseteq A{\text{ and }}g(X)<'f(X){\text{ for every }}X\in [B]^{\omega }}$

Мы говорим плохо ${\displaystyle Q}$-множество ${\displaystyle g}$ является минимально плохо (относительно частичного ранжирования ${\displaystyle \leq '}$) если нет плохого ${\displaystyle Q}$-множество ${\displaystyle f}$ такой, что ${\displaystyle f<^{*}g}$.Определения ${\displaystyle \leq ^{*}}$ и ${\displaystyle <'}$ зависеть от частичного ранжирования ${\displaystyle \leq '}$ из ${\displaystyle Q}$. Соотношение ${\displaystyle <^{*}}$ не является строгой частью отношения ${\displaystyle \leq ^{*}}$.

Теорема (Лемма о минимальном плохом массиве). Позволять ${\displaystyle Q}$ быть квазипорядок оснащен частичным ранжированием и предположим ${\displaystyle f}$ это плохо ${\displaystyle Q}$-множество. Тогда есть минимальный недостаток ${\displaystyle Q}$-множество ${\displaystyle g}$ такой, что ${\displaystyle g\leq ^{*}f}$.

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

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

Рекомендации

1. Радо, Ричард (1954). «Частичная упорядоченность множеств векторов». Математика. 1 (2): 89–95. Дои:10.1112 / S0025579300000565. Г-Н  0066441.
2. Нэш-Уильямс, К. Сент-Дж. А. (1965). «О хорошо квазиупорядоченных бесконечных деревьях». Математические труды Кембриджского философского общества. 61 (3): 697–720. Bibcode:1965PCPS ... 61..697N. Дои:10.1017 / S0305004100039062. ISSN  0305-0041. Г-Н  0175814.
3. Лейвер, Ричард (1971). "О гипотезе типа порядка Фрейсса". Анналы математики. 93 (1): 89–111. Дои:10.2307/1970754. JSTOR  1970754.
4. Мартинес-Ранеро, Карлос (2011). «Квази-упорядоченные линии Ароншайн». Fundamenta Mathematicae. 213 (3): 197–211. Дои:10.4064 / FM213-3-1. ISSN  0016-2736. Г-Н  2822417.
5. Симпсон, Стивен Г. (1985). "Теория BQO и гипотеза Фраиссе". В Мэнсфилде, Ричард; Вайткамп, Гален (ред.). Рекурсивные аспекты дескриптивной теории множеств. Clarendon Press, Oxford University Press. стр.124–38. ISBN  978-0-19-503602-2. Г-Н  0786122.
6. Лейвер, Ричард (1978). «Лучше-квазипорядки и класс деревьев». В Роте, Джан-Карло (ред.). Исследования по основам и комбинаторике. Академическая пресса. С. 31–48. ISBN  978-0-12-599101-8. Г-Н  0520553.