Teorema lui Cantor

Deși acest articol conține o listă de referințe bibliografice, sursele sale rămân neclare deoarece îi lipsesc notele de subsol.
Puteți ajuta introducând citări mai precise ale surselor.
Nu confundați cu Teorema Cantor-Bernstein.

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

Enunț

Fie A o mulțime nevidă și P ( A ) {\displaystyle {\mathfrak {P}}(A)} mulțimea submulțimilor acesteia. Atunci cardinalul lui A este strict mai mic decât cardinalul lui P ( A ) {\displaystyle {\mathfrak {P}}(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 → P ( A ) {\displaystyle {\mathfrak {P}}(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 ∈ A : x ∉ f ( x ) } . {\displaystyle B=\left\{\,x\in A:x\not \in f(x)\,\right\}.}

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 ∈ A {\displaystyle x\in A} avem f ( x ) = B {\displaystyle f(x)=B} . Avem cazurile:

  • x ∈ B {\displaystyle x\in B}  :

atunci x ∉ f ( x ) {\displaystyle x\not \in f(x)} deci x ∉ B {\displaystyle x\not \in B}

  • x ∉ B {\displaystyle x\not \in B}

atunci x ∈ f ( x ) {\displaystyle x\in f(x)} deci x ∈ B {\displaystyle 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 P ( A ) {\displaystyle {\mathfrak {P}}(A)} nu sunt echipotente.

Bibliografie

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

Vezi și

  • Mulțime
  • Cardinal (matematică)

Legături externe

  • en Teorema lui Cantor la MathWorld[nefuncțională]