Bon ordre - Well-order

En mathématiques , un ordre de puits (ou une relation d'ordre bien ou d' ordre bien ) sur un ensemble S est un ordre total sur S avec la propriété que chaque sous- ensemble non vide de S a un moindre élément dans cet ordre. L'ensemble S avec la relation d' ordre du bien est alors appelé un ensemble bien ordonné . Dans certains articles académiques et manuels ces termes sont plutôt écrits comme wellorder , wellordered et wellordering ou bien l' ordre , bien ordonné , et bon ordre .

Chaque ensemble bien ordonné non vide a un moindre élément. Chaque élément s d'un ensemble bien ordonné, à l'exception d'un élément le plus grand possible , a un successeur unique (élément suivant), à savoir le plus petit élément du sous-ensemble de tous les éléments supérieurs à s . Il peut y avoir des éléments en plus du moindre élément qui n'ont pas de prédécesseur (voir § Nombres naturels ci-dessous pour un exemple). Un ensemble bien ordonné S contient pour chaque sous - ensemble T avec une limite supérieure d' une borne supérieure , à savoir le plus petit élément du sous - ensemble de toutes les bornes supérieures de T à S .

Si ≤ est un ordre de puits non strict , alors <est un ordre de puits strict. Une relation est un ordre de puits strict si et seulement s'il s'agit d'un ordre total strict et bien fondé . La distinction entre les commandes de puits strictes et non strictes est souvent ignorée car elles sont facilement interconvertibles.

Chaque ensemble bien ordonné est isomorphe d'ordre unique à un nombre ordinal unique , appelé le type d'ordre de l'ensemble bien ordonné. Le théorème du bon ordre , qui équivaut à l' axiome du choix , déclare que chaque ensemble peut être bien ordonné. Si un ensemble est bien ordonné (ou même s'il admet simplement une relation bien fondée ), la technique de preuve de l'induction transfinie peut être utilisée pour prouver qu'une déclaration donnée est vraie pour tous les éléments de l'ensemble.

L'observation que les nombres naturels sont bien ordonnés par la relation habituelle moins que est communément appelée le principe de bien ordonné (pour les nombres naturels).

Nombres ordinaux

Chaque ensemble bien ordonné est isomorphe d'ordre unique à un nombre ordinal unique , appelé le type d'ordre de l'ensemble bien ordonné. La position de chaque élément dans l'ensemble ordonné est également donnée par un nombre ordinal. Dans le cas d'un ensemble fini, l'opération de base de comptage , pour trouver le nombre ordinal d'un objet particulier, ou pour trouver l'objet avec un nombre ordinal particulier, correspond à attribuer des nombres ordinaux un à un aux objets. La taille (nombre d'éléments, nombre cardinal ) d'un ensemble fini est égale au type d'ordre. Le comptage au sens quotidien commence généralement à partir de un, donc il attribue à chaque objet la taille du segment initial avec cet objet comme dernier élément. Notez que ces nombres sont un de plus que les nombres ordinaux formels selon l'ordre isomorphe, car ils sont égaux au nombre d'objets antérieurs (ce qui correspond à compter à partir de zéro). Ainsi, pour n fini , l'expression " n -ième élément" d'un ensemble bien ordonné nécessite un contexte pour savoir si cela compte à partir de zéro ou de un. Dans une notation «β-ème élément» où β peut également être un ordinal infini, il comptera généralement à partir de zéro.

Pour un ensemble infini, le type d'ordre détermine la cardinalité , mais pas l'inverse: des ensembles bien ordonnés d'une cardinalité particulière peuvent avoir de nombreux types d'ordre différents, voir la section #Nombres naturels pour un exemple simple. Pour un ensemble infini dénombrable , l'ensemble des types d'ordres possibles est même indénombrable.

Exemples et contre-exemples

Nombres naturels

L'ordre standard ≤ des nombres naturels est un ordre bien et a la propriété supplémentaire que chaque nombre naturel différent de zéro a un prédécesseur unique.

Un autre bon ordre des nombres naturels est donné en définissant que tous les nombres pairs sont inférieurs à tous les nombres impairs, et l'ordre habituel s'applique dans les paires et les cotes:

0 2 4 6 8 ... 1 3 5 7 9 ...

Il s'agit d'un ensemble bien ordonné de type d'ordre ω + ω. Chaque élément a un successeur (il n'y a pas d'élément le plus grand). Deux éléments n'ont pas de prédécesseur: 0 et 1.

Entiers

Contrairement à l'ordre standard ≤ des nombres naturels , l'ordre standard ≤ des entiers n'est pas un bon ordre, puisque, par exemple, l'ensemble des entiers négatifs ne contient pas le moindre élément.

La relation R suivante est un exemple de classement des entiers: x R y si et seulement si l' une des conditions suivantes est vérifiée:

  1. x = 0
  2. x est positif et y est négatif
  3. x et y sont tous deux positifs, et x y
  4. x et y sont tous deux négatifs, et | x | ≤ | y |

Cette relation R peut être visualisée comme suit:

0 1 2 3 4 ... −1 −2 −3 ...

R est isomorphe au nombre ordinal ω + ω.

Une autre relation pour bien ordonner les entiers est la définition suivante: x  ≤ z   y si et seulement si (| x | <| y | ou (| x | = | y | et x  ≤  y )). Cet ordre de puits peut être visualisé comme suit:

0 −1 1 −2 2 −3 3 −4 4 ...

Celui-ci a le type de commande ω.

Reals

L'ordre standard ≤ de tout intervalle réel n'est pas un ordre bien, puisque, par exemple, l' intervalle ouvert (0, 1) ⊆ [0,1] ne contient pas le moindre élément. A partir des axiomes ZFC de la théorie des ensembles (y compris l' axiome du choix ), on peut montrer qu'il existe un bon ordre des réels. Aussi Wacław Sierpiński a prouvé que ZF + GCH (l' Hypothèse de continuum généralisée ) implique l'axiome du choix et donc un puits ordre des nombres réels. Néanmoins, il est possible de montrer que les axiomes ZFC + GCH seuls ne sont pas suffisants pour prouver l'existence d'un ordre de puits définissable (par une formule) des réels. Cependant, il est cohérent avec ZFC qu'il existe un ordre de puits définissable des réels - par exemple, il est cohérent avec ZFC que V = L , et il découle de ZFC + V = L qu'une formule particulière ordonne bien les réels, voire tout ensemble.

