O USTAWIANIU LICZB NATURALNYCH,
czyli twierdzenie Szarkowskiego

Są takie słowa, które nie tylko stosunkowo często pojawiają się w języku potocznym, ale również należą do terminologii matematycznej. Jednym z nich jest "porządek".

Matematyczne znaczenie tego słowa jest podobne do potocznie używanego. Mamy jakiś zbiór i chcemy jego elementy jakoś... no, właśnie. Pierwsze słowo, które przychodzi nam na myśl, to "uporządkować".

Formalna, matematyczna definicja porządku nie jest trudna. Warto ją tu przytoczyć. Załóżmy, że mamy jakiś zbiór i chcemy porównywać jego elementy. Porównanie to nazwijmy, dla uproszczenia, "mniejszością". Powinno ono spełniać tylko dwa naturalne warunki: po pierwsze - dowolne dwa różne elementy powinny być porównywalne, i to "tylko w jedną stronę", to znaczy, że jeśli a jest różne od b, to albo a jest mniejsze od b, albo większe od b, ale nie może być jednocześnie i mniejsze, i większe; po drugie - jeśli a jest mniejsze od b i b jest mniejsze od c, to a jest mniejsze od c.

i to wszystko. Należy zaznaczyć, że rozważane są różne rodzaje porządków, z dodatkowymi warunkami (lub rezygnacją z niektórych); do tego zagadnienia jeszcze wrócimy. Warto jednak już w tym momencie zaznaczyć, że ta tematyka stanowi istotny fragment ważnego działu matematyki.

Ktoś mógłby stwierdzić: a po co nam to? Przecież takie porządkowanie wydaje się rzeczą tak absolutnie oczywistą, że chyba nie ma sensu się tym zajmować!
Otóż jest inaczej. Najpierw zauważmy, że porządki w sposób niezwykle istotny odgrywają rolę w życiu codziennym, choć może na pierwszy rzut oka tego nie widać. Pomyślmy jednak, jakie problemy mieliby listonosze, gdyby domy na ulicach nie były ponumerowane? Jak wypożyczyć książkę bez katalogu? Jak odnaleźć kasetę z nagraniem wśród tysiąca innych? Wyobraźmy sobie, jak długo musielibyśmy czekać w kolejce, by oddać głos w wyborach, gdyby spis wyborców nie był ułożony w logicznej kolejności. Zapewne frekwencja wyborcza nie przekroczyłaby jednego procenta. Przykłady można mnożyć.

Myliłby się ten, kto myślałby, że w każdym zbiorze można podać tylko jeden sensowny porządek. Rozważmy choćby zbiór uczniów jednej klasy w szkole, powiedzmy, wyłącznie męskiej. w dzienniku są oni umieszczeni, rzecz jasna, alfabetycznie i jest to kolejność logiczna. Ale podczas lekcji wychowania fizycznego (czyli, mówiąc po ludzku, gimnastyki) chłopcy nie będą się ustawiali w szeregu alfabetycznie, lecz według wzrostu i takie ustawienie wydaje się najbardziej sensowne. z kolei wojskowa komisja poborowa będzie ich wzywała według jeszcze innej reguły: począwszy od najstarszego (dokładnie po ukończeniu 18 lat). Można znaleźć jeszcze kilka kryteriów: od najlepszego ucznia (według średniej ocen szkolnych), według tego, jak chłopcy siedzą w klasie (począwszy od pierwszej ławki przy oknie).

Oczywiście, takie ustawienia spełniają nasze wyjściowe warunki. Dwóch uczniów nie będzie miało tego samego numeru w dzienniku, zawsze jeden z nich ma numer wyższy. z kolei jeśli Ciesielski jest przed Pogodą, a Pogoda przed Pośmiechowskim, to Ciesielski jest przed Pośmiechowskim. Podobnie przy innych uporządkowaniach.

Oznacza to, że w tym samym zbiorze często możemy stosować rozmaite porządki. Ogólnie jest ich bardzo wiele. Na przykład już w zbiorze pięcioelementowym aż sto dwadzieścia! Pierwszy element możemy wybrać na pięć sposobów, drugi na cztery... Bez trudu można znaleźć wzór ogólny na liczbę porządków w zbiorze n-elementowym. Nie o to jednak chodzi, by rozważanych porządków było jak najwięcej. Ważne jest, ażeby te, którymi się chcemy zajmować, były w jakiś sposób sensownie określone.

Jeżeli rozważamy rozmaite porządki w tym samym zbiorze, musimy je inaczej oznaczać - w przeciwnym razie zapanowałby niezły galimatias. Symbolem "<" oznaczamy standardową mniejszość; inne znaczki, których możemy używać, to na przykład:


w świetnie nam znanym nieskończonym zbiorze liczbowym, zbiorze liczb naturalnych N, mamy taki porządek, którego nawet nie zauważamy, tak się do niego przyzwyczailiśmy:
0 < 1 < 2 < ... (lub 1 < 2 < 3 < ..., jeśli zaczynamy od jedynki). Oczywiście, można wymyślać rozmaite inne ustawienia, ale wydawać by to się mogło zwyczajnym udziwnianiem. Po co to komu?
Porządkiem w zbiorze liczb naturalnych dodatnich będzie, w szczególności, ustawienie następujące:



Wytłumaczmy regułę, według której wypisaliśmy te liczby. Nietrudno ją zresztą odgadnąć. Najpierw wypisujemy w kolejności rosnącej wszystkie liczby nieparzyste; potem (ponownie w kolejności rosnącej) wszystkie możliwe iloczyny liczb nieparzystych i liczby 2, następnie wszystkie możliwe iloczyny liczb nieparzystych i liczby 4 i tak dalej. Wiadomo, że każda dodatnia liczba naturalna rozkłada się w sposób jednoznaczny na iloczyn liczb pierwszych. w przedstawionym porządku na początku są te, które nie mają w rozkładzie dwójki, potem te, które mają tylko jedną dwójkę... Wypisywanie możemy kontynuować. Jasne, że żadna liczba nie będzie użyta dwukrotnie. Chcemy jednak wypisać wszystkie liczby naturalne, została nam jedynka i potęgi dwójki. Te jednak wymieńmy w kolejności malejącej, to znaczy na końcu będzie jedynka, przed nią dwójka, przed dwójką czwórka... Uporządkowaliśmy w ten sposób wszystkie liczby całkowite dodatnie.