Оглавление
Теорема о дереве Крускала
-
Теорема Крускала о дереве
- Множество конечных деревьев над хорошо квазиупорядоченным набором меток само по себе хорошо квазиупорядочено при гомеоморфном вложении.
- Теорема была доказана Джозефом Крускалом в 1960 году и кратко доказана Криспином Нэшем-Уильямсом в 1963 году.
- Теорема стала ярким примером в обратной математике, так как не может быть доказана в ATR0.
-
Обобщение на графики
- В 2004 году теорема была обобщена на графики в виде теоремы Робертсона–Сеймура.
- Теорема Робертсона–Сеймура также важна в обратной математике и привела к быстрому росту функции SSCG.
-
Применение теоремы
- Теорема приводит к существованию быстрорастущей ДРЕВОВИДНОЙ функции.
- ДРЕВОВИДНАЯ функция определяется как наибольшая m, для которой утверждение “P(n) истинно для всех n” не может быть доказано в арифметике Пеано.
-
Работа Фридмана
- Харви Фридман обнаружил, что теорема недоказуема в ATR0 для немаркированных деревьев.
- Фридман также обнаружил, что теорема недоказуема в Π11-CA0 с “условием разрыва”.
-
Порядковый анализ
- Теоретико-доказательный порядковый номер теоремы равен малому порядковому номеру Веблена.
-
Слабая древовидная функция
- Слабая древовидная функция определяется как наибольшая m, для которой утверждение “P(n) истинно для всех n” не может быть доказано в арифметике Пеано.
- Слабая древовидная функция растет феноменально быстро с увеличением n.
-
ДРЕВОВИДНАЯ функция
- ДРЕВОВИДНАЯ функция включает метки и определяется как наибольшая m, для которой утверждение “P(n) истинно для всех n” не может быть доказано в арифметике Пеано.
- ДРЕВОВИДНАЯ функция также быстро растет с увеличением n.