Теорема Краскала о дереве

В математике утверждает , теорема Краскала о дереве что множество конечных деревьев над хорошо квазиупорядоченным набором меток само по себе является хорошо квазиупорядоченным при гомеоморфном вложении.

История

Теорема была доказана выдвинута Эндрю Вассони и ; Джозефом Крускалом ( 1960 ) короткое доказательство было дано Криспином Нэш-Уильямсом ( 1963 ). С тех пор оно стало ярким примером в обратной математике как утверждение, которое невозможно доказать в ATR ₀ ( арифметическая теория второго порядка с формой арифметической трансфинитной рекурсии ).

В 2004 году результат был обобщен с деревьев на графы как теорема Робертсона-Сеймура , результат, который также оказался важным в обратной математике и приводит к еще более быстро растущей функции SSCG , которая затмевает ${\text{TREE}}(3)$ . Финитное функции применение теоремы приводит к существованию быстрорастущей TREE .

Заявление

Представленная здесь версия доказана Нэш-Вильямсом; Формулировка Краскала несколько более сильная. Все деревья, которые мы рассматриваем, конечны.

Учитывая дерево $T$ с корнем и вершины $v$ , $w$ , назовите $преемником$ v , w $если$ уникальный путь от корня до $w$ содержит $v$ , и назовите $w$ непосредственным преемником v $,$ если дополнительно путь от $v$ до $w$ содержит никакой другой вершины.

Возьмем $X$ множеством частично упорядоченным . Если $T1 T1$ , $T2 —$ корневые деревья с вершинами, помеченными в $,$ мы говорим, что $инф X$ - вложимо в $T2,$ и пишем $T_{1}\leq T_{2}$ если существует инъективное отображение $F$ вершин $T 1$ в вершины $T 2$ такое, что:

Для всех вершин $v$ из $T 1$ метка $v$ предшествует метке вершины. $F(v)$ ;
Если $w$ — любой преемник $v$ в $T 1$ , то $F(w)$ является преемником $F(v)$ ; и
Если $w1,$ v $w2 —$ любые два различных непосредственных наследника $,$ то путь от $F(w_{1})$ к $F(w_{2})$ в $Т 2$ содержится $F(v)$ .

Теорема Краскала о дереве гласит:

Если $X$ , хорошо квазиупорядочено то множество корневых деревьев с метками в $X$ хорошо квазиупорядочено в соответствии с inf-вложимым порядком, определенным выше. (То есть, для любой бесконечной последовательности $T 1, T 2, \dots$ корневых деревьев, помеченных в $X$ , существует некоторая $i<j$ так что $T_{i}\leq T_{j}$ .)

работа Фридмана

Для счетного множества меток $X$ теорема Крускала о дереве может быть выражена и доказана с использованием арифметики второго порядка . Однако, как и теорема Гудштейна или теорема Пэрис-Харрингтона , некоторые частные случаи и варианты теоремы могут быть выражены в подсистемах арифметики второго порядка, гораздо более слабых, чем подсистемы, где они могут быть доказаны. Впервые это заметил Харви Фридман в начале 1980-х годов, что стало первым успехом зарождавшейся тогда области обратной математики. В случае, когда деревья выше считаются непомеченными (то есть в случае, когда $X$ имеет размер один), Фридман обнаружил, что результат недоказуем в ATR ₀ , ^[1] таким образом давая первый пример предикативного результата с доказуемо непредикативным доказательством. ^[2] Этот случай теоремы все еще доказывается П. ¹
₁ -CA ₀ , но добавив «условие разрыва» ^[3] к определению порядка на деревьях, приведенному выше, он нашел естественный вариант теоремы, недоказуемый в этой системе. ^[4]^[5] Намного позже теорема Робертсона-Сеймура дала еще одну теорему, недоказуемую П. ¹
₁ -СА ₀ .

Порядковый анализ подтверждает силу теоремы Крускала, при этом теоретико-доказательный ординал теоремы равен малому ординалу Веблена (иногда его путают с меньшим ординалом Аккермана ). ^[6]

Слабая древовидная функция

Предположим, что $P(n)$ это утверждение:

Существует некоторое

m

такое, что если

