Teorema lui Cantor

Teorema lui Cantor este o teoremă matematică privind teoria mulțimilor.

Enunț

Fie A o mulțime nevidă și $𝔓(A)$ mulțimea submulțimilor acesteia. Atunci cardinalul lui A este strict mai mic decât cardinalul lui $𝔓(A)$

Demonstrație

Fie funcția oarecare care pune în corespondență o mulțime A cu mulțimea submulțimilor P(A) a acestei mulțimi A:

f: A → $𝔓(A)$

Demonstrarea acestei teoreme este echivalentă cu a demonstra enunțul: f nu poate fi surjectivă. Pentru aceasta e suficient a determina o submulțime a lui A care să nu fie imaginea lui f.

Considerăm mulțimea

$B=\{x\in A:x\in ̸f(x)\}.$

Pentru a arăta că B nu este imaginea lui f, să presupunem prin absurd că B este imaginea lui f. Atunci pentru un $x\in A$ avem $f(x)=B$. Avem cazurile:

• $x\in B$ :

atunci $x\in ̸f(x)$ deci $x\in ̸B$

• $x\in ̸B$

atunci $x\in f(x)$ deci $x\in B$

În ambele cazuri se obține o contradicție. Aceasta dovedește că B nu este imaginea lui f, deci f nu este surjectivă.

Deci mulțimile A și $𝔓(A)$ nu sunt echipotente.

Bibliografie

• Format:En icon Halmos, Paul R., Naive Set Theory, Princeton, N.J.: Van Nostrand (1960) ISBN 0387900926
• Format:En icon Stoll, Robert R., Set Theory and Logic, Mineola, N.Y.: Dover Publications (1979) ISBN 0486638294

Vezi și

• Mulțime
• Cardinal (matematică)

Legături externe

• Format:En icon Teorema lui Cantor la MathWorldFormat:Legătură nefuncțională