Ensembles de cardinal infini

1. Autre définition rigoureuse d'un ensemble infini.
2. Cardinal d'un ensemble infini.
3. Quelques précisions sur les ensembles dénombrables (*) Card (Z ²) = Card Q
4. Quelques précisions sur les ensembles indénombrables (*)
5. Rapport dénombrable/indénombrable.
6. Hypothèse du Continu...
7. Opérations sur les cardinaux.
8. Références.

---

a) Autre définition rigoureuse d'un ensemble infini :

Un ensemble E est dit infini si on peut trouver une bijection entre lui-même et une de ses parties (strictes) F,

ie : F inclus dans E, F différent de E, F ~ E.

Dans le cas contraire, E est dit fini.

Ex : N est en bijection avec N*, par la fonction f : n --> n+1 ainsi, N est infini .

Haut de page

b) Cardinal d'un ensemble infini :

La façon parfaitement rigoureuse de définir le cardinal pour un ensemble infini s'appuie sur le théorème de Cantor-Bernstein :

Théorème :

Soient A et B deux ensembles (finis ou infinis).
Si A s'injecte dans B et B s'injecte dans A, alors A et B sont équipotents.

La démonstration est facile dans le cas fini, un peu moins dans le cas général.

Ce théorème justifie les écritures :

• Card(A) = Card(B) si A et B sont équipotents
• Card(A) ≤ Card(B) si A s'injecte dans B.

En effet, on peut alors appliquer la règle d'antisymétrie : si ( n ≤ m et m ≤ n ) alors n = m.

Écrire cette règle avec les cardinaux infinis est une simple ré-écriture du théorème de Cantor-Bernstein.

D'autre part, on a l'équivalence (moyennant l'axiome du choix) :

• Théorème : (A s'injecte dans B) équivaut à (B se surjecte sur A).

Pour la culture (merci à David Madore) :

Si A et B sont deux ensembles quelconques, alors
soit A s'injecte dans B (ie Card(A) ≤ Card(B)),
soit B s'injecte dans A (ie Card(B) ≤ Card(A)).

En d'autres termes : les cardinaux forment une classe "totalement ordonnée".

Haut de page

c) Quelques précisions sur les ensembles dénombrables (*) Card (Z ²) = Card Q

On a une injection évidente f : Q → Z²

et f(p/q) = (p,q) avec p,q premiers entre eux et q>0 [on peut rajouter f(0)=(0,1) pour être parfaitement rigoureux]

Évidemment, ce n'est pas une bijection : (4,6) par exemple n'a pas d'antécédent, puisque f(4/6) = (2,3).
On a donc Card Q ≤ Card(Z²). 

D'autre part, on a vu dans la première partie : Card (Z²) = Card Z.

Or Z s'injecte trivialement dans Q : Card Z ≤ Card Q.
De ces deux inégalités on déduit Card (Z²) = Card Q, alors qu'il serait fastidieux d'exhiber une bijection explicite entre Q et Z².

Haut de page

d) Quelques précisions sur les ensembles indénombrables (*)

La non-dénombrabilité de IR peut être prouvée en la démontrant pour le sous-ensemble J = { x tel que 0 < x < 1, x réel },
car J est équipotent à IR.

En effet, la fonction f : J → IR définie ci-contre est bijective

 

La non-dénombrabilité de J se démontre par l'absurde.

Supposons que J soit dénombrable, alors il existe une application bijective de IN sur J.
et donc

0 <--> 0, x00x01x02x03x04......... 1 <--> 0, x10x11x12x13x14......... 2 <--> 0, x20x21x22x23x24......... 3 <--> 0, x30x31x32x33x34......... Avec les xij sont dans {0,1,2,..,9}

Le nombre z = 0,y0y1y2y3y4......... avec   yi= 2   si   xii =1       yi= 1   sinon n'est jamais atteint, il y a donc contradiction.

 

e) Rapport dénombrable/indénombrable

• IR est non dénombrable.

Voici une démonstration plus indirecte du fait que IR est indénombrable, mais qui a l'avantage de préciser le rapport entre les 2,
à savoir IR ~ P(N), l'ensemble des parties de N. (*)

