Zasada dobrego uporządkowania

Zasada dobrego uporządkowania – reguła matematyczna mówiąca, że każdy niepusty podzbiór zbioru liczb naturalnych zawiera element najmniejszy.

Wyrażenie „zasada dobrego uporządkowania” traktowana jest czasami jako synonim wyrażenia „twierdzenie o dobrym uporządkowaniu”. Niekiedy rozumie się przez nie stwierdzenie, iż zbiór liczb całkowitych zawiera podzbiór dobrze uporządkowany, nazywany liczbami naturalnymi, w którym każdy niepusty podzbiór zawiera element najmniejszy.

W zależności od sposobu wprowadzenia liczb naturalnych wspomniana własność (drugiego rzędu) liczb naturalnych jest albo aksjomatem albo twierdzeniem, którego można dowieść. Przykładowo:

• W arytmetyce Peano, arytmetyce drugiego rzędu i podobnych systemach oraz w większości (niekoniecznie formalnych) podejść matematycznych do zasady dobrego uporządkowania jest ona konsekwencją zasady indukcji matematycznej, która z kolei przyjęta jest jako pojęcie pierwotne.
• Traktując liczby naturalne jako podzbiór liczb rzeczywistych i przyjmując, że wiadomo, iż są one zupełne (jako przestrzeń; raz jeszcze na podstawie aksjomatu lub twierdzenia), tzn. każdy zbiór ograniczony z dołu ma kres dolny, można dowieść, że każdy zbiór $A$ liczb naturalnych ma kres dolny, dalej oznaczany $a^*.$ Wystarczy teraz znaleźć taką liczbę całkowitą $n^*,$ dla której $a^*$ leży w przedziale $(n^* - 1, n^*],$ a następnie pokazać, że musi zachodzić $a^* = n^*,$ przy czym $n^* \in A.$
• W aksjomatycznej teorii mnogości liczby naturalne definiowane są jako najmniejszy zbiór induktywny (tzn. zbiór zawierający 0 i zamknięty ze względu na operację następnika). Można pokazać (nawet bez odwoływania się do aksjomatu regularności), że zbiór wszystkich liczb naturalnych o własności „$\scriptstyle \{0, \dots, n\}$ jest dobrze uporządkowany” jest induktywny i dlatego musi zawierać wszystkie liczby naturalne; z własności tej można wydedukować, że zbiór wszystkich liczb naturalnych również jest dobrze uporządkowany.

Przytoczone wyżej wyrażenie wykorzystuje się też czasem w celu uzasadnienia dowodów następującej postaci: aby dowieść, że każda liczba naturalna należy do określonego zbioru $S$ załóżmy przeciwnie i wywnioskujmy dzięki temu istnienie (niezerowego) najmniejszego kontrprzykładu. W dalszej kolejności wystarczy pokazać, że musi istnieć również mniejszy kontrprzykład albo, że najmniejszy kontrprzykład nim nie jest, co w obu przypadkach daje sprzeczność. Ten rodzaj argumentacji ma ten sam związek z dowodem przez indukcję matematyczną, co „jeśli nie B, to nie A” (reguła modus tollens) w stosunku do „jeśli A, to B” (reguła modus ponens). Metoda ta jest podobna do „metody nieskończonego schodzenia” Fermata.

Garrett Birkhoff i Saunders Mac Lane dowiedli w A Survey of Modern Algebra, że własność ta, podobnie jak aksjomat ciągłości liczb rzeczywistych, jest niealgebraiczna, tzn. nie może być wyprowadzona z własności algebraicznych liczb całkowitych (tworzących uporządkowaną dziedzinę całkowitości). W ten sposób wyróżnia ona liczby całkowite wśród pozostałych dziedzin całkowitości; każda dobrze uporządkowana dziedzina całkowitości jest izomorficzna z liczbami całkowitymi.