Axiome du choix

L'axiome du choix permet de justifier l'existence d'objets "non constructibles". Par exemple, dans un espace vectoriel de dimension finie, on peut construire une base. Dans un espace de dimension infinie, on ne peut pas systématiquement en construire une, ou en identifier une... dans l'espace des polynômes $\mathbb{R}[X]$, qui est entre gros guillemets de "dimension dénombrable", on peut identifier une base $1, X, X^2,...$ mais dans l'espace $\mathbb{R}^{\mathbb{R}}$ des fonctions quelconques de $\mathbb{R}$ dans $\mathbb{R}$, laisse tomber. Pour démontrer que cet espace admet une base, on utilise le lemme de Zorn, qui est équivalent à l'axiome du choix.

Si tu es étudiant et que la BU de ta fac possède le L3 Algèbre de chez Pearson, ils montrent que l'axiome du choix, le lemme de Zorn et le principe de Zermelo sont tous équivalents.

Une autre forme très intéressante de l'axiome du choix (à mon avis en tout cas) est : toute relation d'équivalence admet un système de représentants. Vu combien d'objets mathématiques sont obtenus en faisant un quotient, je pense qu'on voit clairement l'utilité de l'axiome du choix. D'ailleurs, on peut illustrer le lien entre les deux énoncés : prendre un représentant dans chaque classe, lorsque le nombre de classes d'équivalence d'une relation donnée est infini, ça oblige à "choisir" avec l'axiome du choix.

Mais justement, comme je disais, ça fait exister des trucs qu'on ne peut pas faire exister de façon constructiviste : par exemple, on peut fabriquer ce machin-là. Jusqu'à sa construction, les matheux espéraient que toute partie de $\mathbb{R}$ serait mesurable, mais si on veut bénéficier de l'axiome du choix, il faut accepter que non.

Si tu parviens à trouver une contradiction en te servant de l'axiome du choix, alors bravo tu as obtenu une contradiction dans les maths en général ! (théorème de Gödel)

Plus précisément, Gödel a montré que si $\mathsf{ZF}$ (le système axiomatique de Zermelo-Frankel) est non contradictoire, alors on ne peut pas prouver la négation de l'axiome du choix à partir de $\mathsf{ZF}$ (et Cohen a montré que l'on ne pouvait pas montrer l'axiome du choix non plus). En conséquence, quand on fait des maths, il faut choisir (sans jeu de mot :-D ) si on travaille avec l'axiome du choix ou non.

Certaines personnes préfèrent s'en passer autant que possible (qui peut le plus peut le moins), notamment pour des raisons de constructivité : il est souvent plus satisfaisant (surtout du point de vue algorithmique) d'avoir une construction explicite qu'un argument abstrait d'existence. Un autre argument contre l'axiome du choix est l'existence d'objets pathologiques qui en découle. Comme l'a dit Homo Topi, ça implique par exemple l'existence de parties non mesurables de $\mathbb R$, ou encore le paradoxe de Banach-Tarski (lien).

Mais d'un autre côté, l'axiome du choix a des conséquences très puissantes dont il est difficile de se passer dans les maths modernes (Hahn-Banach, Krull, Zorn en général). On se restreint parfois à des variantes plus faibles de l'axiome du choix (axiome du choix dénombrable, axiome du choix dépendant), car on n'a rarement besoin de toute la généralité de l'axiome du choix, mais la non constructivité est toujours présente. Et quand on se met à creuser un peu les choses, on se rend compte qu'il y a d'autres principes premiers qui peuvent poser problème d'un point de vue logique (l'existence et la nature de l'ensemble $\mathbb N$ par exemple).

Difficile de détailler, d'autant que je ne suis pas expert. Tu peux regarder du côté de l'axiome de l'infini et des entiers non standards. Mais tu peux déjà te poser la question suivante : comment définir l'ensemble $\mathbb N$ à partir des axiomes suivant : extensionnalité, paire, union, parties,compréhension, remplacement ? Si on veut dire "bah c'est l'ensemble de tous les entiers", on est en train de dire $\mathbb N = \{n \in \mathbb N\}$, difficile de faire plus circulaire. :-D On résout ça à l'aide d'un axiome supplémentaire (axiome de l'infini), mais autant dire que ce n'est pas très satisfaisant comparé à la construction des autres ensembles de nombres (à partir de $\mathbb N$ !). Le principe de récurrence est, en un sens, inclus dans l'énoncé de l'axiome de l'infini, donc pareil, pas très satisfaisant.

La lecture du récent Théorie des ensembles de Patrick Dehornoy est chaudement recommandée pour aborder ces choses fascinantes. J'ai probablement dit des bêtises et vais me faire tomber dessus par CC. :-D

@xax : techniquement, c'est possible, mais ce n'est pas ça qui construit $\mathbb{N}$ ! Il y a une différence entre construire chaque entier naturel, et construire l'ensemble qui les contient tous (et rien d'autre).

@Poirot oui ok ça me revient un peu on ne prend pas l'existence de l'ensemble vide parce que c'est trop pénible à gérer en logique d'où l'axiomatisation dont il est déduit. Bon au moins je sais par où (re)commencer.

