• Aide pour la navigation
  • Page d'accueil
  • Mise à jour
  • A faire
  • Rechercher
  • Plan du site
• Contacts
  • Connexion
  • Livre d'or
  • Forum
  • Auteurs
  • Liens
• Grandes parties
  • International (en)
  • Maths
  • Smileys
  • Programmation
  • Nos Programmes
  • Nos jeux
  • Jeux vidéo
• Nos Demos
  • Sommaire « Nos démos »
  • Somme directe de sous-espaces vectoriels
  • Non prouvabilité dans ZF de l'existence de bons ordres
  • Démonstrations et algorithmes : infiniment longs ou impossibles ?
  • Existence d'une base dans un espace vectoriel bien ordonnable
  • Parties indéfinissables par le schéma d'axiomes de séparation
  • Terme général d'une suite u(n+1) = au(n) + b
  • Coefficients directeurs
  • Critère de divisibilité
  • Critère de divisibilité par B+1 en base B
  • Série de puissance
  • Ensembles bien ordonnables

Introduction

Cet article nécessite quelques pré-requis. Pour les notions fondamentales sur la logique et la théorie des ensembles, je vous recommande le cours de Patrick Dehornoy [1]. Quant aux notations utilisées, vous pouvez en plus vous reporter aux préliminaires de [2]. Dans toute la suite, on supposera la consistance de ZF.

Le but est de montrer la non prouvabilité dans ZF des trois énoncés suivants :

1. "Si $E$ est bien ordonnable, alors $\wp \left(E\right)$ est bien ordonnable."
2. "Si $E$ et $F$ sont bien ordonnables, alors $F^E$ est bien ordonnable."
3. "Le produit d'une famille d'ensembles bien ordonnables indexée par un ensemble bien ordonnable est bien ordonnable."

En particulier, ma tentative de démonstration précédente sur l'existence d'un bon ordre sur $ℝ$ sans utiliser l'axiome du choix [3], dont la proposition 4.5 aurait impliqué le premier point, ne peut être achevée de la sorte.

Notons que l'on a un résultat plus fort, à savoir que ces énoncés sont non seulement indémontrables mais aussi indécidables dans ZF. En effet, on sait que la consistance de ZF entraîne celle ZFC et aussi que ZFC prouve ces trois énoncés via le théorème de Zermelo. Par conséquent si leurs négations étaient prouvables dans ZF elles le seraient a fortiori dans ZFC et cela contredirait sa consistance.

Énoncés et démonstrations

Théorème

ZF ne prouve pas "Pour tout ensemble $E$ bien ordonnable, $\wp \left(E\right)$ est bien ordonnable."

Lemme (ZF)

Si pour tout ensemble $E$ bien ordonnable, $\wp \left(E\right)$ est bien ordonnable alors pour tout ordinal $\alpha$, $V_{\alpha }$ est bien ordonnable.

Démonstration

Par induction ordinale :

• $V_0=\varnothing$ est trivialement bien ordonnable.
• Pour tout ordinal $\alpha$, si $V_{\alpha }$ est bien ordonnable alors $\wp \left(V_{\alpha }\right)=V_{\alpha +1}$ l'est aussi par hypothèse.
• Pour tout ordinal limite $\lambda$, si pour tout $\alpha <\lambda$, $V_{\alpha }$ est bien ordonnable, alors $V_{\lambda }=\bigcup _{\alpha <\lambda }{V}_{\alpha }$ aussi. Ceci découle d'un résultat plus général conçernant l'existence d'un bon ordre sur une réunion bien ordonnable d'une famille d'ensembles bien ordonnables [3]. Dans le cas présent, on peut utiliser un argument direct : on définit un bon ordre sur $V_{\lambda }$ en disant que $x\le y$ si et seulement si $\mathrm{rang}\left(x\right)<\mathrm{rang}\left(y\right)$ ou que les rangs sont égaux à un même ordinal $\alpha <\lambda$ avec $x$ inférieur à $y$ pour le bon ordre sur $V_{\alpha }$. □

Démonstration du théorème

Supposons l'énoncé prouvable, alors par le théorème de complétude, il est vrai dans tout modèle $M$ de ZF. Un élément $E$ d'un tel modèle est inclus dans $V_{\mathrm{rang}\left(E\right)+1}^M$ donc la restriction à $E$ d'un bon ordre sur $V_{\mathrm{rang}\left(E\right)+1}^M$ est un bon ordre sur $E$. Par conséquent, le théorème de Zermelo et a fortiori l'axiome du choix est vrai dans $M$. A nouveau par le théorème de complétude, on aurait $\mathrm{ZF}├\mathrm{AC}$, alors que l'axiome du choix est bien connu pour être indécidable dans ZF [1]. D'où une contradiction. □

Corollaire

ZF ne prouve pas les énoncés :

• "Si $E$ et $F$ sont bien ordonnables, alors $F^E$ est bien ordonnable."
• "Le produit d'une famille d'ensembles bien ordonnables indexée par un ensemble bien ordonnable est bien ordonnable"

Démonstration

Si l'énoncé était prouvable il serait vrai dans tout modèle $M$ de ZF. En l'appliquant à tout ensemble $E$ bien ordonnable et à $F=\{0^M,1^M\}$ qui est bien ordonnable, sachant que $F^E$ est équipotent à $\wp \left(E\right)$ on obtient que $M$ satisfait le premier énoncé. Par le théorème de complétude, le premier énoncé serait prouvable dans ZF. Contradiction.

On peut appliquer le même raisonnement pour le dernier énoncé qui implique évidemment les deux autres. □

Conclusion

Cette étude a montré que les opérations simples sur des ensembles bien ordonnés n'assuraient pas la bonne ordonnabilité des nouveaux ensembles sans recours à l'axiome du choix, contrairement à ce que l'on aurait pu espérer après les résultats obtenus en [3]. Informellement, on perd la possibilité de transporter des bons ordres lorsque l'on considère un ensemble plus "gros". En particulier ceci montre qu'on ne peut espérer construire sans axiome du choix une exponentiation ordinale pour laquelle ${\alpha }^{\beta }$ serait l'ordinal isomorphe à l'ensemble ${}^{\beta }\alpha$. C'est pourquoi la définition retenue [1] consiste à ne considèrer qu'une partie de cet ensemble sur laquelle on sait construire un bon ordre explicite...

Références

1. Dehornoy Patrick - « Logique et théorie des ensembles », Notes de cours, FIMFA ENS
   Disponible à l'adresse http://www.math.unicaen.fr/~dehornoy/surveys.html
2. Kanamori Akihiro - « The Higher infinite», Second Edition
3. Wang Frédéric - « Ensembles bien ordonnables »
   Disponible à l'adresse http://www.maths-informatique-jeux.com/maths/nos_demos/bons_ordres/index.php

Cette page est conforme aux normes du W3C - Auteur : Frédéric WANG - Dernière mise à jour : dimanche 18 février 2007