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ó <math>f : E \to F</math>.
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 proprietats següentes:
- É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ó <math>f : E \to F</math> ; aleshores <math>f^{-1}</math> és una bijecció <math>F \to E</math>)
- É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ó <math>f : E \to F</math> i una bijecció <math>g : F \to G</math> ; aleshores la composició <math>g \circ f : E \to G</math> es una bijecció)
Açò prova que dins tot conjunt <math>\mathcal{E}</math> de conjunts, la relació binària d'equipotència és una relació d'equivalència, i que el conjunt quocient <math>\mathcal{E} / \approx\quad</math> pot ésser identificat al conjunt dels cardinals dels elements de <math>\mathcal{E}</math>.
Per exemple, si <math>\mathcal{E} = \mathcal{P}(\Omega)</math> és el conjunt de les parts d'un conjunt <math>\Omega</math>, l'equipotència és una relació d'equivalència dins <math>\mathcal{E}</math>.
Tanmateix, no és possible de dir que l'equipotència es 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 <math>i : E \to F</math> i <math>j : F \to E</math>, aleshores E ≈ F.
Exemples i contra-exemples
- El conjunt <math>\mathbb{N}</math> dels enters naturals i el conjunt dels enters naturals parells, notat ací <math>\mathcal{P}</math>, són equipotents: l'aplicació <math>\mathbb{N} \to \mathcal{P},\, n \mapsto 2\, n</math> és bijectiva. De fet els conjunts que són equipotents amb ℕ es diu que són numerables.
- Cas dels intervals del conjunt <math>\mathbb{R}</math> dels nombres reals
- Sien dos reals <math>a</math>, <math>b</math> tals que <math>a < b</math>, i els intervals
<math>[a,\, b] = \{x \in \mathbb{R} \mid a \leq x \leq b\}</math> , <math>\,]a,\, b[\, = \{x \in \mathbb{R} \mid a < x < b\}</math>- Els intervals <math>[a,\, b] </math> i <math>[0,\, 1]</math> són equipotents: l'aplicació <math>[a,\, b] \to [0,\, 1],\, x \mapsto \frac{x - a}{b - a}</math> és bijectiva.
- Anàlogament, els intervals <math>\,]a,\, b[\, </math> i <math>\,]0,\, 1[\,</math> són equipotents.
- Els intervals <math>\,]0,\, 1[\,</math> i <math>[0,\, 1]</math> són equipotents:
- l'aplicació <math>i : \,]0,\, 1[\, \to [0,\, 1],\, x \mapsto x </math> és injectiva (en fet, és la injecció canònica).
- l'aplicació <math>j : [0,\, 1] \to \,]0,\, 1[\,,\, x \mapsto \frac{x + 1}{3} </math> és injectiva.
- l'equipotència de <math>\,]0,\, 1[\,</math> i <math>[0,\, 1]</math> és, aleshores, conseqüència del teorema de Cantor-Bernstein.
- Els intervals <math>\mathbb{R} = \,]-\infty,\,+\infty[\,</math> i <math>\,]-1,\, +1[\,</math> són equipotents:
l'aplicació <math>\mathbb{R} \to \,]-1,\, +1[\,,\, x \mapsto \frac{x}{1 + |x|}</math> és bijectiva. - En fet, es pot generalitzar açò: dos intervals de <math>\mathbb{R}</math> qualssevulla (posat que cada un contenga almenys dos punts) són equipotents.
- Sien dos reals <math>a</math>, <math>b</math> tals que <math>a < b</math>, i els intervals
- Essent un conjunt <math>\Omega</math>, el conjunt <math>\mathcal{P}(\Omega)</math> de les seves parts és equipotent al conjunt <math>\{0,\, 1\}^\Omega</math> de les funcions <math>\Omega \to \{0,\, 1\} </math>.
Per provar-ho, s'associa a tota part A de <math>\Omega</math> la seva funció característica <math>\chi_A : \Omega \to \{0,\, 1\} </math> definida així: per a tot element x de <math>\Omega</math>, <math>\chi_A(x) = 1 </math> si <math>x \in A</math> i <math>\chi_A(x) = 0 </math> si <math>x \notin A</math>.
L'aplicació <math>\mathcal{P}(\Omega) \to \{0,\, 1\}^\Omega,\, A \mapsto \chi_A</math> és bijectiva : si f és una funció <math>\Omega \to \{0,\, 1\} </math> i si es defineix <math>A = \{x \in \Omega \mid f(x) = 1\}</math>, és clar que A es l'única part de <math>\Omega</math> tal que <math>\chi_A = f</math>.
- Segons un teorema clàssic de Cantor, el conjunt <math>\mathbb{N}</math> dels enters naturals no és equipotent al conjunt <math>\mathbb{R}</math> dels reals.
- Semblantment, un conjunt <math>\Omega</math> no és equipotent al conjunt <math>\mathcal{P}(\Omega)</math> de les seves parts.
Per provar-ho (per reducció a l'absurd), suposem l'existència d'una bijecció <math>f : \Omega \to \mathcal{P}(\Omega)</math> i definim el conjunt <math>A = \{x \in \Omega | x \notin f(x)\}</math>.
Com que <math>A \in \mathcal{P}(\Omega)</math> i f és bijectiva, existeix un element (únic) <math>\ x_0</math> del conjunt <math>\Omega</math> tal que <math>\ f(x_0) = A</math>.
Llavors: <math>x_0 \in A \iff x_0 \notin f(x_0) \iff x_0 \notin A</math>, una contradicció.
- (observeu que en aquesta demostració, no hem fet servir la unicitat de <math>x_0</math>: així, hem provat que no existeix cap suprajecció <math>f : \Omega \to \mathcal{P}(\Omega)</math>).
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).