Teorema di Bourbaki-Witt

Teorema di Bourbaki-Witt In matematica, il teorema di Bourbaki-Witt nella teoria degli ordini, intitolato a Nicolas Bourbaki e Ernst Witt, è un teorema di base del punto fisso per insiemi parzialmente ordinati. Afferma che se X è un poset completo di catena non vuota, e {stile di visualizzazione f:Xto X} tale che {stile di visualizzazione f(X)gek x} per tutti {stile di visualizzazione x,} allora f ha un punto fisso. Tale funzione f è chiamata inflazionistica o progressiva.

Contenuti 1 Caso speciale di poset finito 2 Dimostrazione del teorema 3 Applicazioni 4 References Special case of a finite poset If the poset X is finite then the statement of the theorem has a clear interpretation that leads to the proof. La sequenza di iterazioni successive, {stile di visualizzazione x_{n+1}=f(X_{n}),n=0,1,2,ldot ,} dove x0 è un qualsiasi elemento di X, è monotono in aumento. Per la finitezza di X, si stabilizza: {stile di visualizzazione x_{n}=x_{infty },} per n sufficientemente grande.

Ne consegue che x∞ è un punto fisso di f.

Proof of the theorem Pick some {stile di visualizzazione yin X} . Definire una funzione K ricorsivamente sugli ordinali come segue: {stile di visualizzazione ,K(0)=y} {stile di visualizzazione ,K(alfa +1)=f(K(alfa )).} Se {displaystyle beta } è un ordinale limite, poi per costruzione {stile di visualizzazione {K(alfa ) : alfa X}).} Questo è consentito come, per assunzione, il set non è vuoto. Poi f(X) > x, quindi f è una funzione inflazionistica senza punto fisso, contraddicendo il teorema.

Questo caso speciale del lemma di Zorn viene quindi utilizzato per dimostrare il principio di massimalità di Hausdorff, che ogni poset ha una catena massima, che è facilmente equivalente al Lemma di Zorn.

Bourbaki–Witt ha altre applicazioni. In particolare in informatica, è usato nella teoria delle funzioni calcolabili. Viene anche utilizzato per definire tipi di dati ricorsivi, per esempio. liste collegate, nella teoria dei domini.

Riferimenti Nicolas Bourbaki (1949). "Sul teorema di Zorn". Archivio di matematica. 2 (6): 434–437. doi:10.1007/bf02036949. S2CID 117826806. Ernest Witt (1951). "Dimostrazioni per il teorema di M. Zorn". Notizie matematiche. 4: 434–438. doi:10.1002/mana.3210040138. Categorie: Teoremi degli ordini Teoremi di punto fisso Teoremi nei fondamenti della matematica