Zornovo lemma - Zorn's lemma

Pomocí Zornova lemmatu lze ukázat, že každý připojený graf má strom spanning . Množina všech dílčích grafů, které jsou stromy, je seřazena podle zahrnutí a spojení řetězce je horní mez. Zornovo lemma říká, že musí existovat maximální strom, což je klenutý strom, protože graf je propojen. Zornovo lemma není nutné pro konečné grafy, jako je ten na obrázku zde.

Zornovo lemma , také známé jako lematko Kuratowski – Zorn , podle matematiků Maxe Zorna a Kazimierze Kuratowského , je návrh teorie množin . Uvádí, že částečně uspořádaná sada obsahující horní hranice pro každý řetězec (tj. Každou zcela seřazenou podmnožinu ) nutně obsahuje alespoň jeden maximální prvek .

Dokázáno Kuratowskim v roce 1922 a nezávisle Zornem v roce 1935, toto lemma se vyskytuje v důkazech několika vět zásadního významu, například Hahnovy -Banachovy věty ve funkční analýze , věty, že každý vektorový prostor má základ , Tychonoffova věta v topologii říkat, že každý produkt kompaktních prostorů je kompaktní, a věty v abstraktní algebře, že v kruhu s identitou je každý správný ideál obsažen v maximálním ideálu a že každé pole má algebraické uzavření .

Princip maximality je ekvivalentní zermelova věta a také k axiomu výběru , v tom smyslu, že každý z těch tří, spolu s Zermelo-Fraenkelova axiomů z teorie množin , je dostačující k prokázání další dva. Dřívější formulace Zornova lemmatu je Hausdorffův maximální princip, který říká, že každá zcela uspořádaná podmnožina dané částečně uspořádané množiny je obsažena v maximální zcela uspořádané podmnožině této částečně uspořádané množiny.

Motivace

Abychom dokázali existenci matematického objektu, který lze určitým způsobem považovat za maximální prvek v nějaké částečně uspořádané množině , můžeme zkusit prokázat existenci takového objektu za předpokladu, že neexistuje žádný maximální prvek, a pomocí transfinitní indukce a předpokladů situaci dostat do rozporu. Zornovo lemma uklidí podmínky, které musí situace splnit, aby takový argument fungoval, a umožňuje matematikům, aby nemuseli pokaždé ručně opakovat transfinitní indukční argument, ale pouze zkontrolovali podmínky Zornova lemmatu.

Pokud stavíte matematický objekt ve fázích a zjistíte, že (i) jste nedokončili ani po nekonečně mnoha fázích a (ii) zdá se, že vám nic nebrání pokračovat v budování, pak Zornovo lemma může dobře pomoci vy.

-  William Timothy Gowers , „Jak používat Zornovo lemma“

Prohlášení o lemmatu

Předběžné pojmy:

• O množině P vybavené reflexivním , antisymetrickým a tranzitivním binárním vztahem ≤ se říká, že je (částečně) uspořádána podle ≤. Vzhledem k tomu, dva prvky x a y z P s x ≤ y , y se říká, že je větší nebo rovná x . Slovo „částečný“ má naznačovat, že ne každý pár prvků částečně uspořádané množiny musí být srovnatelný pod vztahem pořadí, to znamená, že v částečně uspořádané sadě P se vztahem pořadí ≤ mohou existovat prvky x a y ani x ≤ y ani y ≤ x . Řazená sada, ve které je každý pár prvků srovnatelný, se nazývá zcela uspořádaná .
• Každá podmnožina S z uspořádaná množina P může sám být viděn jako částečně nařízeno omezení vztah pořadí zděděnou z P do S . Podskupina S částečně uspořádané množiny P se nazývá řetězec (v P ), pokud je zcela uspořádána ve zděděném pořadí.
• Prvek m částečně uspořádané množiny P s řádovým vztahem ≤ je maximální (s ohledem na ≤), pokud neexistuje žádný jiný prvek P větší než m , to znamená, že pokud neexistuje žádné s v P se s ≠ m a m ≤ s . V závislosti na vztahu pořadí může mít částečně uspořádaná sada libovolný počet maximálních prvků. Zcela seřazená sada však může mít maximálně jeden maximální prvek.
• Vzhledem k tomu, podmnožina S z uspořádaná množina P , prvek u o P je horní hranici z S, pokud je větší než nebo rovnající se každý prvek S . Zde, S nemusí být řetězec, a u , kde musí být srovnatelné s každým prvkem S , ale nemusí být sám o sobě prvek S .

