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

В теории порядка лучший квазиупорядочение или bqo — это квазиупорядочение , которое не допускает определенного типа плохого массива. Любой лучший квазиупорядочение является хорошим квазиупорядочением .

Мотивация

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

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

[Rado54-1] Радо, Ричард (1954). «Частичное упорядочение наборов векторов». Математика . 1 (2): 89–95. дои : 10.1112/S0025579300000565 . МР 0066441 .

[Nash-Williams65-2] Нэш-Уильямс, К. Ст. Дж. А. (1965). «О хорошо-квазиупорядоченных бесконечных деревьях». Математические труды Кембриджского философского общества . 61 (3): 697–720. Бибкод : 1965PCPS...61..697N . дои : 10.1017/S0305004100039062 . ISSN 0305-0041 . МР 0175814 . S2CID 227358387 .

[Laver71-3] Лейвер, Ричард (1971). «О гипотезе типа порядка Фрэссе». Анналы математики . 93 (1): 89–111. дои : 10.2307/1970754 . JSTOR 1970754 .

[Martinez-Ranero2011-4] Мартинес-Ранеро, Карлос (2011). «Ну-подобно упорядочиванию линий Ароншайна» . Основы математики . 213 (3): 197–211. дои : 10.4064/fm213-3-1 . ISSN 0016-2736 . МР 2822417 .

[Simpson85-5] Jump up to: ^а ^б Симпсон, Стивен Г. (1985). «Теория BQO и гипотеза Фрэссе» . В Мэнсфилде, Ричард; Вейткамп, Гален (ред.). Рекурсивные аспекты дескриптивной теории множеств . Кларендон Пресс, Издательство Оксфордского университета. стр. 124–38 . ISBN 978-0-19-503602-2 . МР 0786122 .

[Laver78-6] Лейвер, Ричард (1978). «Лучшие-квазиупорядочения и класс деревьев». В Роте, Джан-Карло (ред.). Исследования по основам и комбинаторике . Академическая пресса. стр. 31–48. ISBN 978-0-12-599101-8 . МР 0520553 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

v т и Теория порядка
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice