Теорема Краскала о дереве
Эта статья может быть слишком технической для понимания большинства читателей . ( июнь 2024 г. ) |
В математике утверждает , теорема Краскала о дереве что множество конечных деревьев над хорошо квазиупорядоченным набором меток само по себе является хорошо квазиупорядоченным при гомеоморфном вложении.
История [ править ]
Теорема была доказана выдвинута Эндрю Вассони и ; Джозефом Крускалом ( 1960 ) короткое доказательство было дано Криспином Нэш-Уильямсом ( 1963 ). С тех пор оно стало ярким примером в обратной математике как утверждение, которое невозможно доказать в ATR 0 ( арифметическая теория второго порядка с формой арифметической трансфинитной рекурсии ).
В 2004 году результат был обобщен с деревьев на графы как теорема Робертсона-Сеймура , результат, который также оказался важным в обратной математике и приводит к еще более быстро растущей функции SSCG , которая затмевает . Финитарное функции применение теоремы приводит к существованию быстрорастущей TREE .
Заявление [ править ]
Представленная здесь версия доказана Нэш-Вильямсом; Формулировка Краскала несколько более сильная. Все деревья, которые мы рассматриваем, конечны.
Учитывая дерево T с корнем и вершины v , w , назовите преемником v , w если уникальный путь от корня до w содержит v , и назовите w непосредственным преемником v, если дополнительно путь от v до w содержит никакой другой вершины.
Возьмем X множеством частично упорядоченным . Если T1 T1 , T2 — корневые деревья с вершинами, помеченными в , мы говорим, что инф X - вложимо в T2 , и пишем если существует инъективное отображение F вершин T 1 в вершины T 2 такое, что:
- Для всех вершин v из T 1 метка v предшествует метке вершины. ;
- Если w — любой преемник v в T 1 , то является преемником ; и
- Если w1 , v w2 — любые два различных непосредственных наследника , то путь от к в Т 2 содержится .
Теорема Краскала о дереве гласит:
Если X , хорошо квазиупорядочено то множество корневых деревьев с метками в X хорошо квазиупорядочено в соответствии с inf-вложимым порядком, определенным выше. (То есть, для любой бесконечной последовательности T 1 , T 2 , … корневых деревьев, помеченных в X , существует некоторая так что .)
Работа Фридмана [ править ]
Для счетного множества меток X теорема Крускала о дереве может быть выражена и доказана с использованием арифметики второго порядка . Однако, как и теорема Гудштейна или теорема Пэрис-Харрингтона , некоторые частные случаи и варианты теоремы могут быть выражены в подсистемах арифметики второго порядка, гораздо более слабых, чем подсистемы, где они могут быть доказаны. Впервые это заметил Харви Фридман в начале 1980-х годов, что стало первым успехом зарождавшейся тогда области обратной математики. В случае, когда деревья выше считаются непомеченными (то есть в случае, когда X имеет размер один), Фридман обнаружил, что результат недоказуем в ATR 0 , [1] таким образом давая первый пример предикативного результата с доказуемо непредикативным доказательством. [2] Этот случай теоремы все еще доказывается П. 1
1 -CA 0 , но добавив «условие разрыва» [3] к определению порядка на деревьях, приведенному выше, он нашел естественный вариант теоремы, недоказуемой в этой системе. [4] [5] Намного позже теорема Робертсона-Сеймура дала еще одну теорему, недоказуемую П. 1
1 -СА 0 .
Порядковый анализ подтверждает силу теоремы Крускала, при этом теоретико-доказательный ординал теоремы равен малому ординалу Веблена (иногда его путают с меньшим ординалом Аккермана ). [6]
Слабая древовидная функция [ править ]
Предположим, что это заявление:
- Существует некоторое m такое, что если T 1 , ..., T m — конечная последовательность немеченых корневых деревьев, где T i имеет вершины, то для некоторых .
Все заявления верны как следствие теоремы Краскала и леммы Кенига . Для каждого n что арифметика Пеано может доказать, верно, но арифметика Пеано не может доказать утверждение» верно для всех n ". [7] При этом длина доказательства кратчайшего в арифметике Пеано растет феноменально быстро как функция n , намного быстрее, чем любая примитивно-рекурсивная функция или функция Аккермана . , например, [ нужна ссылка ] Наименьшее m, для которого Так же очень быстро растет с n .
Определять , слабая древесная функция, как наибольшее m , так что мы имеем следующее:
- Существует последовательность T 1 , ..., T m немаркированных корневых деревьев, где каждое имеет Ti не более вершины, такие что не выполняется ни для какого .
Известно, что , , (около 844 трлн), (где — число Грэма ), и (где аргумент указывает количество меток ; см. ниже ) больше, чем
Чтобы различать эти две функции, «TREE» (со всеми заглавными буквами) — это большая функция TREE, а «tree» (со всеми буквами в нижнем регистре) — это слабая функция дерева.
ДЕРЕВО функция [ править ]
Включив ярлыки, Фридман определил гораздо более быстрорастущую функцию. [8] В качестве натурального числа n возьмем [а] быть наибольшим m, чтобы мы имели следующее:
- Существует последовательность T 1 , ..., T m корневых деревьев, помеченных набором из n меток, где каждое T i имеет не более i вершин, такая, что не выполняется ни для какого .
Последовательность ДЕРЕВА начинается , , а потом вдруг, взрывается до значения, которое настолько велико, что многие другие «большие» комбинаторные константы, такие как константа Фридмана , , и число Грэма , [б] по сравнению с ними чрезвычайно малы. граница Нижняя для и, следовательно, крайне слабая нижняя оценка для , является . [с] [9] Например, число Грэма намного меньше нижней границы. , что примерно , где есть функция Грэма .
См. также [ править ]
Примечания [ править ]
- ^ а Первоначально Фридман обозначил эту функцию TR [ n ].
- ^ б n ( k ) определяется как длина самой длинной возможной последовательности, которую можно составить с помощью k -буквенного алфавита, так что ни один блок букв x i ,...,x 2 i не является подпоследовательностью любого последующего блока x j , ...,x 2 j . [10] .
- ^ с 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), «Что такого особенного в теореме Краскала и ординале Γ 0 ? Обзор некоторых результатов теории доказательств» (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.