Equipotència

De Viquipèdia
Dreceres ràpides: navegació, cerca

En la teoria dels conjunts, es diu que dos conjunts E i F són equipotents, i es nota EF, 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[modifica | modifica el codi]

L'equipotència té les proprietats següentes:

  • És simètrica: essent dos conjunts E i F, si EF, aleshores FE (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 EF i FG, aleshores EG (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 \mathcal{E} de conjunts, la relació binària d'equipotència és una relació d'equivalència, i que el conjunt quocient \mathcal{E} / \approx\quad pot ésser identificat al conjunt dels cardinals dels elements de \mathcal{E}.
Per exemple, si \mathcal{E} = \mathcal{P}(\Omega) és el conjunt de les parts d'un conjunt \Omega, l'equipotència és una relació d'equivalència dins \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[modifica | modifica el codi]

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 EF.

Exemples i contra-exemples[modifica | modifica el codi]

  • El conjunt \mathbb{N} dels enters naturals i el conjunt dels enters naturals parells, notat ací \mathcal{P}, són equipotents: l'aplicació \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 \mathbb{R} dels nombres reals
    • Sien dos reals a, b tals que a < b, i els intervals
      [a,\, b] = \{x \in \mathbb{R} \mid a \leq x \leq b\}, \,]a,\, b[\, = \{x \in \mathbb{R} \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 \mathbb{R} = \,]-\infty,\,+\infty[\, i \,]-1,\, +1[\, són equipotents:
      l'aplicació \mathbb{R} \to \,]-1,\, +1[\,,\, x \mapsto \frac{x}{1 + |x|} és bijectiva.
    • En fet, es pot generalitzar açò: dos intervals de \mathbb{R} qualssevulla (posat que cada un contenga almenys dos punts) són equipotents.
  • Essent un conjunt \Omega, el conjunt \mathcal{P}(\Omega) de les seves parts és equipotent al conjunt \{0,\, 1\}^\Omega de les funcions \Omega \to \{0,\, 1\} .
    Per provar-ho, s'associa a tota part A de \Omega la seva funció característica \chi_A : \Omega \to \{0,\, 1\} definida així: per a tot element x de \Omega, \chi_A(x) = 1 si x \in A i \chi_A(x) = 0 si x \notin A.
    L'aplicació \mathcal{P}(\Omega) \to \{0,\, 1\}^\Omega,\, A \mapsto \chi_A és bijectiva : si f és una funció \Omega \to \{0,\, 1\} i si es defineix A = \{x \in \Omega \mid f(x) = 1\}, és clar que A es l'única part de \Omega tal que \chi_A = f.
  • Semblantment, un conjunt \Omega no és equipotent al conjunt \mathcal{P}(\Omega) de les seves parts.
    Per provar-ho (per reducció a l'absurd), suposem l'existència d'una bijecció f : \Omega \to \mathcal{P}(\Omega) i definim el conjunt A = \{x \in \Omega | x \notin f(x)\}.
    Com que A \in \mathcal{P}(\Omega) i f és bijectiva, existeix un element (únic) \ x_0 del conjunt \Omega tal que \ f(x_0) = A.
    Llavors: 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 x_0: així, hem provat que no existeix cap suprajecció f : \Omega \to \mathcal{P}(\Omega)).

Cas dels conjunts finits i dels conjunts infinits[modifica | modifica el codi]

Conjunts equipotents a un conjunt finit[modifica | modifica el codi]

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[modifica | modifica el codi]

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é[modifica | modifica el codi]