T 1, ..., T m

— конечная последовательность немеченых корневых деревьев, где

T i

имеет

i+n

вершины, то

T_{i}\leq T_{j}

для некоторых

i<j

.

Все заявления $P(n)$ верны как следствие теоремы Краскала и леммы Кенига . Для каждого $n$ что арифметика Пеано может доказать, $P(n)$ верно, но арифметика Пеано не может доказать утверждение» $P(n)$ верно для всех $n$ ". ^[7] При этом длина доказательства кратчайшего $P(n)$ в арифметике Пеано растет феноменально быстро как функция $n$ , намного быстрее, чем любая примитивно-рекурсивная функция или функция Аккермана . , например, ^{[ нужна ссылка ]} Наименьшее $m,$ для которого $P(n)$ Так же очень быстро растет с $n$ .

Определять ${\text{tree}}(n)$ , слабая древесная функция, как наибольшее $m$ , так что мы имеем следующее:

Существует последовательность

T 1, ..., T m

немаркированных корневых деревьев, где каждое $имеет Ti$ не более

i+n

вершины, такие что

T_{i}\leq T_{j}

не выполняется ни для какого

i<j\leq m

.

Известно, что ${\text{tree}}(1)=2$ , ${\text{tree}}(2)=5$ , ${\text{tree}}(3)\geq 844,424,930,131,960$ (около 844 трлн), ${\text{tree}}(4)\gg g_{64}$ (где $g_{64}$ — число Грэма ), и ${\text{TREE}}(3)$ (где аргумент указывает количество меток ; см. ниже ) больше, чем $\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{8}(7)}(7)}(7)}(7)}(7).$

Чтобы различать эти две функции, «TREE» (со всеми заглавными буквами) — это большая функция TREE, а «tree» (со всеми буквами в нижнем регистре) — это слабая функция дерева.

ДЕРЕВО функция

Включив ярлыки, Фридман определил гораздо более быстрорастущую функцию. ^[8] В качестве натурального числа $n$ возьмем ${\text{TREE}}(n)$ ^[а] быть наибольшим $m,$ чтобы мы имели следующее:

Существует последовательность

T 1, ..., T m

корневых деревьев, помеченных набором из

n

меток, где каждое $T i$ имеет не более

i

вершин, такая что

T_{i}\leq T_{j}

не выполняется ни для какого

i<j\leq m

.

Последовательность ДЕРЕВА начинается ${\text{TREE}}(1)=1$ , ${\text{TREE}}(2)=3$ , а потом вдруг, ${\text{TREE}}(3)$ взрывается до значения, которое настолько велико, что многие другие «большие» комбинаторные константы, такие как константа Фридмана $n(4)$ , $n^{n(5)}(5)$ , и число Грэма , ^[б] по сравнению с ними чрезвычайно малы. граница Нижняя для $n(4)$ и, следовательно, крайне слабая нижняя оценка для ${\text{TREE}}(3)$ , является $A^{A(187196)}(1)$ . ^[с]^[9] Например, число Грэма намного меньше нижней границы. $A^{A(187196)}(1)$ , что примерно $g_{3\uparrow ^{187196}3}$ , где $g_{x}$ есть функция Грэма .

См. также

Примечания

^{^ а} Первоначально Фридман обозначил эту функцию TR [ n ].

^{^ б} n ( k ) определяется как длина самой длинной возможной последовательности, которую можно построить с помощью k -буквенного алфавита, так что ни один блок букв x _i ,...,x _{2 i} не является подпоследовательностью любого последующего блока x _j , ...,x _{2 j} . ^[10]

n(1)=3,n(2)=11,\,{\textrm {and}}\,n(3)>2\uparrow ^{7197}158386

.

^{^ с} A ( x ), принимающая один аргумент, определяется как A ( x , x ), где A ( k , n ), принимающая два аргумента, представляет собой конкретную версию функции Аккермана , определенную как: A (1, n ) = 2 n , А ( к +1, 1) = А ( к , 1), А ( к +1, п +1) = А ( к , А ( к +1, п )).

Ссылки

Цитаты