Je parlais de parties non Lebesgue mesurables. Il n'y a pas besoin d'axiome du choix pour montrer que $\mathcal B(\mathbb R)$ est en bijection avec $\mathbb R$. Ça se montre par récurrence transfinie, en introduisant la "hiérarchie de Borel" : $$\mathcal B_0(\mathbb R) = \{]a, b[ \mid a, b \in \mathbb R\}$$ $$\text{Pour tout ordinal } \alpha < \omega_1, \mathcal B_{\alpha+1}(\mathbb R) = \{\text{Réunions et intersections dénombrables et complémentaires d'éléments de } \mathcal B_{\alpha}(\mathbb R)\}$$ $$\text{Pour tout ordinal limite } \beta < \omega_1, \mathcal B_{\beta}(\mathbb R) = \bigcup_{\alpha < \beta} \mathcal B_{\alpha}(\mathbb R).$$ On montre qu'à chaque étape, $\mathcal B_{\alpha}(\mathbb R)$ est équipotent à $\mathbb R$ et que $\mathcal B(\mathbb R) = \displaystyle \bigcup_{\alpha < \omega_1} \mathcal B_{\alpha}(\mathbb R)$.

@Cali, je te donneune surjection explicite.

A toute suite d'entiers $u$ appliquer l'algorithme $A$ qui suit, en notant $u^+:n\mapsto u_{n+1}:$

IF $u$ commence par $0$ THEN renvoyer $]\frac{u_1}{u_2}, \frac{u_3}{u_4}[$ ELSE
IF $u$ commence par $1$ THEN renvoyer le complémentaire de $A(u^+)$ ELSE
renvoyer la réunion des suites $A(w_n)$ quand $n$ parcourt $\N$, où $\forall p: w_n (p):= (u^+)_{(2^n(2p+1))}$

qui te donne une fonction partielle envoyant surjectivement $\N^\N$ sur $B(\R)$.

Oui je détaillerai d'un PC si tu veux.

Pour info, en fait, contrairement à la complexité algorithmique, on a une échelle au comportement beaucoup plus simple avec les ensembles "peu complexes" de réels (on suppose ici travailler avec $\R\setminus \Q$ afin de disposer de nombreuses fonctions continues, rendues impossibles en environnement connexe):

Pour tout ensemble analytique qui n'est pas borélien $X$, et tout borélien $Y$ il existe une continue $f$ telle que $Y=ImageReciproqueDePar(X,f)$

Dans le contexte des partie de $\N$, ce n'est pas du tout aussi "dreamique": tu as des tas d'ensembles non récursifs, récursivement énumérables qui n'ont strictement rien d'universel. Avec $\R$ c'est bien plus simple: tout ce qui est strictement au dessus d'un échelon est universel pour cet échelon. Et en plus, c'est bien ordonné au complémentaire près, ie $(A,B)\mapsto A<B$ en termes de complexité est un pré-bon-ordre. (A condition de procéder à l'identification de complexité entre $A$ et $non(A)$ )

Tous ces résultats en fait "simples", utilisent l'axiome du choix dépendant a priori, sauf à recenser précisément quand et pour lesquels ont peut s'en passer, mais je ne crois pas qu'il existe de fascicule publié exhaustif les signalant, il faut se taper à la main la question chaque fois.

Euh attention. C'est pas parce qu'ilne faut pas "full axiome du choix" qu'il ne faut pas d'axiome du choix. Il y a des modèles de ZF où $\mathbb R$ est réunion dénombrable de parties dénombrables et donc il y a trop de boréliens (voir : par exemple)

Donc il faut au moins une pincée d'axiome du choix pour prouver qu'il y a des non boréliens, en particulier pour prouver que $B(\mathbb R)$ est de même cardinal que $\mathbb R$. Dans la preuve de Poirot, ça apparaît à plusieurs endroits : premièrement, dire qu'on peut s'arrêter à $\omega_1$, dire que des surjections suffisent à avoir une inégalité de cardinal, et dire que $\omega_1\leq \mathbb R$.

Je ne sais plus trop à quel point on peut minimiser AC dans cette preuve, j'avais été persuadé à un moment que l'AC dénombrable suffisait, mais quand j'y réfléchis vite fait il me manque un argument ou deux, donc je ne suis plus sûr (et flemme d'y réfléchir trop :-D )
Mais donc cette preuve n'est certainement pas valable dans ZF (ni celle de Christophe d'ailleurs, si elle fournit une surjection $\mathbb R\to B(\mathbb R)$ puisque ça impliquerait, dans le modèle en question, une surjection $\mathbb R\to P(\mathbb R)$ )

Soit $u$ une fonction satisfaisant ces propriétés http://www.les-mathematiques.net/phorum/read.php?16,1910442,1910698#msg-1910698 sur une partie convenable de $\N^{\N}$.
Soit $(A_n)_{n \in \N}$ une suite d'éléments de $Im(u)$. Pourquoi $\bigcup_{n\in \N} A_n$ est dans $Im(u)$ ?
On "prend" pour tout $n$, $x_n\in \N^{\N}$ tel que $u(x_n)=A_n$ et puis... oh wait.