Worldlex Wiki Exemples
- Tout sous-ensemble d'un ensemble totalement ordonné nombres ordinaux (plus précisément, il s'agit d'ordres bien définis ).
- Si fonction injective de ordre lexicographique sur le produit cartésien d'une famille d'ensembles totalement ordonnés, indexés par un ensemble bien ordonné , est lui-même un ordre total.
- L'ensemble des nombres réels ordonnés par les relations usuelles « inférieur ou égal à » (≤) ou « supérieur ou égal à » (≥) est totalement ordonné. Par conséquent, tout sous-ensemble des nombres réels est totalement ordonné, comme les nombres naturels , les entiers et les nombres rationnels . On peut montrer que chacun d'eux est l'unique « exemple initial » (à un isomorphisme d'ordre près) d'un ensemble totalement ordonné possédant une certaine propriété (ici, un ordre total borne supérieure .
- Les entiers forment un ensemble initial non vide totalement ordonné sans borne supérieure ni inférieure .
- L'ensemble des nombres rationnels forme un ensemble initial totalement ordonné, dense dans l'ensemble des nombres réels. De plus, la réduction réflexive < est un ordre dense sur l'ensemble des nombres rationnels.
- Les nombres réels forment un ensemble initial non borné totalement ordonné qui est connexe dans la topologie d'ordre (définie ci-dessous).
Un exemple courant d'utilisation du terme « chaîne » pour désigner des sous-ensembles totalement ordonnés est le lemme de Zorn, qui affirme que si toute chaîne d'un ensemble partiellement ordonné espace vectoriel possède des bases de Hamel et qu'un anneau possède des idéaux maximaux .
Dans certains contextes, les chaînes considérées sont isomorphes à l'ordre des nombres naturels, avec leur ordre usuel ou leur ordre opposé . Dans ce cas, une chaîne peut être identifiée à une suite monotone et est appelée chaîne ascendante ou chaîne descendante , selon qu'elle est croissante ou décroissante.
Un ensemble partiellement ordonné satisfait la condition de chaîne descendante si toute chaîne descendante finit par se stabiliser. Par exemple, un ordre est bien fondé s'il satisfait cette condition. De même, la condition de chaîne ascendante signifie que toute chaîne ascendante finit par se stabiliser. Par exemple, un anneau noethérien est un anneau dont les idéaux satisfont la condition de chaîne ascendante.
Dans d'autres contextes, seules les chaînes qui sont des ensembles finis sont considérées. On parle alors de chaîne finie , souvent abrégée en chaîne . La longueur d'une chaîne est alors le nombre d'inégalités (ou d'inclusions) entre éléments consécutifs de la chaîne ; autrement dit, le nombre d'éléments de la chaîne moins un. Ainsi, un singleton est une chaîne de longueur nulle, et un couple ordonné est une chaîne de longueur un. La dimension d'un espace est souvent définie ou caractérisée comme la longueur maximale des chaînes de sous-espaces. Par exemple, la dimension d'un espace vectoriel est la longueur maximale des chaînes de sous-espaces vectoriels , et la dimension de Krull d'un anneau commutatif est la longueur maximale des chaînes d' idéaux premiers .
Le terme « chaîne » peut également désigner certains sous-ensembles totalement ordonnés de structures qui ne sont pas des ensembles partiellement ordonnés. Les chaînes régulières de polynômes en sont un exemple. On peut également utiliser « chaîne » comme synonyme de parcours dans un graphe .
Autres concepts
Théorie des réseaux
On peut définir un ensemble totalement ordonné comme un type particulier de treillis , à savoir un treillis dans lequel on a
On écrit alors a ≤ b si et seulement si . Par conséquent, un ensemble totalement ordonné est un treillis distributif .
Commandes totales finies
Un simple argument de dénombrement permet de vérifier que tout ensemble fini non vide totalement ordonné (et donc tout sous-ensemble non vide de celui-ci) possède un plus petit élément. Ainsi, tout ordre total fini est en fait un bon ordre . Soit par une démonstration directe, soit en observant que tout bon ordre est isomorphe à un ordinal , on peut montrer que tout ordre total fini est isomorphe à un segment initial des nombres naturels ordonnés par <. Autrement dit, un ordre total sur un ensemble à k éléments induit une bijection avec les k premiers nombres naturels. Par conséquent, il est courant d'indexer les ordres totaux finis ou les bons ordres de type ω par des nombres naturels de manière à respecter l'ordre (en commençant par zéro ou par un).
théorie des catégories
Les ensembles totalement ordonnés forment une sous-catégorie complète de la catégorie des ensembles partiellement ordonnés , les morphismes étant des applications qui respectent les ordres, c'est-à-dire des applications f telles que si a ≤ b alors f ( a ) ≤ f ( b ).
Une application bijective entre deux ensembles totalement ordonnés qui respecte les deux ordres est un isomorphisme dans cette catégorie.
topologie de l'ordre
Pour tout ensemble totalement ordonné intervalles ouverts
- topologie sur n’importe quel ensemble ordonné, la topologie d’ordre .
Lorsqu'on utilise plusieurs ordres sur un ensemble, on parle de topologie d'ordre induite par un ordre particulier. Par exemple, si N est l'ensemble des nombres naturels, normale .
Complétude
Un ensemble totalement ordonné est dit complet si tout sous-ensemble non vide possédant une borne supérieure admet une borne supérieure minimale . Par exemple, l'ensemble des nombres réels ℝ est complet, mais l'ensemble des nombres rationnels ℝ ne l'est pas. Autrement dit, les différentes notions de complétude (à ne pas confondre avec la « totalité ») ne s'appliquent pas aux restrictions . Par exemple, sur l'ensemble des nombres réels , une propriété de la relation non vide S de ℝ possédant une borne supérieure dans ℝ admet une borne supérieure minimale (ou supremum) dans ℝ . Cependant, pour les nombres rationnels, ce supremum n'est pas nécessairement rationnel ; par conséquent, cette propriété ne s'applique pas à la restriction de la relation treillis complet est compact . On peut citer comme exemples les intervalles fermés de nombres réels, par exemple l' intervalle unité [0,1], et le système des nombres réels étendu affinement (la droite réelle étendue). Il existe des homéomorphismes préservant l'ordre entre ces exemples.
Sommes des ordres
Pour deux ordres totaux disjoints quelconques et , il existe un ordre naturel sur l'ensemble , appelé la somme des deux ordres ou parfois simplement :
- En effet , est vrai si et seulement si l'une des conditions suivantes est vraie :
Intuitivement, cela signifie que les éléments du deuxième ensemble sont ajoutés aux éléments du premier ensemble.
Plus généralement, si est un ensemble d'indices totalement ordonné, et si pour chaque est une structure d'ordre linéaire, où les ensembles sont deux à deux disjoints, alors l'ordre total naturel sur est défini par
- Pour , est valable si :
Décidabilité
La théorie du premier ordre des ordres totaux est décidable , c'est-à-dire qu'il existe un algorithme permettant de déterminer quelles assertions du premier ordre sont vraies pour tous les ordres totaux. Grâce à l'interprétabilité dans S2S , la théorie monadique du second ordre des ordres totaux dénombrables est également décidable.
Ordres sur le produit cartésien d'ensembles totalement ordonnés
Il existe plusieurs façons d'étendre deux ensembles totalement ordonnés à un ordre sur le produit cartésien , même si l'ordre résultant peut n'être que partiel . Voici trois de ces ordres possibles, classés de manière à ce que chaque ordre soit plus fort que le précédent :
- Ordre lexicographique : ( a , b ) ≤ ( c , d ) si et seulement si a < c ou ( a = c et b ≤ d ). Il s'agit d'un ordre total.
- ( a , b ) ≤ ( c , d ) si et seulement si a ≤ c et b ≤ d (l' ordre produit ). Il s'agit d'un ordre partiel.
- ( a , b ) ≤ ( c , d ) si et seulement si ( a < c et b < d ) ou ( a = c et b = d ) (la clôture réflexive du produit direct des ordres totaux stricts correspondants). Il s'agit également d'un ordre partiel.
Chacun de ces ordres prolonge le suivant, en ce sens que si x ≤ y dans l'ordre produit, cette relation est également vraie dans l'ordre lexicographique, et ainsi de suite. Ces trois ordres peuvent être définis de manière analogue pour le produit cartésien de plus de deux ensembles.
Appliquées à l' espace vectoriel R n , chacune de ces propriétés en fait un espace vectoriel ordonné .
Voir aussi des exemples d'ensembles partiellement ordonnés .
Une fonction réelle de n variables réelles définie sur un sous-ensemble de R n définit un ordre faible strict et un préordre total correspondant sur ce sous-ensemble.
Structures apparentées
- v
- t
- e
| Symétrique | Antisymétrique | Connecté | Bien fondé | A des joints | A rencontré | Réfléchi | Irréflexif | Asymétrique | |
| Total, Semiconnecté | Anti- réflexif | ||||||||
| relation d'équivalence |  Y | ✗ | ✗ | ✗ | ✗ | ✗ | Y | ✗ | ✗ |
| Précommande (Quasicommande) | ✗ | ✗ | ✗ | ✗ | ✗ | ✗ | Y | ✗ | ✗ |
| Commande partielle | ✗ | Y | ✗ | ✗ | ✗ | ✗ | Y | ✗ | ✗ |
| Précommande totale | ✗ | ✗ | Y | ✗ | ✗ | ✗ | Y | ✗ | ✗ |
| Commande totale | ✗ | Y | Y | ✗ | ✗ | ✗ | Y | ✗ | ✗ |
| Précommande | ✗ | ✗ | Y | Y | ✗ | ✗ | Y | ✗ | ✗ |
| Bien quasi-commander | ✗ | ✗ | ✗ | Y | ✗ | ✗ | Y | ✗ | ✗ |
| Bien ordonné | ✗ | Y | Y | Y | ✗ | ✗ | Y | ✗ | ✗ |
| Treillis | ✗ | Y | ✗ | ✗ | Y | Y | Y | ✗ | ✗ |
| Jointure-semi-treillis | ✗ | Y | ✗ | ✗ | Y | ✗ | Y | ✗ | ✗ |
| Rencontre-semi-treillis | ✗ | Y | ✗ | ✗ | ✗ | Y | Y | ✗ | ✗ |
| Ordre partiel strict | ✗ | Y | ✗ | ✗ | ✗ | ✗ | ✗ | Y | Y |
| ordre faible strict | ✗ | Y | ✗ | ✗ | ✗ | ✗ | ✗ | Y | Y |
| Commande totale stricte | ✗ | Y | Y | ✗ | ✗ | ✗ | ✗ | Y | Y |
| Symétrique | Antisymétrique | Connecté | Bien fondé | A des joints | A rencontré | Réfléchi | Irréflexif | Asymétrique | |
| Définitions, pour tous et |
YLe symbole « + » indique que la propriété de la colonne est toujours vraie pour le terme de la ligne (à l'extrême gauche), tandis que le symbole « ✗ » indique que la propriété n'est pas garantie en général (elle peut être vraie ou fausse). Par exemple, le fait que toute relation d'équivalence soit symétrique, mais pas nécessairement antisymétrique, est indiqué par « + » dans la colonne « Symétrique » et par « ✗ » dans la colonne « Antisymétrique ». YToutes les définitions exigent tacitement que la relation homogène soit transitive : pour tout si et alors La définition d'un terme peut exiger des propriétés supplémentaires qui ne sont pas répertoriées dans ce tableau.
Une relation binaire antisymétrique, transitive et réflexive (mais pas nécessairement totale) est un ordre partiel .
Un groupe dont l'ordre total est compatible est un groupe totalement ordonné .
Il n'existe que quelques structures non triviales qui soient des réduits (interdéfinissables) d'un ordre total. Omettre l'orientation conduit à une relation d'intermédiarité . Omettre la position des extrémités conduit à un ordre cyclique . Omettre les deux données conduit à l'utilisation de la séparation par paires de points pour distinguer, sur un cercle, les deux intervalles déterminés par une paire de points.