nLab Cantor' s tétel
Összegzés
Georg Cantor számos tételt bizonyított, de az úgynevezett Cantor-tétel az első nem triviális tétel nak, – nek Cantor új halmazelmélete: hogy egyes végtelenségek nagyobbak, mint mások; különösen bármely végtelen kardinális szám (vagy végtelen halmaz) nagyobbat generál a teljesítménykészlet felvételével.
(a tétel minden halmazra vonatkozik, nem csak a végtelenekre, bár a véges halmazok esetében meglehetősen nyilvánvaló.)
Cantor tétele nem tévesztendő össze a CantorSchroederCantor-tételével (lásd bíboros szám), amely különbözik (de összefügg, mivel fontos igazolni Cantor tételének értelmezését).
történelem
Cantor előtt az emberek hajlamosak voltak a végtelenre gondolni (akár hittek benne, akár nem), mint abszolút fogalomra: minden végtelenség egyenértékű. Észrevették (például Galileo), hogy egy végtelen halmaznak öninjekciót lehet adni, amely nem surjekció; például a páros egész számok felvétele az egész számokba duplázással. Tehát itt van két végtelenség, a “páros egészek végtelen ee-je és az összes egész szám végtelen NN-je”, amelyek valójában ekvivalensek, még akkor is, ha első pillantásra úgy tűnik, hogy EE kisebb.
Cantor megmutatta, hogy egy ilyen egyenértékűség nem sikerül a valós számokkal RR: NN-től RR-ig egyetlen térkép sem lehet surjektív (tehát RR megszámlálhatatlan). Az első érv az volt, ad hoc, de aztán általánosította ezt a diagonális érv azt mutatják, hogy nincs térkép bármely meghatározott SS a hatalom set”s\mathcal{p}S lehet surjektív. (Ez magában foglalta az RR megszámlálhatatlanságát, mivel Cantor talált egy bijekciót RR és”n\mathcal{p} n” között, amelyet ma a CantorSchrCantor “Cantor” példájának tekinthetünk.) Mivel van egy nyilvánvaló injektív térkép (a szingulett térkép) SS-től a”s\mathcal{p}s-ig, Cantor arra a következtetésre jutott, hogy az egyik kardinalitása szigorúan kisebb, mint a másik kardinalitása.
Cantor érvelése, mint az egész halmazelmélete, ellentmondásos volt abban az időben. Azok, akik Kroneckerhez hasonlóan úgy vélték, hogy minden matematikának véges matematikának kell lennie, értelmetlennek tartották. Még a mérsékeltebb korai konstruktivisták, mint például Brouwer és Weyl, úgy találták, hogy ennek nincs értelme. (Különösen nem mond semmit közvetlenül RR – ről, mivel az RR és a”n\mathcal{p}n” közötti bijekció konstruktívan nem érvényes, bár Cantor eredeti bizonyítéka, hogy RR megszámlálhatatlan, működőképes lehet.)
az alábbiakban ismertetett tétel változatai azonban konstruktívan érvényesek, sőt a tétel predikatívan is érvényes (mindaddig, amíg vannak függvénykészletek); a modern konstruktivisták ezeket általában tételként fogadják el. (Az értelmezés azonban nem ilyen egyértelmű.) Ezek valójában tételek bármely toposz belső nyelvén (a tétel pedig tétel minden esetben \Pi-pretopos).
állítások és bizonyítékok
tétel
(Lawvere változata.)
adott SS és VV halmazok esetén tegyük fel, hogy az SS Függvényhalmaz S-től a V-ig (szintén írva v SV^s). Ezután minden térkép n: v ‘ VN\kettőspont V \nak nek v van egy fix pont; vagyis n(x)=xn(x) = x egyeseknél x:Vx\colon V.
(ez általánosítja Lawvere fixpontos tételét.)
Proof
legyen f: S(A) = N (f(A)) f\Colon S \to(s \to v) bármilyen függvény, és tekintsük a G:s(a)=n(f (a) (A)) által megadott G: S (V)\Vg \Colon s \ to V függvényt. g (a) = n(f(a)(A)) .
Ez az, ha valaki használ currying értelmezni ff, mint egy funkció a SASS \alkalommal, S hogy VV, akkor gg felhasználásával határozza meg a átlós térkép Î S\Delta_S, mint a
tegyük fel, hogy az ff surjektív. Akkor kell lennie valamilyen elemnek a:Sa\colon S olyan, hogy f(a)=gf(a) = g. de akkor
tehát g(a)g(a) egy rögzített pontja nn.
a diagonális Térkép jelenléte s\Delta_S itt megmagyarázza, hogy miért hívják ezt a bizonyítékot diagonális argumentumnak. (Ez a magyarázat anakronisztikus, de erkölcsileg helyes.) Lawvere ‘ s a bizonyítás megmagyarázza (valójában általánosítja) a yy vagy fixpontos kombinátor be nem írt Lambda-kalkulusban, ahol y(n)y(n) bármely kifejezés fixpontja NN.
azonnal következik (még konstruktívan is), hogy ha a VV-nek van egy rögzített pont nélküli önleképezése, akkor az SS-től S-ig tartó s-ig terjedő térkép nem lehet surjekció. Valójában van valami valamivel erősebb, mint (de klasszikusan egyenértékű) a FF hogy surjekció legyen: valójában létezik egy elem GG nak, – nek Svs \nak nek V ami nem egyenlő az FF tartományának egyetlen értékével sem. (Ha a VV-nek van apartness-relációja, akkor még erősebb eredményt kaphat egy ennek megfelelően erősebb hipotézishez nn, de ez nem vonatkozik az alábbi verziókra.)
tétel
(Cantor változata.)
adott SS-halmaz esetén nincs surjekció az SS-től a teljesítményhalmazig” ” s\mathcal{p}S.
Proof
legyen VV az igazságértékek halmaza, és legyen N: V (V) VN\kettőspont V-től V-ig tagadás. Mivel nn nincs rögzített pontja, alkalmazza a tételt .
jegyezzük meg, hogy bár a tagadás nem rendelkezik a konstruktív matematikában szokásos összes tulajdonsággal, A P=Xhampp = \neg{p} még mindig lehetetlen.
a következő verzió klasszikusan egyenértékű az előző verzióval (legalábbis ha ellenőrizzük, hogy a”s\mathcal{p}s lakott-e), de konstruktívan nem egyenértékű. (Valójában a tételtől eltérően nyilvánvalóan nincs konstruktív analógja, amikor a”s\mathcal{p}s helyébe v SV ^ S.) Ez az érv Taylor gyakorlati alapjainak 2.8.8. tételéből származik (bár nem tudom, hogy valóban onnan származik-e).
tétel
(Taylor változata.)
egy sor SS-t adva nincs injekció A”S\mathcal{P}S-ből az SS-be.
Proof
Let I:”SS’ S ‘ si \ Colon \mathcal{p} s \ to S legyen bármilyen függvény. Határozzuk meg az F:S\Con s \to \mathcal{p}s értéket a következőképpen:
ha a ii egy injekció, akkor az ff a II visszahúzása, tehát egy surjekció, ami tétel szerint lehetetlen .
természetesen Cantor is bizonyította tétel, de a bizonyíték nem volt konstruktív.
mi lehet kombinálni tételek és a következő még általánosabb nyilatkozatot vett D4.1.8 Johnstone elefánt.
tétel
(Johnstone változata.)
adott SS-halmaz esetén a hatványhalmaza (“s\mathcal{p} s) nem fejezhető ki SS részhányadosaként.
Bizonyíték
Tegyük fel, hogy egy meghatározott BB, egy injekció én:BâªSi\vastagbél B \hookrightarrow S egy surjection f:Bâð ez”J\vastagbél B \a \mathcal{P}S., Akkor a preimage funkció *:đ ez”Sâð ez”Bi^*\colon\mathcal{P}S \a \mathcal{P}B lenne surjection (mert én *∃ i=1 đ ez”Bi^\ast \exists_i = 1_{\mathcal{P}B}), csakúgy, mint a kép funkció ∃ f:ð ez”Bâð ez”ð ez”S\exists_f\colon \mathcal{P}B \a \mathcal{P}\mathcal{P}S (mert ∃ ff *=1 đ ez”ð ez”S\exists_f f^\ast = 1_{\mathcal{P}\mathcal{P}S}). Így a kompozit lenne surjection ð ez”Sâð ez”ð ez”S\mathcal{P}S \a \mathcal{P}\mathcal{P}S, ami lehetetlen által Tétel .
értelmezés
vegye figyelembe, hogy létezik egy injekció SS-től a”s\mathcal{P}S-hez, amelyet a Singleton térkép ad. Tehát a kardinális számok aritmetikájában a
de mivel nincs ilyen surjekció, bizonyosan nincs bijekció, és itt van
tehát azt a következtetést vonjuk le, hogy
vagyis minden készlet szigorúan kisebb a kardinalitásban, mint a teljesítménykészlete.
ez az értelmezés egy jó kapcsolaton alapul, mely a főszámok osztályán alapul, különösen a Cantor (Cantor)Schroeder (Schroeder)Bernstein-tételen, mely szerint a Cantor (Cantor)\leq antiszimmetrikus. A konstruktív matematikában ez a kapcsolat hiányzik, és teljesen lehetséges, hogy két halmaz szigorúan kisebb legyen, mint a fenti értelemben. A tételnek köszönhetően ez nem lehetséges egy halmazra és annak hatványkészletére, de ez azt jelenti, hogy a <\lt relatív méretként való értelmezése problematikusvalójában majdnem olyan problematikus, mint az az elképzelés, hogy kevesebb páros egész szám van, mint egész!
Paul Taylor azzal érvelt, hogy Cantor tételének alapvető értéke a lemma, implicit Cantor bizonyításában, hogy Bill Lawvere tételként izolált . Mivel a tétel fő értelmezése csak egy meghatározott halmazelméleti kontextusban értelmezhető (különösen olyanban, ahol a Cantor GmbHSchroeder(Cantor)) tartja magát), lehet, hogy nem éli túl az A-t (a Cantor)) forradalom, amely megdönti ennek a kontextusnak az elsőbbségét. De Lawvere van lemma fog túlélni, hiszen âjelent a workâ míg a Cantor-tétel âveszi a creditâ. (Lásd Taylor 2009 alább további tárgyalása a munka és a tételeket, hogy vegye a credit GmbH.)
ban ben posets
a tétel analóg Cantor a halmazok s tétele megfogalmazható más derékszögű zárt kategóriákra. Különösen feltehetjük a kérdést, hogy lehetséges-e a surjekció x ‘ 2 xx \nak nek 2^x posetek között, ahol a 22 alap nem a diszkrét poset {0,1}\{0, 1\} sokkal inkább a {0 ons 1}\{0 \leq 1\} sorrendet.
a válasz az, hogy nincs ilyen surjekció f: X 6 XF: X \ to 2^X, de ez nem következik a Lawvere egyszerű alkalmazásából! \ s fix pont tétel, ahol az ember megpróbálja kizárni az ilyen FF-t egy 2. számú térkép létezésére hivatkozva22 \nak nek 2 amelynek nincs fix pontja (nincs ilyen poset térkép 2! \22 \ nak nek 2!). Nem tudunk fellebbezni néhány nyers kardinalitási érvre sem; például, ha XX A sorszámos\Omega, akkor 2 x2 ^ x az a sorrend, hogy\\\op\bot \ Sqcup \ Omega^{op} (szabadon csatlakozhat egy alsó elemhez \ Bot nak nek \ OP \ omega ^ {op}), amelynek ugyanaz a kardinalitása van. Tehát más bizonyítékot kell keresni.
szórakoztató gyakorlat annak bizonyítása, hogy nincs x 6 xx \ – 2 xx \ – 2^x surjekció. Egy Támadási Vonal (amely bármely toposzra internalizálódik) itt található.
- Lawvere fixpontos tétele