Zornovo lemma pak může být uvedeno jako:

Někdy se používají varianty této formulace, jako například požadavek, aby sada P a řetězce nebyly prázdné.

Ačkoli se tato formulace jeví formálně slabší (protože klade na P dodatečnou podmínku neprázdnosti, ale získává stejný závěr o P ), ve skutečnosti jsou tyto dvě formulace ekvivalentní. Chcete-li to ověřit, předpokládám, že první P splňuje podmínku, že každý řetězec P má horní hranici v P . Pak prázdná podmnožina P je řetězec, protože vakuově splňuje definici ; hypotéza tedy naznačuje, že tato podmnožina musí mít horní mez v P a tato horní hranice ukazuje, že P ve skutečnosti není prázdné. Naopak, pokud se předpokládá , že P je neprázdné a splňuje hypotézu, že každý neprázdný řetězec má horní hranici v P , pak P také splňuje podmínku, že každý řetězec má horní hranici, protože libovolný prvek P slouží jako horní mez pro prázdný řetězec (tj. prázdnou podmnožinu považovanou za řetěz).

Rozdíl se může zdát nepatrný, ale v mnoha důkazech, které vyvolávají Zornovo lemma, člověk potřebuje nějaké svazky k vytvoření horní hranice, a tak může být případ prázdného řetězce přehlédnut; to znamená, že ověření, že všechny řetězce mají horní hranice, bude muset řešit prázdné a neprázdné řetězce samostatně. Mnoho autorů dává přednost ověřování prázdnoty množiny P , než aby se v obecném argumentu zabývali prázdným řetězcem.

Příklad aplikace

Zornovým lemmatem lze ukázat, že každý netriviální prsten R s jednotou obsahuje maximální ideál .

Nechť P je množina skládající se ze všech (oboustranných) ideálů v R kromě samotného R. Ideální R byl vyloučen, protože maximální ideál podle definice se nerovná R . Protože R není netriviální, sada P obsahuje triviální ideál {0}, a proto P není prázdné. Kromě toho je P částečně seřazen nastaveným zahrnutím (viz pořadí zařazení ). Nalezení maximální ideál v R je stejný jako nalezení maximální prvek P .

Chcete -li použít Zornovo lemma, vezměte řetězec T v P (to znamená, že T je podmnožina P, která je zcela uspořádaná). Pokud T je prázdná množina, pak je triviální ideální {0} je horní hranice pro T v P . Předpokládejme tedy, že T není prázdné. Je nutné ukázat, že T má horní hranici, to znamená, že existuje ideální I ⊆ R, které je větší než všechny členy T, ale stále menší než R (jinak by to nebylo v P ). Vezměte I za sjednocení všech ideálů v T . Chtěli bychom ukázat, že jsem je horní hranice pro T v P . Budeme nejprve ukázat, že jsem je ideální z R , a že to je vlastní ideál R , a tak je prvek P . Protože každý prvek T je obsažen v I , toto ukáže, že I je horní mez pro T v P , jak je požadováno.

Protože T obsahuje alespoň jeden prvek a tento prvek obsahuje alespoň 0, sjednocení I obsahuje alespoň 0 a není prázdné. K prokázání, že jsem je ideální, na vědomí, že v případě, a b jsou prvky I , potom existují dva ideály J , K ∈ T tak, že je prvek J a b je prvek K . Vzhledem k tomu, T je zcela nařízeno, víme, že J ⊆ K nebo K ⊆ J . V prvním případě, a to jak a b jsou členy ideálního K , a proto jejich součet + b je členem skupiny K , což ukazuje, že + b je členem I . Ve druhém případě, jak a b jsou členy ideálu J , a tak + b ∈ I . Kromě toho, je-li r ∈ R , pak ar a RA jsou prvky J a tím prvky I . Proto jsem v R ideálem .

