Equipotència

En la teoria dels conjunts, es diu que dos conjunts E i F són equipotents, i es nota E ≈ F, si existeix una bijecció $f:E\to F$.

Per definició, dos conjunts (finits o no) tenen la mateixa cardinalitat (el mateix nombre d'elements) si són equipotents.

Propietats de l'equipotència

L'equipotència té les propietats següents:

• És reflexiva: per a tot conjunt E, E ≈ E (existeix almenys una bijecció de E vers E : l'aplicació idèntica de E)

• És simètrica: essent dos conjunts E i F, si E ≈ F, aleshores F ≈ E (per hipotèsi, hi ha almenys una bijecció $f:E\to F$; aleshores $f^{-1}$ és una bijecció $F\to E$)

• És transitiva: essent tres conjunts E, F i G, si E ≈ F i F ≈ G, aleshores E ≈ G (per hipotèsi, hi ha almenys una bijecció $f:E\to F$ i una bijecció $g:F\to G$; aleshores la composició $g\circ f:E\to G$ és una bijecció)

Açò prova que dins tot conjunt $ℰ$ de conjunts, la relació binària d'equipotència és una relació d'equivalència, i que el conjunt quocient $ℰ/\approx$ pot ésser identificat al conjunt dels cardinals dels elements de $ℰ$.
Per exemple, si $ℰ=𝒫(\mathrm{\Omega })$ és el conjunt de les parts d'un conjunt $\mathrm{\Omega }$, l'equipotència és una relació d'equivalència dins $ℰ$.

Tanmateix, no és possible de dir que l'equipotència és una relació d'equivalència dins el conjunt de tots els conjunts: dins la teoria clàssica dels conjunts, el conjunt de tots els conjunts no existeix pas.

Teorema de Cantor-Bernstein

El teorema de Cantor-Bernstein (o teorema de Cantor-Bernstein-Schröder) és una caracterització de l'equipotència. S'enuncia així:

Essent dos conjunts E i F, si existeixen dues injeccions $i:E\to F$ i $j:F\to E$, aleshores E ≈ F.

Exemples i contra-exemples

• El conjunt $\mathbb{N}$ dels enters naturals i el conjunt dels enters naturals parells, notat ací $𝒫$, són equipotents: l'aplicació $\mathbb{N}\to 𝒫,n\mapsto 2n$ és bijectiva. De fet els conjunts que són equipotents amb ℕ es diu que són numerables.
• Cas dels intervals del conjunt $ℝ$ dels nombres reals
  • Sien dos reals $a$, $b$ tals que $a<b$, i els intervals
    $[a,b]=\{x\in ℝ\mid a\le x\le b\}$, $]a,b[=\{x\in ℝ\mid a<x<b\}$
    • Els intervals $[a,b]$ i $[0,1]$ són equipotents: l'aplicació $[a,b]\to [0,1],x\mapsto \frac{x-a}{b-a}$ és bijectiva.
    • Anàlogament, els intervals $]a,b[$ i $]0,1[$ són equipotents.
  • Els intervals $]0,1[$ i $[0,1]$ són equipotents:
    • l'aplicació $i:]0,1[\to [0,1],x\mapsto x$ és injectiva (en fet, és la injecció canònica).
    • l'aplicació $j:[0,1]\to ]0,1[,x\mapsto \frac{x+1}{3}$ és injectiva.
    • l'equipotència de $]0,1[$ i $[0,1]$ és, aleshores, conseqüència del teorema de Cantor-Bernstein.
  • Els intervals $ℝ=]-\mathrm{\infty },+\mathrm{\infty }[$ i $]-1,+1[$ són equipotents:
    l'aplicació $ℝ\to ]-1,+1[,x\mapsto \frac{x}{1+|x|}$ és bijectiva.
  • En fet, es pot generalitzar açò: dos intervals de $ℝ$ qualssevulla (posat que cada un contenga almenys dos punts) són equipotents.

• Essent un conjunt $\mathrm{\Omega }$, el conjunt $𝒫(\mathrm{\Omega })$ de les seves parts és equipotent al conjunt $\{0,1{\}}^{\mathrm{\Omega }}$ de les funcions $\mathrm{\Omega }\to \{0,1\}$.
  Per provar-ho, s'associa a tota part A de $\mathrm{\Omega }$ la seva funció característica ${\chi }_A:\mathrm{\Omega }\to \{0,1\}$ definida així: per a tot element x de $\mathrm{\Omega }$, ${\chi }_A(x)=1$ si $x\in A$ i ${\chi }_A(x)=0$ si $x\notin A$.
  L'aplicació $𝒫(\mathrm{\Omega })\to \{0,1{\}}^{\mathrm{\Omega }},A\mapsto {\chi }_A$ és bijectiva : si f és una funció $\mathrm{\Omega }\to \{0,1\}$ i si es defineix $A=\{x\in \mathrm{\Omega }\mid f(x)=1\}$, és clar que A es l'única part de $\mathrm{\Omega }$ tal que ${\chi }_A=f$.

• Segons un teorema clàssic de Cantor, el conjunt $\mathbb{N}$ dels enters naturals no és equipotent al conjunt $ℝ$ dels reals.

• Semblantment, un conjunt $\mathrm{\Omega }$ no és equipotent al conjunt $𝒫(\mathrm{\Omega })$ de les seves parts.
  Per provar-ho (per reducció a l'absurd), suposem l'existència d'una bijecció $f:\mathrm{\Omega }\to 𝒫(\mathrm{\Omega })$ i definim el conjunt $A=\{x\in \mathrm{\Omega }|x\notin f(x)\}$.
  Com que $A\in 𝒫(\mathrm{\Omega })$ i f és bijectiva, existeix un element (únic) $x_0$ del conjunt $\mathrm{\Omega }$ tal que $f(x_0)=A$.
  Llavors: $x_0\in A⟺x_0\notin f(x_0)⟺x_0\notin A$, una contradicció.

(observeu que en aquesta demostració, no hem fet servir la unicitat de $x_0$: així, hem provat que no existeix cap suprajecció $f:\mathrm{\Omega }\to 𝒫(\mathrm{\Omega })$).

Cas dels conjunts finits i dels conjunts infinits

Conjunts equipotents a un conjunt finit

Si E és un conjunt finit, els conjunts equipotents a E són aquells conjunts finits que tenen el mateix nombre d'elements que E.

Conjunts equipotents a un conjunt infinit

Tot conjunt equipotent a un conjunt infinit és també infinit. Però se sap d'ençà del Plantilla:Segle, per les obres de Georg Cantor, que hi ha conjunts infinits que no són equipotents, valent a dir que no tenen la mateixa cardinalitat (cf. ací a sobre).

Vegeu també

• Conjunt numerable
• Funció bijectiva
• Nombre cardinal
• Teoria dels conjunts