Twierdzenie Kruskala o drzewie - Kruskal's tree theorem

W matematyce , drzewo Kruskala Twierdzenie mówi, że zbiór skończonych drzew nad dobrze quasi-zamówił zestaw etykiet jest sam dobrze quasi-zamawiane zgodnie homeomorficzny osadzania. Twierdzenie to zostało wymyślone przez Andrew Vázsonyi i udowodnione przez Josepha Kruskala  ( 1960 ); krótki dowód podał Crispin Nash-Williams  ( 1963 ). Od tego czasu stało się wybitnym przykładem w matematyce odwrotnej jako zdanie, którego nie można udowodnić w ATR 0 (forma arytmetycznej rekurencji transskończonej ), a skończone zastosowanie tego twierdzenia daje istnienie szybko rosnącej funkcji DRZEWA .

W 2004 r. wynik uogólniono z drzew na grafy jako twierdzenie Robertsona-Seymoura , wynik, który okazał się również ważny w matematyce odwrotnej i prowadzi do jeszcze szybszego wzrostu funkcji SSCG .

Oświadczenie

Podajemy wersję sprawdzoną przez Nasha-Williamsa; Sformułowanie Kruskala jest nieco silniejsze. Wszystkie drzewa, które uważamy za skończone.

Mając drzewo T z korzeniem i wierzchołki v , w , nazwijmy w następnikiem v , jeśli unikalna ścieżka od korzenia do w zawiera v , i nazwijmy w bezpośrednim następcą v , jeśli dodatkowo ścieżka od v do w zawiera żaden inny wierzchołek.

Weź X jako częściowo uporządkowany zestaw . Jeśli T 1 , T 2 są zakorzenionymi drzewami z wierzchołkami oznaczonymi w X , mówimy, że T 1 jest nieosadzane w T 2 i zapisujemy T 1 ≤ T 2 , jeśli istnieje iniektywna mapa F od wierzchołków T 1 do wierzchołków z T 2 takie, że

  • Dla wszystkich wierzchołków v z T 1 , etykieta v poprzedza etykietę F ( v ) ,
  • Jeśli w jest dowolnym następcą v w T 1 , to F ( w ) jest następcą F ( v ) i
  • Jeśli w 1 , w 2 są dowolnymi dwoma odrębnymi bezpośrednimi następcami v , to ścieżka od F ( w 1 ) do F ( w 2 ) w T 2 zawiera F ( v ) .

Twierdzenie Kruskala o drzewie stwierdza zatem:

Jeśli X jest dobrze uporządkowane , to zbiór drzew ukorzenionych z etykietami w X jest dobrze uporządkowany w porządku nieosadzonym zdefiniowanym powyżej. (To znaczy, biorąc pod uwagę dowolny nieskończony ciąg T 1 , T 2 , … ukorzenionych drzew oznaczonych w X , istnieje pewna ilość i < j , tak że T i ≤ T j .)

Słaba funkcja drzewa

Zdefiniuj tree( n ) , słabą funkcję drzewa, jako długość najdłuższego ciągu drzew oznaczonych 1 (tzn. X = {1} ) tak, że:

  • Drzewo w pozycji k w sekwencji ma nie więcej niż k + n wierzchołków, dla wszystkich k .
  • Żadne drzewo nie jest homeomorficznie osadzone w żadnym drzewie następującym po nim w sekwencji.

Wiadomo, że tree(1) = 2, tree(2) = 5 i tree(3) ≥ 844424930131960, ale TREE(3) (gdzie argument określa liczbę etykiet ; patrz niżej ) jest większe niż

Praca Friedmana

