nlab Cantor'teorema s
rezumat
Georg Cantor a dovedit multe teoreme, dar cea numită de obicei teorema lui Cantor este prima teoremă nontrivială a noii teorii a mulțimilor lui Cantor: că unele infinități sunt mai mari decât altele; în special, orice număr cardinal infinit (sau mulțime infinită) generează unul mai mare luând mulțimea de putere.
(teorema se aplică tuturor mulțimilor, nu doar celor infinite, deși este destul de evidentă pentru mulțimile finite.)
teorema lui Cantor nu trebuie confundată cu Teorema Bernstein a cantoruluiSchroeder(a se vedea numărul cardinal), care este diferită (dar înrudită, deoarece este important să se justifice interpretarea lui Cantor a teoremei sale).
Istorie
înainte de Cantor, oamenii tindeau să se gândească la infinit (indiferent dacă credeau sau nu în el) ca la un concept absolut: toate infinitățile sunt echivalente. S-a observat (de exemplu, de către Galileo) că este posibil să se dea unui set infinit o autoinjecție care nu este o surjecție; de exemplu, includerea numerelor întregi pare în numere întregi prin dublare. Astfel, aici sunt două infinitățiinfinitul ee al numerelor întregi pare și infinitul NN al tuturor numerelor întregi ” care sunt de fapt echivalente, chiar dacă la prima vedere s-ar părea că Ee este mai mic.
Cantor a arătat că o astfel de echivalență eșuează cu numerele reale RR: nicio hartă de la NN la RR nu poate fi surjectivă (astfel încât RR este nenumărabilă). Primul său argument a fost ad hoc, dar apoi a generalizat acest lucru cu argumentul diagonal pentru a arăta că nicio hartă de la niciun set SS la setul său de putere”s\mathcal{p}s ar putea fi surjectivă. (Acest lucru a acoperit uncountability RR, deoarece Cantor a găsit o bijecție între RR și”n\mathcal{p} n”, pe care o putem considera acum ca un exemplu al cantorului ” Schr.) Deoarece există o hartă injectivă evidentă (harta singleton) de la SS la”S\mathcal{p}s, Cantor a concluzionat că cardinalitatea unuia este strict mai mică decât cardinalitatea celuilalt.
argumentul lui Cantor, ca și întreaga sa teorie a mulțimilor, a fost controversat la acea vreme. Cei care, la fel ca Kronecker, au crezut că toată matematica ar trebui să fie matematică finită, au considerat-o lipsită de sens. Chiar și constructiviștii timpurii mai moderați, cum ar fi Brouwer și Weyl, au descoperit că nu are prea mult rost. (În special, nu spune nimic direct despre RR, din moment ce bijecția dintre RR și XV”n\mathcal{p}n nu este validă din punct de vedere constructiv, deși dovada originală a lui Cantor că RR este nenumărabilă poate fi făcută să funcționeze.)
cu toate acestea, versiunile teoremei menționate mai jos sunt valide din punct de vedere constructiv, iar Teorema este chiar validă din punct de vedere predicativ (atâta timp cât cineva are seturi de funcții); constructiviștii moderni le acceptă în general ca teoreme. (Cu toate acestea, interpretarea nu este atât de clară.) Sunt, de fapt, teoreme în limbajul intern al oricărui topos (și teorema este o teoremă în orice XV \Pi-pretopos).
enunțuri și dovezi
Teorema
(versiunea lui Lawvere.)
dat seturi SS și VV, să presupunem că există o surjecție de la SS la setul de funcții s Inktivvs \La V (de asemenea scris v SV^s). Apoi, fiecare hartă N: V Xqqvn\colon V \la V are un punct fix; adică n(x) = xn (x) = x pentru unii x:Vx\colon V.
(aceasta se generalizează la teorema punctului fix al lui Lawvere.)
dovada
fie f:S(S)) F\colon S \la (S \la v) fie orice funcție, și ia în considerare funcția G:S(S)) G: S(2771>
Care este, dacă se folosește curtau pentru a interpreta ff ca o funcție de SECURITATESS \ori S VV, atunci gg este definită folosind diagonala hartă Î S\Delta_S ca
acum să presupunem că ff este surjectiv. Atunci trebuie să existe un element a:Sa\colon S astfel încât f(a) = gf(a)=g. dar apoi
deci g(A) g(a) este un punct fix al nn.
prezența hărții diagonale s\Delta_S aici explică de ce această dovadă se numește argumentul diagonal. (Această explicație este anacronică, dar corectă din punct de vedere moral.Dovada lawvereixt s explică, de asemenea (de fapt, generalizează) YY combinatorul de puncte fixe sau fixe în calculul lambda netipat, unde Y(N)Y(N) este un punct fix pentru orice termen NN.
rezultă imediat (chiar și constructiv) că dacă VV are o auto-cartografiere fără punct fix, atunci nici o hartă de la SS la S-vs-V nu poate fi o surjecție. De fapt, avem ceva puțin mai puternic decât (dar echivalent clasic cu) eșecul ff de a fi o surjecție: există de fapt un element GG al lui s XQCvs \La V care nu este egal cu nicio valoare din intervalul FF. (Dacă VV are o relație de apartenență, atunci puteți obține un rezultat și mai puternic pentru o ipoteză corespunzător mai puternică pe nn, dar acest lucru nu se aplică versiunilor de mai jos.)
Teorema
(versiunea lui Cantor.)
dat un set SS, nu există nici o surjecție de la SS la setul de putere”s\mathcal{P}S.
dovada
fie VV setul de valori de adevăr, și lăsați n:V VN\Colon V \la v fi negare. Deoarece nn nu are punct fix, aplicați Teorema .
rețineți că, deși negația nu are toate proprietățile sale uzuale în matematica constructivă, p=Inktiptpp = \neg{p} este încă imposibilă.
următoarea versiune este clasic echivalent cu versiunea anterioară (cel puțin dacă verificați că”s\mathcal{P}S este locuită), dar nu constructiv echivalent. (Într-adevăr , spre deosebire de teoremă, se pare că nu are Analog constructiv atunci când”s\mathcal{P}S este înlocuit cu v SV^S.) Acest argument este din propoziția 2.8.8 a fundamentelor practice ale lui Taylor (deși nu știu dacă a provenit cu adevărat acolo).
Teorema
(versiunea lui Taylor.)
dat un set SS, nu există nici o injecție de la”S\mathcal{P}S la SS.
dovada
lasa i:”s” si\colon \mathcal{P}S \sa fie orice functie. Se definește F: S-ult.” – ult. ” Sf\Colon s \to \mathcal{P}S după cum urmează:
Dacă ii este o injecție, atunci ff este o retragere a lui ii și, prin urmare, o surjecție, ceea ce este imposibil prin teoremă .
desigur, Cantor a dovedit , de asemenea, Teorema, dar dovada lui nu a fost constructivă.
putem combina teoreme și în următoarea afirmație și mai generală, preluată din D4.1.8 din Elefantul lui Johnstone.
Teorema
(versiunea lui Johnstone.)
având în vedere un set SS, setul său de putere”s\mathcal{P}S nu poate fi exprimat ca subcotient al SS.
Dovada
să Presupunem că avem un set BB, o injecție i:BâªSi\colon B \hookrightarrow S și o surjection f:Bâð”Sf\colon B \a \mathcal{P}S. Apoi preimage funcție de i *:ð”Sâð”Bi^*\colon\mathcal{P}S \a \mathcal{P}B ar fi un surjection (pentru că *∃ i=1 ð”Bi^\ast \exists_i = 1_{\mathcal{P}B}), cum ar fi imaginea funcției f ∃:ð”Bâð”ð”S\exists_f\colon \mathcal{P}, B \a \mathcal{P}\mathcal{P}S (pentru că ∃ ff *=1 ð”ð”S\exists_f f^\ast = 1_{\mathcal{P}\mathcal{P}S}). Astfel compozit ar fi o surjection ð”Sâð”ð”S\mathcal{P}S \a \mathcal{P}\mathcal{P}S, ceea ce este imposibil de Teorema .
interpretare
rețineți că există o injecție de la SS la”S\mathcal{p}s, dat de harta Singleton. Deci, în aritmetica numerelor cardinale, avem
dar, deoarece nu există o astfel de surjecție, cu siguranță nu există nici o bijecție și avem
deci, concluzionăm că
adică, fiecare set este strict mai mic în cardinalitate decât setul său de putere.
această interpretare se bazează pe o bună relație între clasele de numere cardinale și == pe clasa de numere cardinale; în special, cantorulSchroeder, Teorema lui Bernstein, conform căreia ” Leq ” este antisimetrică. În matematica constructivă, această relație lipsește și este foarte posibil ca două seturi să fie strict mai mici între ele în sensul de mai sus. Datorită teoremei, acest lucru nu este posibil pentru un set și setul său de putere, dar înseamnă că interpretarea <\lt ca dimensiune relativă este problematicăîntr-adevăr aproape la fel de problematică ca ideea că există mai puține numere întregi chiar decât numere întregi!
Paul Taylor a susținut că valoarea esențială a teoremei lui Cantor este lema, implicită în dovada lui Cantor, pe care Bill Lawvere a izolat-o ca teoremă . Deoarece interpretarea principală a teoremei este semnificativă doar într-un context specific teoretic-set (în special, unul în care cantorulSchroederTeorema lui Bernstein deține), este posibil să nu supraviețuiască unei revoluții a lui XV, care să răstoarne primatul acelui context. Dar lema lui Lawvere va supraviețui, deoarece ea se ocupă de lucrarea lui lawvere, în timp ce Teorema lui Cantor, Lawvere, preia creditul. (A se vedea Taylor 2009 de mai jos pentru discuții suplimentare de lemmas de la sută care fac munca și teoremele care iau credit de la sută.)
în posete
o teoremă analogă cu teorema cantorului S pentru mulțimi poate fi formulată pentru alte categorii carteziene închise. În special, s-ar putea întreba dacă este posibil să existe o surjecție x Xx2 XX \la 2^x între posete, unde baza 22 nu este Poseta discretă {0,1}\{0, 1\} ci mai degrabă ordinea {0 1}\{0 \LEQ 1\}.
raspunsul este ca nu exista o astfel de surjectie F: X 2 XF: X \ la 2 ^ X, dar acest lucru nu rezultă dintr-o simplă aplicare a teoremei punctului fix al lui Lawvereqif, în care se încearcă excluderea unui astfel de FF invocând existența unei hărți de la 2cif22 \la 2 care nu are punct fix (nu există o astfel de hartă de la 2cif22 \la 2!). De asemenea, nu putem face apel la un argument de cardinalitate brută; de exemplu, dacă XX este ordinalul Irak\omega, atunci 2 X2^X este ordinul Irakop\bot \sqcup \Omega^{op} (se învecinează liber cu un element de jos de la Irak\bot la OP\Omega^{op}), care are aceeași cardinalitate. Deci, trebuie căutată o altă dovadă.
dovedind că nu există nici o surjecție x 2 XX \la 2^x este un exercițiu amuzant. O linie de atac (care se internalizează la orice topos) poate fi găsită aici.
- teorema punctului fix al lui Lawvere