Nyní je ideál roven R právě tehdy, pokud obsahuje 1. (Je jasné, že pokud se rovná R , pak musí obsahovat 1; na druhou stranu, pokud obsahuje 1 a r je libovolný prvek R , pak r1 = r je prvek ideálu, a tak se ideál rovná R. ) Pokud bych se tedy rovnal R , pak by obsahoval 1, a to znamená, že jeden z členů T bude obsahovat 1 a tak by se rovná R -, ale R je z výslovně vyloučeno P .

Hypotéza o princip maximality byla zkontrolována, a tudíž je zde maximální prvkem P , jinými slovy maximální ideální R .

Důkaz závisí na skutečnosti, že prsten R má multiplikativní jednotku 1. Bez tohoto by důkaz nefungoval a tvrzení by bylo nepravdivé. Například kruh s aditivní skupinou a triviální multiplikací (tj. Pro všechny ) nemá žádný maximální ideál (a samozřejmě ne 1): Jeho ideály jsou právě aditivní podskupiny. Skupina faktorů správnou podskupinou je dělitelná skupina , a proto rozhodně není generována konečným způsobem , a proto má vlastní netriviální podskupinu, která vede k vytvoření podskupiny a ideálního obsahu . ${\ displaystyle \ mathbb {Q}}$${\ displaystyle ab = 0}$${\ displaystyle a, b}$ ${\ displaystyle \ mathbb {Q} /A}$${\ displaystyle A}$${\ displaystyle A}$

Důkaz skica

Následuje náčrt důkazu Zornova lemmatu za předpokladu zvoleného axiomu . Předpokládejme, že je lemma falešné. Pak existuje částečně uspořádaná množina nebo poset P tak, že každá zcela uspořádaná podmnožina má horní hranici a že pro každý prvek v P existuje jiný prvek větší než ona. Pro každou zcela seřazenou podmnožinu T pak můžeme definovat větší prvek b ( T ), protože T má horní hranici a tato horní hranice má větší prvek. Abychom vlastně definovali funkci b , musíme použít axiom volby.

Pomocí funkce b , budeme definovat prvky ₀ < ₁ < ₂ < ₃ <... v P . Tato sekvence je opravdu dlouhý : indexy nejsou jen přirozená čísla , ale všechny řadové . Ve skutečnosti je sekvence pro sadu P příliš dlouhá ; existuje příliš mnoho řadových čísel ( správná třída ), více než prvků v jakékoli sadě a množina P se brzy vyčerpá a pak narazíme na požadovaný rozpor.

_I jsou definovány transfinitní rekurze : vybíráme ₀ v P svévolné (to je možné, protože P obsahuje horní mez pro prázdné množiny, a tudíž není prázdný) a pro jakýkoli jiný pořadové w nastavíme _w = b ( { a _v  : v < w }). Protože a a _v jsou zcela uspořádány, je to opodstatněná definice.

Tento důkaz ukazuje, že ve skutečnosti je pravda o něco silnější verze Zornova lemmatu:

Dějiny

Princip Hausdorff kapacita je jedním z prvních prohlášení podobný princip maximality.

Kazimierz Kuratowski prokázal v roce 1922 verzi lemmatu blízkou své moderní formulaci (platí pro sady seřazené zařazením a uzavřené pod svazky dobře uspořádaných řetězců). V podstatě stejná formulace (oslabená použitím libovolných řetězců, nejen dobře uspořádaných) byla nezávisle dána Maxem Zornem v roce 1935, který ji navrhl jako nový axiom teorie množin nahrazující dobře uspořádanou větu, ukázal některé její aplikace v algebře , a slíbil ukázat svou ekvivalenci s axiomem volby v jiném dokumentu, který se nikdy neobjevil.

Jméno „princip maximality“ Zdá se, že vzhledem k John Tukey , kdo používal to ve své knize Konvergence a jednotnost topologie v roce 1940. Bourbaki ‚s Théorie des Ensembles z roku 1939 odkazuje na podobném principu maximální jako‚le théorème de Zorn‘. V Polsku a Rusku převládá název „ Kuratowski – Zorn lemma “.

Ekvivalentní formy Zornova lemmatu

