Funzione di Veblen

In matematica , e più precisamente nella teoria degli insiemi , le funzioni di Veblen formano una serie di funzioni definite sugli ordinali , introdotte nel 1908 da Oswald Veblen .

Le funzioni di Veblen

Sia f una funzione normale (en) definita sugli ordinali , cioè una funzione continua per la topologia dell'ordine , strettamente crescente. Nel 1908, Oswald Veblen dimostrò che si poteva costruire una sequenza di funzioni indicizzate da ordinali, tutte normali, definite come segue:, e per ogni ordinale diverso da zero α, è la funzione che enumera i punti fissi comuni a tutti per β <α . ${\ displaystyle \ varphi _ {0} = f}$ ${\ displaystyle \ varphi _ {\ alpha}}$ ${\ displaystyle \ varphi _ {\ beta}}$

La gerarchia di Veblen

Nel caso particolare , la famiglia di funzioni di Veblen è nota come gerarchia di Veblen . ${\ displaystyle \ varphi _ {0} (\ alpha) = \ omega ^ {\ alpha}}$

La funzione è allora la funzione ε: . Quindi . Se allora Quello, e il fatto che è strettamente crescente, implica che abbiamo l'ordine: se e solo se ( e ), o e ) o ( e ). $\ varphi _ {1}$ ${\ displaystyle \ varphi _ {1} (\ alpha) = \ varepsilon _ {\ alpha}}$ ${\ displaystyle \ varphi _ {1} (0) = \ varepsilon _ {0} = \ omega ^ {\ omega ^ {\ omega ^ {\ dots}}}}$ $\ alpha <\ beta \ ,,$ ${\ displaystyle \ varphi _ {\ alpha} (\ varphi _ {\ beta} (\ gamma)) = \ varphi _ {\ beta} (\ gamma) \,.}$ ${\ displaystyle \ varphi _ {\ beta}}$ ${\ displaystyle \ varphi _ {\ alpha} (\ beta) <\ varphi _ {\ gamma} (\ delta) \,}$ $\ alpha = \ gamma \,$ $\ beta <\ delta \,$ $(\ alpha <\ gamma \,$ ${\ displaystyle \ beta <\ varphi _ {\ gamma} (\ delta) \,}$ $\ alpha> \ gamma \,$ ${\ displaystyle \ varphi _ {\ alpha} (\ beta) <\ delta \,}$

Suite fondamentali per la gerarchia di Veblen