Soit E un ensemble. P(E) n'est jamais équipotent à E.

• Démonstration :
  Supposons qu'il existe une bijection h : E → P(E)
  Pour tout x dans E, h(x) est un sous-ensemble de E.
  Notons F = { x dans E | x n'est pas dans h(x) }.
  Par construction, F est une partie de E, donc F est dans P(E). Comme h est une bijection, F a un antécédent dans E,
  ie : il existe y dans E tel que h(y) = F = {x dans E | x n'est pas dans h(x)}
  Alors :
  - si y est dans F, par définition de F, y n'est pas dans h(y)=F. Absurde.
  - si y n'est pas dans F, par définition de F, y est dans h(y)=F. Absurde aussi.
  
  C'est donc l'hypothèse d'existence de la bijection h qui est fausse. Cqfd. (*)

 

• Card P(IN) = Card IR .

On constitue donc l'application p : P(N) → R de la façon suivante.

Soit E dans P(N). E est donc un sous-ensemble (fini ou infini) de IN.
On forme un nombre d écrit en base 2 de la façon suivante :

d = 0, d₀ d₁ d₂ d₃ d₄ d₅... où d_n = 1 si n est dans E, 0 sinon.

On a alors d dans [0,1], de façon claire (d=0 si E=ø, d=1 si E=IN).

La fonction p : E → p(E) = d est alors une surjection de P(IN) dans IR.
[Tout réel r de [0,1] est atteint, et pour connaître son antécédent, il suffit d'écrire le développement binaire de r].

En revanche, p n'est pas une bijection, en raison de l'existence de 2 développements binaires, comme pour les développements décimaux.]

D'autre part, si on fabrique l'application q comme p, mais en considérant que cette fois d est écrit en base 3 (ou 10, ou n > 2),
alors l'application q est une injection de P(IN) dans IR.
[Tous les réels ne sont pas atteints, mais chaque réel atteint a un antécédent unique.]
P(IN) se surjecte et s'injecte à la fois dans IR, donc P(N) ~ R : Card P(N) = Card R

Par généralisation du cas fini, on écrit : Card IR = Card P(IN) = 2×Card N = 2 × aleph₀

• (*) Card IN < Card IR

En effet, puisque IN est inclus (donc s'injecte) dans IR, Card IN ≤ Card IR.
De plus, on vient de montrer que Card IR = Card P(IN), et que P(IN) n'est pas équipotent à IN.
Donc Card IN < Card IR.

Haut de page

f) Hypothèse du Continu...

On définit aleph1 comme étant le plus petit cardinal strictement supérieur à aleph_0
(pour une définition plus rigoureuse de aleph₁, voir l'article de David Madore )

Le fait de savoir si Card IR = aleph₁ est indécidable d'après la construction de IR seule, c'est à dire qu'on peut arbitrairement décider que oui ou non.
Habituellement, on fait l'hypothèse que c'est bien le cas (hypothèse du Continu) : aleph₁ = Card IR.
En termes plus simples, l'hypothèse du Continu dit que : toute partie de R est soit au plus dénombrable, soit équipotente à IR.
En termes intuitifs (!) : il n'existe pas d'ensemble "strictement plus gros" que IN mais "strictement plus petit" que IR.

Haut de page

g) Opérations sur les cardinaux.

Toutes les opérations valables avec les cardinaux finis, sont extensibles aux cardinaux infinis, mais l'intérêt est moindre : Si A ou B est infini : Card (A U B) = Card A + Card B = Max (Card A , Card B)
Card (A × B) = Card A . Card B = Max (Card A , Card B)
Card (P(A)) = 2×Card(A)
L'hypothèse du Continu "dit" ainsi que aleph₁ = 2 × aleph₀.

---

h) Références

• Initiation à la théorie des ensembles, J. Breuer Dunod, 1961
• Théorie axiomatique des ensembles, Jean-Louis Krivine, Presses Universitaires de France, 1972 (niveau maîtrise)
• voir aussi : -- Théorie des ensembles, Jean-Louis Krivine, Vuibert, 1998

Haut de page