Kantorin lause

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 15.11.2020 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Cantorin lause on klassikko joukkoteoriassa . Todisti Georg Cantor vuonna 1891. Väittää, että mikä tahansa joukko on vähemmän tehokas kuin kaikkien sen osajoukkojen joukko . $A$ $2^A$

Todiste

Oletetaan, että on joukko , joka on yhtä suuri kuin kaikkien sen osajoukkojen joukko , eli että on olemassa sellainen bijektio , joka määrittää jokaiselle joukon elementille jonkin joukon osajoukon . $A$ $2^A$ $f$ $A$ $A$

Tarkastellaan joukkoa , joka koostuu kaikista elementeistä , jotka eivät kuulu niiden kuviin kartoituksessa [1] : $B$ $A$ $f$

{\displaystyle B=\left\{\,x\in A:x\not \in f(x)\,\right\))

Kartoitus on bijektiivinen, ja siksi on olemassa sellainen, että . $f$ $B\subseteq A$ $y\in A$ $f(y)=B$

Katsotaan nyt jos . Jos , sitten , ja sitten määritelmän mukaan . Ja päinvastoin, jos , niin , ja siksi . Joka tapauksessa saamme ristiriidan. $y$ $B$ $y\in B$ $y\in f(y)$ $B$ ${\näyttötyyli y\not \in B}$ ${\näyttötyyli y\not \in B}$ ${\näyttötyyli y\not \in f(y)}$ $y\in B$

Siksi alkuperäinen oletus on virheellinen eikä ekvipotentti . Siten epätasa-arvon ankaruus on todistettu. $A$ $2^A$

Epäyhtälön merkin määrittämiseksi rakennamme surjektiivisen mappauksen g: → joka yhdistää jokaisen yhdestä elementistä koostuvan osajoukon tähän samaan elementtiin kohteesta . Joukot (jotka koostuvat useammasta kuin yhdestä elementistä) jätetään kohtaan B. Tästä voidaan päätellä, että . $2^A$ $A$ $2^A$ $A$ $2^A$ $|2^{A}|>|A|$

Muistiinpanot

↑ Se on olemassa valintaaksiooman mukaan, arvo on A:n osajoukko.

Linkit

R. Courant, G. Robbins Mitä matematiikka on? Luku II, § 4, s. 111-122.

Katso myös

Sanakirjat ja tietosanakirjat	Suuri katalaani Iso venäläinen Liettuan universaali Britannica (verkossa)