Twierdzenie o dobrym porządku - Well-ordering theorem

„Twierdzenie Zermelo” przekierowuje tutaj. Aby zapoznać się z twierdzeniem Zermelo w teorii gier, zobacz twierdzenie Zermelo (teoria gier) .
Nie mylić z zasadą dobrego zamawiania .

W matematyce twierdzenie o dobrym porządku , znane również jako twierdzenie Zermelo , stwierdza, że ​​każdy zbiór może być uporządkowany . Zbiór X jest uporządkowany według ścisłego porządku całkowitego, jeśli każdy niepusty podzbiór X ma przynajmniej element pod porządkiem. Twierdzenie o dobrym porządku wraz z lematem Zorna są najważniejszymi twierdzeniami matematycznymi, które są równoważne aksjomatowi wyboru (często nazywanemu AC, patrz także Aksjomat wyboru § Równoważniki ). Ernst Zermelo wprowadził aksjomat wyboru jako „niepodważalną zasadę logiczną”, aby udowodnić twierdzenie o dobrym porządku. Z twierdzenia o dobrym porządku można wywnioskować, że każdy zbiór jest podatny na indukcję pozaskończoną , która jest uważana przez matematyków za potężną technikę. Jedną ze znanych konsekwencji twierdzenia jest paradoks Banacha–Tarskiego .

Historia

Georg Cantor uważał twierdzenie o dobrym porządku za „podstawową zasadę myślenia”. Uważa się jednak, że wizualizacja prawidłowego uporządkowania ; taka wizualizacja musiałaby zawierać aksjomat wyboru. W 1904 Gyula Kőnig twierdził, że udowodnił, że takie uporządkowanie nie może istnieć. Kilka tygodni później Felix Hausdorff znalazł błąd w dowodzie. Okazało się jednak, że twierdzenie o dobrym porządku jest równoważne aksjomatowi wyboru, w tym sensie, że jeden razem z aksjomatami Zermelo-Fraenkla wystarcza do udowodnienia drugiego, w logice pierwszego rzędu (to samo dotyczy twierdzenia Zorna). Lemat ). Jednak w logice drugiego rzędu twierdzenie o dobrym porządku jest ściślej silniejsze niż aksjomat wyboru: z twierdzenia o dobrym porządku można wydedukować aksjomat wyboru, ale z aksjomatu wyboru nie można wyprowadzić twierdzenia o dobrym porządku.

Jest znany żart dotyczący tych trzech stwierdzeń i ich względnej podatności na intuicję:

Aksjomat wyboru jest oczywiście prawdziwy, zasada dobrego uporządkowania oczywiście fałszywa, a kto może powiedzieć o lemie Zorna ?

Dowód AC

Aksjomat wyboru można udowodnić na podstawie twierdzenia o dobrym porządku w następujący sposób.

Aby utworzyć funkcję wyboru dla zbioru niepustych zbiorów E , weź sumę zbiorów w E i nazwij ją X . Istnieje dobre uporządkowanie X ; niech R będzie takim porządkiem. Funkcja, która każdemu zbiorowi S z E kojarzy najmniejszy element z S , uporządkowany przez (ograniczenie do S z) R , jest funkcją wyboru dla zbioru E .

Istotnym punktem tego dowodu jest to, że obejmuje on tylko jeden arbitralny wybór, wybór R ; zastosowanie twierdzenia o dobrym uporządkowaniu do każdego elementu S z E z osobna nie zadziałałoby, ponieważ twierdzenie to potwierdza jedynie istnienie dobrego uporządkowania, a wybór dla każdego elementu S nie byłby łatwiejszy niż wybranie elementu.

Uwagi

  1. ^ Kuczma, Marek (2009). Wprowadzenie do teorii równań i nierówności funkcyjnych . Berlin: Springer. P. 14. Numer ISBN 978-3-7643-8748-8.
  2. ^ Hazewinkel, Michiel (2001). Encyklopedia Matematyki: Suplement . Berlin: Springer. P. 458. ISBN 1-4020-0198-3.
  3. ^ B Thierry Vialar (1945). Podręcznik matematyki . Norderstedt: Springer. P. 23. Numer ISBN 978-2-95-519901-5.
  4. ^ Georg Cantor (1883), "Ueber unendliche, lineare Punktmannichfaltigkeiten", Mathematische Annalen 21, s. 545-591.
  5. ^ Sheppard, Barnaby (2014). Logika nieskończoności . Wydawnictwo Uniwersytetu Cambridge. P. 174. Numer ISBN 978-1-1070-5831-6.
  6. ^ Plotkin, JM (2005), "Wprowadzenie do "Pojęcie władzy w teorii mnogości " " Hausdorffa na zbiorów uporządkowanych , historii matematyki, 25 American Mathematical Society, s. 23-30, ISBN 9780821890516
  7. ^ Shapiro, Stewart (1991). Fundamenty bez fundamentalizmu: przypadek logiki drugiego rzędu . Nowy Jork: Oxford University Press. Numer ISBN 0-19-853391-8.
  8. ^ Krantz, Steven G. (2002), "Aksjomat wyboru", w Krantz, Steven G. (red.), Handbook of Logic and Proof Techniques for Computer Science , Birkhäuser Boston, s. 121-126, doi : 10.1007 /978-1-4612-0115-1_9 , ISBN 9781461201151

Linki zewnętrzne