W przypadku przeliczalnego zbioru etykiet twierdzenie Kruskala o drzewie można wyrazić i udowodnić za pomocą arytmetyki drugiego rzędu . Jednak, podobnie jak twierdzenie Goodsteina lub twierdzenie Parisa-Harringtona , pewne szczególne przypadki i warianty twierdzenia mogą być wyrażone w podsystemach arytmetyki drugiego rzędu znacznie słabszych niż podsystemy, w których można je udowodnić. Po raz pierwszy zauważył to Harvey Friedman we wczesnych latach osiemdziesiątych, wczesny sukces rodzącej się wówczas dziedziny matematyki odwrotnej. W przypadku, gdy powyższe drzewa są uważane za nieoznakowane (to znaczy w przypadku, gdy ma jeden rząd), Friedman stwierdził, że wynik był niedowodliwy w ATR 0 , podając w ten sposób pierwszy przykład wyniku predykatywnego z dowodem nie do udowodnienia . Ten przypadek twierdzenia jest nadal możliwy do udowodnienia w Π1
1-CA 0 , ale dodając "warunek przerwy" do definicji porządku na drzewach powyżej, znalazł naturalną odmianę twierdzenia nie do udowodnienia w tym systemie. Znacznie później twierdzenie Robertsona-Seymoura dałoby inne twierdzenie nie do udowodnienia w środku Π1
1-CA 0 .

Analiza porządkowa potwierdza siłę twierdzenia Kruskala, przy czym teoretyczna liczba porządkowa twierdzenia równa się małej liczbie porządkowej Veblena (czasami mylonej z mniejszą liczbą porządkową Ackermanna ).

DRZEWO(3)

Załóżmy, że P ( n ) jest stwierdzeniem:

Istnieje kilka m takich, że jeśli T 1 ,..., T m jest skończonym ciągiem nieoznaczonych drzew zakorzenionych, w których T k ma n + k wierzchołków, to T i  ≤  T j dla niektórych i < j .

Wszystkie zdania P ( n ) są prawdziwe jako konsekwencja twierdzenia Kruskala i lematu Kőniga . Dla każdego n , arytmetyka Peano może udowodnić, że P ( n ) jest prawdziwe, ale arytmetyka Peano nie może udowodnić, że zdanie „ P ( n ) jest prawdziwe dla wszystkich n ”. Co więcej, długość najkrótszego dowodu P ( n ) w arytmetyce Peano rośnie fenomenalnie szybko jako funkcja n , znacznie szybciej niż jakakolwiek prymitywna funkcja rekurencyjna czy na przykład funkcja Ackermanna . Najmniejsze m, dla którego P ( n ) utrzymuje podobnie, rośnie niezwykle szybko z n .

Włączając etykiety, Friedman zdefiniował znacznie szybciej rozwijającą się funkcję. Dla dodatniej liczby całkowitej n , przyjmij TREE ( n ) jako największe m , abyśmy otrzymali:

Istnieje ciąg T 1 ,..., T m ukorzenionych drzew oznaczonych ze zbioru n etykiet, gdzie każde T i ma co najwyżej i wierzchołki, takie, że T i  ≤  T j nie zachodzi dla żadnego i < j  ≤  m .

TREE sekwencja zaczyna TREE (1) = 1, TREE (2) = 3, a następnie nagle TREE (3) eksploduje do wartości tak niezwykle duży, że wiele innych "dużych" kombinatoryczne stałe, takie jak Friedmana n (4), są niezwykle mały w porównaniu. W rzeczywistości jest znacznie większy niż n n (5) (5). Dolnym ograniczeniem dla n (4), a więc skrajnie słabym dolnym ograniczeniem dla DRZEWA (3), jest A A (187196) (1), gdzie A () jest wersją funkcji Ackermanna : . Na przykład liczba Grahama wynosi w przybliżeniu A 64 (4), czyli znacznie mniej niż dolna granica A A (187196) (1). Można wykazać, że tempo wzrostu funkcji DRZEWO znajduje się przynajmniej w szybko rosnącej hierarchii . A A (187196) (1) jest w przybliżeniu , gdzie g x jest funkcją Grahama .

Zobacz też

Uwagi

^ * Friedman pierwotnie określał tę funkcję przezTR[n].
^ ** n(k) jest zdefiniowana jako długość najdłuższego możliwego ciągu, który można skonstruować za pomocąalfabetuk-literowego, tak że żaden blok liter xi,...,x2i niejest podciągiem żadnego późniejszego bloku xj,...,x2j. .

Bibliografia

Cytaty
Bibliografia