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

Хорошо-квази-упорядочение конечных деревьев

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

История

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

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

Заявление

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

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

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

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

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

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

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

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

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

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

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

Существует некоторое m такое, что если T ₁ , ..., T _m — конечная последовательность непомеченных корневых деревьев, где T _i имеет вершины, то для некоторого . ${\displaystyle i+n}$ ${\displaystyle T_{i}\leq T_{j}}$ ${\displaystyle i<j}$

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

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

Существует последовательность T ₁ , ..., T _m непомеченных корневых деревьев, где каждое T _i имеет не более вершин, такая, что не выполняется ни для одного . ${\displaystyle i+n}$ ${\displaystyle T_{i}\leq T_{j}}$ ${\displaystyle i<j\leq m}$

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

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

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

Последовательность корневых деревьев, помеченных из набора из 3 меток (синий < красный < зеленый). Дерево n в последовательности содержит не более n вершин, и ни одно дерево не является inf-вкладываемым в любое последующее дерево в последовательности. TREE(3) определяется как максимально возможная длина такой последовательности.

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

Существует последовательность T ₁ , ..., T _m корневых деревьев, помеченных из набора из n меток, где каждое T _i имеет не более i вершин, такая, что не выполняется ни для одного . ${\displaystyle T_{i}\leq T_{j}}$ ${\displaystyle i<j\leq m}$

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

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

• Теорема Париса–Харрингтона
• Теорема Канамори–Макалуна
• Теорема Робертсона–Сеймура

Примечания

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

^ b n ( k ) определяется как длина максимально возможной последовательности, которую можно построить с помощью алфавита из k букв таким образом, что никакой блок букв x _i ,...,x _{2 i} не является подпоследовательностью любого более позднего блока x _j ,...,x _{2 j} . ^[10] . ${\displaystyle n(1)=3,n(2)=11,\,{\textrm {and}}\,n(3)>2\uparrow ^{7197}158386}$

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

Ссылки

Цитаты

1. Симпсон 1985, Теорема 1.8
2. Фридман 2002, стр. 60
3. Симпсон 1985, Определение 4.1
4. Симпсон 1985, Теорема 5.14
5. Марконе 2001, стр. 8–9 harvnb error: no target: CITEREFMarcone2001 (help)
6. Ратьен и Вайерманн 1993.
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 г. .

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

• Фридман, Харви М. (2002). «Внутренние конечные древесные вложения». В Sieg, Wilfried; Feferman, Solomon (ред.). Размышления об основах математики: эссе в честь Соломона Фефермана . Конспект лекций по логике. Том 15. Natick, Mass: AK Peters . стр. 60–91. ISBN 978-1-56881-170-3. МР  1943303.
• H. Gallier, Jean (сентябрь 1991 г.). «Что такого особенного в теореме Крускала и ординале Γ0? Обзор некоторых результатов в теории доказательств» (PDF) . Annals of Pure and Applied Logic . 53 (3): 199–260. doi : 10.1016/0168-0072(91)90022-E . MR  1129778.
• Kruskal, JB (май 1960). "Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture" (PDF) . Transactions of the American Mathematical Society . 95 (2). American Mathematical Society : 210–225. doi :10.2307/1993287. JSTOR  1993287. MR  0111704.
• Marcone, Alberto (2005). Simpson, Stephen G. (ред.). "WQO и BQO-теория в подсистемах арифметики второго порядка" (PDF) . Обратная математика . Конспект лекций по логике. 21 . Cambridge: Cambridge University Press : 303–330. doi :10.1017/9781316755846.020. ISBN 978-1-316-75584-6.
• Nash-Williams, C. St. JA (октябрь 1963 г.). "On well-quasi-ordering final trees" (PDF) . Mathematical Proceedings of the Cambridge Philosophical Society . 59 (4): 833–835. Bibcode :1963PCPS...59..833N. doi :10.1017/S0305004100003844. ISSN  0305-0041. MR  0153601. S2CID  251095188.
• Ратьен, Михаэль; Вайерманн, Андреас (февраль 1993 г.). "Исследования теории доказательств по теореме Крускала" (PDF) . Annals of Pure and Applied Logic . 60 (1): 49–88. doi :10.1016/0168-0072(93)90192-G. MR  1212407.
• Симпсон, Стивен Г. (1985). «Недоказуемость некоторых комбинаторных свойств конечных деревьев». В Фридман, Харви; Харрингтон, Л.А.; Скедров, А.; и др. (ред.). Исследования Харви Фридмана по основаниям математики . Исследования по логике и основаниям математики. Амстердам; Нью-Йорк: Северная Голландия . С. 87–117. ISBN 978-0-444-87834-2.
• Смит, Рик Л. (1985). "Силы непротиворечивости некоторых конечных форм теорем Хигмана и Краскала". В Фридман, Харви ; Харрингтон, LA (ред.). Исследования Харви Фридмана по основаниям математики . Исследования по логике и основаниям математики. Том 117. Амстердам ; Нью-Йорк: Северная Голландия . стр. 119–136. doi :10.1016/s0049-237x(09)70157-0. ISBN 978-0-444-87834-2.