Zasada dobrego uporządkowania

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

Wyrażenie „zasada dobrego uporządkowania” traktowane 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óre można dowieść. Przykładowo:

  • W arytmetyce Peana, 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 liczb naturalnych ma kres dolny, dalej oznaczany Wystarczy teraz znaleźć taką liczbę całkowitą dla której leży w przedziale a następnie wykazać, że musi zachodzić przy czym
  • 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 „ 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 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 schodzeniaFermata.

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.

Przypisy

  1. Tom Apostol: Introduction to Analytic Number Theory. Nowy Jork: Springer-Verlag, 1976, s. 13. ISBN 0-387-90163-9.