Théorème de Cantor-Bernstein
-Enoncé
Soit X et Y deux ensembles.-DémonstrationS'il existe une injection de X vers Y et une autre de Y vers X, alors les deux ensembles sont en bijection.
Si X et Y sont en bijection, alors X et Z sont en bijection
Soit f : Y X, bijective.
Posons A =
On a alors f( (Z - X) A ) = A
En effet f( (Z - X) A ) = f(Z - X) f(A) = f(Z - X) ()
= = A
Comme Z peut être partitionné en (Z - X) A et (X
- A), on pose
g : Z X
a (Z - X) A f(a)
a (X - A) a
g est alors bijective car ses restrictions à (Z - X) A
et (X - A) (qui forment une partition) sont f et l'identité
qui sont bijectives.
Finalement il existe bien une bijection entre X et Z.
Soit j une injection de X vers Y.
Soit y une injection de Y vers X.
On a j(X) Y et y(Y) X donc y(j(X)) y(Y) X
Comme j est injective, X et j(X) sont en bijection.
De même, comme y est injective, y(j(X)) et j(X) sont en bijection.
D'où X et y(j(X))
sont en bijection.
En utilisant le lemme sur y(j(X)), y(Y) et X, il vient
X est en bijection avec y(Y)
Comme y est injective, Y est en bijection avec y(Y) et finalement
X et Y sont en bijection
- La partie la plus difficile de la démonstration est celle du lemme, dont le résultat peut sembler évident au premier abord.
-Un énoncé équivalent à ce théorème
est :
Soit X et Y deux ensembles.
S'il existe une surjection de X vers Y et une autre de Y vers
X, alors les deux ensembles sont en bijection.