nLab Cantor's lause

by Posted on

Yhteenveto

Georg Cantor todisti monia teoreemoja, mutta Cantorin lauseeksi yleensä kutsuttu lause on Cantorin uuden joukko-opin ensimmäinen ei-triviaalilause: että jotkut infiniteetit ovat suurempia kuin toiset; erityisesti mikä tahansa ääretön kardinaaliluku (tai ääretön joukko) synnyttää suuremman ottamalla potenssijoukon.

(lause koskee kaikkia joukkoja, ei vain äärettömiä, vaikka se on melko ilmeinen äärellisille joukoille.)

Cantorin lausetta ei tule sekoittaa Cantorin Schroederin Bernsteinin lauseeseen (katso kardinaaliluku), joka on erilainen (mutta sukua, koska on tärkeää perustella Cantorin tulkinta lauseestaan).

historia

ennen Cantoria ihmisillä oli taipumus ajatella äärettömyyttä (uskoivatpa he siihen tai eivät) absoluuttisena käsitteenä: kaikki äärettömyydet ovat ekvivalentteja. Oli huomattu (esimerkiksi Galileo) että on mahdollista antaa äärettömälle joukolle itseruiskutus, joka ei ole surjektio; esimerkiksi parillisten kokonaislukujen sisällyttäminen kokonaislukuihin kaksinkertaistamalla. Tässä on siis kaksi äärettömyyttä, parillisten kokonaislukujen äärettömyys EE ja kaikkien kokonaislukujen äärettömyys nn, jotka ovat itse asiassa ekvivalentteja, vaikka ensi silmäyksellä näyttäisi siltä, että EE on pienempi.

Cantor osoitti, että tällainen ekvivalenssi epäonnistuu reaalilukujen RR: n kanssa: mikään kartta nn: stä RR: ään ei voi olla surjektiivinen (niin, että RR on laskematon). Hänen ensimmäinen argumentti oli ad hoc, mutta hän sitten yleistää tämän kanssa diagonaalinen argumentti osoittaa, että mitään karttaa mistä tahansa joukko SS sen teho joukko ð’”s\mathcal{P}S voisi olla surjective. (Tämä kattoi rr: n uncountability-periaatteen, sillä Cantor löysi bijektion rr: n ja ð’”n\mathcal{P}n välillä, jota voimme nyt pitää Cantorin Schrøderin Bernsteinin lauseen ilmentymänä.) Koska on olemassa ilmeinen injektoiva kartta (Singletonin kartta) SS: stä ð’”s\mathcal{P}S: ään, Cantor päätteli, että toisen kardinaalisuus on ehdottomasti pienempi kuin toisen kardinaalisuus.

Cantorin väite, kuten koko joukko-oppi, oli tuolloin kiistanalainen. Ne, jotka kroneckerin tavoin uskoivat, että kaiken matematiikan tulisi olla äärellistä matematiikkaa, pitivät sitä merkityksettömänä. Vielä maltillisemmat varhaiset konstruktivistit, kuten Brouwer ja Weyl, havaitsivat, että sillä ei ollut juurikaan merkitystä. (Erityisesti se ei sano mitään suoraan RR: stä, koska rr: n ja ð’”n\mathcal{P}n välinen bijektio ei ole konstruktiivisesti pätevä, vaikka Cantorin alkuperäinen todiste siitä, että RR on laskematon, voidaan saada toimimaan.)

alla esitetyt teoreeman versiot ovat kuitenkin konstruktiivisesti päteviä, ja lause on jopa predikatiivisesti pätevä (kunhan on funktioita); nykyaikaiset konstruktivistit hyväksyvät nämä yleensä teoreemoina. (Tulkinta ei kuitenkaan ole niin selkeä.) Ne ovat itse asiassa teoreemoja minkä tahansa topoksen sisäisessä kielessä (ja lause on lause missä tahansa Î \Pi-pretopoksessa).

väittämät ja todisteet

lause

(Lawveren versio.)

annetut joukot SS ja VV oletetaan, että on olemassa surjektio SS: stä funktion joukkoon s†’VS \V (kirjoitetaan myös V SV^s). Sitten jokaisella kartalla n: V→Vn\kaksoispiste V \ – V on kiinteä piste; toisin sanoen n(x)=XN(x) = x joillekin x:Vx\colon V.

(tämä yleistyy Lawveren kiintopistelauseeseen.)

todiste

olkoon f: s† “(s† “V)F\kaksoispiste s \to(s \to V) mikä tahansa funktio, ja tarkastellaan funktiota g:s†” VG\kaksoispiste s \to V annettuna

