Teorema da árvore de Kruskal - Kruskal's tree theorem

Em matemática , a árvore de Kruskal teorema afirma que o conjunto de finitos árvores ao longo de um bem ordenada-quasi conjunto de etiquetas é o próprio bem-quasi-ordenada sob homeomorphic incorporação. O teorema foi conjecturado por Andrew Vázsonyi e provado por Joseph Kruskal  ( 1960 ); uma curta prova foi dada por Crispin Nash-Williams  ( 1963 ). Desde então, tornou-se um exemplo proeminente na matemática reversa como uma afirmação que não pode ser provada dentro do ATR ₀ (uma forma de recursão aritmética transfinita ), e uma aplicação finitária do teorema dá a existência da função TREE de crescimento rápido .

Em 2004, o resultado foi generalizado de árvores para gráficos como o teorema de Robertson-Seymour , um resultado que também se provou importante na matemática reversa e leva à função SSCG de crescimento ainda mais rápido .

Demonstração

Damos a versão provada por Nash-Williams; A formulação de Kruskal é um pouco mais forte. Todas as árvores que consideramos são finitas.

Dada uma árvore T com uma raiz, e dados os vértices v , w , chame w um sucessor de v se o caminho único da raiz para w contiver v , e chame w um sucessor imediato de v se adicionalmente o caminho de v para w contiver nenhum outro vértice.

Considere X como um conjunto parcialmente ordenado . Se T ₁ , T ₂ são árvores enraizadas com vértices rotulados em X , dizemos que T ₁ é inf-embutido em T ₂ e escrevemos T ₁ ≤ T ₂ se houver um mapa injetivo F dos vértices de T ₁ aos vértices de T ₂ de tal modo que

• Para todos os vértices v de T ₁ , o rótulo de v precede o rótulo de F ( v ) ,
• Se w for qualquer sucessor de v em T ₁ , então F ( w ) é um sucessor de F ( v ) , e
• Se w ₁ , w ₂ são quaisquer dois sucessores imediatos distintos de v , então o caminho de F ( w ₁ ) a F ( w ₂ ) em T ₂ contém F ( v ) .

O teorema da árvore de Kruskal então afirma:

Se X for bem quase ordenado , então o conjunto de árvores enraizadas com rótulos em X é bem quase ordenado sob a ordem inf-embeddable definida acima. (Ou seja, dada qualquer sequência infinita T ₁ , T ₂ , ... de árvores enraizadas rotuladas em X , há algum i < j de modo que T _i ≤ T _j .)

Função de árvore fraca

Defina árvore ( n ) , a função de árvore fraca, como o comprimento da sequência mais longa de árvores rotuladas com 1 (ou seja, X = {1} ), de modo que:

• A árvore na posição k na sequência não tem mais do que k + n vértices, para todo k .
• Nenhuma árvore é homeomorficamente embutida em qualquer árvore seguinte na sequência.

É conhecido que árvore (1) = 2, árvore (2) = 5 e árvore (3) ≥ 844424930131960, mas ÁRVORE (3) (onde o argumento especifica o número de rótulos ; veja abaixo ) é maior que${\ displaystyle \ mathrm {árvore} ^ {\ mathrm {árvore} ^ {\ mathrm {árvore} ^ {\ mathrm {árvore} ^ {\ mathrm {árvore} ^ {8} (7)} (7)} (7 )} (7)} (7)}$

Trabalho de Friedman

Para um conjunto de rótulos contável , o teorema da árvore de Kruskal pode ser expresso e provado usando aritmética de segunda ordem . No entanto, como o teorema de Goodstein ou o teorema de Paris-Harrington , alguns casos especiais e variantes do teorema podem ser expressos em subsistemas de aritmética de segunda ordem muito mais fracos do que os subsistemas onde podem ser provados. Isso foi observado pela primeira vez por Harvey Friedman no início dos anos 1980, um sucesso inicial do campo então nascente da matemática reversa. No caso em que as árvores acima são consideradas não rotuladas (ou seja, no caso em que tem ordem um), Friedman descobriu que o resultado era improvável em ATR ₀ , dando assim o primeiro exemplo de um resultado predicativo com uma prova comprovadamente impredicativa . Este caso do teorema ainda é demonstrável em Π${\ displaystyle X}$${\ displaystyle X}$¹
₁-CA ₀ , mas ao adicionar uma "condição de lacuna" à definição da ordem nas árvores acima, ele encontrou uma variação natural do teorema improvável neste sistema. Muito mais tarde, o teorema de Robertson-Seymour daria outro teorema improvável dentro de Π¹
₁-CA ₀ .

A análise ordinal confirma a força do teorema de Kruskal, com o ordinal teórico da prova do teorema igualando o ordinal de Veblen pequeno (às vezes confundido com o ordinal de Ackermann menor ).

ÁRVORE (3)

Suponha que P ( n ) seja a declaração:

Existe algum m tal que se T ₁ , ..., T _m é uma sequência finita de árvores enraizadas não rotuladas onde T _k tem n + k vértices, então T _i  ≤  T _j para algum i < j .

