nlab Cantor' twierdzenie s
podsumowanie
Georg Cantor udowodnił wiele twierdzeń, ale to, które zwykle nazywa się twierdzeniem Cantora, jest pierwszym nietrywialnym twierdzeniem nowej teorii zbiorów Cantora: że niektóre nieskończoności są większe od innych; w szczególności, Dowolna nieskończona liczba kardynalna (lub nieskończony zbiór) generuje większą przez pobranie zbioru mocy.
(twierdzenie dotyczy wszystkich zbiorów, nie tylko nieskończonych, choć jest dość oczywiste dla zbiorów skończonych.)
twierdzenia Cantora nie należy mylić z twierdzeniem Cantora SchroederâBernsteina (patrz liczba kardynalna), które jest inne (ale pokrewne, ponieważ ważne jest uzasadnienie interpretacji cantora jego twierdzenia).
Historia
przed Cantorem ludzie mieli tendencję do myślenia o nieskończoności (niezależnie od tego, czy w nią wierzyli, czy nie) jako o pojęciu absolutnym: wszystkie nieskończoności są równoważne. Zauważono (np. przez Galileusza), że można dać nieskończonemu zbiorowi samowstrzykiwanie, które nie jest surjekcją; na przykład, włączenie parzystych liczb całkowitych do liczb całkowitych przez podwojenie. Tak więc oto dwie nieskończoności Ânieskończoność EE parzystych liczb całkowitych i Nieskończoność NN wszystkich liczb całkowitych, które są faktycznie równoważne, chociaż na pierwszy rzut oka wydaje się, że EE jest mniejsze.
Cantor pokazał, że taka równoważność zawodzi z liczbami rzeczywistymi RR: Żadna mapa z NN do RR nie może być surjektywna (tak, że RR jest niepoliczalna). Jego pierwszy argument był ad hoc, ale następnie uogólnił go argumentem diagonalnym, aby pokazać, że żadna mapa z dowolnego zbioru SS do jego zbioru mocy ð \ ‘ s \ mathcal{p}s nie może być surjektywna. (To objÄ ™ Ĺo niepoliczalnoĺ”Ä ‡ RR, poniewaĹź Cantor znalazĹ’ sprzecznoĺÄ ‡ pomiÄ ™ dzy RR i ð ð ‘n\mathcal{P}N, ktĂłrÄ … moĹźemy teraz uznaÄ ‡ za instancjÄ ™ Cantora “Schră¶derâ” twierdzenia Bernsteina.), Ponieważ istnieje ewidentna Mapa injektywna (Mapa Singletona) od SS do ð ð”s\mathcal{P}S, Cantor doszedł do wniosku, że cardinalność jednej jest ściśle mniejsza od cardinalności drugiej.
argument Cantora, podobnie jak cała jego teoria zbiorów, był wówczas kontrowersyjny. Ci, którzy, podobnie jak Kronecker, wierzyli, że cała matematyka powinna być matematyką skończoną, uważali ją za bezsensowną. Nawet bardziej umiarkowani wczesni konstruktywiści, tacy jak Brouwer i Weyl, uznali, że nie ma to większego sensu. (W szczególności, nie mówi nic bezpośrednio o RR, ponieważ bijatyka między RR i ð ð ” n \ mathcal{P}N nie jest konstruktywnie ważna, chociaż oryginalny dowód Cantora, że RR jest niezliczalny, może zadziałać.)
jednak wersje twierdzenia podane poniżej są konstruktywnie poprawne, a twierdzenie jest nawet predykatywnie poprawne (o ile ktoś ma zbiory funkcji); współcześni konstruktywiści generalnie akceptują je jako twierdzenia. (Interpretacja nie jest jednak tak jasna.) Są w rzeczywistości twierdzeniami w języku wewnętrznym dowolnego toposu (a twierdzenie jest twierdzeniem w dowolnym Î \ Pi-pretopos).
twierdzenia i dowody
twierdzenie
(Wersja Lawvere.)
biorąc pod uwagę zestawy SS i VV, Załóżmy, że istnieje surjection z SS do funkcji set sâ ‘ VS \to V (również napisane V SV^S). Wtedy każda mapa n: VâVN\colon V \to V ma stały punkt; to znaczy, n(x)=xn (x) = X dla niektórych x:Vx\colon V.
(to uogólnia do twierdzenia o punkcie stałym Lawvere ‘ a.)
Proof
niech f:Sâ ‘ (SâV)F\colon s \to (s \to V) będzie dowolną funkcją i rozważ funkcję G:SâVG\colon s \to v podaną przez
oznacza to, że jeśli ktoś używa currying do interpretacji ff jako funkcji z SÃSS \razy s do VV, to gg jest zdefiniowany za pomocą diagonalnej Mapy Î s\Delta_S jako
teraz Załóżmy, że ff jest surjective. Więc musi być jakiś element a:Sa\colon S takie, że f(A)=gf(A) = g. ale wtedy
więc G(A)G(A) jest stałym punktem nn.
obecność diagonalnej mapy s\Delta_S ” wyjaśnia, dlaczego dowód ten nazywa się argumentem diagonalnym. (Wyjaśnienie to jest anachroniczne jednak moralnie poprawne.) Dowód Lawvereâ € s wyjaśnia również (w rzeczywistości uogólnia) yyâ € ‘ lub kombinator o stałym punkcie w nieprzepisowym rachunku lambda, gdzie Y (n)Y (N) jest stałym punktem dla dowolnego terminu nn.
natychmiast wynika (nawet konstruktywnie), ze jeĹ ” li VV ma samo-mapowanie bez ustalonego punktu, to ĺźadna mapa z SS do sÂVS \do V nie moĹźe byÄ ‡ surjekcjä…. W rzeczywistości mamy coś nieco silniejszego niż (ale klasycznie równoważnego) niepowodzenie FF, aby być surjection: istnieje element gg sâ ‘ VS \to V, który nie jest równy żadnej wartości z zakresu ff. (Jeśli VV ma relację oddalenia, wtedy można uzyskać jeszcze silniejszy wynik dla odpowiednio silniejszej hipotezy na nn, ale to nie dotyczy poniższych wersji.)
twierdzenie
(Wersja Cantora.)
biorąc pod uwagę zbiór SS, nie ma surjekcji od SS do zbioru mocy.
dowód
niech VV będzie zbiorem wartości prawdy, a n: Vâ ‘ VN \ colon V \ to v będzie negacją. Ponieważ nn nie ma stałego punktu, zastosuj twierdzenie .
zauważ, że chociaż negacja nie ma wszystkich swoich typowych właściwości w matematyce konstruktywnej, p = Âpp = \neg{p} jest nadal niemożliwe.
następna wersja jest klasycznie równoważna z poprzednią wersją (przynajmniej jeśli sprawdzisz, że jest zamieszkana), ale nie jest konstruktywnie równoważna. (Rzeczywiście, w przeciwieństwie do twierdzenia, najwyraźniej nie ma konstruktywnego analogu, gdy ð ð ‘” s \ mathcal{P}S jest zastąpiony przez V SV^S.) ten argument pochodzi z propozycji 2.8.8 praktycznych podstaw Taylora (chociaż Nie wiem, czy naprawdę tam powstał).
(Wersja Taylora.)
biorąc pod uwagę zestaw SS, nie ma zastrzyku z ” S \ mathcal{P}S do SS.
dowód
niech i: ð ð ‘”Sâ’ Si\colon \ mathcal{P} S \to s będzie dowolną funkcją. Zdefiniuj f: sâð ð ‘ “SF\colon S \to \mathcal{p}s następująco:
jeśli ii jest iniekcją, to ff jest retrakcją ii, a więc surjekcją, co jest niemożliwe przez twierdzenie .
oczywiście Cantor również udowodnił twierdzenie, ale jego dowód nie był konstruktywny.
możemy połączyć twierdzenia i do następnego jeszcze bardziej ogólnego stwierdzenia, zaczerpniętego z D4.1.8 słonia Johnstone ‘ a.
(Wersja Johnstone ‘ a.)
biorąc pod uwagę zbiór SS, jego zbiór mocy nie może być wyrażony jako subkontynent SS.
dowód
Załóżmy, że mamy zestaw BB, zastrzyk i:Bââsi\colon B \hookrightarrow S I surjection f:Bâð ð”SF\colon B \to \mathcal{P}S. Następnie funkcja preimage i *:ð ð”sâð”bi^*\colon\mathcal{P}S \to \mathcal{P}B będzie surjection (ponieważ i *ƒƒ i=1 ð”bi^\AST \Exists_i = 1_{\mathcal{P}B}), podobnie jak funkcja obrazu ƒƒ f:ðƒ”Bâð ð”ð ð”s\exists_f\colon \mathcal{P}B \to \mathcal{P}\mathcal{P}S (ponieważ ƒƒ FF *=1 ðƒ”ð ‘” s\exists_f f^\ast = 1_{\mathcal{p}\mathcal{P}S}). Tak więc ich zespolenie byłoby surjekcją ð ‘”sâ †’ ð ð ‘”ð ð ‘” s \mathcal{P}S \ do \ mathcal{P} \ mathcal{p}s, co jest niemożliwe przez twierdzenie .
interpretacja
zauważ, że istnieje zastrzyk z SS do S\mathcal{P}S, podany przez mapę Singletona. Tak więc w arytmetyce liczb kardynalnych mamy
ale jak nie ma takiej surjekcji, to na pewno nie ma bijekcji i mamy
wnioskujemy więc, że
oznacza to, że każdy zestaw jest ściśle mniejszy niż jego zestaw mocy.
ta interpretacja opiera się na dobrym związku między â¤\leq i == na klasie liczb kardynalnych; w szczególności, cantorâSchroederâtwierdzenie Bernsteina, że â\leq jest antysymetryczny. W matematyce konstruktywnej tej zależności brakuje i jest całkiem możliwe, że dwa zbiory są ściśle mniejsze od siebie w powyższym znaczeniu. Dzięki twierdzeniu, nie jest to możliwe dla zbioru i jego zbioru mocy, ale to oznacza, że interpretacja < \lt jako względnej wielkości jest problematyczna Ârzeczywiście prawie tak problematyczne, jak idea, że istnieje mniej nawet liczb całkowitych niż liczb całkowitych!
Paul Taylor argumentował, że zasadniczą wartością twierdzenia Cantora jest lemat, ukryty w dowodzie Cantora, że Bill Lawvere wyodrębnił jako twierdzenie. Jako główna interpretacja twierdzenia ma znaczenie tylko w określonym kontekście zbioru teoretycznego (szczególnie, jeden, gdzie Cantor “Schroederâ €” Bernstein twierdzenie posiada), to nie może przetrwać Ârevolutionâ, który obala prymat tego kontekstu. Ale lemat Lawvere przetrwa, ponieważ  € robi pracęâ € podczas twierdzenia Cantora Âbierze kredytâ€. (Patrz Taylor 2009 poniżej do dalszej dyskusji â € Lemmy, które wykonują pracę i twierdzenia, które biorą kredytâ.)
w pozetach
twierdzenie analogiczne do twierdzenia Cantora dla zbiorów można sformułować dla innych kartezjańskich kategorii zamkniętych. W szczegĂłlnoĹ “ci moĹźna zapytać, czy pomiÄ ™ dzy posetami moĹźna mieÄ ‡ iloĹ” Ä ‡ xÂ2 XX \do 2^X, gdzie baza 22 nie jest posetem dyskretnym {0,1}\{0, 1\} ale raczej kolejność {0â¤1}\{0 \ leq 1\}.
odpowiedź jest taka, że nie ma takiej surjekcji f:x ‘ 2 Xf: X \do 2^X, ale nie wynika to z prostego zastosowania twierdzenia o punkcie stałym Lawvere ‘a, gdzie próbuje się wykluczyć takie ff, powołując się na istnienie mapy 2â’ 22 \do 2, która nie ma punktu stałego (nie ma takiej mapy poset 2Â22 \do 2!). Nie możemy też odwoływać się do jakiegoś prostego argumentu kardynalności; na przykład, jeśli XX jest porządkiem Ï\omega, to 2 X2^X jest porządkiem Š¥âŠÏ op\bot \sqcup \omega^{op} (swobodnie przylega do dolnego elementu ⊥\bot do Ï op\omega^{op}), który ma taką samą Kardynalność. Więc trzeba szukać innego dowodu.
udowodnienie, że nie ma surjekcji Xâ2 XX \do 2^X jest zabawnym ćwiczeniem. Jedną linię ataku (która internalizuje się do dowolnego toposu) można znaleźć tutaj.
- twierdzenie o punkcie stałym Lawvere ‘ a
