Satz von Bourbaki-Witt

Satz von Bourbaki-Witt In der Mathematik, das Bourbaki-Witt-Theorem in der Ordnungstheorie, benannt nach Nicolas Bourbaki und Ernst Witt, ist ein grundlegender Fixpunktsatz für teilweise geordnete Mengen. Es besagt, dass, wenn X eine nicht leere Kette ist, vollständiges Poset ist, und {Anzeigestil f:X bis X} so dass {Anzeigestil f(x)gek. x} für alle {Anzeigestil x,} dann hat f einen Fixpunkt. Eine solche Funktion f heißt inflationär oder progressiv.

Inhalt 1 Sonderfall eines endlichen Poset 2 Beweis des Satzes 3 Anwendungen 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. Die Folge aufeinanderfolgender Iterationen, {Anzeigestil x_{n+1}= f(x_{n}),n=0,1,2,lPunkte ,} wobei x0 ein beliebiges Element von X ist, ist monoton steigend. Durch die Endlichkeit von X, es stabilisiert: {Anzeigestil x_{n}=x_{unendlich },} für n hinreichend groß.

Daraus folgt, dass x∞ ein Fixpunkt von f ist.

Proof of the theorem Pick some {Anzeigestil Yin X} . Definieren Sie eine Funktion K rekursiv auf den Ordnungszahlen wie folgt: {Anzeigestil ,K(0)=y} {Anzeigestil ,K(Alpha +1)= f(K(Alpha )).} Wenn {Displaystyle-Beta } ist eine Grenzordnungszahl, dann konstruktionsbedingt {Anzeigestil {K(Alpha ) : Alpha x}).} Dies ist als erlaubt, nach Annahme, die Menge ist nicht leer. Dann f(x) > x, also ist f eine Inflationsfunktion ohne Fixpunkt, Widerspruch zum Theorem.

Dieser Spezialfall von Zorns Lemma wird dann verwendet, um das Hausdorff-Maximalitätsprinzip zu beweisen, dass jedes Poset eine maximale Kette hat, was leicht als äquivalent zu Zorns Lemma zu sehen ist.

Bourbaki-Witt hat andere Anwendungen. Insbesondere in der Informatik, es wird in der Theorie der berechenbaren Funktionen verwendet. Es wird auch verwendet, um rekursive Datentypen zu definieren, z.B. verknüpfte Listen, in der Domänentheorie.

Referenzen Nicolas Bourbaki (1949). "Zum Satz von Zorn". Archiv der Mathematik. 2 (6): 434–437. doi:10.1007/bf02036949. S2CID 117826806. Ernst Witt (1951). "Beweisstudien zum Satz von M. Zorn". Mathematische Nachrichten. 4: 434–438. doi:10.1002/mana.3210040138. Kategorien: OrdnungstheorieFixpunktsätzeTheoreme der Grundlagen der Mathematik