g(a)=n(f(a) (a)). g (a) = n(f(a) (a)).

eli jos käytetään kursiivia tulkitsemaan ff funktiona SÃ-s \times S: stä VV: hen, niin gg määritellään diagonaalikartalla Δ s\Delta_S as

s†’Δ SS×s†’fV→NV. S \stackrel{\Delta_S}\to s \times s \stackrel{f}\to v \stackrel{n}\to v.

oletetaan nyt, että ff on surjektiivinen. Sitten täytyy olla jokin elementti a:Sa\colon S sellainen, että f(a)=gf(a) = g. mutta sitten

g(a)=n(f(a)(A))=n(g(a))), G(A) = n(f(a) (A)) = n(g(a))),

niin G(A) g(A) on nn: n kiinteä piste.

diagonaalikartan Δ s\Delta_S läsnäolo tässä selittää, miksi tätä todistusta kutsutaan diagonaaliargumentiksi. (Tämä selitys on vanhentunut, mutta moraalisesti oikea.) Lawvere ‘ s todiste myös selittää(itse asiassa yleistää) YY‘ tai kiinteän pisteen combinator untyped lambda-calculus, jossa Y(n)Y (n) on kiinteä piste tahansa termi nn.

Tästä seuraa välittömästi (jopa konstruktiivisesti), että jos VV: ssä on omakartoitus, jossa ei ole kiinteää pistettä, niin ei mikään kartta SS: stä s†’VS \V: hen voi olla surjektio. Itse asiassa, meillä on jotain hieman vahvempi kuin (mutta klassisesti vastaava) epäonnistuminen ff on surjection: on todella olemassa Elementti gg s†’VS \V, joka ei ole sama kuin mitään arvoa alueella ff. (Jos VV: llä on apartness-relaatio, voidaan saada vielä vahvempi tulos vastaavasti vahvemmalle hypoteesille nn: lle, mutta se ei päde alla oleviin versioihin.)

lause

(Cantorin versio.)

kun otetaan huomioon joukko SS, ei ole surjektiota SS: stä potenssijoukkoon ð ‘” s\mathcal{P}S.

Proof

olkoon VV totuusarvojen joukko, ja olkoon n: V→VN\kaksoispiste V \to V negaatio. Koska nn: llä ei ole kiinteää pistettä, sovelletaan teoreemaa .

huomaa, että vaikka negaatiolla ei ole kaikkia tavanomaisia ominaisuuksiaan konstruktiivisessa matematiikassa, p=Âpp = \neg{p} on silti mahdotonta.

seuraava versio on klassisesti ekvivalentti edellisen version kanssa (ainakin jos tarkistaa, että ð’”s\mathcal{P}S on asuttu), mutta ei konstruktiivisesti ekvivalentti. (Itse asiassa, toisin kuin lause, se ilmeisesti ei ole rakentava analoginen, kun ð’s\mathcal{P}s korvataan V SV^S.) tämä argumentti on propositio 2.8.8 Taylorin käytännön perusteet (vaikka en tiedä, jos se todella alkunsa siellä).

lause

(Taylorin versio.)

kun otetaan huomioon joukko SS, ð’”s\mathcal{P}S: stä ei ole pistosta SS: ään.

Proof

olkoon I: ð ‘”s†” Si\colon \mathcal{P}s \to S mikä tahansa funktio. Määrittele f: s† “ð” ” SF\colon s \to \mathcal{P}S seuraavasti:

f(A) = {b:S/∀(U:ð ‘ s), i(U)=a‡’bâu}. f (a) = \ {b\colon s \;|\; \forall (U\colon \mathcal{P}S),\; i(U) = a \;\Rightarrow\; b \in U \} .

jos ii on injektio, niin ff on II: n retribuutio ja siten surjektio, joka on teoreeman mukaan mahdotonta .

tietenkin Cantor myös todisti lauseen, mutta hänen todisteensa eivät olleet rakentavia.

voidaan yhdistää teoreemoja ja seuraavaan vielä yleisempään lauseeseen, joka on otettu Johnstonen elefantin D4.1.8: sta.

lause

(Johnstonen versio.)

kun otetaan huomioon joukko SS, sen potenssijoukko ð ‘” s\mathcal{P}S ei voi ilmaista SS: n alakiintiönä.

Proof