Una sequenza fondamentale per un ordinale limite (di cofinalità ω, ma è sempre il caso degli ordinali numerabili di questo articolo) è una sequenza strettamente crescente avente questo ordinale come limite. I dati di un sistema di sequenze fondamentali per tutti gli ordinali limite inferiori a un dato ordinale α consentono di costruire una biiezione esplicita (non utilizzando in particolare l' assioma di scelta ) tra ω e α. Le sequenze fondamentali che verranno descritte coprono gli ordinali raggiunti dalla gerarchia di Veblen e salgono all'ordinale di Feferman-Schütte . L' elemento n- esimo della sequenza fondamentale scelta per α sarà indicato con α [ n ].

Una forma analoga alla forma normale di Cantor usata in questo contesto consiste nello scrivere qualsiasi ordinale α diverso da zero nella forma (unica) , dove k > 0 è un numero intero naturale, la sequenza dei termini è decrescente (non necessariamente strettamente): e dove ciascuna Se esiste una sequenza fondamentale per l'ultimo termine, possiamo riscrivere questa, ottenendo una sequenza fondamentale per α: ${\ displaystyle \ alpha = \ varphi _ {\ beta _ {1}} (\ gamma _ {1}) + \ varphi _ {\ beta _ {2}} (\ gamma _ {2}) + \ cdots + \ varphi _ {\ beta _ {k}} (\ gamma _ {k})}$ ${\ displaystyle \ varphi _ {\ beta _ {m}} (\ gamma _ {m}) \ geq \ varphi _ {\ beta _ {m + 1}} (\ gamma _ {m + 1}) \ ,, }$ ${\ displaystyle \ gamma _ {m} <\ varphi _ {\ beta _ {m}} (\ gamma _ {m}) \,.}$ ${\ displaystyle \ alpha [n] = \ varphi _ {\ beta _ {1}} (\ gamma _ {1}) + \ cdots + \ varphi _ {\ beta _ {k-1}} (\ gamma _ { k-1}) + (\ varphi _ {\ beta _ {k}} (\ gamma _ {k}) [n]) \,.}$

Per ogni β, se γ è un ordinale limite con allora impostiamo ${\ displaystyle \ gamma <\ varphi _ {\ beta} (\ gamma) \ ,,}$ ${\ displaystyle \ varphi _ {\ beta} (\ gamma) [n] = \ varphi _ {\ beta} (\ gamma [n]) \,.}$

Ovviamente non esiste una sequenza fondamentale per = ω 0 = 1; perché ci mettiamo in posa ${\ displaystyle \ varphi _ {0} (0)}$ ${\ displaystyle \ varphi _ {0} (\ gamma +1) = \ omega ^ {\ gamma +1} = \ omega ^ {\ gamma} \ cdot \ omega \ ,,}$ ${\ displaystyle \ varphi _ {0} (\ gamma +1) [n] = \ varphi _ {0} (\ gamma) \ cdot n = \ omega ^ {\ gamma} \ cdot n \,.}$

Perché prendiamo e questa è la sequenza 0 , ecc. ${\ displaystyle \ varphi _ {\ beta +1} (0) \ ,,}$ ${\ displaystyle \ varphi _ {\ beta +1} (0) [0] = 0 \,}$ ${\ displaystyle \ varphi _ {\ beta +1} (0) [n + 1] = \ varphi _ {\ beta} (\ varphi _ {\ beta +1} (0) [n]) \ ,,}$ ${\ displaystyle \ varphi _ {\ beta} (0)}$ ${\ displaystyle \ varphi _ {\ beta} (\ varphi _ {\ beta} (0))}$

Per , prendiamo e ${\ displaystyle \ varphi _ {\ beta +1} (\ gamma +1)}$ ${\ displaystyle \ varphi _ {\ beta +1} (\ gamma +1) [0] = \ varphi _ {\ beta +1} (\ gamma) +1 \,}$ ${\ displaystyle \ varphi _ {\ beta +1} (\ gamma +1) [n + 1] = \ varphi _ {\ beta} (\ varphi _ {\ beta +1} (\ gamma +1) [n] ) \,.}$

Supponiamo allora che β sia un ordinale limite: se , poniamo ${\ displaystyle \ beta <\ varphi _ {\ beta} (0)}$ ${\ displaystyle \ varphi _ {\ beta} (0) [n] = \ varphi _ {\ beta [n]} (0) \,.}$

Per , prendiamo ${\ displaystyle \ varphi _ {\ beta} (\ gamma +1)}$ ${\ displaystyle \ varphi _ {\ beta} (\ gamma +1) [n] = \ varphi _ {\ beta [n]} (\ varphi _ {\ beta} (\ gamma) +1) \,.}$

Altrimenti, l'ordinale non può essere descritto utilizzando ordinali e funzioni più piccoli e questo metodo non si applica: questo è ciò che accade dall'ordinale di Feferman-Schütte . $\ varphi$

La funzione Γ

La funzione Γ enumera gli ordinali α per i quali non si applica il metodo precedente, cioè quelli per i quali . Γ 0 è l' ordinale di Feferman-Schütte , quindi il più piccolo α tale che . ${\ displaystyle \ varphi _ {\ alpha} (0) = \ alpha}$ ${\ displaystyle \ varphi _ {\ alpha} (0) = \ alpha}$

Per Γ 0 , possiamo prendere come sequenza fondamentale e $\ Gamma _ {0} [0] = 0 \,$ ${\ displaystyle \ Gamma _ {0} [n + 1] = \ varphi _ {\ Gamma _ {0} [n]} (0) \,.}$

Per Γ β + 1 , prendiamo e $\ Gamma _ {{\ beta +1}} [0] = \ Gamma _ {{\ beta}} + 1 \,$ ${\ displaystyle \ Gamma _ {\ beta +1} [n + 1] = \ varphi _ {\ Gamma _ {\ beta +1} [n]} (0) \,.}$

Infine, per Γ β , dove è un ordinale limite, prendiamo . Di nuovo, non possiamo continuare oltre il primo ordinale come , e dovremmo creare una nuova funzione; il processo, ripetuto in modo transfinito, porta al piccolo ordinale di Veblen ( fr ) . $\ beta <\ Gamma _ {{\ beta}} \,$ $\ Gamma _ {{\ beta}} [n] = \ Gamma _ {{\ beta [n]}} \,.$ $\ beta = \ Gamma _ {{\ beta}} \,$

Generalizzazioni

Per poter generalizzare queste notazioni, è più semplice considerarle come una funzione di due variabili. Veblen mostrò come dedurne una funzione multivariata , e più in generale mostrò come si possa definire anche per una sequenza transfinita di ordinali α β , purché solo un numero finito di essi sia diverso da zero. ${\ displaystyle \ varphi _ {\ alpha} (\ beta)}$ ${\ displaystyle \ varphi (\ alpha, \ beta)}$ ${\ displaystyle \ varphi _ {(} \ alpha _ {n}, \ alpha _ {n-1}, \ dots, \ alpha _ {0})}$ $\ varphi$

Appunti

Veblen 1908
La prova di questo risultato, e di tutti quelli menzionati in questo articolo, si trova in Veblen 1908 ; per un approccio rigoroso ma più intuitivo possiamo consultare, ad esempio, questo testo di Xavier Caruso [PDF] . Il punto chiave della maggior parte di queste dimostrazioni è che se β è un ordinale, la sequenza β, f (β), f ( f (β)), ... ha come limite un ordinale maggiore di β, e che è un punto fisso di f .

Riferimenti

Xavier Caruso, Bons orders sur N [PDF] , articolo introduttivo in francese.
(it) Hilbert Levitz, Transfinite Ordinals and Their Notations: For The Uninitiated , articolo introduttivo (8 pagine, in PostScript )
(en) Wolfram Pohlers , Proof theory: An Introduction , vol. 1407, Springer-Verlag,1989, 213 p. ( ISBN 3-540-51842-8 , leggi in linea )
(en) Kurt Schütte , Teoria della dimostrazione , vol. 225, Springer-Verlag,1977( ISBN 3-540-07911-4 ) , xii + 299
(en) Gaisi Takeuti , Proof theory , vol. 81, North-Holland Publishing Co.,1987, 490 p. ( ISBN 0-444-87943-9 )
(en) C. Smorynski , Le varietà dell'esperienza arborea , vol. 4,1982( leggi in linea ) , p. 182–189 [PDF] : una descrizione informale della gerarchia di Veblen.
(en) Oswald Veblen , " Funzioni crescenti continue di ordinali finiti e transfiniti " , Transactions of the American Mathematical Society , vol. 9, n o 3,1908, p. 280–292 ( leggi in linea ) [PDF]
(en) Larry W. Miller , " Funzioni normali e notazioni ordinali costruttive " , The Journal of Symbolic Logic , vol. 41, n o 21976, p. 439–459 ( DOI 10.2307 / 2272243 , JSTOR 2272243 )

Vedi anche

Gerarchia di rapida crescita

(fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato " Funzione di Veblen " ( vedere l'elenco degli autori ) .