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

В теории порядка улучшенный квазиупорядочение или 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}$

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

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

Пусть будет квазипорядком и снабдим дискретной топологией . -массив является борелевской функцией для некоторого бесконечного подмножества . -массив плох , если для каждого ; хорош в противном случае. Квазипорядок является лучшим квазипорядком, если в этом смысле нет плохих -массивов. ${\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). «Частичное хорошее упорядочение множеств векторов». Mathematika . 1 (2): 89–95. doi :10.1112/S0025579300000565. MR  0066441.
2. Nash-Williams, C. St. JA (1965). «О хорошо квазиупорядоченных бесконечных деревьях». Математические труды Кембриджского философского общества . 61 (3): 697–720. Bibcode :1965PCPS...61..697N. doi :10.1017/S0305004100039062. ISSN  0305-0041. MR  0175814. S2CID  227358387.
3. Лейвер, Ричард (1971). «О гипотезе Фресса о типе порядка». Анналы математики . 93 (1): 89–111. doi :10.2307/1970754. JSTOR  1970754.
4. Мартинес-Ранеро, Карлос (2011). «Хорошо-квазиупорядоченные линии Ароншайна». Фундамента Математика . 213 (3): 197–211. дои : 10.4064/fm213-3-1 . ISSN  0016-2736. МР  2822417.
5. Simpson, Stephen G. (1985). "Теория BQO и гипотеза Фресса". В Mansfield, Richard; Weitkamp, ​​Galen (ред.). Рекурсивные аспекты дескриптивной теории множеств . The Clarendon Press, Oxford University Press. стр. 124–38. ISBN 978-0-19-503602-2. МР  0786122.
6. Laver, Richard (1978). «Лучшие квазиупорядочения и класс деревьев». В Rota, Gian-Carlo (ред.). Исследования по основам и комбинаторике . Academic Press. стр. 31–48. ISBN 978-0-12-599101-8. МР  0520553.