Bourbakiho-Wittova věta - Bourbaki–Witt theorem

v matematika, Bourbakiho-Wittova věta v teorie objednávek, pojmenoval podle Nicolas Bourbaki a Ernst Witt, je základní věta o pevném bodě pro částečně objednané sady. Uvádí se v něm, že pokud X není prázdné řetěz dokončen poset, a

${ displaystyle f: X až X}$

takhle

${ displaystyle f (x) geq x}$ pro všechny ${ displaystyle x,}$

pak F má pevný bod. Taková funkce F je nazýván inflační nebo progresivní.

Zvláštní případ konečné posety

Pokud je to poset X je konečné, pak věta má jasnou interpretaci, která vede k důkazu. Posloupnost po sobě jdoucích iterací,

${ displaystyle x_ {n + 1} = f (x_ {n}), n = 0,1,2, ldots,}$

kde X₀ je jakýkoli prvek X, se monotónně zvyšuje. Podle konečnosti X, stabilizuje:

${ displaystyle x_ {n} = x _ { infty},}$ pro n dostatečně velký.

Z toho vyplývá, že X_∞ je pevný bod F.

Důkaz věty

Vyberte nějaké ${ displaystyle y v X}$. Definujte funkci K. rekurzivně na ordinále takto:

${ displaystyle , K (0) = y}$

${ displaystyle , K ( alfa +1) = f (K ( alfa)).}$

Li ${ displaystyle beta}$ je mezní pořadové číslo, pak podle konstrukce

${ displaystyle {K ( alfa) : alfa < beta }}$

je řetězec v X. Definovat

${ displaystyle K ( beta) = sup {K ( alfa) : alfa < beta }.}$

Toto je nyní rostoucí funkce od ordinálů do X. Nemůže se striktně zvyšovat, jako kdybychom měli injekční funkce z ordinálů do množiny, porušující Hartogsovo lemma. Proto funkce musí být nakonec konstantní, takže pro některé

${ displaystyle alpha, K ( alfa +1) = K ( alfa);}$

to je

${ displaystyle , f (K ( alfa)) = K ( alfa).}$

Takže nechám

${ displaystyle , x = K ( alfa),}$

máme náš požadovaný pevný bod. Q.E.D.

Aplikace

Bourbakiho-Wittova věta má různé důležité aplikace. Jeden z nejběžnějších je v důkazu, že axiom volby naznačuje Zornovo lemma. Nejprve to dokážeme pro případ, kdy X je řetěz kompletní a nemá žádný maximální prvek. Nechat G být volbou funkce na

${ displaystyle P (X) - { varnothing }.}$

Definujte funkci

${ displaystyle f: X až X}$

podle

${ displaystyle f (x) = g ( {y : y> x }).}$

To je povoleno, protože za předpokladu, že sada není prázdná. Pak F(X) > X, tak F je inflační funkce bez pevného bodu, odporující teorému.

Tento speciální případ Zornova lemmatu se poté používá k prokázání Hausdorffův princip maximality, že každý poset má maximální řetězec, který lze snadno považovat za ekvivalent Zornova lemma.

Bourbaki – Witt má i další aplikace. Zejména v počítačová věda, je používán v teorii vypočítatelné funkce Používá se také k definování rekurzivních datových typů, např. propojené seznamy v teorie domény.

Reference

• Nicolas Bourbaki (1949). „Sur le théorème de Zorn“. Archiv der Mathematik. 2: 434–437. doi:10.1007 / bf02036949.
• Ernst Witt (1951). „Beweisstudien zum Satz von M. Zorn“. Mathematische Nachrichten. 4: 434–438. doi:10,1002 / many.3210040138.