Théorie des ensembles
Axiomes de Zermelo–Fraenkel, cardinaux infinis, axiome du choix — les fondements formels de toute la mathématique.
§ 1 Les axiomes de Zermelo–Fraenkel (ZFC)
La théorie ZFC (Zermelo-Fraenkel avec l'axiome du Choix) constitue le cadre axiomatique standard des mathématiques. Tout objet mathématique est un ensemble.
- Extensionnalité : $\forall x\,\forall y\,(\forall z\,(z\in x\leftrightarrow z\in y)\rightarrow x=y)$
- Fondation (régularité) : tout ensemble non vide contient un élément disjoint de lui-même
- Schéma de compréhension : $\{x\in A : P(x)\}$ est un ensemble pour toute propriété $P$
- Paire : $\{a,b\}$ est un ensemble
- Réunion : $\bigcup A$ est un ensemble
- Schéma de remplacement : l'image d'un ensemble par une fonction (définissable) est un ensemble
- Infini : il existe un ensemble infini (contenant $\emptyset$ et stable par $x\mapsto x\cup\{x\}$)
- Parties : $\mathcal{P}(A)$ est un ensemble
- Choix (C) : voir §5
$0 = \emptyset$, $1=\{\emptyset\}$, $2=\{\emptyset,\{\emptyset\}\}$, plus généralement $n+1 = n\cup\{n\}$. $\mathbb{N}$ est le plus petit ensemble contenant $0$ et stable par successeur (axiome de l'infini).
§ 2 Opérations ensemblistes
- $A\cap B = \{x : x\in A \text{ et } x\in B\}$ (intersection)
- $A\cup B = \{x : x\in A \text{ ou } x\in B\}$ (union)
- $A\setminus B = \{x\in A : x\notin B\}$ (différence)
- $A\triangle B = (A\setminus B)\cup(B\setminus A)$ (différence symétrique)
- $\overline{A} = E\setminus A$ (complémentaire dans $E$)
$A\times B = \{(a,b) : a\in A, b\in B\}$. Dans ZFC, $(a,b) = \{\{a\},\{a,b\}\}$ (définition de Kuratowski).
$\mathcal{P}(A) = \{B : B\subset A\}$ : l'ensemble de toutes les parties de $A$. Si $|A|=n$, alors $|\mathcal{P}(A)|=2^n$.
$(\mathcal{P}(E), \cup, \cap, \overline{\cdot}, \emptyset, E)$ est une algèbre de Boole : commutativité, associativité, distributivité, idempotence ($A\cup A=A$), complémentation ($A\cup\overline{A}=E$, $A\cap\overline{A}=\emptyset$).
§ 3 Relations et fonctions
Une relation sur $A$ est un sous-ensemble $R\subset A\times A$. On note $aRb$ pour $(a,b)\in R$. Types : réflexive ($aRa$), symétrique ($aRb\Rightarrow bRa$), antisymétrique, transitive.
- Relation d'équivalence : réflexive + symétrique + transitive. Partitionne $A$ en classes $[a]_R$.
- Relation d'ordre : réflexive + antisymétrique + transitive. Ordre total si tout couple est comparable.
Une fonction $f:A\to B$ est une relation $f\subset A\times B$ telle que $\forall a\in A, \exists!b\in B : (a,b)\in f$. Propriétés :
- Injective : $f(a)=f(b)\Rightarrow a=b$
- Surjective : $\forall b\in B, \exists a\in A : f(a)=b$
- Bijective : injective et surjective $\Leftrightarrow$ inversible
Si $|A|\leq|B|$ et $|B|\leq|A|$ (i.e. il existe des injections $A\hookrightarrow B$ et $B\hookrightarrow A$), alors $|A|=|B|$ (il existe une bijection).
§ 4 Cardinaux finis et infinis
Le cardinal $|A|$ (ou $\#A$, ou $\mathrm{card}(A)$) de $A$ est sa "taille". Deux ensembles ont même cardinal ssi il existe une bijection entre eux (équipotents).
- $\aleph_0 = |\mathbb{N}|$ : cardinal des ensembles dénombrables infinis
- $\mathfrak{c} = 2^{\aleph_0} = |\mathbb{R}|$ : cardinal du continu
- $|\mathbb{Z}|=|\mathbb{N}|=\aleph_0$ (bijection : $0,1,-1,2,-2,3,-3,\ldots$)
- $|\mathbb{N}\times\mathbb{N}|=\aleph_0$ (diagonale de Cantor)
- $|\mathbb{Q}|=\aleph_0$ (fractions irréductibles, diagonale)
- Réunion dénombrable de dénombrables est dénombrable
$\mathbb{R}$ n'est pas dénombrable. De plus $|\mathbb{R}|=|(0,1)|=|\mathcal{P}(\mathbb{N})|=2^{\aleph_0}$. Autres égaux : $|\mathbb{R}^n|=|\mathbb{R}|$, $|\mathcal{C}[0,1]|=\mathfrak{c}$.
§ 5 Axiome du choix et équivalents
Pour toute famille non vide d'ensembles non vides $(A_i)_{i\in I}$, il existe une fonction de choix $f:I\to\bigcup A_i$ telle que $f(i)\in A_i$ pour tout $i$.
Dans ZF, les assertions suivantes sont toutes équivalentes à AC :
- Lemme de Zorn : Tout ensemble ordonné inductif (toute chaîne est majorée) admet un élément maximal
- Théorème de Zermelo : Tout ensemble peut être bien ordonné
- Théorème de Tychonoff : Tout produit de compacts est compact
- Tout espace vectoriel a une base
- Tout surjectif admet une section droite
- $|A|\leq|B|$ ou $|B|\leq|A|$ (comparabilité des cardinaux)
AC implique : une boule $B^3$ peut être décomposée en 5 parties (non mesurables) et réassemblée en deux boules de même taille que l'originale. Ce "paradoxe" illustre le caractère non constructif de AC.
§ 6 Nombres ordinaux
Un ordinal est un ensemble bien ordonné par $\in$, transitif ($x\in\alpha\Rightarrow x\subset\alpha$). Les ordinaux forment une classe bien ordonnée : $0=\emptyset$, $1=\{0\}$, $2=\{0,1\}$, ..., $\omega=\mathbb{N}$, $\omega+1$, ..., $\omega\cdot 2$, ..., $\omega^2$, ..., $\omega^\omega$, ..., $\varepsilon_0$, ...
- $\omega + 1 \neq 1 + \omega = \omega$ (non commutative)
- $\omega \cdot 2 = \omega + \omega \neq 2\cdot\omega = \omega$
- $\omega^\omega$ : premier ordinal $\varepsilon$ tel que $\omega^\varepsilon=\varepsilon$ est $\varepsilon_0$
Pour tout ordinal $\alpha$ et toute "règle de construction" $G$, il existe une unique fonction $f$ définie sur $\alpha+1$ telle que $f(\beta)=G(f|\beta)$ pour tout $\beta\leq\alpha$. Généralise la récurrence ordinaire à tous les ordinaux.
§ 7 Théorèmes de Cantor sur l'infini
Pour tout ensemble $A$, $|A| < |\mathcal{P}(A)|$ : l'ensemble des parties est strictement plus grand. En particulier, $\aleph_0 < 2^{\aleph_0} < 2^{2^{\aleph_0}} < \cdots$
$\mathrm{HC}$ : $2^{\aleph_0} = \aleph_1$ (il n'existe pas de cardinal strictement entre $\aleph_0$ et $\mathfrak{c}$). Cohen (1963) a montré que HC est indépendante de ZFC : elle ne peut ni être prouvée ni réfutée dans ZFC (Gödel 1940 : consistent avec ZFC ; Cohen 1963 : sa négation aussi).
| Cardinal | Notation | Exemple |
|---|---|---|
| $\aleph_0$ | Aleph zéro | $|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|$ |
| $\aleph_1$ | Premier cardinal non dénombrable | $=|\omega_1|$ (premier ordinal non dénombrable) |
| $\mathfrak{c} = 2^{\aleph_0}$ | Cardinal du continu | $|\mathbb{R}|=|\mathcal{P}(\mathbb{N})|$ |
| $\beth_1$ | Beth un | $= 2^{\aleph_0} = \mathfrak{c}$ |
| $\beth_2$ | Beth deux | $= 2^\mathfrak{c} = |\mathcal{P}(\mathbb{R})|$ |
§ 8 Paradoxes et fondements
L'ensemble $R = \{x : x\notin x\}$ (ensemble de tous les ensembles n'appartenant pas à eux-mêmes) conduit à une contradiction : $R\in R \Leftrightarrow R\notin R$. Cela a montré que la "théorie naïve des ensembles" (Cantor, Frege) est incohérente. ZFC résout cela par le schéma de compréhension restreint : on ne peut former $\{x\in A : P(x)\}$ que si $A$ est déjà un ensemble.
L'ensemble de tous les ordinaux serait lui-même un ordinal, donc il s'appartiendrait, contredisant la fondation. Solution ZFC : la collection de tous les ordinaux est une classe propre, pas un ensemble.
- 1er théorème : Toute théorie formelle cohérente suffisamment expressive (comme ZFC) contient des énoncés vrais qu'elle ne peut pas prouver.
- 2e théorème : Une telle théorie ne peut pas prouver sa propre cohérence.
Conséquence : ZFC ne peut pas prouver "ZFC est cohérente" (si elle l'est !).
- NBG (von Neumann–Bernays–Gödel) : distingue ensembles et classes, conservative sur ZFC
- MK (Morse–Kelley) : version plus forte de NBG
- NF (New Foundations, Quine) : axiomatique différente, encore peu explorée
- Théorie des types (Russell, puis Martin-Löf) : alternative fondée sur les types