Função de Veblen
Na matemática , e mais precisamente na teoria dos conjuntos , as funções de Veblen formam uma série de funções definidas em ordinais , introduzidas em 1908 por Oswald Veblen .
Funções de Veblen
Seja f uma função normal (en) definida em ordinais , ou seja, uma função contínua para a topologia da ordem , estritamente crescente. Em 1908, Oswald Veblen mostrou que poderíamos construir uma sequência de funções indexadas por ordinais, todas normais, definidas da seguinte forma:, e para qualquer ordinal diferente de zero α, é a função que enumera os pontos fixos comuns a todos os para β < α.
φ0=f{\ displaystyle \ varphi _ {0} = f}φα{\ displaystyle \ varphi _ {\ alpha}}φβ{\ displaystyle \ varphi _ {\ beta}}
A hierarquia de Veblen
Nesse caso específico , a família de funções de Veblen é conhecida como hierarquia de Veblen .
φ0(α)=ωα{\ displaystyle \ varphi _ {0} (\ alpha) = \ omega ^ {\ alpha}}
A função é então a função ε: . Então . Se então Aquilo, e o fato de que está estritamente aumentando, implica que temos a ordem: se e somente se ( e ), ou
e ) ou ( e ).
φ1{\ displaystyle \ varphi _ {1}}φ1(α)=εα{\ displaystyle \ varphi _ {1} (\ alpha) = \ varepsilon _ {\ alpha}}φ1(0)=ε0=ωωω...{\ displaystyle \ varphi _ {1} (0) = \ varepsilon _ {0} = \ omega ^ {\ omega ^ {\ omega ^ {\ dots}}}}α<β,{\ displaystyle \ alpha <\ beta \ ,,}φα(φβ(γ))=φβ(γ).{\ displaystyle \ varphi _ {\ alpha} (\ varphi _ {\ beta} (\ gamma)) = \ varphi _ {\ beta} (\ gamma) \,.}φβ{\ displaystyle \ varphi _ {\ beta}}φα(β)<φγ(δ){\ displaystyle \ varphi _ {\ alpha} (\ beta) <\ varphi _ {\ gamma} (\ delta) \,}α=γ{\ displaystyle \ alpha = \ gamma \,}β<δ{\ displaystyle \ beta <\ delta \,}(α<γ{\ displaystyle (\ alpha <\ gamma \,}β<φγ(δ){\ displaystyle \ beta <\ varphi _ {\ gamma} (\ delta) \,}α>γ{\ displaystyle \ alpha> \ gamma \,}φα(β)<δ{\ displaystyle \ varphi _ {\ alpha} (\ beta) <\ delta \,}
Suítes fundamentais para a hierarquia de Veblen
Uma seqüência fundamental para um ordinal limite (de cofinalidade ω, mas é sempre o caso para os ordinais contáveis deste artigo) é uma seqüência estritamente crescente tendo esse ordinal como limite. O dado de um sistema de sequências fundamentais para todos os ordinais limites inferiores a um dado ordinal α torna possível construir uma bijeção explícita (sem usar em particular o axioma de escolha ) entre ω e α. As sequências fundamentais que serão descritas abrangem os ordinais alcançados pela hierarquia de Veblen, e vão até o ordinal de Feferman-Schütte . O n- ésimo elemento da sequência fundamentais escolhido para α será denotado α [ n ].
Uma forma análoga à forma normal de Cantor usada neste contexto consiste em escrever qualquer ordinal diferente de zero α na forma (única) , onde k > 0 é um inteiro natural, a sequência de termos é decrescente (não necessariamente estritamente): e onde each Se existir uma sequência fundamental para o último termo, podemos reescrever esta, obtendo uma sequência fundamental para α:α=φβ1(γ1)+φβ2(γ2)+⋯+φβk(γk){\ displaystyle \ alpha = \ varphi _ {\ beta _ {1}} (\ gamma _ {1}) + \ varphi _ {\ beta _ {2}} (\ gamma _ {2}) + \ cdots + \ varphi _ {\ beta _ {k}} (\ gamma _ {k})}φβm(γm)≥φβm+1(γm+1),{\ displaystyle \ varphi _ {\ beta _ {m}} (\ gamma _ {m}) \ geq \ varphi _ {\ beta _ {m + 1}} (\ gamma _ {m + 1}) \ ,, }γm<φβm(γm).{\ displaystyle \ gamma _ {m} <\ varphi _ {\ beta _ {m}} (\ gamma _ {m}) \,.}α[não]=φβ1(γ1)+⋯+φβk-1(γk-1)+(φβk(γk)[não]).{\ displaystyle \ alpha [n] = \ varphi _ {\ beta _ {1}} (\ gamma _ {1}) + \ cdots + \ varphi _ {\ beta _ {k-1}} (\ gamma _ { k-1}) + (\ varphi _ {\ beta _ {k}} (\ gamma _ {k}) [n]) \,.}
Para todos os β, se γ é um ordinal limite com então definimosγ<φβ(γ),{\ displaystyle \ gamma <\ varphi _ {\ beta} (\ gamma) \ ,,}φβ(γ)[não]=φβ(γ[não]).{\ displaystyle \ varphi _ {\ beta} (\ gamma) [n] = \ varphi _ {\ beta} (\ gamma [n]) \,.}
Obviamente, não há sequência fundamental para = ω 0 = 1; para nós posarmosφ0(0){\ displaystyle \ varphi _ {0} (0)}φ0(γ+1)=ωγ+1=ωγ⋅ω,{\ displaystyle \ varphi _ {0} (\ gamma +1) = \ omega ^ {\ gamma +1} = \ omega ^ {\ gamma} \ cdot \ omega \ ,,}φ0(γ+1)[não]=φ0(γ)⋅não=ωγ⋅não.{\ displaystyle \ varphi _ {0} (\ gamma +1) [n] = \ varphi _ {0} (\ gamma) \ cdot n = \ omega ^ {\ gamma} \ cdot n \,.}
Pois nós pegamos e essa é a sequência 0 , etc.
φβ+1(0),{\ displaystyle \ varphi _ {\ beta +1} (0) \ ,,}φβ+1(0)[0]=0{\ displaystyle \ varphi _ {\ beta +1} (0) [0] = 0 \,}φβ+1(0)[não+1]=φβ(φβ+1(0)[não]),{\ displaystyle \ varphi _ {\ beta +1} (0) [n + 1] = \ varphi _ {\ beta} (\ varphi _ {\ beta +1} (0) [n]) \ ,,}φβ(0){\ displaystyle \ varphi _ {\ beta} (0)}φβ(φβ(0)){\ displaystyle \ varphi _ {\ beta} (\ varphi _ {\ beta} (0))}
Pois , nós pegamos eφβ+1(γ+1){\ displaystyle \ varphi _ {\ beta +1} (\ gamma +1)}φβ+1(γ+1)[0]=φβ+1(γ)+1{\ displaystyle \ varphi _ {\ beta +1} (\ gamma +1) [0] = \ varphi _ {\ beta +1} (\ gamma) +1 \,}φβ+1(γ+1)[não+1]=φβ(φβ+1(γ+1)[não]).{\ displaystyle \ varphi _ {\ beta +1} (\ gamma +1) [n + 1] = \ varphi _ {\ beta} (\ varphi _ {\ beta +1} (\ gamma +1) [n] ) \,.}
Suponha então que β é um ordinal limite: se , definimosβ<φβ(0){\ displaystyle \ beta <\ varphi _ {\ beta} (0)}φβ(0)[não]=φβ[não](0).{\ displaystyle \ varphi _ {\ beta} (0) [n] = \ varphi _ {\ beta [n]} (0) \,.}
Para , nós tomamosφβ(γ+1){\ displaystyle \ varphi _ {\ beta} (\ gamma +1)}φβ(γ+1)[não]=φβ[não](φβ(γ)+1).{\ displaystyle \ varphi _ {\ beta} (\ gamma +1) [n] = \ varphi _ {\ beta [n]} (\ varphi _ {\ beta} (\ gamma) +1) \,.}
Caso contrário, o ordinal não pode ser descrito usando ordinais e funções menores , e este método não se aplica: é o que acontece a partir do ordinal de Feferman-Schütte .
φ{\ displaystyle \ varphi}
A função Γ
A função Γ enumera os ordinais α para os quais o método anterior não se aplica, ou seja, aqueles para os quais . Γ 0 é o ordinal de Feferman-Schütte , portanto, o menor α desse tipo .
φα(0)=α{\ displaystyle \ varphi _ {\ alpha} (0) = \ alpha}φα(0)=α{\ displaystyle \ varphi _ {\ alpha} (0) = \ alpha}
Para Γ 0 , podemos tomar como uma sequência fundamental eΓ0[0]=0{\ displaystyle \ Gamma _ {0} [0] = 0 \,}Γ0[não+1]=φΓ0[não](0).{\ displaystyle \ Gamma _ {0} [n + 1] = \ varphi _ {\ Gamma _ {0} [n]} (0) \,.}
Para Γ β + 1 , pegamos eΓβ+1[0]=Γβ+1{\ displaystyle \ Gamma _ {\ beta +1} [0] = \ Gamma _ {\ beta} +1 \,}Γβ+1[não+1]=φΓβ+1[não](0).{\ displaystyle \ Gamma _ {\ beta +1} [n + 1] = \ varphi _ {\ Gamma _ {\ beta +1} [n]} (0) \,.}
Finalmente, para Γ β , onde é um ordinal limite, tomamos . Novamente, não podemos continuar além do primeiro ordinal, como , e teríamos que criar uma nova função; o processo, repetido transfinitamente, leva ao pequeno ordinal de Veblen ( fr ) .
β<Γβ{\ displaystyle \ beta <\ Gamma _ {\ beta} \,}Γβ[não]=Γβ[não].{\ displaystyle \ Gamma _ {\ beta} [n] = \ Gamma _ {\ beta [n]} \,.}β=Γβ{\ displaystyle \ beta = \ Gamma _ {\ beta} \,}
Generalizações
Para poder generalizar essas notações, é mais simples considerá-las como uma função de duas variáveis. Veblen mostrou como deduzir uma função multivariada a partir dela e, de maneira mais geral, mostrou como pode ser definida até mesmo para uma sequência transfinita de ordinais α β , desde que apenas um número finito deles seja diferente de zero.
φα(β){\ displaystyle \ varphi _ {\ alpha} (\ beta)}φ(α,β){\ displaystyle \ varphi (\ alpha, \ beta)}φ(αnão,αnão-1,...,α0){\ displaystyle \ varphi _ {(} \ alpha _ {n}, \ alpha _ {n-1}, \ dots, \ alpha _ {0})}φ{\ displaystyle \ varphi}
Notas
-
Veblen 1908
-
A prova desse resultado, e de todos os mencionados neste artigo, pode ser encontrada em Veblen 1908 ; para uma abordagem rigorosa mas mais intuitiva, podemos consultar, por exemplo, este texto de Xavier Caruso [PDF] . O ponto chave da maioria dessas provas é que se β for qualquer ordinal, a sequência β, f (β), f ( f (β)), ... tem como limite um ordinal maior que β, e que é um ponto fixo de f .
Referências
- Xavier Caruso, Bons orders sur N [PDF] , artigo introdutório em francês.
-
(pt) Hilbert Levitz, Transfinite Ordinals and Their Notations: For The Uninitiated , artigo introdutório (8 páginas, em PostScript )
- (pt) Wolfram Pohlers , Teoria da prova: Uma introdução , vol. 1407, Springer-Verlag,1989, 213 p. ( ISBN 3-540-51842-8 , leia online )
- (pt) Kurt Schütte , Teoria da prova , vol. 225, Springer-Verlag,1977( ISBN 3-540-07911-4 ) , xii + 299
- (pt) Gaisi Takeuti , Teoria da prova , vol. 81, North-Holland Publishing Co.,1987, 490 p. ( ISBN 0-444-87943-9 )
-
(pt) C. Smorynski , As variedades de experiência arbórea , vol. 4,1982( leia online ) , p. 182-189 [PDF] : uma descrição informal da hierarquia de Veblen.
-
(pt) Oswald Veblen , " Continuous Aumenting Functions of Finite and Transfinite Ordinals " , Transactions of the American Mathematical Society , vol. 9, n o 3,1908, p. 280-292 ( ler online ) [PDF]
- (pt) Larry W. Miller , " Funções normais e notações ordinais construtivas " , The Journal of Symbolic Logic , vol. 41, n o 21976, p. 439-459 ( DOI 10.2307 / 2272243 , JSTOR 2272243 )
Veja também
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">