Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Ensemble bien ordonné
Résumé
En mathématiques, un ensemble ordonné (E, ≤) est bien ordonné et la relation ≤ est un bon ordre si la condition suivante est satisfaite :
Toute partie non vide de E possède un plus petit élément. Formellement cela donne ∀X⊆E, X≠∅ ⇒ (∃u∈X, ∀v∈X u≤v).
Si (E, ≤) est bien ordonné alors ≤ est nécessairement un ordre total, c'est-à-dire que deux éléments quelconques x et y de E sont toujours comparables. En effet, l'ensemble { x, y } possède un plus petit élément, donc on a x ≤ y ou y ≤ x.
Si de plus l'axiome du choix dépendant est vérifié, cette propriété (être bien ordonné) est équivalente, pour un ordre présupposé total, à la condition de chaîne descendante « il n'existe pas de suite infinie strictement décroissante ». D'après le théorème de Zermelo, l'axiome du choix dans toute sa force équivaut au fait que tout ensemble peut être bien ordonné.
Toute partie d'un ensemble bien ordonné est elle-même bien ordonnée (pour l'ordre induit).
L'ensemble vide est bien ordonné par sa seule relation : (Ø, Ø) (c'est le plus petit ordinal).
Plus généralement, tout ensemble totalement ordonné fini est bien ordonné. Un tel ensemble ordonné est caractérisé (à isomorphisme près) par le nombre n d'éléments de l'ensemble, ce qui légitime la notation n pour le type d'ordre correspondant.
Si définit un ordre bien fondé sur et une chaîne de , la restriction est un bon ordre.
L'ensemble (N, ≤) des entiers naturels, muni de son ordre usuel, est bien ordonné ; il est souvent noté ω dans ce contexte.
Si est une famille d'ensembles bien ordonnés et si est muni d'un bon ordre, alors :
si est fini, sur le produit , l'ordre lexicographique est un bon ordre. Pour quatre exemples de produits d'un couple de bons ordres, voir n×p, 2×N, N×2 et N×N (isomorphes respectivement aux ordinaux produits pn, ω2, 2ω (= ω) et ω) ;
l'union disjointe est bien ordonnée par : si ou ( et ). Ce bon ordre s'appelle la somme ordinale de la famille. Remarquons que . La somme ordinale d'un couple de bons ordres se note . Pour trois exemples, voir ω + ω (= ω2) et 3 + ω, ω + 3 (⊂ ω2).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.