Oletetaan, että meillä olisi joukko BB, injektio i:B↪Si\kaksoispiste b \hookrightarrow s ja surjektio f:B→ð’”SF\kaksoispiste b \to \mathcal{P}S. silloin preimage-funktio i *:ð””s†”ð” Bi^*\\kaksoispiste \mathcal{P}s \to\mathcal{P}B olisi surjektio (koska I *â / I=1 ð “” Bi^\Ast\Exists_i = 1_ {\mathcal{P}B}), kuten Kuvafunktio:ð”B↔ð”s\exists_f\colon \mathcal{P}B \to \mathcal{P}\mathcal{P}S (koska \ FF *=1 ð” ð ” S\exists_f F^\ast = 1_{\mathcal{p}\mathcal{P}s}). Näin heidän yhdistelmänsä olisi surjektio ð’”s†’ð’”ð’”s\mathcal{P}s \to \mathcal{P}\mathcal{P}S, mikä on Teoreemalla mahdotonta .

tulkinta

huomaa, että SS: stä on olemassa Singletonin kartan antama pistos ð’”s\mathcal{p}s. Kardinaalilukujen aritmetiikassa meillä on siis

|s|≠/ ð’”S/. {|S/} \leq {/\mathcal{P}s/} .

mutta koska tällaista surjektiota ei ole, bijektiota ei varmasti ole, ja meillä on

|s|≠|ð’”s|. {|S|} \ne {/\mathcal{P}s/} .

näin päätellään, että

/ s / <|ð’”s/. {|S|} \lt {/\mathcal{P}s/}.

eli jokainen joukko on kardinaaliudeltaan ehdottomasti pienempi kuin sen potenssijoukko.

tämä tulkinta perustuu hyvään suhteeseen â‰\leqin ja == kardinaalilukujen luokan välillä; erityisesti Cantor–Schroeder–Bernsteinin lauseeseen, jonka mukaan â‰\leq on antisymmetrinen. Konstruktiivisessa matematiikassa tämä suhde puuttuu, ja on täysin mahdollista, että kaksi joukkoa ovat kumpikin tiukasti toisiaan pienempiä edellä mainitussa mielessä. Teoreeman ansiosta tämä ei ole mahdollista joukolle ja sen potenssijoukolle, mutta se tarkoittaa, että <\lt: n tulkinta suhteellisena suuruutena on ongelmallinen —itse asiassa lähes yhtä ongelmallinen kuin ajatus siitä, että parillisia kokonaislukuja on vähemmän kuin kokonaislukuja!

Paul Taylor on väittänyt, että Cantorin lauseen olennainen arvo on Cantorin todistuksessa implisiittisesti esitetty lempi, jonka Bill Lawvere eristi lauseeksi . Koska lauseen päätulkinta on merkityksellinen vain tietyssä joukko-teoreettisessa kontekstissa (erityisesti sellaisessa, jossa Cantor Schroeder Bernsteinin lause pätee), se ei välttämättä selviä vallankumouksesta, joka syrjäyttää kyseisen kontekstin ensisijaisuuden. Mutta Lawveren lemma selviää, koska se tekee työn, kun taas Cantorin lause vie kunnian. (Katso Taylor 2009 alla lisäkeskustelua Lemmas jotka tekevät työtä ja teoreemojen, jotka ottavat luottoa.)

poseteissa

voidaan muotoilla Cantorin lausetta vastaava lause joukoille muille karteesisille suljetuille luokille. Erityisesti voidaan kysyä, onko mahdollista saada surjektio X↠‘ 2 XX \- 2^x posetien välillä, jossa kantaluku 22 ei ole diskreetti poset {0,1}\{0, 1\} pikemminkin järjestys {0≤1}\{0 \leq 1\}.

vastaus on, ettei tällaista surjektiota f: X→2 Xf: X \to 2^x, mutta tämä ei seuraa yksinkertaisesta Lawveren kiinteän pisteen lauseen soveltamisesta, jossa yritetään sulkea pois tällainen ff vetoamalla sellaisen kartan olemassaoloon 2†’22 \to 2, jolla ei ole kiinteää pistettä (tällaista poset-karttaa 2→22 \to 2 ei ole olemassa!). Emme voi myöskään vedota mihinkään karkeaan kardinaaliargumenttiin; esimerkiksi, jos XX on ordinaali {‰\omega, niin 2 x2^X on järjestys ⚥⚠” {‰op\bot \sqcup \ omega^{op} (Vapaasti adjoin alaelementti ⚥\bot {op}), jolla on sama kardinaalisuus. On siis etsittävä muita todisteita.

surjektion X→2 XX \ – 2^x todistaminen on huvittavaa. Yksi hyökkäyslinja (joka sisäistää mihin tahansa topokseen) löytyy täältä.

  • Lawveren kiinteän pisteen lause

Published by admin

Vastaa

Sähköpostiosoitettasi ei julkaista.