POSZUKIWANIE MAKSYMALNEGO,
czyli lemat Kuratowskiego-Zorna

Opowieść o niezwykłym uporządkowaniu liczb naturalnych (w rozdziale dziesiątym) rozpoczęliśmy od określenia porządku. Rozpatrywane tam porządki, choć wydawały się jak najbardziej naturalne, nie są jednak jedynymi, które badają matematycy. Definiując porządek, wprowadziliśmy pewne warunki. Zrezygnujmy z jednego z nich; dokładnie - nie wymagajmy, by dowolne różne „porządkowane" obiekty można było ze sobą porównywać. Inaczej: wcale nie jest powiedziane, że albo a jest "mniejsze" od b (względnie a poprzedza b), albo b jest "mniejsze" od a (b poprzedza a). Elementy a oraz b mogą po prostu nie mieć ze sobą żadnego związku.

Czy po takiej zmianie usprawiedliwione jest nazywanie porządkiem badanego porównywania elementów? Okazuje się, że tak, o czym przekonuje wiele przykładów.

Doskonale wiemy, jak wygląda mapa Polski - ograniczmy nasze zainteresowanie tylko do sieci wodnej Wisły, czyli do Wisły i jej dopływów. Naturalna wydaje się umowa, że punkt a poprzedza punkt b, jeśli z punktu a można dopłynąć do b "z prądem", to znaczy bez użycia wioseł, motorówki itp. Pozostałe warunki z definicji porządku są tu spełnione, ale bez trudu znajdziemy elementy nieporównywalne - na przykład jeden punkt na Dunajcu, drugi zaś na Pisie.

Bardzo ważny przykład dotyczy zbioru liczb naturalnych. Możemy w nim wprowadzić porządek za pomocą podzielności liczb. Przypomnijmy: liczba a dzieli liczbę b, gdy istnieje taka liczba , że b =  a. Umawiamy się, że a poprzedza b (albo a jest mniejsze od b), gdy a dzieli b. Tak więc 2 poprzedza 4, 4 poprzedza 8, z kolei 8 poprzedza 16. Podobnie 3 poprzedza 6, oraz 6 poprzedza 12... a jak się ma 4 do 6? Jest to typowy przykład elementów nieporównywalnych. Przy takim uporządkowaniu ani 4 nie poprzedza 6, ani 6 nie poprzedza 4 - liczby te są względnie pierwsze i w tej relacji nie dają się porównać.

A oto jeszcze inny przykład, również ważny, tym razem dotyczący zbiorów. w każdej rodzinie zbiorów można w naturalny sposób wprowadzić porządek, wykorzystując pojęcie zawierania się zbiorów. Powiemy, że zbiór A jest "mniejszy" od zbioru B, gdy A zawiera się w B. Rozważmy zbiór trójelementowy (elementami mogą być zupełnie dowolne obiekty, nawet bardzo abstrakcyjne) i jego podzbiory. Łatwo policzyć, że tych podzbiorów jest 8. Wśród nich są oczywiście zbiór wyjściowy i zbiór pusty, który zawiera się w dowolnym zbiorze. Ponadto są tam trzy podzbiory jednoelementowe i trzy podzbiory dwuelementowe. Wyobraźmy sobie, że nasze trzy elementy to jabłko, gruszka i śliwka. Zbadajmy teraz wprowadzony porządek w zbiorze wszystkich podzbiorów tego zbioru. Nietrudno zauważyć, że są tu obiekty nieporównywalne. Znajdziemy dwa zbiory takie, że żaden z nich nie zawiera się w drugim, na przykład - zbiór jednoelementowy, którego jedynym elementem jest jabłko, i zbiór, którego jedynym elementem jest śliwka. Żadne zresztą dwa różne podzbiory jednoelementowe nie dadzą się porównać, podobnie jak podzbiory dwuelementowe. Istnieją jednak zbiory porównywalne, choćby zbiór pusty i jakikolwiek inny zbiór.

Często wielu obiektów nie można porównać w rozsądny sposób. Gdy mówimy o wynikach sportowców, sensowne wydaje się określenie, że lepszy był ten zawodnik, który uzyskał lepszy wynik. Ale jak powiązać ze sobą rezultaty lekkoatlety w biegu na sto metrów i narciarza w slalomie gigancie?
Skoro rozważane są różne porządki, to nie mogą one być nazywane tak samo. Ten, w którym dowolne dwa elementy są porównywalne, nazywa się porządkiem liniowym (albo czasem - zupełnym). Nazwa bierze się stąd, że elementy zbioru w ten sposób uporządkowanego można ustawić w szeregu, w linii. Gdy dopuszczamy możliwość istnienia elementów nieporównywalnych, to mówimy o porządku częściowym. Terminologia zresztą nie jest jednolita, czasem różni autorzy używają różnych nazw. Za twórcę całej teorii zbiorów uporządkowanych należy chyba uznać Richarda Dedekinda, choć definicje porządków podawali (niezależnie od siebie) rozmaici matematycy, między innymi Georg Cantor i Felix Hausdorff. Działo się to na przełomie XIX i XX wieku.

Bliższy intuicji jest porządek liniowy, który najczęściej kojarzy się z uporządkowaniem zbioru liczb rzeczywistych. Jednak w praktyce matematycznej różne sytuacje prowadzą w naturalny sposób do porządków częściowych. Oprócz tych już wspomnianych, świetnego modelu dostarcza próba uporządkowania punktów na płaszczyźnie. Każdy punkt jest opisany przez parę współrzędnych. Naturalne wydaje się przyjęcie umowy, że punkt (x₁, y₁) poprzedza punkt (x₂, y₂), gdy x₁ x₂ i y₁ y₂. Będzie to, oczywiście, porządek, ale tylko częściowy. Na przykład pary (3,1) i (1,3) są nieporównywalne.


w matematyce, po trafnym wprowadzeniu definicji, zazwyczaj możemy określić kolejne pojęcia, które często okazują się ważne i przydatne. Tak jest i w przypadku porządków. w szczególności mówimy o elementach największych, najmniejszych, maksymalnych i minimalnych.

Definicja elementu największego w danym zbiorze jest zgodna z intuicją: element największy to element większy od wszystkich innych elementów tego zbioru. Słowo "wszystkich" jest tu bardzo ważne, oznacza bowiem w szczególności, że element największy jest porównywalny ze wszystkimi innymi - co, jak wiemy, ogólnie w przypadku porządku częściowego zachodzić nie musi. w podobny sposób definiujemy element najmniejszy.

Oczywiście, zarówno element największy, jak i najmniejszy wcale nie muszą w badanym zbiorze (z zadanym porządkiem) istnieć. Na przykład nie ma ich w standardowo uporządkowanym zbiorze liczb rzeczywistych. w zbiorze liczb naturalnych, uporządkowanym "klasycznie", istnieje element najmniejszy - jest nim 0 - ale elementu największego nie ma. w zbiorze liczb naturalnych dodatnich, uporządkowanym metodą Szarkowskiego, istnieje zarówno element najmniejszy (jest nim liczba 3), jak i największy (liczba 1).