^ Симпсон 1985, Теорема 1.8.
^ Фридман 2002, с. 60
^ Симпсон 1985, Определение 4.1.
^ Симпсон 1985, Теорема 5.14.
^ Марконе 2001, с. 8–9
^ Ратьен и Вейерманн 1993 .
^ Смит 1985, с. 120
^ Фридман, Харви (28 марта 2006 г.), «273: Sigma01/optimal/size» , Университета штата Огайо математический факультет , получено 8 августа 2017 г.
^ Фридман, Харви М. (1 июня 2000 г.), «Огромные целые числа в реальной жизни» (PDF) , Университет штата Огайо , получено 8 августа 2017 г.
^ Фридман, Харви М. (8 октября 1998 г.), «Длинные конечные последовательности» (PDF) , математический факультет Университета штата Огайо , стр. 5, 48 (Thm.6.8) , получено 8 августа 2017 г.

Библиография

Фридман, Харви М. (2002), Внутренние вложения конечных деревьев. Размышления об основах математики (Стэнфорд, Калифорния, 1998) , Lect. Журнал примечаний, вып. 15, Урбана, Иллинойс: доц. Символ. Логика, стр. 60–91, МР 1943303.
Галье, Жан Х. (1991), «Что такого особенного в теореме Краскала и ординале Γ ₀ ? Обзор некоторых результатов теории доказательств» (PDF) , Ann. Чистое приложение. Логика , 53 (3): 199–260, doi : 10.1016/0168-0072(91)90022-E , MR 1129778
Крускал, Дж. Б. (май 1960 г.), «Хороший квазиупорядочение, теорема о дереве и гипотеза Вассони» (PDF) , Transactions of the American Mathematical Society , 95 (2), American Mathematical Society: 210–225, doi : 10.2307 /1993287 , JSTOR 1993287 , MR 0111704
Марконе, Альберто (2001), «Теория Wqo и bqo в подсистемах арифметики второго порядка» (PDF) , Reverse Mathematics , 21 : 303–330
Нэш-Вильямс, К. Ст.Дж.А. (1963), «О хорошо квазиупорядоченных конечных деревьях», Proc. Кэмб. Фил. Соц. , 59 (4): 833–835, Bibcode : 1963PCPS...59..833N , doi : 10.1017/S0305004100003844 , MR 0153601 , S2CID 251095188
Ратьен, Майкл; Вейерманн, Андреас (1993), «Теоретико-доказательные исследования теоремы Краскала» (PDF) , Annals of Pure and Applied Logic , 60 (1): 49–88, doi : 10.1016/0168-0072(93)90192-G , МР 1212407
Симпсон, Стивен Г. (1985), «Недоказуемость некоторых комбинаторных свойств конечных деревьев», в Харрингтоне, Луизиана; Морли, М.; Щедров А.; и др. (ред.), Исследования Харви Фридмана по основам математики , Исследования по логике и основам математики, Северная Голландия, стр. 87–117.
Смит, Рик Л. (1985), «Сила непротиворечивости некоторых конечных форм теорем Хигмана и Краскала», в Харрингтоне, Луизиана; Морли, М.; Щедров А.; и др. (ред.), Исследования Харви Фридмана по основам математики , Исследования по логике и основам математики, Северная Голландия, стр. 119–136.

[1] Симпсон 1985, Теорема 1.8.

[2] Фридман 2002, с. 60

[3] Симпсон 1985, Определение 4.1.

[4] Симпсон 1985, Теорема 5.14.

[5] Марконе 2001, с. 8–9

[FOOTNOTERathjenWeiermann1993-6] Ратьен и Вейерманн 1993 .

[SmiA-7] Смит 1985, с. 120

[8] Фридман, Харви (28 марта 2006 г.), «273: Sigma01/optimal/size» , Университета штата Огайо математический факультет , получено 8 августа 2017 г.

[9] Фридман, Харви М. (1 июня 2000 г.), «Огромные целые числа в реальной жизни» (PDF) , Университет штата Огайо , получено 8 августа 2017 г.

[10] Фридман, Харви М. (8 октября 1998 г.), «Длинные конечные последовательности» (PDF) , математический факультет Университета штата Огайо , стр. 5, 48 (Thm.6.8) , получено 8 августа 2017 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

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