Quelques rudiments de théorie des ensembles.
Théorie des ensembles
– autres systèmes axiomatiques – construction des ensembles usuels
Ce chapitre, à vocation plutôt culturelle qu’utilitaire, est délibérement bref. Il peut être laissé de côté en première lecture. Le lecteur intéressé est renvoyé à [KRI] par exemple. Quoique directement peu utile à l’agrégation et dans la vie quotidienne de l’enseignement en mathématique, et encore moins utile pour l’ingénieur, la théorie des ensembles, comme la logique que nous abordons peu, constitue la base des mathématique ainsi qu’une bonne gymnastique intellectuelle.
Les axiomes de la théorie des ensembles de Zermelo-Fraenkel
Une classe est associée à une propriété d’un seul élément; c’est-à-dire que l’on se donne une assertion comportant une et une seule variable libre; un élément est dans la classe correspondante s’il vérifie la propriété. Les prédicats comportant plusieurs variables libres sont appelées relations. Éventuellement on peut avoir une distinction entre des variables et des paramètres; dans ce cas on a une classe pour chaque valeur possible des paramètres.
La théorie des ensembles est basée sur un ensemble d’axiomes. Les objets de cette théorie sont appelés ensembles, et la classe des ensembles est appelée univers. Les axiomes de la théorie des ensembles de Zermelo-Fraenkel sont les suivants:
\(\bullet\ \) Axiome d’extensionnalité : \[\forall x \forall y (\forall z (z \in x \iff z \in y) \rightarrow x=y)\] (deux ensembles sont égaux si et seulement si ils contiennent exactement les mêmes éléments)
Axiome de l’union : \[\forall x \exists y \forall z (z \in y \iff \exists t ( t \in x \land z \in t ))\] (une union d’ensembles est un ensemble)
Axiome de l’ensemble des parties : \[\forall x \exists y \forall z ( z\in y \iff z \subset x )\] (les parties d’un ensemble forment un ensemble)
Axiome du schéma de remplacement :Étant donné une formule \(E(x,y,z_0,...,z_n)\) de paramètres \(z_0,...,z_n\), définissant pour toute valeur des \(z_i\) une fonction, alors: \[\forall z_0 ... \forall z_n \left( \forall x \forall y \forall y' E(x,y,z_0,...,z_n)\land E(x,y',z_0,...,z_n) \rightarrow y=y'\right)\] \[\rightarrow \forall t \exists w \forall v \left( v \in w \iff \exists u ( u \in t \land E(u,v,z_0,...,z_{n}) )\right)\]
On ajoute usuellement un axiome supplémentaire à ces axiomes: l’axiome de l’infini, qui affirme qu’il existe un ordinal infini. Nous verrons plus loin ce qu’est un ordinal, et ce qu’est un ordinal fini.
(Une théorie est consistante si elle ne permet pas de prouver à la fois un énoncé et sa négation).
On appelle paire l’ensemble \(\{x,y\}\). Ne pas confondre avec le couple \((x,y)\), qui désigne en fait l’ensemble \(\{\{x\},\{x,y\}\}\). On note de même \((x,y,z)\) l’ensemble \((x,(y,z))\), et ainsi de suite pour les \(n\)-uplets ordonnés. La différence entre \(\{x_0,...,x_n\}\) et \((x_0,...,x_n)\) est que dans le premier cas l’ordre des termes (et même leurs nombres d’apparitions) n’importe pas, alors que dans le second il importe. On démontre l’associativité et la commutativité de l’union. On notera \({\cal P}(E)\) l’ensemble des parties de l’ensemble \(E\).
Intuition On notera que toutes les opérations intuitives sur les ensembles sont possibles, ou presque. On peut utiliser les intersections, définir l’ensemble des éléments d’un ensemble donné qui vérifient une propriété donnée, on peut travailler sur l’ensemble des parties d’un ensemble, on peut travailler sur un produit cartésien d’ensembles, toutes choses sans lesquelles les mathématiques seraient moins commodes. Notons qu’on peut aussi montrer l’existence et l’unicité de l’ensemble vide.
La taille des ensembles : ordinaux, cardinaux
On présente ci-dessous les nombres ordinaux et les nombres cardinaux.
Les ordinaux
Un ensemble est dit transitif si tout élément de cet ensemble est inclu dans cet ensemble. C’est-à-dire que si \(S \in E\), alors \(S \subset E\) (non, il n’y a pas de faute de frappe!).
Par exemple les ensembles suivants sont des ordinaux: \(\emptyset\), \(\{\emptyset\}\), \(\{ \emptyset,\{\emptyset\}\}\), \(\{\emptyset,\{\emptyset\},\{ \emptyset, \{ \emptyset \} \} \}\).
L’ensemble \(\{\emptyset, \{\{\emptyset\}\}\}\) n’en est pas un.
\(\bullet\)Tout élément d’un ordinal est un ordinal.
\(\bullet\)Le second point est laissé en exercice.
\(\bullet\)\(O \in P\)
\(\bullet\)\(P \in O\)
La relation \(\in\) est donc une relation d’ordre total sur la classe des ordinaux.
\(\bullet\)La relation \(\in\) est un bon ordre sur la classe des ordinaux.
\(\bullet\)Le plus petit élément de la classe des ordinaux plus grands que \(E\) est \(E\cup\{E\}\).
\(\bullet\)\(E\) appartient à tout ordinal plus grand que \(E\), et \(E\) est inclus dans tout tel ordinal; donc tout élément de la classe des ordinaux plus grands que \(E\) doit contenir l’union de \(E\) et \(\{E\}\). L’ensemble \(E \cup\{E\}\) est bien un ordinal contenant \(E\), donc plus grand que \(E\); il est donc bien le plus petit ordinal plus grand que \(E\).
Ce théorème étonnant a notamment pour corollaire que la classe (ne pas dire « l’ensemble »!) des cardinaux infinis est isomorphe à la classe des ordinaux. On peut montrer par ailleurs que si une certaine propriété \(P\) à une seule variable libre vérifie : \[\mbox{$P(E)$ est vrai pour tout ordinal $E$ plus petit que $F$, alors la $P$ est vraie pour $F$},\] alors on peut conclure que la propriété \(P(E)\) est vraie pour tout ordinal \(E\). Ceci est une induction sur les ordinaux (on parle aussi d’induction transfinie). Il faut noter que la condition [inductransfinie] contient l’initialisation de l’induction, car l’équation [inductransfinie] implique \(P(\emptyset)\).
Les cardinaux
Cette section est consacrée aux nombres cardinaux, plus connus que les ordinaux.
\(\boxcircle\) Le théorème de Cantor-Bernstein
Représentation schématique de la démonstration du théorème de Cantor-Bernstein.
\(\bullet\)On montre que cet ensemble admet un élément maximal pour l’union (car il est stable par réunion).
\(\bullet\)On montre ensuite que le maximum \(X\) vérifie \(g(f(X)^c) \cup X = E\).
\(\boxcircle\) L’axiome du choix et ses dérivés
\(\diamond\) Généralités - rappels
label@diamond-guxe9nuxe9ralituxe9s—rappels@finlabel
Une relation d’ordre strict est une relation \(<\) telle que \(\leq\) définie par \(x \leq y \iff (x=y \lor x < y)\) soit une relation d’ordre, et telle que pour tout \(x\), on a \(\neg (x < x)\).
Un élément \(x\) d’une partie \(E\) est un minimum de cette partie \(E\) si et seulement si \(x \in E\) et si \(\forall e \in E \ e \geq x\).
Un élément \(x\) d’une partie \(E\) est un élément minimal de \(E\) si et seulement si \(x \in E\) et si \(((e \in E) \land (e \leq x)) \rightarrow e=x\).
Un élément \(x\) est dit minorant d’une partie \(E\) si \(\forall e \in E \ e \geq x\); il n’est pas nécessaire que \(x\) soit dans \(E\).
On définit de même maximum, élément maximal, majorant en remplaçant\(\leq\) par \(\geq\).
\(\diamond\) L’axiome du choix
On montre que ces deux axiomes sont équivalents. Pour des applications intéressantes de l’axiome du choix on pourra consulter la section [funzorn].
Il est difficile de montrer ce théorème à partir de l’axiome du choix. La réciproque est par contre simple.
On appelle chaîne un ensemble totalement ordonné, c’est-à-dire tel que deux éléments de cet ensemble soient toujours comparables.
Le lemme de Zorn est équivalent au théorème de Zermelo, lui même équivalent aux deux versions de l’axiome du choix. On peut montrer le théorème de Zermelo à partir du lemme de Zorn en considérant l’ensemble des bons ordres sur des parties de \(E\), un couple \((X,{\cal R})\) étant inférieur à un couple \((X',{\cal R}')\), avec \(X\) et \(X'\) des parties de \(E\) et \({\cal R}\) et \({\cal R}'\) des bons ordres sur respectivement \(X\) et \(X'\), si \(X \subset X'\), \({\cal R}\subset {\cal R}'\), et si \(x \in X \wedge x' \in X' \wedge x'{\cal R}'x, \ \rightarrow \ x' \in X\).
L’axiome du choix permet par exemple de démontrer l’existence d’une base pour tout espace vectoriel. L’axiome du choix est équivalent à l’existence d’une injection de \(A\) dans \(B\) ou de \(B\) dans \(A\) pour tous ensembles \(A\) et \(B\); la preuve de ce fait à partir du lemme de Zorn se fait simplement, en considérant les bijections entre des parties de \(A\) et des parties de \(B\), par contre la réciproque est difficile.
L’axiome de fondation est l’assertion selon laquelle dans tout ensemble non vide il existe un élément d’intersection vide avec cet ensemble; l’axiome de fondation sera plus détaillé en [fondation].
Si la théorie axiomatique de Zermelo-Fraenkel avec axiome de fondation est consistante, alors la théorie de Zermelo-Fraenkel avec axiome de fondation et axiome du choix est consistante.
Si la théorie axiomatique de Zermelo-Fraenkel est consistante, alors la théorie de Zermelo-Fraenkel avec axiome du choix est consistante.
D’autre part si la théorie de Zermelo-Fraenkel est consistante, alors la théorie de Zermelo-Fraenkel avec la négation de l’axiome du choix (i.e. en supposant qu’il existe un ensemble sur lequel on ne peut pas construire une relation de bon ordre) est consistante.
Intuition Il est aussi possible de remplacer la négation de l’axiome du choix par le fait que \({\cal P}({\omega})\) ne puisse pas être bien ordonné; une telle théorie est consistante si la théorie avec axiome de fondation est consistante (voir la définition [ensembles:omega] de \(\omega\)).
\(\diamond\) Quelques exercices
On peut énoncer sans l’axiome du choix:
\(\boxcircle\) Définition des cardinaux. Ordinaux finis et infinis
Il est évident qu’il s’agit là d’une relation d’équivalence.
L’axiome du choix permet de démontrer le théorème suivant:
On notera que \(Card\) (qui est par définition la classe des cardinaux) n’est pas un ensemble; sinon on pourrait construire un ensemble égal à \(On\) (qui est par définition la classe des ordinaux), ce qui est impossible comme précédemment souligné.
On notera que cette définition pose quelques petits problèmes (il faut préciser quels deux ensembles respectivement équipotents à \(A\) et \(B\) on utilise). Il est nécessaire de préciser « disjointe » pour éviter des pathologies, et cela implique de ne pas prendre simplement \(A\) et \(B\) mais bien deux ensembles respectivement équipotents à \(A\) et \(B\). Une fois la définition bien posée, on montre que l’addition de cardinaux est commutative et associative.
Une propriété importante est le fait que la somme des \(E_i\) pour \(i \in I\) est le plus grand élément entre \(\overline {\overline I}\) et les \(E_i\), sous réserve que l’un au moins de ces ensembles (\(I\) ou l’un des \(E_i\)) soit infini.
Il convient de vérifier que les produits de deux couples d’ensembles de mêmes cardinaux respectifs sont bien les mêmes (si \(A\) et \(A'\) sont équipotents, si \(B\) et \(B'\) sont équipotent, alors \(A\times B\) et \(A'\times B'\) sont équipotents). On peut en outre vérifier que la multiplication de cardinaux est associative et commutative, et distributive par rapport à l’addition. On notera que le produit de deux cardinaux non-finis est le plus grand de ces deux cardinaux.
On vérifiera facilement que la définition a bien un sens. On peut aussi montrer que \(A^{B+C}=A^B\times A^C\) et que \({A^B}^C=A^{B\times C}\).
Il faut bien noter que \(\emptyset\) est un ordinal fini pour cette définition (il s’agit du reste bien d’un entier naturel, du moins pour la définition usuelle française d’un entier naturel). Cette définition des entiers naturels n’est bien sûr pas la plus intuitive pour des lycéens. Elle permet par contre de construire, dans la théorie des ensembles, un modèle de l’arithmétique, ce qui montre que si la théorie des ensembles est consistante, alors l’arithmétique (de Péano) l’est aussi. Cette définition a aussi le mérite de montrer que l’on peut construire tout l’édifice standard des mathématiques à partir de la théorie des ensembles et de la logique. Il est à noter que l’axiome du choix, précédemment cité, est plus discutable que les autres au niveau du caractère standard . Plus complexe que les autres axiomes, il introduit en outre des cas particuliers: les ensembles non-mesurables. D’autres axiomes peuvent être choisis en remplacement de cet axiome. Ce point ne sera pas plus développé ici.
On montre diverses choses commodes et intuitives sur les ordinaux finis; ils sont stables par union, produit, exponentiation. On montre aussi que tout ordinal fini est un cardinal.
Nous supposons maintenant l’axiome de la théorie des ensembles selon lequel il existe un ordinal infini. Un ordinal infini est, par définition, un ordinal qui n’est pas fini. Cet axiome de la théorie des ensembles est équivalent à l’axiome selon lequel la classe des ordinaux finis est un ensemble; ainsi, puisque la classe des ordinaux n’est pas un ensemble, il existe un ordinal infini. On peut encore formuler cet axiome en disant qu’il existe un ordinal limite, au vu de la définition ci-dessous:
Un ensemble est dit fini si son cardinal est fini.
Un ensemble est dit dénombrable si son cardinal est inférieur ou égal à \({\omega}\) (on trouve parfois la définition: cardinal égal à \({\omega}\), selon les auteurs).
Quelques axiomes supplémentaires
On a déjà évoqué l’axiome du choix, fort débattu, tant sa position centrale dans les mathématiques le fait positionner directement au contact de la théorie des ensembles standards. On va ici passer à d’autres axiomes importants, pris ou non dans les mathématiques selon les choix de chacun. Il faut noter que l’on sait (en logique) que l’on ne peut « fermer » la théorie des ensembles (au sens de la complétude) en lui adjoignant des axiomes, tout en restant cohérent, jusqu’à ce qu’on ne puisse plus rien ajouter sans être redondant ou incohérent. Le théorème dit d’incomplétude de Gödel assure qu’une telle construction est impossible.
On ne s’aventurera que peu en logique dans cet ouvrage. Il convient d’être prudent en logique à moins de bien maîtriser son sujet; il existe deux théorèmes dits d’incomplétude de Gödel et un théorème dit de complétude. Ces complétudes et incomplétudes ne sont bien sûr pas la négation les uns des autres; l’incomplétude est celle de tout système axiomatique suffisamment fort, la complétude est celle de la logique.
L’axiome d’accessibilité
Un cardinal est dit accessible s’il n’est pas inaccessible.
Nous donnons sans preuve un théorème difficile:
Axiome dit de l’hypothèse du continu
Le théorème de Cantor nous dit que \(\aleph_{E+1}\leq 2^{\aleph_E}\) (il est clair que \(2^{\aleph_E}\) est le cardinal de l’ensemble des parties de \(E\)).
Nous donnons aussi, sans preuve, le théorème difficile suivant:
L’axiome de fondation
Cet axiome entraîne, par exemple, qu’il n’existe pas d’ensemble \(x\) tel que \(x =\{x\}\), ni plus généralement d’ensemble \(x\) tel que \(x \in x\).
Nous ne donnerons pas, encore une fois, la démonstration du difficile résultat de consistance relative suivant:
La preuve, laissée en exercice simple, nécessite l’axiome de fondation et en est une bonne application. Le résultat suivant est par contre difficile:
\(\bullet\)\(u \in v\)
\(\bullet\)\(u=v\)
Bien sûr on peut montrer que si ces hypothèses sont vérifiées alors pour tout couple \((u,v)\) c’est l’une et une seule des assertions qui est vérifiée. Le résultat suivant est lui aussi non-trivial et nécessaire à la définition de fermeture transitive:
Un ensemble extensif est isomorphe à un ensemble transitif, et l’isomorphisme est unique (nécessitant l’axiome de fondation).
Résumé de théorie des ensembles
En résumé on a les implications de consistance du schéma [consis].
Commentaire: \(ZF\) désigne la théorie de Zermelo-Fraenkel. \(ZF \setminus infini\) désigne la même théorie mais privée de l’axiome de l’infini et muni de sa négation. \(AC\) désigne l’axiome du choix. \(not(AC)\) désigne un axiome qui est incompatible avec \(AC\); cette « négation » est laissée sans plus de précision ici (voir e.g. [KRI] pour plus d’informations). \(COH\) désigne l’axiome selon lequel les parties de \({\omega}\) ne peuvent pas être bien ordonnées. \(AF\) désigne l’axiome de fondation. \(ACC\) désigne l’axiome d’accessibilité. \(CH\) désigne l’hypothèse du continu, et \(GCH\) l’hypothèse du continu généralisée. Une flèche relie une théorie \(T\) à une théorie \(T'\) si \(T'\) est plus forte que \(T\), c’est-à-dire que tous les théorèmes de \(T\) sont des théorèmes de \(T'\). Notez que toutes les théories présentes sur la figure sont consistantes si et seulement si \(ZF\) est consistante. Notez aussi que si \(ZF\) est consistante, alors il est impossible de le prouver (théorème d’incomplétude de Gödel); mais que par contre si elle ne l’est pas, on dispose d’un algorithme théorique permettant en temps fini de le prouver (il suffit d’énumérer toutes les preuves, l’une après l’autre, jusqu’à ce que 0=1 soit établi par une démonstration; cet algorithme termine bien en temps fini si une inconsistance existe).
Ensembles ordonnés
Ordres et graphes sont très liés. On commencera ici par les ordres, avant de passer aux graphes, sur lesquels une vision plus algorithmique sera proposée.
Ordres
Soit \(E\) un ensemble. Un ordre (partiel) sur \(E\) est une relation \(\leq\) telle que pour tout \((x,y,z) \in E^3\):
\(\bullet\)\(x \leq x\)
\(\bullet\)\((x \leq y \land y \leq x) \rightarrow x=y\)
\(\bullet\)\((x \leq y \land y \leq z) \rightarrow x \leq z\)
Ces trois propriétés sont respectivement la réflexivité, l’antisymétrie et la transitivité.
\(E\) équipé d’un tel ordre est appelé ensemble partiellement ordonné .
Un ordre \(\leq\) donne naissance à une relation d’inégalité stricte \(<\) par : pour tout \(x\) et tout \(y\), on a \(x<y \iff (x \leq y \land x \neq y)\).
On définit aussi:
\(\bullet\)\(x \geq y \iff y \leq x\)
\(\bullet\)\(x \not \leq y \iff \neg ( x \leq y)\)
\(\bullet\)\(x \parallel y \iff x \not \leq y \land y \not \leq x\) (\(x\) et \(y\) ne sont pas comparables)
Soit \(F\) un sous-ensemble de \(E\), \(E\) étant muni d’un ordre partiel \(\leq_E\); on définit l’ordre partiel \(\leq_E\) induit sur \(F\) par : pour tout \(x\) et tout \(y\), on a \(x \leq_F y \iff x \leq_E y\).
Un ensemble \(E\) muni d’un ordre partiel \(E\) est dit totalement ordonné si et seulement si \(\forall (x,y) \in E^2, x \leq y \lor y \leq x\). Un ensemble totalement ordonné est aussi appelé une chaîne. Un ensemble tel que \(x \leq y \rightarrow x=y\) est appelé une antichaîne.
Une chaîne \(C\) contenue dans \(E\) est dite maximale dans \(E\) si et seulement si quel que soit l’élément \(x \not\in C\), l’ensemble \(C \cup \{x\}\) n’est pas une chaîne.
Une antichaîne \(C\) est dite maximale si et seulement si quel que soit l’élément \(x \not\in C\), l’ensemble \(C \cup \{x\}\) n’est pas une antichaîne.
On note \(n\) la chaîne \([[0,n[[\) (pour la cohérence de cette notation avec la définition des entiers naturels, on peut se référer à la construction des entiers naturels par les ordinaux, plus haut).
Dans la suite du texte \(\leq\) désigne une relation d’ordre partiel.
Étant donné \(\leq\), on définit la relation de couverture \(\prec\) par \(x \prec y\) (\(y\) couvre \(x\) ou \(x\) est couvert par \(y\)) si et seulement si \(x < y \land \forall z ( x \leq z <y \rightarrow z=x)\). Ceci signifie qu’il n’y a pas de \(z\) tel que \(x<z<y\).
Si \(E\) est fini, la relation de couverture détermine la relation d’ordre partiel (et réciproquement).
On définit maintenant le diagramme de Hasse pour un ensemble fini partiellement ordonné. À chaque élément de \(E\) on associe un point du plan, et on trace une ligne de \(x\) à \(y\) si \(x \prec y\). On veille à ce que ces lignes n’intersectent pas les autres points, et on veille à ce que \(x \prec y\) implique que l’ordonnée du point associé à \(x\) soit inférieure à l’ordonnée du point associé à \(y\).
Une application \(\phi : E \rightarrow F\) est dite:
\(\bullet\ \) croissante si \(x \leq y \rightarrow \phi (x) \leq \phi (y)\).
\(\bullet\)un morphisme si \(x \leq y \iff \phi(x) \leq \phi (y)\).
\(\bullet\)un isomorphisme d’ordre si c’est un morphisme d’ordre bijectif.
Quand \(\phi\) est un morphisme, on écrit \(\phi : E \hookrightarrow F\).
Quand \(\phi\) est un isomorphisme on écrit \(E \cong F\) pour signifier qu’il existe un isomorphisme de \(E\) vers \(F\) ; \(E\) et \(F\) sont alors dits isomorphes.
Soit \(\phi\) bijective de \(E\) dans \(F\) avec \(E\) et \(F\) finis; alors les trois énoncés suivants sont équivalents:
\(\bullet\) \(\phi\) est un isomorphisme d’ordre
\(\bullet\)\(x < y\) dans \(E\) si et seulement si \(\phi (x) < \phi (y)\) dans \(F\)
\(\bullet\)\(x \prec y\) dans \(E\) si et seulement si \(\phi (x) \prec \phi (y)\) dans \(F\)
Deux ensembles finis ordonnés sont isomorphes si et seulement si on peut leur construire un même diagramme de Hasse.
Le dual d’un ensemble ordonné est le même ensemble mais muni de l’ordre \(\leq ^ \delta\) tel que \(x \leq ^ \delta y\) si et seulement si \(y \leq x\). Le dual d’un énoncé \(\psi\) est l’énoncé \(\psi ^ \delta\) obtenu en remplaçant \(\leq\) par \(\geq\) et réciproquement.
Un énoncé est vrai pour tous les ensembles ordonnés si et seulement si son dual est vrai pour tous les ensembles ordonnés.
Soit \(F\) sous-ensemble de \(E\) tel que \(F \subset E\), avec \(E\) ordonné. \(F\) est un idéal d’ordre si et seulement si \((x \in F \land y \leq x) \rightarrow y \in F\). \(F\) est un filtre d’ordre si et seulement si \((x \in F \land x \leq y) \rightarrow y \in F\).
\(F\) est un filtre d’ordre si et seulement si le complémentaire de \(F\) est un idéal d’ordre.
On définit \(\downarrow F\) par l’ensemble des \(x\) tel que pour un certain \(y\) dans \(F\) on a \(x \leq y\). Par abus d’écriture, \(\downarrow x\) est égal à \(\downarrow \{x\}\). \(\downarrow F\) se lit section initiale engendrée par \(F\).
On définit \(\uparrow F\) par l’ensemble des \(x\) tel que pour un certain \(y\) dans \(F\) on a \(y \leq x\). Par abus d’écriture \(\uparrow x\) est égal à \(\uparrow \{x\}\). \(\uparrow F\) se lit section finale engendrée par \(F\).
\(\downarrow F\) est donc le plus petit idéal d’ordre contenant \(F\), et \(\uparrow F\) est le plus petit filtre d’ordre contenant \(F\).
On note \(O(E)\) l’ensemble des idéaux d’ordre de l’ensemble ordonné \(E\).
Les trois énoncés suivants sont équivalents:
\(\bullet\)\(x \leq y\)
\(\bullet\)\(\downarrow x \subset \downarrow y\)
\(\bullet\)\((\forall F \in O(E)) y \in F \rightarrow x \in F\)
\(x\) est maximal si et seulement si pour tout \(y\), on a \(x \leq y \rightarrow x=y\)
\(x\) est le maximum de \(E\) si et seulement si \(x\in E\) et si pour tout \(y\), on a \(y \leq x\). On écrit \(x=max E\). Notons que certains ensembles n’ont pas de maximum (e.g., \([0,1[\) pour la relation d’ordre usuelle)
Les notions de minimal et d’élément minimum sont définies de manière duale, en renversant l’ordre.
L’élément maximum d’un ensemble \(E\) est généralement noté \(\top E\), et l’élément minimum est généralement noté \(\bot E\).
Lorsque l’ensemble est fini, l’ensemble des éléments maximaux et l’ensemble des éléments minimaux sont des anti-chaînes maximales.
Lorsqu’une chaîne \(\{ x_1,\dots,x_n\}\) avec \(x_1<x_2<...<x_n\) est maximale, alors \(\forall i \ x_i \prec x_{i+1}\) (démonstration: en cas contraire, on aurait, pour un certain \(z\), \(x_i < z < x_{i+1}\), et donc la chaîne pourrait être augmentée par ajout de \(z\), ce qui contredit le fait qu’elle est maximale).
On appelle généralement:
\(\bullet\ \) graphe de la relation le graphe dans lequel on supprime les réflexivités.
\(\bullet\ \) graphe de compatibilité l’ensemble des \((x,y)\) avec \(x\) comparable à \(y\).
\(\bullet\ \) graphe de Hasse (ne pas confondre avec diagramme de Hasse) l’ensemble des \((x,y)\) tels que \(x \prec y\).
\(\bullet\ \) graphe de couverture l’ensemble des \({x,y}\) tels que \(x \prec y\) ou \(y \prec x\).
Construisons un exemple classique d’isomorphisme d’ordre. Soit \(X= \{ 1,2,...,n \}\), et soit \(\phi : P(X) \rightarrow \{ 0,1 \} ^n\) défini par \(\phi (A) = ( \epsilon_1, ... , \epsilon_n )\) avec \(\epsilon_i = 1\) si \(i \in A\) et \(\epsilon_i=0\) sinon. Alors \(\phi\) est un isomorphisme d’ordre des parties de \(X\) dans \([[0,1]]^n\).
Construisons maintenant des ensembles ordonnés classiques.
L’ensemble \(Y^X\) des applications d’un ensemble \(X\) vers un ensemble ordonné \(Y\) est naturellement ordonné par \(f \leq g \iff \forall x \ f(x) \leq g(x)\). Si \(X\) est lui-même ordonné, on peut considérer simplement l’ensemble des applications croissantes, que l’on note \(Y^{<X>}\).
On peut aussi considérer des fonctions au lieu de considérer des applications; on considère alors que \(f \leq g\) si et seulement si pour tout élément \(x\) du domaine de définition de \(f\) on a \(f(x) \leq g(x)\).
Pour manier ‘confortablement’ l’ensemble des fonctions de \(X\) dans \(Y\) on ajoute un élément \(\bot\) dans \(Y\) inférieur à tous les éléments (\(Y_\bot=Y\cup \{ \bot \}\) et \(\forall x\in Y, \bot < x\)), et en remplaçant une fonction par l’application qui lui est égale sur son domaine de définition et qui est égale à \(\bot\) en dehors de ce domaine. Cette fonction qui à une fonction de \(X\) dans \(Y\) associe une application de \(X\) dans \(Y_{\bot}\) est un isomorphisme d’ordre.
Graphes
Les graphes sont des outils indispensables en informatique; par exemple, les graphes acycliques (le terme anglais direct acyclic graphs sera plus facile à trouver sur www) sont très utiles en compilation et en optimisation de code. Les graphes sont aussi le support de ce que l’on appelle les réseaux bayésiens, utilisés pour la modélisation statistique. Ils servent aussi à l’étude des réseaux, dont Internet; en particulier, on s’intéresse souvent dans ce cas aux graphes aléatoires. La recherche d’un tri topologique est importante aussi en mathématiques appliquées, pour l’optimisation multi-objectifs par exemples. Enfin, la recherche de plus court chemin sur un graphe, sous des formes très variées, a un vaste réseau d’applications. On pourra trouver une introduction aux graphes et aux algorithmes qui les concernent dans [GM].
On note \(\Gamma^+(x)\) l’ensemble des \(y\) tels que \((x,y) \in U\); on l’appelle ensemble des successeurs de \(x\).
On note \(\Gamma^-(x)\) l’ensemble des \(y\) tels que \((y,x) \in U\); on l’appelle ensemble des prédécesseurs de \(x\).
On note \(d^+(x)=|\Gamma^+(x)|\) le degré sortant ou degré externe de \(x\).
On note \(d^-(x)=|\Gamma^-(x)|\) le degré entrant ou degré interne de \(x\).
Si \(d^-(x)=0\) \(x\) est appelé une source.
\(\bullet\)\(\exists x \in X \ d^-(x)=0\).
Voici un algorithme déterminant si oui ou non un graphe est sans circuit ou non. La structure de données employée consiste en une liste de successeurs pour chaque sommet.
Algorithme sans-circuit(\(G\))
\(d^-(x)=0\)
Pour tout \(x \in X\) faire
Pour tout \(y \in \Gamma^+(x)\) faire
\(d^-(y) \leftarrow d^-(y) + 1\)
\(Source \leftarrow \emptyset\)
\(Nbsommets \leftarrow 0\)
Pour tout \(x \in X\) faire
Si \(d^-(x)=0\) alors \(Source \leftarrow Source \cup \{x\}\).
Tant que \(Source \neq \emptyset\) faire
\(x \leftarrow choix(Source)\)
\(Source \leftarrow Source\backslash \{ x \}\)
\(Nbsommets \leftarrow Nbsommets +1\)
Pour chaque successeur \(y\) de \(x\) faire
\(d^-(y) \leftarrow d^-(y) - 1\)
Si \(d^-(y)=0\) alors
\(Source \leftarrow Source \cup \{ y \}\).
Si (\(Nbsommets=n\)) alors \(G\) est sans circuit sinon \(G\) a au moins un circuit.
La complexité de cet algorithme est \(O(n+m)\) avec \(n\) le nombre de sommets et \(m\) le nombre d’arcs. \(Source\) peut être implémentée sous forme de liste, avec pour fonction de choix la fonction simplissime qui choisit le premier élément.
Notons que la permutation calculée par l’algorithme précédent (ie. l’ordre de sortie de \(Source\)) est un tri topologique.
L’algorithme suivant sert à engendrer tous les tris topologiques:
Algorithme Tri-topologique(\(G\))
Calculer \(d^-(x)\) (comme dans l’algorithme précédent)
\(S \leftarrow \emptyset\)
Pour tout \(x \in X\) faire
Si \(d^-(x)=0\) alors \(S \leftarrow S \cup \{ x \}\)
\(\sigma \leftarrow \emptyset\) Tri-topo(\(G,S,\sigma\))
avec la procédure récursive Tri-topo suivante :
Algorithme Tri-topo(\(G,S,\sigma\))
Pour tout \(x \in S\) faire
\(S' \leftarrow S - \{ x \}\)
\(\sigma \leftarrow \sigma . x\) (concaténation)
Pour tout \(y \in \Gamma^+(x)\) faire
\(d^-(y) \leftarrow d^-(y) - 1\)
Si \(d^-(y)=0\) alors
\(S' \leftarrow S' \cup \{ y \}\)
Tri-topo(\(G,S',\sigma\))
Pour tout \(y \in \Gamma^+(x)\) faire
\(d^-(y) \leftarrow d^-(y) - 1\)
\(\sigma \leftarrow \sigma\) privé de \(x\)
La complexité est en \(O((n+m) * | L(G) |)\), où \(L(G)\) est le nombre de tri topologiques, \(n\) est le nombre de sommets, \(m\) est le nombre d’arcs.
Il existe des algorithmes de complexité \(O(n*|L(G)|)\) (beaucoup plus compliqués).
Pour aller plus loin, le lecteur est encouragé à consulter [BOU].
Bibliographie
- [KRI] J.-L. Krivine, Introduction to axiomatic set theory, D. Reidel Publishing Company, Dordrecht-Holland.[GM] M. Gondran, M. Minoux Graphes et algorithmes, 2e édition, Eyrolles, 1986.[BOU] Vincent Bouchitté, Brice Goglin, Jean-Baptiste Rouquier, Graphes et algorithmique des graphes, http://laure.gonnord.org/site-ens/mim/graphes/cours/cours_graphes.ps Licence ’OpenContent’, Ecole Normale Supérieure de Lyon, 1998.
Barre utilisateur
[ID: 16] [Date de publication: 6 mars 2021 14:56] [Catégorie(s): Le cours d'agrégation ] [ Nombre commentaires: 0] [nombre d'éditeurs: 1 ] [Editeur(s): Emmanuel Vieillard-Baron ] [nombre d'auteurs: 5 ] [Auteur(s): Christophe Antonini Olivier Teytaud Pierre Borgnat Annie Chateau Edouard Lebeau ]
Commentaires sur le cours
Documents à télécharger
L'article complet
Continuer à lire

Séries entières et fonctions holomorphes

Polynômes

Fourier

Graphes

Ensembles ordonnés

Polynômes à plusieurs indéterminées

Produit de convolution

Combinatoire et dénombrements

Dénombrements et probabilités

Quelques résultats supplémentaires de théorie des nombres

Géométrie affine et projective

Géométrie projective

Zoologie de la géométrie

Fonctions holomorphes

Statistique

Analyse fonctionnelle

Quelques résultats inclassables

Analyse numérique et mathématiques appliquées

Topologie

Espaces \({\cal L}^p\) et espaces \(L^p\)

Développements limités et comparaison de fonctions

Approximation de fonctions

Calcul différentiel

Extrema

Formes différentielles

Théorie des groupes

Anneaux et corps

Corps

Algèbre linéaire

Algèbre multilinéaire

Espaces préhilbertiens et espaces de Hilbert

Algèbre linéaire en dimension finie

Intégration

Réduction des endomorphismes
