Nlab Cantor's stelling
samenvatting
Georg Cantor bewees vele stellingen, maar de stelling die gewoonlijk de stelling van Cantor wordt genoemd, is de eerste niet-triviale stelling van Cantors nieuwe verzamelingenleer: dat sommige oneindigheden groter zijn dan andere; in het bijzonder genereert elk oneindig kardinaalgetal (of oneindige verzameling) een grotere door de machtsverzameling te nemen.
(de stelling is van toepassing op alle Verzamelingen, niet alleen op oneindige verzamelingen, hoewel het vrij duidelijk is voor eindige verzamelingen.)
de stelling van Cantor moet niet worden verward met de stelling van CantorâSchroederâBernstein (zie kardinaalgetal), die anders is (maar verwant, omdat het belangrijk is om Cantors interpretatie van zijn stelling te rechtvaardigen).
geschiedenis
voorafgaand aan Cantor hadden mensen de neiging oneindigheid (of ze er nu in geloofden of niet) als een absoluut begrip te beschouwen: alle oneindigheden zijn gelijkwaardig. Het was opgemerkt (door Galileo, bijvoorbeeld) dat het mogelijk is om een oneindige verzameling een zelfinjectie te geven die geen surjectie is; bijvoorbeeld, het opnemen van de even gehele getallen in de gehele getallen door verdubbeling. Dus hier zijn twee oneindigheden-de oneindigheid EE van even gehele getallen en de oneindigheid NN van alle gehele getallen – die eigenlijk equivalent zijn, ook al lijkt het op het eerste gezicht dat EE kleiner is.
Cantor toonde aan dat een dergelijke equivalentie faalt met de reële getallen RR: geen afbeelding van NN naar RR kan surjectief zijn (zodat RR ontelbaar is). Zijn eerste argument was ad hoc, maar hij veralgemeende dit met het diagonaal argument om aan te tonen dat geen enkele kaart van een verzameling SS naar zijn machtsverzameling ð”s\mathcal{P}S surjectief kon zijn. (Dit had betrekking op de ontkoppelbaarheid van RR, aangezien Cantor een bijectie vond tussen RR en ð”n\mathcal{P}N, die we nu kunnen beschouwen als een voorbeeld van de Stelling van Cantor Schröder Bernstein. Omdat er een duidelijke injectieve kaart is (de singleton kaart) van SS naar ð” ” s\mathcal{P}S, concludeerde Cantor dat de kardinaliteit van de ene strikt kleiner is dan de kardinaliteit van de andere.Cantors argument was, net als zijn hele verzamelingenleer, destijds controversieel. Degenen die, zoals Kronecker, geloofden dat alle wiskunde eindige wiskunde moest zijn, vonden het zinloos. Nog gematigder vroege constructivisten, zoals Brouwer en Weyl, vonden dat het weinig zin had. (In het bijzonder zegt het niets direct over RR, omdat de bijectie tussen RR en ð” ” n\mathcal{P}N niet constructief geldig is, hoewel Cantors oorspronkelijke bewijs dat RR ontelbaar is, aan het werk kan worden gemaakt.)
echter, de versies van de onderstaande stelling zijn constructief geldig, en stelling is zelfs predicatief geldig (zolang men functieverzamelingen heeft); moderne constructivisten accepteren deze over het algemeen als stellingen. (De interpretatie is echter niet zo duidelijk.) Het zijn in feite stellingen in de interne taal van elke topos (en stelling is een stelling in elke Î \Pi-pretopos).
stellingen en bewijzen
stelling
(versie van Lawvere.)
gegeven sets SS en VV, stel dat er een surjectie is van SS naar de functieset sâ ‘ VS \naar V (ook geschreven V SV^s). Dan heeft elke kaart n:vâVn\colon v \to V een vast punt; dat wil zeggen, n(x)=XN(x) = x voor sommige x:Vx\colon V.
(dit veralgemeniseert de vaste puntstelling van Lawvere.)
bewijs
Laat f: s ‘ (sÂV) f\colon s \to (S \to V) elke functie zijn, en beschouw de functie g:sÂVg\colon s \to V gegeven door
dat wil zeggen, als men currying gebruikt om ff te interpreteren als een functie van SÃ-SS \ times s naar VV, dan wordt gg gedefinieerd met behulp van de diagonale kaart Î S\Delta_S als
stel nu dat ff surjectief is. Dan moet er een element zijn a:Sa\colon S zodanig dat f(a) = gf(a)=g. maar dan
dus g(A) g(a) is een vast punt van nn.
de aanwezigheid van de diagonale kaart Î ” S\Delta_S verklaart hier waarom dit bewijs het diagonale argument wordt genoemd. (Deze verklaring is anachronistisch maar moreel correct.) Lawvereâ € s bewijs verklaart ook (in feite generaliseert)de YYâ of vaste punt combinator in untyped lambda-calculus, waar Y(n) Y(n) is een vast punt voor elke term nn.
het volgt onmiddellijk (zelfs constructief) dat als VV een zelfafbeelding heeft zonder vast punt, dan kan geen afbeelding van SS naar sâVS \naar V een surjectie zijn. In feite hebben we iets sterker dan (maar klassiek gelijk aan) het falen van ff om een surjectie te zijn: er bestaat eigenlijk een element gg Van sâVS \tot V dat niet gelijk is aan enige waarde in het bereik van ff. (Als VV een apartheidsrelatie heeft, dan kun je een nog sterker resultaat krijgen voor een navenant sterkere hypothese over nn, maar dat geldt niet voor de onderstaande versies.)
stelling
(Cantor ‘ s version.)
bij een verzameling SS is er geen surjectie van SS naar de machtsset ð ” S \ mathcal{P}S.
bewijs
laat VV De verzameling waarheidswaarden zijn, en laat n: vâ ‘ Vn \ colon v \ to V negatie zijn. Omdat nn geen vast punt heeft, pas stelling toe .
merk op dat hoewel negatie niet alle gebruikelijke eigenschappen heeft in de constructieve wiskunde, p=Âpp = \neg{p} nog steeds onmogelijk is.
de volgende versie is klassiek gelijkwaardig aan de vorige versie (tenminste als je controleert dat ð”S\mathcal{P}S bewoond is), maar niet constructief equivalent. (Inderdaad , in tegenstelling tot stelling, heeft het blijkbaar geen constructieve analoog wanneer ð ” S \ mathcal{P}S wordt vervangen door V SV^S.) Dit argument komt uit stelling 2.8.8 van Taylors praktische funderingen (hoewel ik niet weet of het daar echt is ontstaan).
stelling
(Taylors versie.)
Als u een set SS krijgt, wordt er geen injectie van” ” S\mathcal{P}S naar SS gegeven.
bewijs
laat I: ð “Sâ’ Si \ colon \ mathcal{P}S \ to S zijn elke functie. Definieer f:sâð”SF\colon s \to \mathcal{P}s als volgt:
Als ii een injectie is, dan is ff een retractie van ii en dus een surjectie, wat onmogelijk is door de stelling .
natuurlijk bewees Cantor ook stelling, maar zijn bewijs was niet constructief.
we kunnen stellingen combineren en in de volgende nog algemenere stelling, overgenomen uit D4.1.8 van Johnstones Olifant.
stelling
(Johnstones versie.)
gegeven een verzameling SS, kan de machtsverzameling ð” ” S\mathcal{P}S niet worden uitgedrukt als een subquotiënt van SS.
bewijs
stel dat we een verzameling BB hadden, een injectie i:BâªSi\colon B \hookrightarrow S en een surjectie f:Bâðƒ”Sf\colon B \to \mathcal{P}S. dan zou de preimagefunctie i *:ð””Sâð” “Bi^*\colon\mathcal{P}S \to \mathcal{P}B een surjectie zijn (omdat i *ƒƒƒ i=1 ð” Bi^\AST \Exists_i = 1_{\mathcal{P}B}), net als de Afbeeldingsfunctie:ð “Bâ’ ð “ð” S \ exists_f \ colon \ mathcal{P}B \ to \ mathcal{P}\mathcal{P}S (omdat ⃃ ff * = 1 ð “ð” S \ exists_f f^ \ ast = 1_ {\mathcal{P}\mathcal{P}s}). Hun composiet zou dus een surjectie zijn ð ‘”Sâ’ ð 𠑔𠑔 s\mathcal{P}S \to \mathcal{P}\mathcal{P}S, wat onmogelijk is door stelling .
interpretatie
merk op dat er een injectie van SS naar ð” ” S\mathcal{P}S bestaat, gegeven door de singleton kaart. Dus in de rekenkunde van hoofdtelwoorden hebben we
maar aangezien een dergelijke surjectie niet bestaat, is er zeker geen bijectie en hebben we
dus concluderen we dat
dat wil zeggen, elke verzameling is strikt kleiner in kardinaliteit dan zijn machtsverzameling.
deze interpretatie steunt op een goede relatie tussen â¤\leq en == op de klasse van de kardinaalgetallen; in het bijzonder de stelling van Cantorâ Schroederâ €  € Bernstein dat â¤\leq antisymmetrisch is. In de constructieve wiskunde ontbreekt deze relatie, en het is heel goed mogelijk dat twee verzamelingen elk strikt kleiner zijn dan elkaar in de zin hierboven. Dankzij de stelling is dit niet mogelijk voor een verzameling en haar machtsverzameling, maar het betekent wel dat de interpretatie van <\lt als relatieve grootte problematisch is-inderdaad bijna net zo problematisch als het idee dat er minder even gehele getallen dan gehele getallen zijn!
Paul Taylor heeft betoogd dat de essentiële waarde van de Stelling van Cantor het lemma is, impliciet in het bewijs van Cantor, dat Bill Lawvereisde als stelling . Aangezien de belangrijkste interpretatie van de stelling alleen zinvol is in een specifieke settheoretische context (in het bijzonder een context waarin de stelling van CantorâSchroederâBernstein geldt), kan het een ârevolutieâ die het primaat van die context omverwerpt niet overleven. Maar Lawvere ‘s lemma zal overleven, omdat het  € doet het werk € ™ terwijl Cantor’ s stelling  € neemt het Krediet€. (Zie Taylor 2009 hieronder voor verdere bespreking van â € Lemma ‘ s die het werk doen en stellingen die het krediet nemen.)
in posets
kan een stelling die analoog is aan de stelling van Cantor voor Verzamelingen worden geformuleerd voor andere Cartesiaanse gesloten categorieën. In het bijzonder kan men zich afvragen of het mogelijk is om een surjectie Xâ2 XX \tot 2^X tussen posets te hebben, waarbij de basis 22 niet de discrete poset is{0,1}\{0, 1\} maar eerder de orde {0â¤1}\{0 \ leq 1\}.
het antwoord is dat er geen surjectie bestaat f: x ‘ 2 Xf: X \tot 2^X, maar dit volgt niet uit een eenvoudige toepassing van de vaste-puntstelling van Lawvereâ, waar men een dergelijke ff probeert uit te sluiten door het bestaan aan te roepen van een kaart 2â22 \tot 2 die geen vast punt heeft (er is geen dergelijke posetkaart 2â22 \tot 2!). Evenmin kunnen we een beroep doen op een grof kardinaliteitsargument; bijvoorbeeld, als XX de ordinale Ï\Omega is, dan is 2 X2^X de orde ⊥âšï op\bot \sqcup \omega^{op} (vrij aangrenzend aan een bodemelement ⊥\bot aan Ï op\omega^{op}), die dezelfde kardinaliteit heeft. Er moet dus een ander bewijs worden gezocht.
bewijzen dat er geen surjectie Xâ ‘ 2 XX \tot 2^X is een vermakelijke oefening. Een aanvalslijn (die internaliseert naar alle topos) kan hier worden gevonden.
- de vaste puntstelling van Lawvere