Un sous-ensemble indénombrable des nombres réels avec l'ordre standard ≤ ne peut pas être un ordre de puits: Supposons que X est un sous-ensemble de R bien ordonné par ≤. Pour chaque x de X , soit s ( x ) le successeur de x dans ≤ ordering sur X (sauf si x est le dernier élément de X ). Soit A = {( x , s ( x )) | x X } dont les éléments sont des intervalles non vides et disjoints. Chacun de ces intervalles contient au moins un nombre rationnel, donc il y a une fonction injective de A à Q . Il y a une injection de X vers A (sauf peut-être pour un dernier élément de X qui pourrait être mappé à zéro plus tard). Et il est bien connu qu'il y a une injection de Q aux nombres naturels (qui pourrait être choisie pour éviter d'atteindre zéro). Il y a donc une injection de X aux nombres naturels, ce qui signifie que X est dénombrable. D'un autre côté, un sous-ensemble dénombrable infini des réels peut ou non être un bon ordre avec le standard "≤". Par example,

  • Les nombres naturels sont un ordre de puits sous l'ordre standard ≤.
  • L'ensemble {1 / n: n = 1,2,3, ...} n'a pas le moindre élément et n'est donc pas un bon ordre dans l'ordre standard ≤.

Exemples de commandes de puits:

  • L'ensemble des nombres {- 2 - n | 0 ≤ n <ω} a le type d'ordre ω.
  • L'ensemble des nombres {- 2 - n - 2 - m - n | 0 ≤ m , n <ω} a le type d'ordre ω 2 . L'ensemble précédent est l'ensemble des points limites dans l'ensemble. Dans l'ensemble des nombres réels, que ce soit avec la topologie ordinaire ou la topologie d'ordre, 0 est également un point limite de l'ensemble. C'est également un point limite de l'ensemble des points limites.
  • L'ensemble des nombres {- 2 - n | 0 ≤ n <ω} ∪ {1} a le type d'ordre ω + 1. Avec la topologie d'ordre de cet ensemble, 1 est un point limite de l'ensemble. Avec la topologie ordinaire (ou de manière équivalente, la topologie d'ordre) des nombres réels, ce n'est pas le cas.

Formulations équivalentes

Si un ensemble est totalement ordonné , alors les éléments suivants sont équivalents les uns aux autres:

  1. L'ensemble est bien ordonné. Autrement dit, chaque sous-ensemble non vide a un moindre élément.
  2. L'induction Transfinite fonctionne pour l'ensemble de l'ensemble commandé.
  3. Toute séquence strictement décroissante d'éléments de l'ensemble doit se terminer après seulement un nombre fini d'étapes (en supposant l' axiome du choix dépendant ).
  4. Chaque sous-ordre est isomorphe à un segment initial.

Commander la topologie

Chaque ensemble bien ordonné peut être transformé en un espace topologique en le dotant de la topologie d'ordre .

En ce qui concerne cette topologie, il peut y avoir deux types d'éléments:

  • points isolés - ce sont le minimum et les éléments avec un prédécesseur.
  • points limites - ce type ne se produit pas dans des ensembles finis, et peut ou non se produire dans un ensemble infini; les ensembles infinis sans point limite sont les ensembles de type d'ordre ω, par exemple N .

Pour les sous-ensembles, nous pouvons distinguer:

  • Sous-ensembles avec un maximum (c'est-à-dire des sous-ensembles qui sont limités par eux-mêmes); cela peut être un point isolé ou un point limite de l'ensemble complet; dans ce dernier cas, il peut ou non être également un point limite du sous-ensemble.
  • Sous-ensembles qui sont illimités par eux-mêmes mais limités dans l'ensemble entier; ils n'ont pas de maximum, mais un supremum en dehors du sous-ensemble; si le sous-ensemble n'est pas vide, ce supremum est un point limite du sous-ensemble et donc aussi de l'ensemble entier; si le sous-ensemble est vide, ce supremum est le minimum de l'ensemble entier.
  • Sous-ensembles illimités dans l'ensemble.

Un sous-ensemble est cofinal dans l'ensemble entier si et seulement s'il est illimité dans l'ensemble entier ou s'il a un maximum qui est également maximum de l'ensemble entier.

Un ensemble bien ordonné en tant qu'espace topologique est un premier espace dénombrable si et seulement s'il a un type d'ordre inférieur ou égal à ω 1 ( oméga-un ), c'est-à-dire si et seulement si l'ensemble est dénombrable ou a le plus petit type de commande indénombrable .

Voir également

Les références

  1. ^ Feferman, S. (1964). "Quelques Applications des Notions de Forçage et des Ensembles Génériques" . Fundamenta Mathematicae . 56 (3): 325–345. doi : 10.4064 / fm-56-3-325-345 .