Lemat Kuratowskiego-Zorna

Lemat Kuratowskiego-Zorna, lemat Zorna^[1] – twierdzenie teorii mnogości, nazywane zwyczajowo lematem, dające pewien warunek dostateczny istnienia elementu maksymalnego w danym zbiorze częściowo uporządkowanym; znajduje ono wiele zastosowań w pozostałych działach matematyki, gdzie wykorzystywane jest w dowodach istnienia różnych obiektów (gdy szukany element, którego istnienie jest postulowane, jest maksymalnym w pewnym zbiorze z częściowym porządkiem).

Lemat ten został sformułowany przez Kazimierza Kuratowskiego w 1922 roku oraz niezależnie przez Maxa Zorna w 1935 roku. Jest on równoważny aksjomatowi wyboru – każdy z nich można udowodnić przy pomocy drugiego (na gruncie aksjomatyki Zermela-Fraenkla teorii mnogości) – przy czym jest to jedna z bardziej użytecznych jego postaci (zob. pozostałe). Istnieją również dowody wykorzystujące równoważniki aksjomatu wyboru, np. twierdzenie Zermela, czy twierdzenie Hausdorffa o łańcuchu maksymalnym.

Motywacja

Niekiedy zachodzi potrzeba udowodnienia istnienia^[a] obiektu matematycznego (który można postrzegać jako element maksymalny pewnego zbioru częściowo uporządkowanego). Dowód istnienia takiego obiektu można próbować przeprowadzić nie wprost zakładając, że nie ma wspomnianego elementu (maksymalnego), wykorzystując przy tym indukcję pozaskończoną oraz założenia sytuacyjne do tego, by wykazać sprzeczność. Lemat Kuratowskiego-Zorna służy wyklarowaniu założeń, które muszą być spełnione w danej sytuacji, aby można było wykorzystać takie rozumowanie. Tym samym lemat Kuratowskiego-Zorna umożliwia matematykom wyzbycie się konieczności każdorazowego powtarzania rozumowania indukcyjnego na rzecz sprawdzenia założeń lematu.

Jeśli konstruując obiekt matematyczny etapami okazuje się, że (i) nie skończyłeś nawet po nieskończenie wielu etapach oraz (ii) zdaje się, że nie ma nic, co mogłoby powstrzymać cię przed dalszym konstruowaniem, wówczas pomocny może okazać się lemat Kuratowskiego-Zorna.

William Timothy Gowers, Jak używać lematu Kuratowskiego-Zorna^[2]

Twierdzenie

Zobacz też: porządek częściowy, porządek liniowy, łańcuch, ograniczenie górne i element maksymalny.

Zbiór $P$ nazywa się częściowo uporządkowanym przez (dwuargumentową) relację $\preccurlyeq$ (tzw. częściowy porządek), jeśli jest ona zwrotna ( $x\preccurlyeq x$ ), antysymetryczna ( $x\preccurlyeq y$ oraz $y\preccurlyeq x$ pociągają $x=y$ ) i przechodnia ( $x\preccurlyeq y$ oraz $y\preccurlyeq z$ pociągają $x\preccurlyeq z$ ); jeśli $x\preccurlyeq y,$ to element $y$ nazywa się późniejszym od $x$ (a element $x$ nazywa się wcześniejszym od $y$ ).

Podzbiór $C$ zbioru $P$ nazywa się liniowo uporządkowanym, jeżeli dowolne jego dwa elementy można porównać za pomocą relacji $\preccurlyeq ;$ zbiór $C$ nazywa się wtedy łańcuchem w $P.$ Element $u\in P$ nazywa się ograniczeniem górnym łańcucha $C,$ jeśli element $u$ jest późniejszy od jakiegokolwiek innego elementu tego łańcucha.

Zbiór częściowo uporządkowany, w którym każdy łańcuch ma ograniczenie górne, nazywa się łańcuchowo zupełnym; element $m$ nazywa się maksymalnym w zbiorze $P,$ jeśli $m\preccurlyeq x$ pociąga $x=m$ dla dowolnego $x\in P.$

Twierdzenie Kuratowskiego-Zorna: W dowolnym niepustym zbiorze łańcuchowo zupełnym istnieje (co najmniej jeden) element maksymalny.

Wniosek: W dowolnej niepustej rodzinie zbiorów częściowo uporządkowanej relacją zawierania, do której należy suma każdego jej niepustego łańcucha, istnieje element maksymalny^[b].

Uwagi

↑ Zob. filozofia matematyki oraz Bartol 1996 ↓.
↑ Jeśli ${\mathcal {L}}$ jest łańcuchem w rodzinie ${\mathcal {S}}$ jak w założeniu, to $\bigcup {\mathcal {L}}$ zawiera każdy ze zbiorów tego łańcucha; stąd jeśli $\bigcup {\mathcal {L}}\in {\mathcal {S}},$ to zbiór ten jest ograniczeniem górnym łańcucha ${\mathcal {L}}$ w ${\mathcal {S}}.$ W ten sposób spełnione są założenia lematu Kuratowskiego-Zorna: ograniczeniem górnym dowolnego niepustego łańcucha ${\mathcal {S}}$ jest jego suma, zaś pustego – przez dowolny element ${\mathcal {S}},$ czyli w rodzinie ${\mathcal {S}}$ istnieje element maksymalny.

Przypisy

↑ Kuratowskiego–Zorna lemat, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2022-11-22] .
↑ William Timothy Gowers: How to use Zorn’s lemma. 2008-08-12. [dostęp 2019-10-29]. Cytat: If you are building a mathematical object in stages and find that (i) you have not finished even after infinitely many stages, and (ii) there seems to be nothing to stop you continuing to build, then Zorn’s lemma may well be able to help you.

Bibliografia

Krzysztof Ciesielski, Set Theory for the Working Mathematician. Cambridge University Press, 1997. ISBN 0-521-59465-0

Linki zewnętrzne

WiktorW. Bartol WiktorW., Istnienie i nieistnienie w matematyce, „Delta”, listopad 1996, ISSN 0137-3005 [dostęp 2021-09-14] .

[2] Zob. filozofia matematyki oraz Bartol 1996 ↓.

[4] Jeśli ${\mathcal {L}}$ jest łańcuchem w rodzinie ${\mathcal {S}}$ jak w założeniu, to $\bigcup {\mathcal {L}}$ zawiera każdy ze zbiorów tego łańcucha; stąd jeśli $\bigcup {\mathcal {L}}\in {\mathcal {S}},$ to zbiór ten jest ograniczeniem górnym łańcucha ${\mathcal {L}}$ w ${\mathcal {S}}.$ W ten sposób spełnione są założenia lematu Kuratowskiego-Zorna: ograniczeniem górnym dowolnego niepustego łańcucha ${\mathcal {S}}$ jest jego suma, zaś pustego – przez dowolny element ${\mathcal {S}},$ czyli w rodzinie ${\mathcal {S}}$ istnieje element maksymalny.

[epwn-1] Kuratowskiego–Zorna lemat, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2022-11-22] .

[3] William Timothy Gowers: How to use Zorn’s lemma. 2008-08-12. [dostęp 2019-10-29]. Cytat: If you are building a mathematical object in stages and find that (i) you have not finished even after infinitely many stages, and (ii) there seems to be nothing to stop you continuing to build, then Zorn’s lemma may well be able to help you.

[1]

[a]

[2]

[b]

Fahrer / Team für die Suche eingeben: