Aksjomat regularności - Axiom of regularity

W matematyce , aksjomat regularności (znany również jako pewnika fundacji ) jest aksjomatem aksjomaty zermelo-fraenkela który stanowi, że każdy niepusty zbiór zawiera element, który jest odłączony od A . W logice pierwszego rzędu aksjomat brzmi:

${\ Displaystyle \ forall x \ (x \ neq \ varnic \ rightarrow \ istnieje r (y \ w x \ \ ziemi y \ cap x = \ var nic)).}$

Aksjomat regularności wraz z aksjomatowi parowania oznacza, że nie jest elementem zestawu sama w sobie i nie nieskończonym sekwencja ( _n ), tak że _{i + 1} jest elementem o _I dla wszystkich I . Za pomocą aksjomatu zależnego wyboru (który jest osłabioną formą aksjomatu wyboru ) można ten wynik odwrócić: jeśli nie ma takich nieskończonych ciągów, to aksjomat regularności jest prawdziwy. Stąd w tym kontekście aksjomat regularności jest równoważny zdaniu, że nie ma nieskończonych w dół łańcuchów przynależności.

Aksjomat został wprowadzony przez von Neumanna (1925) ; przyjęto ją w sformułowaniu bliższym temu, jakie można znaleźć we współczesnych podręcznikach Zermelo (1930) . Praktycznie wszystkie wyniki w działach matematyki opartych na teorii mnogości utrzymują się nawet przy braku regularności; patrz rozdział 3 Kunen (1980) . Jednak regularność sprawia, że ​​niektóre właściwości liczb porządkowych są łatwiejsze do udowodnienia; i nie tylko umożliwia indukcję na dobrze uporządkowanych zbiorach, ale także na odpowiednich klasach, które są dobrze ugruntowanymi strukturami relacyjnymi, takimi jak uporządkowanie leksykograficzne na${\ Displaystyle \ {(n \ alfa ) \ mid n \ w \ omega \ land \ alfa {\ tekst {jest liczbą porządkową}} \} \,.}$

Biorąc pod uwagę inne aksjomaty teorii mnogości Zermelo-Fraenkla, aksjomat regularności jest równoważny aksjomatowi indukcji . Aksjomat indukcji jest zwykle używany zamiast aksjomatu regularności w teoriach intuicjonistycznych (takich, które nie akceptują prawa wyłączonego środka ), gdzie te dwa aksjomaty nie są równoważne.

Oprócz pominięcia aksjomatu regularności, niestandardowe teorie zbiorów rzeczywiście postulowały istnienie zbiorów, które są same w sobie elementami.

Elementarne implikacje prawidłowości

Żaden zestaw nie jest elementem samym w sobie

Niech A będzie zbiorem i zastosujmy aksjomat regularności do { A } , który jest zbiorem przez aksjomat parowania . Widzimy, że musi istnieć element { A }, który jest rozłączny od { A }. Ponieważ jedynym elementem { A } jest A , musi być tak, że A jest rozłączne od { A }. Zatem skoro , nie możemy mieć A ∈ A (z definicji rozłącznego ). ${\ Displaystyle A \ czapka \ {A \} = \ varnothing}$

Nie istnieje nieskończona malejąco sekwencja zbiorów

Załóżmy, że jest inaczej, to nie jest to funkcja , F , na liczb naturalnych z F ( n + 1) elementu f ( n ) dla każdego n . Zdefiniuj S = { f ( n ): n liczbę naturalną} , zakres f , który może być zbiorem ze schematu aksjomatu zastępowania . Stosując aksjomat regularności do S , niech B będzie elementem S rozłącznym od S . Z definicji S , B musi być f ( k ) dla pewnej liczby naturalnej k . Jednak mamy dane, że f ( k ) zawiera f ( k +1 ), które jest również elementem S . Tak F ( k + 1) jest w przecięciu z F ( k ) i S . Przeczy to faktowi, że są to zbiory rozłączne. Ponieważ nasze przypuszczenie prowadziło do sprzeczności, nie może istnieć taka funkcja, f .

Nieistnienie zbioru zawierającego sam siebie można postrzegać jako szczególny przypadek, w którym ciąg jest nieskończony i stały.

Zauważ, że ten argument dotyczy tylko funkcji f, które mogą być reprezentowane jako zestawy, w przeciwieństwie do klas niedefiniowalnych. W dziedzicznie skończonych zestawów , V _ω , spełnia aksjomat regularności (i wszystkie inne aksjomaty ZFC z wyjątkiem aksjomat nieskończoności ). Więc jeśli utworzymy nietrywialną ultramoc V _ω , to również spełni aksjomat regularności. Otrzymany model będzie zawierał elementy zwane niestandardowymi liczbami naturalnymi, które spełniają definicję liczb naturalnych w tym modelu, ale nie są tak naprawdę liczbami naturalnymi. Są to fałszywe liczby naturalne, które są „większe” niż jakakolwiek rzeczywista liczba naturalna. Ten model będzie zawierał nieskończone malejące sekwencje elementów. Załóżmy na przykład, że n jest niestandardową liczbą naturalną, wtedy i i tak dalej. Dla dowolnej rzeczywistej liczby naturalnej k , . To niekończąca się sekwencja elementów. Ale ta sekwencja nie jest definiowalna w modelu, a zatem nie jest zbiorem. Tak więc nie można udowodnić żadnej sprzeczności z regularnością. ${\displaystyle (n-1)\wn}$${\displaystyle (n-2)\w (n-1)}$${\ Displaystyle (nk-1) \ w (nk)}$

Prostsza teoretyczna definicja mnogości uporządkowanej pary

Aksjomat regularności umożliwia zdefiniowanie pary uporządkowanej ( a , b ) jako { a ,{ a , b }}; patrz zamówiona para, aby uzyskać szczegółowe informacje. Ta definicja eliminuje jedną parę nawiasów klamrowych z kanonicznej definicji Kuratowskiego ( a , b ) = {{ a },{ a , b }}.

Każdy zestaw ma rangę porządkową

Była to właściwie pierwotna forma aksjomatu w aksjomatyzacji von Neumanna.

Załóżmy, że x jest dowolnym zbiorem. Niech t będzie domknięciem przechodnim { x }. Niech u będzie podzbiorem t składającym się ze zbiorów nierankingowych. Jeśli u jest puste, to x jest uszeregowane i gotowe. W przeciwnym razie zastosuj aksjomat regularności do u, aby uzyskać element w z u, który jest rozłączny od u . Ponieważ w jest w u , w jest nierankingowe. w jest podzbiorem t zgodnie z definicją domknięcia przechodniego. Ponieważ w jest rozłączne od u , każdy element w jest uszeregowany. Stosując aksjomaty zastąpienia i sumy do połączenia rzędów elementów w , otrzymujemy rząd porządkowy dla w , czyli wit . To przeczy wnioskowi, że w jest nierankingowe. Zatem założenie, że u nie było puste, musi być fałszywe, a x musi mieć rangę. ${\ Displaystyle \ textstyle \ operatorname {ranga} (w) = \ puchar \ {\ operatorname {ranga} (z) + 1 \ średni z \ w w \}}$

Na każde dwa zestawy tylko jeden może być elementem drugiego

Niech X i Y będą zbiorami. Następnie zastosuj aksjomat regularności do zbioru { X , Y } (który istnieje przez aksjomat parowania). Widzimy, że musi istnieć element { X , Y } , który również jest od niego rozłączny. Musi to być X lub Y . Zgodnie z definicją rozłączności musimy więc albo Y nie jest elementem X, albo odwrotnie.

Aksjomat zależnego wyboru i braku nieskończonej malejącej sekwencji zbiorów implikuje regularność

Niech zbiór niepusty S będzie kontrprzykładem dla aksjomatu regularności; to znaczy, że każdy element S ma niepuste przecięcie z S . Definiujemy binarną relację R na S przez , która z założenia jest pełna. W ten sposób, aksjomatowi wybór zależny istnieje kilka sekwencji ( _n ) w S spełniających w _n Ra _{n + 1} dla wszystkich n w N . Ponieważ jest to nieskończony łańcuch zstępujący, dochodzimy do sprzeczności, a więc takie S nie istnieje. ${\ Displaystyle aRb: \ Leftrightarrow b \ w S \ cap a}$

Regularność i reszta aksjomatów ZF(C)

Skolem (1923) i von Neumann (1929) wykazali, że regularność jest stosunkowo zgodna z resztą ZF , co oznacza, że ​​jeśli ZF bez regularności jest niesprzeczny, to ZF (z regularnością) jest również niesprzeczny. Jego dowód we współczesnej notacji można znaleźć na przykład w Vaught (2001 , §10.1).

Wykazano również, że aksjomat regularności jest niezależny od innych aksjomatów ZF(C), zakładając, że są one niesprzeczne. Wynik został ogłoszony przez Paula Bernaysa w 1941 r., chociaż nie opublikował on dowodu aż do 1954 r. Dowód obejmuje (i doprowadził do badania) modeli permutacyjnych (lub metody) Rieger-Bernays , które zostały wykorzystane do innych dowodów niezależności dla systemy nieuzasadnione ( Rathjen 2004 , s. 193 oraz Forster 2003 , s. 210–212).

Regularność i paradoks Russella

Naiwna teoria mnogości (schemat aksjomatu nieograniczonego rozumienia i aksjomat ekstensjonalizmu ) jest niespójna z powodu paradoksu Russella . We wczesnych formalizacjach zbiorów matematycy i logicy uniknęli tej sprzeczności, zastępując schemat aksjomatu rozumienia znacznie słabszym schematem aksjomatu separacji . Jednak sam ten krok prowadzi do teorii zbiorów, które są uważane za zbyt słabe. Tak więc część mocy rozumienia została przywrócona przez inne aksjomaty istnienia teorii mnogości ZF (parowanie, suma, powerset, zastępowanie i nieskończoność), które można uznać za szczególne przypadki rozumienia. Jak dotąd te aksjomaty nie wydają się prowadzić do żadnej sprzeczności. Następnie dodano aksjomat wyboru i aksjomat regularności, aby wykluczyć modele z pewnymi niepożądanymi właściwościami. Wiadomo, że te dwa aksjomaty są stosunkowo spójne.

Wobec aksjomatu separacji paradoks Russella staje się dowodem na to, że nie istnieje zbiór wszystkich zbiorów . Aksjomat regularności wraz z aksjomatem parowania również zabraniają takiego uniwersalnego zbioru. Jednak paradoks Russella dostarcza dowodu, że nie istnieje „zbiór wszystkich zbiorów” wykorzystujący sam aksjomat separacji, bez żadnych dodatkowych aksjomatów. W szczególności ZF bez aksjomatu prawidłowości już zakazuje takiego uniwersalnego zbioru.

Jeśli teoria zostanie rozszerzona przez dodanie aksjomatu lub aksjomatów, to wszelkie (prawdopodobnie niepożądane) konsekwencje pierwotnej teorii pozostają konsekwencjami rozszerzonej teorii. W szczególności, jeśli ZF bez regularności zostanie rozszerzona przez dodanie regularności, aby uzyskać ZF, to każda sprzeczność (taka jak paradoks Russella), która wynikała z oryginalnej teorii, nadal występowałaby w rozszerzonej teorii.

Istnienie atomów Quine'a (zbiorów spełniających równanie x  = { x } , tj. samych siebie jako swoich jedynych elementów) jest zgodne z teorią uzyskaną przez usunięcie aksjomatu regularności z ZFC. Różne nieuzasadnione teorie mnogości pozwalają na „bezpieczne” zbiory kołowe, takie jak atomy Quine’a, bez stania się niespójnymi za pomocą paradoksu Russella.

Regularność, skumulowana hierarchia i typy

W ZF można udowodnić, że klasa , zwana wszechświatem von Neumanna , jest równa klasie wszystkich zbiorów. To stwierdzenie jest nawet równoważne aksjomatowi regularności (jeśli pracujemy w ZF z pominięciem tego aksjomatu). Z dowolnego modelu, który nie spełnia aksjomatu prawidłowości, model, który go spełnia, można zbudować, biorąc tylko zbiory w . ${\ Displaystyle \ bigcup _ {\ alfa} V_ {\ alfa}}$${\ Displaystyle \ bigcup _ {\ alfa} V_ {\ alfa}}$

Herbert Enderton  ( 1977 , s. 206) napisał, że „idea rangi jest potomkiem koncepcji typu Russella ”. Porównując ZF z teorią typów , Alasdair Urquhart napisał, że „system Zermelo ma tę notacyjną zaletę, że nie zawiera żadnych jawnie wpisanych zmiennych, chociaż w rzeczywistości może być postrzegany jako mający wbudowaną niejawną strukturę typu, przynajmniej jeśli aksjomat regularności jest Szczegóły tego niejawnego typowania są opisane w [Zermelo 1930] i ponownie w dobrze znanym artykule George'a Boolosa [Boolos 1971] .

Dana Scott  ( 1974 ) poszła dalej i stwierdziła, że:

Prawda jest taka, że ​​istnieje tylko jeden zadowalający sposób uniknięcia paradoksów: mianowicie użycie jakiejś formy teorii typów . To było podstawą intuicji zarówno Russella, jak i Zermelo. Rzeczywiście, najlepszym sposobem postrzegania teorii Zermelo jest uproszczenie i rozszerzenie teorii Russella. (Oczywiście mamy na myśli prostą teorię typów Russella .) Uproszczenie polegało na tym, aby typy były kumulacyjne . W ten sposób mieszanie typów jest łatwiejsze i unika się denerwujących powtórzeń. Kiedy pozwoli się późniejszym typom na akumulację wcześniejszych, możemy łatwo wyobrazić sobie rozszerzenie typów na pozaskończone — tylko to, jak daleko chcemy się posunąć, musi koniecznie pozostać otwarte. Teraz Russell wyraźnie określił swoje typy w swojej notacji, a Zermelo pozostawił je ukryte . [podkreślenie w oryginale]

W tym samym artykule Scott pokazuje, że system aksjomatyczny oparty na immanentnych właściwościach hierarchii kumulatywnej okazuje się równoważny ZF, w tym regularności.

Historia

Pojęcie zasadności i rangi zbioru wprowadził Dmitrij Mirimanoff ( 1917 ) zob. Lévy (2002 , s. 68) i Halletta (1996 , §4.4, zwłaszcza s. 186, 188). Mirimanoff nazwał zbiór x „regularnym” (po francusku „ordinaire”), jeśli każdy malejący łańcuch x ∋ x ₁ ∋ x ₂ ∋ ... jest skończony. Mirimanoff jednak nie uważał swojego pojęcia regularności (i zasadności) za aksjomat, którego muszą przestrzegać wszystkie zbiory; w późniejszych pracach Mirimanoff badał również to, co obecnie nazywa się zbiorami nieuzasadnionymi ("nadzwyczajne" w terminologii Mirimanoffa).

Skolem (1923) i von Neumann (1925) wskazali, że nieuzasadnione zbiory są zbędne (na s. 404 w przekładzie van Heijenoorta ) i w tej samej publikacji von Neumann podaje aksjomat (s. 412 w przekładzie), który wyklucza niektóre, ale nie wszystkie, nieuzasadnione zestawy. W kolejnej publikacji von Neumann (1928) podał następujący aksjomat (oddany we współczesnej notacji przez A. Riegera):

${\ Displaystyle \ forall x \ (x \ neq \ pusty zestaw \ rightarrow \ istnieje r \ w x \, (y \ cap x = \ pusty zestaw))}$.

Regularność w obecności urelementów

Urelementy to obiekty, które nie są zestawami, ale które mogą być elementami zestawów. W teorii mnogości ZF nie ma urelementów, ale w niektórych innych teoriach mnogości, takich jak ZFA , są. W tych teoriach aksjomat regularności musi zostać zmodyfikowany. Wyrażenie „ ” należy zastąpić instrukcją, która nie jest pusta i nie jest urelementem. Jeden odpowiedni zamiennik to , który stwierdza, że x jest zamieszkane . ${\displaystyle x\neq \pusty zestaw}$${\displaystyle x}$${\displaystyle (\istnieje y)[y\inx]}$

Zobacz też

• Nieuzasadniona teoria mnogości
• Sztuczka Scotta
• Indukcja Epsilon

Bibliografia

Źródła

• Bernays, Paul Isaac (1941), "System aksjomatycznej teorii mnogości. Część II", The Journal of Symbolic Logic , 6 (1): 1-17, doi : 10.2307/2267281 , JSTOR  2267281
• Bernays, Paul Isaac (1954), „System aksjomatycznej teorii mnogości. Część VII” (PDF) , The Journal of Symbolic Logic , 19 (2): 81-96, doi : 10.2307/2268864 , JSTOR  2268864
• Boolos, George (1971), " Iterative koncepcja zbioru", Journal of Philosophy , 68 (8): 215-231, doi : 10.2307/2025204 , JSTOR  2025204przedruk w Boolos, George (1998), Logic, Logic and Logic , Harvard University Press, s. 13-29
• Enderton, Herbert B. (1977), Elementy teorii mnogości , Prasa akademicka
• Forster, T. (2003), Logika, indukcja i zbiory , Cambridge University Press
• Halbeisen, Lorenz J. (2012), Kombinatoryczna teoria mnogości: z delikatnym wprowadzeniem do forsowania , Springer
• Hallett, Michael (1996) [pierwsze wydanie 1984], teoria mnogości kantorów i ograniczenie rozmiaru , Oxford University Press, ISBN 978-0-19-853283-5
• Jech, Thomas (2003), Teoria mnogości: wydanie trzecie tysiąclecie, poprawione i rozszerzone , Springer, ISBN 978-3-540-44085-7
• Kunen, Kenneth (1980), Teoria mnogości: wprowadzenie do dowodów niezależności , Elsevier, ISBN 978-0-444-86839-8
• Lévy, Azriel (2002) [opublikowane po raz pierwszy w 1979], Podstawowa teoria mnogości , Mineola, New York: Dover Publications, ISBN 978-0-486-42079-0
• Mirimanoff, D. (1917), „Les antinomies de Russell et de Burali-Forti et le probleme podstawowa teoria zespołów”, L'Enseignement Mathématique , 19 : 37-52
• Rathjen, M. (2004), " Przewidywanie, cykliczność i anty-fundacja" (PDF) , w Link, Godehard (red.), Sto lat paradoksu Russella: matematyka, logika, filozofia , Walter de Gruyter, ISBN 978-3-11-019968-0
• Rieger, Adam (2011), „Paradoks, ZF i aksjomat fundacji” (PDF) , w DeVidi, David; Halletta, Michaela; Clark, Peter (red.), Logika, Matematyka, Filozofia, Entuzjazmy Vintage. Eseje na cześć Johna L. Bella. , The Western Ontario Series in Philosophy of Science , 75 , str. 171-187 , CiteSeerX  10.1.1.100.9052 , doi : 10.1007/978-94-007-0214-1_9 , ISBN 978-94-007-0213-4
• Riegger, L. (1957), „Wkład do aksjomatycznej teorii mnogości Gödla” (PDF) , Czechosłowacki Mathematical Journal , 7 (3): 323-357, doi : 10.21136/CMJ.1957.100254
• Sangiorgi, Davide (2011), „Początki bisymulacji i koindukcji”, w Sangiorgi, Davide; Rutten, Jan (red.), Advanced Topics in Bisimulation and Coinduction , Cambridge University Press
• Scott, Dana Stewart (1974), "Aksjomatyzująca teoria mnogości", Aksjomatyczna teoria mnogości. Proceedings of Symposia in Pure Mathematics, tom 13, część II , s. 207–214
• Skolem, Thoralf (1923), Aksjomatyzowana teoria mnogościPrzedruk w From Frege to Gödel , van Heijenoort, 1967, przekład angielski Stefan Bauer-Mengelberg, s. 291-301.
• Urquhart, Alasdair (2003), "Teoria typów", w Griffin, Nicholas (red.), The Cambridge Companion to Bertrand Russell , Cambridge University Press
• Vaught, Robert L. (2001), Teoria mnogości: wprowadzenie (2nd ed.), Springer, ISBN 978-0-8176-4256-3
• von Neumann, John (1925), „Eine axiomatiserung der Mengenlehre”, Journal für die Reine und Angewandte Mathematik , 154 : 219-240; przekład van Heijenoort, Jean (1967), From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 , s. 393-413
• von Neumann, John (1928), „Über die Definition durch transfinite Induktion und verwandte Fragen der allgemeinen Mengenlehre”, Mathematische Annalen , 99 : 373-391, doi : 10.1007/BF01459102 , S2CID  120784562
• von Neumann, John (1929), "Uber eine Widerspruchfreiheitsfrage in der axiomatischen Mengenlehre", Journal für die Reine und Angewandte Mathematik , 1929 (160): 227-241, doi : 10.1515/crll.1929.160.227 , S2CID  199545822
• Zermelo, Ernst (1930), „Über Grenzzahlen und Mengenbereiche. Neue Untersuchungen über die Grundlagen der Mengenlehre”. (PDF) , Fundamenta Mathematicae , 16 : 29-47, doi : 10.4064/fm-16-1-29-47; przekład w Ewald, WB, wyd. (1996), Od Kanta do Hilberta: książka źródłowa w podstawach matematyki t. 2 , Clarendon Press, s. 1219–33

Linki zewnętrzne

• Aksjomat założenia w PlanetMath .
• Zbiór zamieszkały i aksjomat założenia na nLab