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ó ${\displaystyle 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ó ${\displaystyle f:E\to F}$; aleshores ${\displaystyle f^{-1}}$ és una bijecció ${\displaystyle 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ó ${\displaystyle f:E\to F}$ i una bijecció ${\displaystyle g:F\to G}$; aleshores la composició ${\displaystyle g\circ f:E\to G}$ és una bijecció)

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

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 ${\displaystyle i:E\to F}$ i ${\displaystyle j:F\to E}$, aleshores E ≈ F.

Exemples i contra-exemples

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

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

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

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

(observeu que en aquesta demostració, no hem fet servir la unicitat de ${\displaystyle x_{0}}$: així, hem provat que no existeix cap suprajecció ${\displaystyle f:\Omega \to {\mathcal {P}}(\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 segle xix, 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