En raison de limitations techniques, la typographie souhaitable du titre, « Exercice : Relation d'ordre Relation (mathématiques)/Exercices/Relation d'ordre », n'a pu être restituée correctement ci-dessus.
Soient trois éléments d'un ensemble ordonné. On suppose que et existent. Montrer que existe et qu'il est égal à .
Solution
Notons , , et montrons que .
.
Soit une partie non vide et bornée de . Déterminer, en fonction de et :
et , où (pour ) ;
, où .
Montrer que ne dépend pas seulement de et .
Solution
Si , . Si , .
.
Les deux ensembles et ont le même inf et le même sup, mais l'inf de leur valeur absolue est 0 pour le premier et 1 pour le second.
Soient deux fonctions majorées.
Établir et donner un exemple ou l'inégalité est stricte.
En déduire et un exemple ou l'inégalité est stricte.
Solution
est un majorant de donc est supérieur ou égal au plus petit majorant, . Soit et . Alors, .
D'après la question précédente, et l'inégalité est stricte pour et .
Déterminer, si elles existent, les bornes supérieures et inférieures des parties suivantes, en précisant de plus si elles appartiennent à la partie considérée.
Dans (muni de sa relation d'ordre usuelle), toute partie non vide et majorée possède une borne supérieure.
Non. Exemple : n'a pas de borne supérieure dans .
Oui et même toute partie majorée (vide ou pas) possède une borne supérieure, puisque l'ensemble des majorants de est non vide donc possède un plus petit élément (par définition des bons ordres).
Pour cet ordre, le disque admet-il des majorants ? des éléments maximaux ? un plus grand élément ? une borne supérieure ?
Mêmes questions pour le carré .
Solution
Vérification immédiate.
L'ensemble des majorants de est , donc . L'ensemble des éléments maximaux de est le quart de cercle . n'a pas de maximum puisqu'il a plusieurs maximaux (ou : puisque ).
a mêmes majorants (donc même borne supérieure) que . Cette borne supérieure appartient à donc est le plus grand élément de et par conséquent, l'unique élément maximal.
Dans , on considère l'ensemble formé par les termes de la suite définie par . admet-il une borne supérieure ? un plus grand élément ? une borne inférieure ? un plus petit élément ?
Même question avec la suite définie par .
On considère l'ensemble ordonné .
Existe-t-il des éléments maximaux dans (si oui, lesquels ?) Existe-t-il des éléments minimaux dans (si oui, lesquels ?)
L'ensemble admet-il des majorants ? une borne supérieure ? un plus grand élément ? des éléments maximaux ? des minorants ? une borne inférieure ? un plus petit élément ? des éléments minimaux ?
Soit un ensemble. On considère l'ensemble ordonné . Dans chacun des deux cas qui suivent, le sous-ensemble de admet-il des majorants ? une borne supérieure ? un plus grand élément ? des éléments maximaux ? des minorants ? une borne inférieure ? un plus petit élément ? des éléments minimaux ?
avec .
avec .
Solution
et .
donc , , n'existe pas.
Le seul élément maximal (c'est-à-dire le seul entier naturel sans multiple strict) est et le seul élément minimal (entier naturel sans diviseur strict) est .
Les majorants de sont les multiples de , donc , donc n'existe pas. Dans , tous les éléments sauf 2 sont maximaux (il y en a plusieurs, ce qui redémontre que n'existe pas). Le seul minorant de est , donc , donc n'existe pas. Dans , tous les éléments sauf 4 sont minimaux (il y en a plusieurs, ce qui redémontre que n'existe pas).
Soit . Les majorants de sont les quatre parties de qui contiennent donc donc n'existe pas. Dans , tous les éléments sauf sont maximaux. Le seul minorant de est , donc , donc n'existe pas. Dans , les éléments minimaux sont et .
Le seul majorant de est donc donc n'existe pas. Le seul minorant de est , donc , donc n'existe pas. Dans , les éléments minimaux sont les singletons et les maximaux sont leurs complémentaires.
L'ensemble des parties finies de a-t-il des éléments minimaux ? un plus petit élément ? des éléments maximaux ? un plus grand élément ? (et si oui, lesquels ?)
Mêmes questions pour l'ensemble des parties de cofinies, c'est-à-dire de complémentaire fini.
Soit un ensemble. On considère l'ensemble ordonné .
Montrer que tout sous-ensemble admet dans une borne inférieure .
On fixe désormais un ensemble de parties de et pour chaque , on pose
, puis .
Montrer que .
Montrer que si alors . La réciproque est-elle vraie ?
Pour toute partie de , montrer que , et en déduire que .
Solution
Les minorants de sont les parties de incluses dans chaque élément de . Le plus grand de ces minorants est donc l'intersection des éléments de (cette intersection étant par convention si ).
est par définition minoré par donc .
Si alors donc . La réciproque est fausse : peut même être vide et l'on a alors toute partie de , en particulier . Autre contre-exemple : et .
d'après la question 2. Si alors réciproquement, . Par conséquent, et donc .
Soit un espace vectoriel (de dimension non nécessairement finie). On considère l'ensemble des parties libres de , ordonné par l'inclusion.
Démontrer formellement que .
a-t-il des éléments minimaux ? un élément minimum ?
a-t-il des éléments maximaux ? un élément maximum ?
Solution
Une partie de est libre si . car on a bien : .
l'unique minimal.
Les maximaux de sont les bases de (car si une partie libre n'est pas une base, donc pas génératrice alors, en lui adjoignant un vecteur de qu'elle n'engendre pas, on constitue une partie libre , c'est-à-dire un majorant strict de ; et réciproquement, s'il existe une partie libre alors il existe des éléments de non engendrés par : les vecteurs de ). En général, a plusieurs bases donc n'a pas d'élément maximum. La seule exception est car dans ce cas, .
Montrer que la partie a une borne supérieure si et seulement si a un maximum.
Montrer que la partie a une borne supérieure si et seulement si a un minimum.
On dit que est un treillis complet si dans , toute partie a une borne supérieure. Montrer que le segment réel (muni de l'ordre usuel) est un treillis complet.
Soit un treillis complet. Démontrer que chaque partie de admet aussi une borne inférieure. (Une piste : en notant l'ensemble des minorants de et la borne supérieure de , montrer que tout élément de est supérieur ou égal à .)
Solution
Une partie de a un maximum si et seulement si existe et appartient à . Cela s'applique en particulier à et dans ce cas, l'appartenance à est automatique.
Dans , la partie a une borne supérieure si et seulement si l'ensemble de ses majorants a un minimum. Or .
Dans , d'après la question précédente. Considérons maintenant une partie non vide de . Puisque c'est une partie non vide et majorée de , elle admet dans une borne supérieure . On a (puisque ) et (puisque est minoré par les éléments de , qui est non vide et ). Donc est aussi la borne supérieure de dans .
Soient l'ensemble des minorants de et (qui existe puisque est un treillis complet). Tout élément de est un majorant de (par définition de ) donc de (par définition de ). Ceci prouve que est un minorant de , c'est-à-dire , c'est-à-dire , c'est-à-dire existe, c'est-à-dire existe. Remarque : on démontrerait de même (ou on en déduit, en considérant l'ordre opposé) que réciproquement, si toute partie de admet une borne inférieure alors toute partie de admet aussi une borne supérieure.
Soit une relation binaire sur un ensemble . On définit, sur l'ensemble des suites à valeurs dans , une relation par :
.
Montrer que si est transitive alors est transitive.
Démontrer la réciproque.
Solution
Supposons que est transitive et soient trois suites telles que et . Il existe alors tels que et . Posons . Alors, pour tout , on a à la fois et donc (par transitivité de ) , ce qui prouve que .
Supposons que est transitive et soient trois éléments de tels que et . Considérons les trois suites constantes définies par : . Alors, et (car et ) donc (par transitivité de ) , c'est-à-dire qu'il existe tel que . En particulier , c'est-à-dire .
Remarque sur une généralisation en remplaçant par , ensemble muni d'une relation : quelles propriétés doit vérifier ?
Dans la question 2, on aurait seulement besoin de : (qui est vrai en particulier si est réflexive).
Dans la question 1, on aurait seulement besoin de : (qui est vrai en particulier si est un ordre total ou plus généralement, « filtrant », c'est-à-dire que toute paire a un majorant).
Dans l'ensemble ordonné ( divise ), l'ensemble a-t-il :
des éléments maximaux ?
un élément maximum ?
une borne supérieure ?
Solution
Les éléments de maximaux (c'est-à-dire sans multiple strict dans ) sont et . Puisqu'il y en a plusieurs, n'a pas de maximum. Les majorants de sont les multiples communs à , , et , c'est-à-dire les multiples de , donc . (On retrouve ainsi que n'a pas de maximum, puisque .)
Dans l'ensemble ordonné , montrer que toute paire admet une borne inférieure et une borne supérieure et les reconnaître.
Solution
est l'ensemble des multiples de et est l'ensemble des diviseurs de .
Dans chaque cas, préciser le(s)quel(s), en justifiant.
Solution
est réflexive par définition. Elle est antisymétrique car si et alors donc . Elle est transitive : si et alors dès que ou , mais aussi dans le cas restant ( et ) car dans ce cas, est impair et .
est le plus petit élément de car il est impair et .
est donc l'unique élément minimal de .
est le plus petit élément de donc est sa borne inférieure.
les éléments maximaux de sont les éléments de qui n'ont pas de majorant strict dans , c'est-à-dire .
n'a pas de majorant (par exemple, et n'ont pas de majorant commun) donc pas de borne supérieure.
n'a pas de plus grand élément puisqu'il n'a même pas de borne supérieure (ou encore : puisqu'il a plusieurs maximaux).
Rappeler les définitions formelles de « est minimum » et « est minimal ».
Montrer que si est minimum alors est l'unique minimal (donc l'unique minimum).
Montrer que si l'ordre est total et si est minimal, alors il est minimum.
Montrer (par deux exemples) que peut avoir plusieurs éléments minimaux, ou aucun.
Montrer (par un exemple) que peut avoir un unique minimal et aucun minimum.
Solution
est minimum si . est minimal s'il n'a pas de minorant strict, c'est-à-dire si .
Supposons que est minimum. Alors, est minimal car pour tout , comme , on a (par antisymétrie de ) . De plus, si est minimal alors, comme , on a . Donc est l'unique minimal.
Supposons que l'ordre est total et que est minimal. Pour tout , on a (par totalité de ) ou et dans le second cas (par minimalité de ), donc dans les deux cas, , ce qui prouve que est minimum.
Soit un ensemble, et l'ensemble des parties non vides de , ordonné par l'inclusion. Les éléments minimaux de sont les singletons, et il y en a plusieurs dès que . Dans (muni de l'ordre usuel ), aucun élément n'est minimal.
Soient et , muni de l'ordre défini par : . Dans , est l'unique minimal et il n'y a pas de minimum.
Soit un ensemble ordonné. On appelle antichaîne de toute partie de dont les éléments sont 2 à 2 incomparables, c'est-à-dire tout ensemble tel que . On note l'ensemble des antichaînes de .
Dans le cas particulier où est total, décrire .
Dans le cas particulier où est (où est un ensemble fixé et désigne l'ensemble de ses parties), soit l'ensemble des parties de à éléments. Montrer que .
On revient au cas général et l'on munit de la relation définie par : pour toutes antichaînes et , . Démontrer que est une relation d'ordre sur .
Solution
Si est total, une partie est une antichaîne si et seulement si , c'est-à-dire si est un singleton ou l'ensemble vide. Donc .
Fixons . Pour tous , c'est-à-dire pour toutes parties de à éléments, on a bien (car dans un ensemble fini , la seule partie x de même cardinal que est lui-même). Donc .
est évidemment réflexive ( : il suffit de choisir ) et transitive (si et alors ). Montrons qu'elle est antisymétrique. Supposons que et que . Alors, . Et puisque (antichaîne) et , on a donc (puisque ) , donc . On a donc montré que si et alors . On en déduit (en intervertissant et ) que si et alors . On a donc bien : si et alors .
Notons la propriété . Montrer par induction que consiste à montrer que pour tout :
.
Démontrons la contraposée, donc supposons que est faux, c'est-à-dire (puisque est total) supposons que et montrons qu'alors, il existe un tel que soit faux, c'est-à-dire tel que . Il suffit de choisir : on a bien (par hypothèse), et c'est-à-dire (par hypothèse + stricte croissance de ).
Soient et deux ensembles ordonnés, une application croissante et une partie de .
Montrer que si existe alors existe et est égal à .
Donner un exemple montrant que la propriété devient fausse si l'on remplace par .
Solution
Supposons que . Alors, donc . Montrons que est non seulement un élément de , mais que c'est le plus grand. Soit , il s'agit de montrer que . Or il existe tel que . Pour un tel , on a donc (par croissance de ). On a donc bien .
Soient , (munis de l'ordre usuel, qui est même total), définie par : si et si , et . Alors, est croissante (et même strictement), et dans , on a mais dans , n'a pas de car l'ensemble de ses majorants est , qui n'a pas de plus petit élément.
Soient et deux ensembles ordonnés et une application croissante.
Montrer que si est injective alors elle est strictement croissante
Montrer (par un contre-exemple) que la réciproque est fausse.
Montrer que cette réciproque devient vraie si l'on suppose que l'ordre sur est total.
Solution
Supposons croissante et injective et montrons qu'elle est strictement croissante, c'est-à-dire montrons que . Soient tels que . On a d'une part (car est croissante et ) et d'autre part (car est injective et ). On a donc bien .
D'après l'énoncé de la question 3, pour fabriquer un contre-exemple, il est indispensable de choisir pour un ensemble ordonné pour lequel l'ordre n'est pas total. Le plus simple est muni non pas de l'ordre usuel, mais de l'égalité (c'est-à-dire qu'on définit sur par : seulement si ), qui est bien une relation d'ordre (réflexive, antisymétrique et transitive). Posons ensuite par exemple et l'application constante. n'est pas injective (). Elle est pourtant strictement croissante car on a bien puisque est toujours faux (quelles que soient les valeurs de ).
Supposons que l'ordre sur est total et que est strictement croissante, et montrons qu'elle est injective. Soient tels que , montrons que . Comme est total, on a ou . Dans le premier cas, on a (puisqu'on a supposé ), donc (puisque est strictement croissante), donc . Dans le second cas, même raisonnement en intervertissant les lettres et .
Soient deux éléments de , un élément entre les deux,
et , etc. À toute partie finie de on associe ainsi un élément , de telle sorte que les sont rangés (dans ) dans le même ordre que les indicatrices (vues comme des suites de zéros et de uns nulles à partir d'un certain rang, ordonnées lexicographiquement).
On étend cette construction à toutes les parties de en posant : .
Soit l'ensemble des parties co-infinies de (les parties de complémentaire infini). Cet ensemble a la puissance du continu comme , puisque son complémentaire, l'ensemble des parties cofinies, est dénombrable (comme l'ensemble des parties finies de ).
Il ne reste plus qu'à prouver que si dans alors dans , c'est-à-dire , c'est-à-dire . Soit tel que et soit tel que (un tel existe puisque est co-infini), alors et et conviennent.
Soient un sous-ensemble borné non vide de et une application croissante.
Prouver les inégalités .
A-t-on des informations supplémentaires si est continue ?
Montrer que et que cette quantité n'est pas nécessairement égale à .
Solution
Notons et .
Pour montrer que , il suffit de montrer que est un minorant de . Soit , il existe tel que . Or donc (car croissante), c'est-à-dire . Remarquons qu'on a prouvé au passage que le sous-ensemble (évidemment non vide) est minoré, donc que son existe bien.
De même, est un majorant de donc ( existe bien et) .
Soit , on a et , d'où .
Supposons de plus continue et montrons que l'inégalité sur les est alors une égalité (et de même pour les ). Il s'agit de prouver que . Soit une suite d'éléments de qui converge vers . Alors (par continuité de ) converge vers . Or les appartiennent à donc sont , donc leur limite aussi.
On peut ici supposer (quitte à remplacer par , ce qui ne modifie pas ni ). En appliquant le point précédent à , on en déduit . En revanche, n'est pas toujours égal à : par exemple si , tandis que .