Todas as afirmações P ( n ) são verdadeiras como consequência do teorema de Kruskal e do lema de Kőnig . Para cada n , a aritmética de Peano pode provar que P ( n ) é verdadeira, mas a aritmética de Peano não pode provar a afirmação " P ( n ) é verdadeira para todo n ". Além disso, o comprimento da prova mais curta de P ( n ) na aritmética de Peano cresce fenomenalmente rápido como uma função de n , muito mais rápido do que qualquer função recursiva primitiva ou a função de Ackermann, por exemplo. O mínimo m para o qual P ( n ) é válido cresce extremamente rapidamente com n .

Ao incorporar rótulos, Friedman definiu uma função de crescimento muito mais rápido. Para um número inteiro positivo n , considere TREE ( n ) como o maior m de modo que tenhamos o seguinte:

Há uma sequência T ₁ , ..., T _m de árvores enraizadas rotuladas de um conjunto de n rótulos, onde cada T _i tem no máximo i vértices, de modo que T _i  ≤  T _j não vale para qualquer i < j  ≤  m .

A sequência de ÁRVORE começa ÁRVORE (1) = 1, ÁRVORE (2) = 3, então de repente ÁRVORE (3) explode em um valor tão imensamente grande que muitas outras constantes combinatórias "grandes", como o n de Friedman (4), são extremamente pequeno em comparação. Na verdade, é muito maior do que n ^{n (5)} (5). Um limite inferior para o n (4), e, portanto, uma muito fraca limite inferior para ÁRVORE (3), é um ^{A (187196)} (1), onde A () é uma versão da função de Ackermann : . O número de Graham , por exemplo, é aproximadamente A ⁶⁴ (4), que é muito menor do que o limite inferior A ^{A (187196)} (1). Pode-se mostrar que a taxa de crescimento da função TREE está pelo menos na hierarquia de crescimento rápido . A ^{A (187196)} (1) é aproximadamente , onde g _x é a função de Graham . ${\ displaystyle A (x) = 2 \ uparrow ^ {x-1} x}$${\ displaystyle f _ {\ theta (\ Omega ^ {\ omega} \ omega)}}$${\ displaystyle g_ {3 \ uparrow ^ {187196} 3}}$

Veja também

• Teorema de Paris-Harrington
• Teorema de Kanamori-McAloon
• Teorema de Robertson-Seymour

Notas

^{^ *} Friedman originalmente denotou esta função porTR[n].

^{^ **} n(k) é definido como o comprimento da sequência mais longa possível que pode ser construída com umalfabeto dek-letra de modo que nenhum bloco de letras x_i, ..., x_2iseja uma subsequência de qualquer bloco posterior x_j, ..., x_2j. .${\ displaystyle n (1) = 3, n (2) = 11, \, {\ textrm {and}} \, n (3)> 2 \ uparrow ^ {7197} 158386}$

Referências

Citações

Bibliografia

• Friedman, Harvey M. (2002), Internal finite tree embeddings. Reflexões sobre os fundamentos da matemática (Stanford, CA, 1998) , Lect. Notes Log., 15 , Urbana, IL: Assoc. Símbolo. Logic, pp. 60-91, MR  1943303
• Gallier, Jean H. (1991), "O que há de tão especial sobre o teorema de Kruskal e o ordinal Γ ₀ ? Uma pesquisa de alguns resultados na teoria da prova" (PDF) , Ann. Pure Appl. Logic , 53 (3): 199-260, doi : 10.1016 / 0168-0072 (91) 90022-E , MR  1129778
• Kruskal, JB (maio de 1960), "Bem-quasi-ordenação, o teorema de árvore, e conjectura de Vazsonyi" (PDF) , Transações da American Mathematical Society , American Mathematical Society, 95 (2): 210-225, doi : 10,2307 / 1993287 , JSTOR  1993287 , MR  0111704
• Marcone, Alberto (2001). "Teoria Wqo e bqo em subsistemas de aritmética de segunda ordem" (PDF) . Matemática reversa . 21 : 303–330.
• Nash-Williams, C. St.JA (1963), "On well-quasi-ordering finite trees", Proc. Camb. Phil. Soc. , 59 (4): 833-835, bibcode : 1963PCPS ... 59..833N , doi : 10,1017 / S0305004100003844 , MR  0.153.601
• Rathjen, Michael; Weiermann, Andreas (1993). "Investigações teóricas de prova sobre o teorema de Kruskal" . Annals of Pure and Applied Logic . 60 (1): 49–88. doi : 10.1016 / 0168-0072 (93) 90192-g .
• Simpson, Stephen G. (1985), "Nonprovability of certas combinatorial properties of finite trees", em Harrington, LA; Morley, M .; Scedrov, A .; et al. (eds.), Harvey Friedman's Research on the Foundations of Mathematics , Studies in Logic and the Foundations of Mathematics, North-Holland, pp. 87-117
• Smith, Rick L. (1985), "As forças de consistência de algumas formas finitas dos teoremas de Higman e Kruskal", em Harrington, LA; Morley, M .; Scedrov, A .; et al. (eds.), Harvey Friedman's Research on the Foundations of Mathematics , Studies in Logic and the Foundations of Mathematics, North-Holland, pp. 119-136