Zornovo lemma odpovídá (v ZF ) třem hlavním výsledkům:

1. Hausdorffův maximální princip
2. Axiom volby
3. Dobře uspořádaná věta .

Známý vtip, který se zmiňuje o této ekvivalenci (což může vzdorovat lidské intuici), je připisován Jerrymu Bona : „Axiom volby je zjevně pravdivý, dobře uspořádaný princip evidentně falešný a kdo může vyprávět o Zornově lemmatu?“

Zornovo lemma je také ekvivalentní silné větě o úplnosti logiky prvního řádu.

Kromě toho Zornovo lemma (nebo jedna z jeho ekvivalentních forem) implikuje některé významné výsledky v jiných matematických oblastech. Například,

1. Banachova věta o rozšíření, která se používá k prokázání jednoho z nejzákladnějších výsledků funkční analýzy, Hahnova – Banachova věta
2. Každý vektorový prostor má základ , výsledek z lineární algebry (které je ekvivalentní). Zejména skutečná čísla, jako vektorový prostor nad racionálními čísly, mají hamelský základ.
3. Každý komutativní jednotný prsten má maximální ideál , což je výsledkem prstencové teorie známé jako Krullova věta , které je Zornovo lemma ekvivalentní
4. Tychonoffova věta v topologii (které je také ekvivalentní)
5. Každý správný filtr je obsažen v ultrafiltru , což je výsledek, který přináší větu o úplnosti logiky prvního řádu

V tomto smyslu vidíme, jak lze na Zornovo lemma pohlížet jako na mocný nástroj, zejména ve smyslu jednotné matematiky.

Analogy pod oslabením zvoleného axiomu

Oslabenou formu Zornova lemmatu lze prokázat pomocí ZF + DC (teorie množin Zermelo – Fraenkel s axiomem volby nahrazeným axiomem závislé volby ). Zornovo lemma lze vyjádřit přímočarým pozorováním, že množina, která nemá žádný maximální prvek, by byla ekvivalentní konstatování, že objednávací vztah množiny by byl celý, což by nám umožnilo použít axiom závislé volby pro konstrukci počitatelného řetězce. Výsledkem je, že každá částečně seřazená sada s výhradně konečnými řetězci musí mít maximální prvek.

Obecněji řečeno, posílení axiomu závislé volby na vyšší pořadové číslo nám umožňuje zobecnit tvrzení v předchozím odstavci na vyšší kardinality. V limitu, kde povolíme libovolně velké pořadové číslo, získáme důkaz plného Zornova lemmatu pomocí zvoleného axiomu v předchozí části.

V populární kultuře

Film Zorns Lemma z roku 1970 je pojmenován po lemmatu.

Lemma byla zmíněna v seriálu Simpsonovi v epizodě „ Bartův nový přítel “.

Viz také

• Antichain  - podmnožina nesrovnatelných prvků
• Szpilrajnova věta o rozšíření  - Matematický výsledek o vztazích objednávek
• Tarskiho konečnost
• Teichmüller – Tukey lemma (někdy nazývané Tukey's lemma)

Poznámky

Reference

• Campbell, Paul J. (únor 1978). „Původ‚ Zorn's Lemma ‘ “ . Historia Mathematica . 5 (1): 77–89. doi : 10.1016/0315-0860 (78) 90136-2 .
• Ciesielski, Krzysztof (1997). Teorie množin pro pracujícího matematika . Cambridge University Press. ISBN 978-0-521-59465-3.
• Jech, Thomas (2008) [1973]. Axiom volby . Mineola, New York: Dover Publications . ISBN 978-0-486-46624-8.
• Moore, Gregory H. (2013) [1982]. Axiom volby Zermelo: Jeho počátky, vývoj a vliv . Dover Publications . ISBN 978-0-486-48841-7.

externí odkazy

• „Zorn lemma“ , encyklopedie matematiky , EMS Press , 2001 [1994]
• Zornova Lemma v ProvenMath obsahuje formální důkaz až do nejjemnějších detailů o rovnocennosti axiomu volby a Zornovy Lemmy.
• Zornova Lemma v Metamathu je dalším formálním důkazem. ( Verze Unicode pro nejnovější prohlížeče.)