Daniel Alibert - Cours Et Exercices Corrigés - Volume 2

Daniel ALIBERT cours et exercices corrigs volume 2 1

Daniel ALIBERT

Relations d'ordre. Entiers. Anneaux et corps. Nombres rels.

Objectifs : -Majorer, minorer, chercher le plus grand lment d'un ensemble ordonn, la borne suprieure, faire une rcurrence. - Calculer dans un anneau, un corps. - Utiliser l'ordre dans un groupe, un anneau, un corps. - Calculer dans le corps ordonn des rels : chercher une borne suprieure (ou infrieure), majorer, minorer, utiliser les intervalles.


Organisation, mode d'emploi

Cet ouvrage, comme tous ceux de la srie, a t conu, dans son format comme dans son contenu, en vue d'un usage pratique simple.

Il s'agit d'un livre d'exercices corrigs, avec rappels de cours. Il ne se substitue en aucune faon un cours de mathmatiques complet, il doit au contraire l'accompagner en fournissant des exemples illustratifs, et des exercices pour aider l'assimilation du cours. Ce livre a t crit pour des tudiants de premire et seconde annes des Licences de sciences, dans les parcours o les mathmatiques tiennent une place importante.

Il est le fruit de nombreuses annes d'enseignement auprs de ces tudiants, et de l'observation des difficults qu'ils rencontrent dans l'abord des mathmatiques au niveau du premier cycle des universits :

- difficult valoriser les nombreuses connaissances mathmatiques dont ils disposent lorsqu'ils quittent le lyce, - difficult pour comprendre un nonc, une dfinition, ds lors qu'ils mettent en jeu des objets abstraits, alors que c'est la nature mme des mathmatiques de le faire, - difficult de conception et de rdaction de raisonnements mme simples, - manque de mthodes de base de rsolution des problmes.

L'ambition de cet ouvrage est de contribuer la rsolution de ces difficults aux cts des enseignants.


Ce livre comporte quatre parties.

La premire, intitule "A Savoir", rassemble les dfinitions et rsultats qui sont utiliss dans les exercices qui suivent. Elle ne contient ni dmonstration, ni exemple.

La seconde est intitule "Pour Voir" : son rle est de prsenter des exemples de toutes les dfinitions, et de tous les rsultats de la partie prcdente, en ne faisant rfrence qu'aux connaissances qu'un tudiant abordant le chapitre considr a ncessairement dj rencontr (souvent des objets et rsultats abords avant le baccalaurat). La moiti environ de ces exemples sont dvelopps compltement, pour clairer la dfinition ou l'nonc correspondant. L'autre moiti est form d'noncs intituls "exemple traiter" : il s'agit de questions permettant au lecteur de rflchir de manire active d'autres exemples trs proches des prcdents. Ils sont suivis immdiatement d'explications dtailles.

La troisime partie est intitule "Pour Comprendre et Utiliser" : des noncs d'exercices y sont rassembls, en rfrence des objectifs. Ces noncs comportent des renvois de trois sortes : () pour obtenir des indications pour rsoudre la question, () lorsqu'une mthode plus gnrale est dcrite, () renvoie une entre du lexique. Tous les exercices sont corrigs de manire trs dtaille dans la partie 3 - 2. Au cours de la rdaction, on a souvent propos au lecteur qui souhaiterait approfondir, ou largir, sa rflexion, des questions complmentaires (QC), galement corriges de faon dtaille.

La quatrime partie, "Pour Chercher", rassemble les indications, les mthodes, et le lexique.


Certains livres d'exercices comportent un grand nombre d'exercices assez voisins, privilgiant un aspect "entranement" dans le travail de l'tudiant en mathmatiques. Ce n'est pas le choix qui a t fait ici : les exemples traiter, les exercices et les questions complmentaires proposs abordent des aspects varis d'une question du niveau du L1 L2 de sciences pour l'clairer de diverses manires et ainsi aider sa comprhension. Le lecteur est invit, propos de chacun d'entre eux, s'interroger sur ce qu'il a de gnral (on l'y aide par quelques commentaires).


Table des matires

1 A Savoir ........................................................................ 9 1-1 Ensembles ordonns ..................................... 9 1-2 Segments, intervalles.................................. 11 1-3 Entiers ........................................................ 13 1-4 Anneaux et corps ........................................ 15 1-5 Les nombres rels ....................................... 17

2 Pour Voir .................................................................... 19 2-1 Ensembles ordonns ................................... 19 2-2 Segments, intervalles.................................. 28 2-3 Entiers ........................................................ 32 2-4 Anneaux et corps ........................................ 40 2-5 Les nombres rels ....................................... 44

3 Pour Comprendre et Utiliser ...................................... 55 3-1 noncs des exercices ................................ 55 3-2 Corrigs des exercices ................................ 73 3-3 Corrigs des questions complmentaires . 129

4 Pour Chercher ........................................................... 139 4-1 Indications pour les exercices .................. 139 4-2 Mthodes .................................................. 147 4-3 Lexique ..................................................... 151


1 A Savoir

Dans cette partie, on rappelle rapidement les principales dfinitions et les principaux noncs utiliss. Vous devrez vous rfrer votre cours pour les dmonstrations. Vous trouverez des exemples dans la partie 2*Pour Voir.

1-1 Ensembles ordonns

Dfinition

Une relation rflexive, antisymtrique et transitive est une relation d'ordre. On la note gnralement , (ou ). Un ensemble muni d'une relation d'ordre est dit ordonn. Soient x et y des lments d'un ensemble ordonn, la relation :

x y et x y, est note :

x < y. Une relation d'ordre est dite totale si pour tout x et tout y on a x y ou y x. L'ensemble est alors dit totalement ordonn. Dans le cas contraire, on dit que l'ordre est partiel.

Dfinitions

Soit E un ensemble ordonn et F une partie de E. On dit que y est un majorant de F dans E, si y est un lment de E et si pour tout x de F, y x. On dfinit de mme les minorants de F dans E par :

y E, et pour tout x de F, y x.


L'ensemble des majorants de F dans E est not MajorE(F), et l'ensemble des minorants MinorE(F). Si F admet un majorant, on dit que c'est une partie majore de E. On dfinit de mme une partie minore. Si F est la fois majore et minore, on dit que c'est une partie borne.

Proprit

Un plus grand lment de F est un majorant de F qui appartient F : si F a un plus grand lment, il est unique, on le note max(F). De mme un plus petit lment de F, s'il existe, est unique, et not min(F).

Dfinition

Un lment a de E est la borne suprieure de F dans E si a est le plus petit des majorants de F dans E. Si F n'est pas major dans E, il n'a donc pas de borne suprieure. Si a existe, il est unique, on le note supE(F). Un lment de E est la borne infrieure de F dans E si c'est le plus grand des minorants de F dans E. Si cet lment de E existe, il est unique, on le note infE(F).

Proprit

Si max(F) existe, alors supE(F) existe aussi et on a max(F) = supE(F).

Dfinition

Soient E et F des ensembles ordonns, et f : E F une application. On dit que f est croissante si on a l'implication, pour tout x et tout y de E:

x y f(x) f(y). On dfinit de mme les applications dcroissantes. On dit que f est monotone si elle est croissante ou dcroissante.


Enfin, on dit que f est strictement croissante si l'implication suivante est vraie :

x < y f(x) < f(y).

1-2 Segments, intervalles

Dfinition

Soit (E, ) un ensemble ordonn ; on appelle segment ferm d'extrmits a et b, avec a b pour fixer les ides, la partie de E dfinie par :

[a , b] = {x E | a x b}. On dfinit de mme les segments ouverts, semi-ouverts. On appelle section finissante, ferme, d'origine a, la partie de E dfinie par :

[a , [ = {x E | a x}. On dfinit de mme une section commenante, not ] , a], et les sections ouvertes.

Proprit

Un segment est une partie borne, qui admet une borne suprieure et une borne infrieure.

Dfinition

Soit (E, ) un ensemble ordonn et I une partie de E. On dit que I est un intervalle de E si pour tout x et tout y de I tels que x y on a :

Tout lment z de E tel que x z y , est un lment de I.

Proprit

Tout segment est un intervalle.


Proprit

Dans un ensemble totalement ordonn, si I est un intervalle, et si a = inf(I) et b = sup(I) existent, alors I est un segment contenu dans [a , b] et contenant ]a , b[.


1-3 Entiers

Dfinition

Soit E un ensemble totalement ordonn, et x, x' des lments de E. On dit que x' est le successeur de x, et on note x' = succ(x), si :

x < x' et, ]x , x'[ = . On dfinit de mme le prdcesseur de x, not pred(x).

Proprit

Un lment x de E a au plus un prdcesseur, et au plus un successeur. S'ils existent, on a pred(succ(x)) = succ(pred(x)) = x.

Dfinition

a- Soit E un ensemble ordonn. On dit que E est bien ordonn (BO) si toute partie non vide A de E admet un plus petit lment. b- Soit E un ensemble bien ordonn. On dit que E est naturellement bien ordonn (NBO) si tout lment de E, sauf min(E), a un prdcesseur.

Proprit

Un ensemble bien ordonn est totalement ordonn.

Dfinition

On dfinit N comme un ensemble totalement ordonn, n'ayant pas de plus grand lment, dans lequel toute partie non vide a un plus petit lment, et tout lment sauf min(N) a un prdcesseur. L'ensemble N est donc un ensemble naturellement bien ordonn, sans lment maximum.


Proprit

Si E est un ensemble NBO sans lment maximum, alors il existe une bijection croissante de N sur E. En ce sens, N est "unique".

Proprit

Dans N, tout lment a un successeur.

Dfinition

Soit P : N {vrai, faux} une proprit. Soit a un lment de N. On dit que P est rcursive partir de a si pour tout x de N suprieur ou gal a on a l'implication :

si P(x) = vrai, alors P(succ(x)) = vrai.

Thorme

Soit P une proprit sur N, rcursive partir de a. S'il existe un lment b de N, plus grand que a, tel que P(b) = vrai, alors P(x) est vrai pour tout x suprieur b.

Proprit

Dans N, 1) toute partie majore a un plus grand lment. 2) les intervalles sont les segments ferms et les sections finissantes fermes.

1-4 Anneaux et corps

Dfinition

Soit (E, T, ) un ensemble muni de deux lois de composition interne. On dit que (E, T, ) est un anneau si :


1- (E, T) est un groupe commutatif, 2- est associative et admet un lment neutre diffrent du neutre de T, 3- est distributive par rapport T.

Si de plus est commutative, on dit que l'anneau est commutatif. Dans la pratique, on note le plus souvent + et les lois d'un anneau, et 0, et 1 les lments neutres respectifs de ces lois.

NB : on n'inclut pas toujours l'existence d'un lment neutre pour dans la dfinition d'un anneau. Dans ce cas, la dfinition donne ci-dessus correspond un "anneau unitaire".

Dfinition

Soit (E, T, ) un ensemble muni de deux lois de composition interne. On dit que (E, T, ) est un corps si : 1- (E, T, ) est un anneau commutatif, 2- Tout lment de E sauf le neutre de T a un symtrique pour .

Dfinition

Dans un anneau (A, +, ), un lment a est un diviseur de 0 s'il existe un lment b de A, non gal 0, tel que :

a b = 0. Un lment a est nilpotent s'il existe un entier naturel n tel que :

an = 0. Un lment a est inversible s'il existe un lment b de A tel que :

a b = 1.

Un anneau est dit intgre s'il ne possde pas de diviseur de zro diffrent de 0.


1-5 Les nombres rels

Dfinition

On appelle groupe ordonn un groupe (G, T) muni d'une relation d'ordre compatible avec T, c'est--dire telle que pour tout x, tout y, tout x', tout y' de G on ait l'implication :

x y et x' y' x T x' y T y'. (On peut composer des ingalits.)

Dfinitions

On dit qu'un groupe (G, T, ) totalement ordonn, d'lment neutre e est archimdien, si pour tout x tel que e < x, et tout y de G, il existe un entier n tel que :

y < xn. Un anneau A est ordonn si le groupe (A, +) est ordonn, et si, de plus, on a l'implication :

x 0 et y 0 x.y 0. Si A est un corps, on dit que c'est un corps ordonn s'il est totalement ordonn.

Proprit

Dans un anneau totalement ordonn, pour tout lment a, le carr a2 est suprieur ou gal 0.

Thorme et dfinition

Il existe un unique corps ordonn (R, +, ) ayant la proprit suivante : Toute partie non vide majore de R a une borne suprieure dans R.


Partie entire d'un rel. Pour tout rel a, il existe un unique entier n tel que :

n a < n+1, cet entier est appel la partie entire de a, et note E(a), ou [a]. Dveloppement dcimal d'un rel, l'ordre n. Pour tout rel a, et tout entier n, il existe un unique rationnel Dn tel que :

10nDn est entier, et Dn a < Dn + 10n , ce nombre rationnel est appel le dveloppement dcimal l'ordre n de a.

Proprit

Dans R, les intervalles sont les segments, les sections finissantes ou commenantes, et R.


2 Pour Voir

Dans cette partie, on prsente des exemples simples des notions ou rsultats abords dans la partie prcdente. Ils sont suivis de questions trs lmentaires pour vrifier votre comprhension.

2-1 Ensembles ordonns

"Une relation rflexive, antisymtrique et transitive est une relation d'ordre."

exemple 1

Sur N*= N {0}, outre la relation d'ordre usuelle, on utilise souvent la relation de divisibilit : a | b s'il existe un entier naturel n tel que :

b = n a. D'abord, a | a, videmment, quel que soit a. Si a | b et b | a, il existe p et q entiers naturels tels que a = pb, b = qa, donc a = pqa, 1 = pq donc p = q = 1 et a = b. Enfin, si a | b et b | c, il existe p et q tels que b = ap, c = bq d'o c = (pq)a, et a | c. Noter toutefois que ces deux relations sont trs diffrentes : la premire est une relation d'ordre total, la seconde est une relation d'ordre partiel. Ainsi, si symbolise la relation entre un plus petit et un plus grand, on a les schmas :

1 2 3 45 6 pour le premier ordre, et pour le second ordre :


exemple 2 ( traiter) D'autres relations d'ordre sont importantes, comme l'inclusion entre parties d'un ensemble. Dans P({1, 2, 3}), muni de la relation d'inclusion, faire un schma de relation analogue celui dessin ci-dessus. Cet ordre est-il total ?

# rponse

Il y a six lments : , {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}. Le schma ci-dessous montre, l'vidence, que l'ordre n'est pas total.


exemple 3 ( traiter) On dfinit galement un ordre sur les ensembles de fonctions valeurs dans un ensemble ordonn (R par exemple). Dans l'ensemble F(]0 , 1], R) des applications de ]0 , 1] dans R, on pose :

f g si, pour tout x de ]0 , 1], f(x) g(x).

Vrifier que c'est bien une relation d'ordre. Ordonner l'ensemble des fonctions "puissance" : x xn (n entier naturel). Cet ordre est-il total ?

# rponse

La vrification ne pose aucune difficult. Soit f, g : ]0 , 1] --. R, on a : x, f(x) f(x), donc f f.

x, f(x) g(x) et g(x) f(x) entrane f(x) = g(x), donc f = g. x, f(x) g(x), et g(x) h(x) entrane f(x) h(x).


Si m n, pour x dans ]0 , 1], xm xn, la fonction "puissance m" est donc suprieure la fonction "puissance n". Le sous-ensemble des fonctions puissances est totalement ordonn.

Par contre, l'ensemble F(]0 , 1], R) ne l'est pas ; ainsi la fonction dfinie par :

f(x) = cos(pi x) est positive ou nulle pour x dans ]0 , 1/2], et ngative ou nulle dans [1/2 , 1]. Elle n'est donc ni suprieure, ni infrieure, la fonction constante gale 0.

"Si F admet un majorant, on dit que c'est une partie majore de E. On dfinit de mme une partie minore."

exemple 4

Ci dessus, dans F(]0 , 1], R) : E = {x xn | n entier naturel}.

Cette partie est majore (par la fonction constante gale 1) et minore (par la fonction constante gale 0).

exemple 5 ( traiter) La proprit d'tre major, ou minor, pour un ensemble donn, dpend de l'ensemble de rfrence. Une partie F peut tre majore dans un ensemble E qui la contient et non majore dans une autre partie E' qui la contient galement. Soit F = {{1}, (2}, {3}}. On utilise l'ordre de l'inclusion. la partie F est-elle majore, minore, dans :

E1 = {, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}} ;


E2 = {{1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}} ; E3 = {, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}}.

# rponse

Pour E1, la rponse est oui aux deux questions : est un minorant, et {1, 2, 3} est un majorant.

Pour E2, F n'est pas minore, mais est majore. Pour E3, F est minore et non majore. Bien noter qu'un ensemble peut tre fini et non born.

"Un plus grand lment de F est un majorant de F qui appartient F : si F a un plus grand lment, il est unique, on le note max(F)."

exemple 6

Ci-dessus, F n'a pas de plus grand, ni de plus petit, lment. Dans F(]0 , 1], R), la partie :

{xxn | n entier naturel}, a un plus grand lment, obtenu pour n = 0. En effet c'est un majorant qui est un lment de cette partie.

exemple 7 ( traiter) Dans N*, muni de l'ordre de la division, soit A = {p | p 12}. Cette partie a-t-elle un plus grand lment, un plus petit lment ?

# rponse

Explicitons A : A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}.


Un minorant de A est un diviseur commun tous ses lments : ce ne peut tre que 1. Or 1 est un lment de A, donc 1 = min(A). Un majorant de A est un multiple commun tous ses lments, en particulier 2, 3, 5, donc il vaut au moins 30. Il n'y a pas de plus grand lment dans A.

"Un lment a E est la borne suprieure de F dans E si a est le plus petit des majorants de F dans E."

exemple 8

On reprend l'exemple prcdent : E = P({1, 2, 3}), F = {{1}, (2}, {3}}.

Il y a un seul majorant, {1, 2, 3}, c'est donc la borne suprieure. Il y a un seul minorant, , c'est donc la borne infrieure.

exemple 9 ( traiter) Dans N*, muni de l'ordre de la division, on appelle F la partie :

F = {2, 3, 5, 12, 30}. Cette partie a-t-elle une borne suprieure, une borne infrieure :

dans N*, dans {2, 3, , 60},

dans {2, 3, 5, 12, 30, 120} ?

# rponse

Une borne suprieure est un multiple commun, le plus petit possible, une borne infrieure est un diviseur commun, le plus grand possible.

Dans N*, inf(F) = 1, sup(F) = 60. Dans {2, 3, , 60}, inf(F) n'existe pas, sup(F) = 60.


Dans {2, 3, 5, 12, 30, 120}, inf(F) n'existe pas, et sup(F) = 120. Bien noter que l'existence, la valeur des bornes suprieure et infrieure dpendent de l'ensemble de rfrence, et pas seulement de la partie tudie.

"Si max(F) existe, alors supE(F) existe aussi et on a : max(F) = supE(F)."

exemple 10

Ce rsultat est intressant par les noncs qu'on peut en dduire : - si supE(F) existe et max(F) n'existe pas, on conclura que supE(F) n'est pas un lment de F. - si supE(F) existe et n'appartient pas F, max(F) n'existe pas.

exemple 11 ( traiter) Dans l'exemple 9, discuter l'existence de min(F), max(F). Cette existence dpend-elle de l'ensemble de rfrence ? Essayer de gnraliser.

# rponse

Dans N*, muni de l'ordre de la division, on appelle F la partie : F = {2, 3, 5, 12, 30}.

Il n'y a ni plus grand lment (un multiple commun est au moins 60) ni plus petit lment (1 est le seul diviseur commun). Ces rsultats ne dpendent pas de l'ensemble dans lequel F est plong. C'est un rsultat gnral : max(F) est un lment de F suprieur aux autres pour la relation d'ordre restreinte F.


"Soient E et F des ensembles ordonns, et f : E --. F une application. On dit que f est croissante si on a l'implication, pour tout x et tout y de E, x y f(x) f(y)."

exemple 12

On connat de nombreuses applications monotones, au moins sur une partie de leur domaine de dfinition :

sin : [0 , pi/2] R, Ln :]0 , +[ R.

exemple 13 ( traiter) Soit E : R+ N, l'application qui x associe sa partie entire E(x). Dessiner le graphe de E sur l'intervalle [0 , 5]. Cette application est-elle croissante ?

# rponse

Le graphe est reprsent ci-dessous. Il a t trac l'aide du logiciel MAPLE, on a donn l'instruction correspondante. Il est clair que cette application est croissante, non strictement.


2-2 Segments, intervalles

"Soit (E, ) un ensemble ordonn, on appelle segment ferm d'extrmits a et b, avec a < b pour fixer les ides, la partie de E dfinie par [a, b] = {x E / a x b}."

exemple 14

Ainsi, dans N*, muni de l'ordre de la division : [2 , 12] = {2, 4, 6, 12}.


Dans Z, avec l'ordre usuel : [2 , 12] = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}.

Noter que certains segments ferms sont aussi des segments ouverts : Dans Z, [2 , 12] =]1 , 13[.

exemple 15 ( traiter) Dans P({1, 2, 3, 4}), avec l'ordre de l'inclusion, crire le segment ferm [{1} , {1, 3, 4}], et le segment ouvert ]{2, 3} , {2, 3, 4}[.

# rponse

Le segment [{1}, {1, 3, 4}] est en gras. Quant au segment ouvert ]{2, 3} , {2, 3, 4}[, on voit qu'il est vide.


"Soit (E, ) un ensemble ordonn et I une partie de E. On dit que I est un intervalle de E si pour tout x et tout y de I tels que x y on a : Tout lment z de E tel que x z y, est un lment de I."

exemple 16

Dans R, la partie dfinie par I = {x | |x| 1} n'est pas un intervalle :

Dans Z*, la partie dfinie par I = {x | |x| 1}, est un intervalle. En effet, il n'y a pas d'lment strictement compris entre 1 et 1 dans Z*, donc l'nonc caractrisant un intervalle n'a pas de contre-exemple.

exemple 17 ( traiter) Dans R, l'ensemble I suivant est-il un intervalle :

I = {x | |x| > 0}.


# rponse

Non, puisque, par exemple, 12 et 36 sont dans I alors que 0 n'y est pas.

"Dans un ensemble totalement ordonn, si I est un intervalle, et si a = inf(I) et b = sup(I) existent, alors I est un segment contenu dans [a , b] et contenant ]a , b[."

exemple 18

On utilise cet nonc pour identifier tous les intervalles de R ou de N. La condition "totalement ordonn" est importante : par exemple, pour N* muni de l'ordre de la division, on peut utiliser les notions (sur lesquelles on reviendra) de plus grand diviseur commun (PGCD) et plus petit multiple commun (PPCM) d'une famille finie d'entiers. Ainsi, un intervalle fini de cet ensemble ordonn a une borne suprieure (PPCM) et une borne infrieure (PGCD), pourtant :

{2, 3, 5, 7} est un intervalle car ses lments ne sont pas lis par la relation d'ordre (aucun n'est divisible par un autre), on voit que :

1 = PGCD(2, 3, 5, 7), et 210 = PPCM(2, 3, 5, 7), mais {2, 3, 5, 7} ]1 , 210[.

exemple 19 ( traiter) Dans (P({1, 2, 3}), ), vrifier que I = {{1}, {2}, {2, 3}} est un intervalle. Est-ce un segment ?

# rponse

Les seuls lments comparables sont {2} et {2, 3}. Aucun lment n'est strictement compris entre les deux. L'ensemble I est bien un intervalle.


Le seul majorant de I est {1, 2, 3}, c'est sup(I). Le seul minorant est , c'est inf(I). Ces lments n'appartiennent pas I, donc, si I est un segment, on a :

I = ] , {1, 2, 3}[, ce qui est faux, bien sr.

2-3 Entiers

"Soit E un ensemble totalement ordonn, et x, x' des lments de E. On dit que x' est le successeur de x, et on note x'= succ(x), si x < x' et si le segment ]x , x'[ est vide ; on dfinit de mme le prdcesseur de x, not pred(x)."

exemple 20

Dans P({1, 2, 3}), {1}, ] , {1}[ est vide, {2}, ] , {2}[ est vide, de mme pour {3}. On voit ici l'utilit de la condition "totalement ordonn" pour que le successeur soit bien dfini s'il existe. Dans Z, ou N, avec l'ordre usuel, on voit que le successeur d'un lment n existe, c'est n+1 (selon le point de vue, ce peut tre la dfinition de n + 1).

exemple 21 ( traiter) Dans Q, le nombre 0 a-t-il un successeur, un prdcesseur ? Gnraliser.

# rponse

Si un successeur existe, soit pq

.

On voit que si pq

> 0, alors 0 < p2q

a

b. On vrifie que

ad + bc2bd

est entre ces deux nombres. Il n'existe donc aucun successeur

dans Q.

"Soit E un ensemble totalement ordonn. On dit que E est bien ordonn (BO) si toute partie non vide A de E admet un plus petit lment min(A)."

exemple 22

Dans E = {2n | n naturel}, ordonn par division, toute partie non vide a un plus petit lment : il suffit de prendre l'lment 2k, k tant le plus petit exposant utilis dans cette partie. Cet ensemble est bien ordonn. NB : ceci repose en fait sur la dfinition axiomatique de N, puisqu'on admet implicitement dans ce raisonnement que l'ensemble des exposants a un plus petit lment.

exemple 23 ( traiter)

Soit A = { 1n

| n est l'oppos d'un naturel non nul}. Vrifier que A, ordonn par l'ordre usuel de Q, est bien ordonn.

# rponse

Soit B une partie non vide de A. Soit B' l'ensemble des opposs des dnominateurs des lments de B. C'est une partie non vide de N. Soit m son plus petit lment.

Si 1n

B, n > m, donc 1n

> 1

m,


de plus m B', donc 1m

B,

donc 1m

= min(B). A est bien ordonn.

"Soit E un ensemble bien ordonn. On dit que E est naturellement bien ordonn (NBO) si tout lment de E, sauf min(E), a un prdcesseur."

exemple 24

Les parties finies de (Z, ) sont naturellement bien ordonnes.

exemple 25 ( traiter) Dans Z, tout lment a un prdcesseur (pred(n) = n 1). Est-ce un ensemble naturellement bien ordonn ?

# rponse

Non, car Z n'est pas bien ordonn : certaines parties n'ont pas de plus petit lment (Z par exemple).

"Soit P : N {vrai, faux} une proprit. Soit a un lment de N. On dit que P est rcursive partir de a si pour tout x de N suprieur ou gal a on a l'implication : si P(x) = vrai, alors P(succ(x)) = vrai."

exemple 26

Soit P la proprit : "le nombre de parties d'un ensemble n lments est 5.2n."


Cette proprit est rcursive partir de 0 : on voit facilement que le nombre de parties d'un ensemble n+1 lments est le double de celui d'un ensemble n lments (voir exemple 28). Remarquer que cette proprit est rcursive partir de 0, mais fausse :

(P(0) = faux).

exemple 27 ( traiter) Vrifier que la proprit "La somme des n premiers entiers naturels est

gale n2

2+

n

2+

12

" est rcursive partir de 1.

# rponse

Supposons la proprit vraie pour n. La somme des n + 1 naturels est alors :

n2

2+

n

2+

12

+ n + 1.

Or n +1( )2

2+

n +12

+12

s'crit :

n2 + 2n +12

+n

2+

12

+12

,

n2

2+ n +

n

2+

12

+ 1.

C'est bien la mme formule, donc la proprit est rcursive.


"Soit P une proprit sur N, rcursive partir de a. S'il existe un lment b de N, plus grand que a, tel que P(b) = vrai, alors P(x) est vrai pour tout x suprieur b."

exemple 28

Le nombre d'lments de l'ensemble des parties d'un ensemble n lments est 2n ; si n = 0, c'est vrai (une seule partie, la partie vide). Supposons le rsultat vrai pour n. Si E est un ensemble n + 1 lments, on note a l'un d'entre eux. Les parties de E sont de deux types, celles qui contiennent a, et les autres. Elles se correspondent biunivoquement puisque toute partie H ne contenant pas a est associe une partie qui contient a, soit H {a}. Les parties qui ne contiennent pas a sont les parties de l'ensemble E-{a} qui a n lments. Il y en a 2n en tout. Le nombre de parties de E est donc 2n + 2n = 2n+1. D'o, par rcurrence, le rsultat annonc.

exemple 29 ( traiter) La proprit :

"La somme des n premiers entiers naturels est gale n2

2+

n

2+

12

" est-

elle vraie (cf. 27) ?

# rponse

On a vu que cette proprit est rcursive. Pour n = 1 elle n'est pas vraie, 1 3/2. Elle n'est mme jamais vraie, puisque le nombre n

2

2+

n

2+

12

n'est jamais entier (n(n + 1) est pair donc n2

2+

n

2 entier).


Revenant au raisonnement du (27) on voit que toute formule de la forme n2

2+

n

2 + c est rcursive quel que soit c. Il suffit de choisir c pour que la

proprit soit vraie pour n = 0, soit c = 0. On retrouve une formule bien connue :

1 + 2 + 3 + + n = n(n + 1)2

.

"Dans N, toute partie majore a un plus grand lment, les intervalles sont les segments ferms et les sections finissantes fermes."

exemple 30

Soit I = {n N | n2 + 2n + 13 37}. C'est un intervalle ; en effet la fonction x x2 + 2x + 13 est croissante sur R+, donc :

si n1, n2 I et n1 m n2, m2 + 2m + 13 n22 + 2n2 +13 37. De plus I est born puisque si n2 + 2n + 13 37 , alors n2 37, donc n 6. C'est donc un segment ferm. Le graphe est trac ci-contre (avec MAPLE).


Le segment est donc [0 , 4]. La fonction tant monotone, on pouvait aussi tablir une table de valeurs :

n 0 1 2 3 4 5 13 16 21 28 37

exemple 31 ( traiter) Soit A = {n N | | n2 + 6n + 3 | 7}. Est-ce un intervalle ? Vrifier que c'est une partie majore, et trouver son plus grand lment. On pourra s'aider d'un graphique, et de calcul numrique.


# rponse

Graphiquement :

La partie au-dessous de 7 correspond aux abscisses 0, 6, 7. Ce n'est pas un intervalle, c'est une partie majore de plus grand lment 7. Par le calcul, on tablit le tableau de variations de la fonction u dfinie par :

u(x) = | x2 + 6x + 3 |.

x 0 3 + 2x + 6 + 0 x2 + 6x + 3 12 0 | x2 + 6x + 3 | 12 0 +

La partie A est donc borne.


2-4 Anneaux et corps

"Soit (E, T, ) un ensemble muni de deux lois de composition interne. On dit que (E, T, ) est un anneau si 1- (E, T) est un groupe commutatif, 2- est associative et admet un lment neutre diffrent du neutre de T, 3- est distributive par rapport T."

exemple 32

Les anneaux usuels sont (Z, +, ), (Q, +, ), (R, +, ), (C, +, ). On en rencontrera d'autres (matrices, polynmes, suites). L'ensemble Z[x] des fonctions sur R, polynomiales coefficients entiers relatifs, est un anneau, par exemple, pour les oprations usuelles d'addition des fonctions, et de multiplication des fonctions. L'lment neutre de l'addition est la fonction 0, l'lment neutre de la multiplication est la fonction constante gale 1.

exemple 33 ( traiter) Appelons A l'ensemble des endomorphismes de (R2, +), c'est--dire des applications u de R2 dans lui-mme qui ont la proprit suivante :

pour tout couple de vecteurs (V, W) du plan, u(V + W) = u(V) + u(W). On dfinit l'addition de deux endomorphismes comme d'habitude :

(u + v) (X) = u(X) + v(X) pour tout vecteur X. On considre une seconde loi interne (le vrifier) dans A, la composition des applications :

uov (X) = u(v(X)). Vrifier que (A, +, o) est un anneau. Questions identiques si on considre B, ensemble de toutes les applications du plan dans lui-mme, avec les mmes oprations.


# rponse

(A, +) est un groupe commutatif : l'opration + est dfinie partir de l'addition des vecteurs, qui est une loi de groupe commutatif. Il n'y a aucun problme de vrification. De mme, il est facile de voir que l'opration o est interne. L'opration o est associative ; pour tout vecteur X :

uo(vow)(X) = u(v(w(X))) = uov(w(X)) = (uov) ow(X). Pour la distributivit ; pour tout vecteur X :

uo (v + w)(X) = u(v(X) + w(X)), = u(v(X)) + u(w(X)), = uov(X) + uow(X).

L'lment neutre pour o est l'application identique id(X) = X pour tout X du plan.

(A, +, o) est un anneau. Pour B, on voit facilement que toutes les vrifications subsistent, sauf la distributivit, qui utilise le fait que u est un endomorphisme. (B, +, o) n'est donc pas un anneau.


"Soit (E, T, ) un ensemble muni de deux lois de composition interne. On dit que (E, T, ) est un corps si 1- (E, T, ) est un anneau commutatif, 2- Tout lment de E sauf le neutre de T a un symtrique pour ."

exemple 34

Les corps que l'on utilise souvent au niveau de la Licence sont les corps de nombres : Q, R, C. On rencontrera, par exemple dans certaines rsolutions d'quations par MAPLE, des "extensions" du corps des rationnels : ce sont des corps contenant Q, et contenus dans C, ou dans R. Notons Q[i] l'ensemble des nombres (complexes) de la forme p + iq, o p et q sont des rationnels, et i dsigne le complexe de module 1 et argument pi/2, comme d'habitude. Ce sous-ensemble de C est stable par les deux oprations de multiplication et d'addition. On peut donc examiner la question :

(Q[i], +, ) est-il un corps ? On va voir que oui : Il est clair que les proprits des oprations telles que associativit, commutativit, distributivit, subsistent puisqu'elles ne sont pas relatives au contexte. (Q[i], +) est un sous-groupe de (C, +) ; il est non vide et :

(a + i b) (p + iq) = (a p) + i (b q), si a, b, p, q sont des rationnels, alors a p et b q galement. Tout lment de Q[i] autre que 0 a un inverse dans Q[i] ; l'inverse de p + iq dans C est :

p iqp2 + q2

,

soit : p

p2 + q2 i q

p2 + q2,


c'est bien un lment de Q[i].

exemple 35 ( traiter) Un autre exemple de corps se rencontre en arithmtique, et joue un rle important dans les applications comme la cryptographie : il s'agit des corps finis. Appelons K l'ensemble {0, 1, 2, 3, 4} muni de deux oprations, + et , supposes commutatives, et dfinies par les tables ci-dessous. On admettra que ces oprations sont associatives, et distributive par rapport +. Vrifier que cet ensemble K de 5 lments est bien un corps.

+ 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3

0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1


# rponse

On constate en effet que K est un anneau commutatif. Dans la seconde table, on vrifie que dans chaque ligne autre que celle de 0, l'lment neutre 1 apparat, ce qui signifie que les lments diffrents de 0 sont inversibles pour . L'ensemble K est bien un corps.

2-5 Les nombres rels

"On appelle groupe ordonn un groupe (G, T) muni d'une relation d'ordre compatible avec T, c'est--dire telle que pour tout x, tout y, tout x', tout y' de G on ait l'implication x y et x' y' entrane x T x' y T y' (on peut composer des ingalits)."

exemple 36

Vous connaissez dj des groupes ordonns : (Z, +, ), (Q, +, ), (R, +, ) par exemple,

o on ajoute membre membre des ingalits. Les groupes de la forme F(A, G), ensemble des applications d'un ensemble A quelconque dans un groupe ordonn G, sont galement de faon naturelle des groupes ordonns.

exemple 37 ( traiter) Le groupe multiplicatif (Q*, ) des rationnels non nuls est galement un ensemble ordonn. Est-ce un groupe ordonn ? Examiner la mme question pour le groupe multiplicatif (R+*, ) des rels strictement positifs.


# rponse

Peut-on multiplier membre membre des ingalits ? On sait bien qu'en gnral, cela conduit un rsultat faux (c'est une erreur classique) :

2 1, 3 1, "donc" 6 1.

Par contre, lorsqu'il s'agit de nombres strictement positifs, il n'y a plus de difficult.

"On dit qu'un groupe (G, T, ) totalement ordonn, d'lment neutre e est archimdien, si pour tout x tel que e < x, et tout y de G, il existe un entier n tel que y < xn."

exemple 38

Reprenons les groupes ordonns de l'exemple 32 : (Z, +, ) est totalement ordonn.

Si x > 0, et y sont des relatifs, existe-t-il un entier n tel que y < n.x ? Intuitivement, la rponse est affirmative. On peut effectivement le dmontrer partir des axiomes de dfinition de N. Ce groupe est bien archimdien.

exemple 39 ( traiter) Le groupe additif des rationnels est-il archimdien ? Et le groupe multiplicatif des rationnels strictement positifs ?

# rponse

Soit pq

un rationnel strictement positif, et rs

un rationnel. On suppose p,

q, s strictement positifs, ce qui est toujours possible.


Peut-on trouver un multiple entier du premier, qui soit suprieur au second. C'est vident si r

s est ngatif ou nul.

Si rs

est positif, on doit rsoudre l'inquation :

nps > qr. On voit donc que cela est possible, puisque (Z, +) est archimdien. Le groupe additif des rationnels est archimdien. Pour le groupe multiplicatif des rationnels strictement positifs, il faut rsoudre le problme suivant :

tant donn pq

strictement plus grand que 1, et rs

,

existe-t-il une puissance de pq

qui dpasse rs

?

Ici encore, on peut, premire vue, dire que c'est bien le cas puisque, si x > 1, xn tend vers l'infini, donc dpasse n'importe quel rationnel fix l'avance. On peut cependant se demander comment on prouve que :

si x > 1, xn tend vers l'infini (laiss au lecteur).

"Un anneau (A, +, ) muni d'une relation d'ordre est ordonn si le groupe (A, +) est ordonn, et si de plus on a l'implication : si x 0 et y 0 alors x.y 0. Si A est un corps, on dit que c'est un corps ordonn s'il est totalement ordonn."

exemple 40

L'anneau des entiers relatifs est un anneau ordonn, de mme l'anneau des rationnels. Bien noter que, dans le cas d'un corps, cela ne suppose pas que le groupe multiplicatif des lments non nuls (diffrents de l'lment neutre de l'addition) soit un groupe ordonn. La condition est plus faible.


exemple 41 ( traiter) On a vu qu'il existe des corps finis, par exemple :

Z/3Z = {0, 1, 2}. En envisageant tous les cas possibles, vrifier que cet ensemble ne peut pas tre un corps ordonn.

# rponse

Un corps ordonn est totalement ordonn, donc il faut voir toutes les faons d'ordonner totalement un ensemble trois lments :

a) 0 < 1 < 2, b) 0 < 2 < 1, c) 1 < 0 < 2, d) 1 < 2 < 0, e) 2 < 1 < 0, f) 2 < 0 < 1.

Compatibilit avec + : (rappel 3 = 0) a) 0 < 1 et 1 < 2 entrane 1 < 3 donc 1 < 0, mais 1 0. Cas impossible. b) 0 < 2 et 2 < 1 entrane 2 < 3 donc 2 < 0, mais 2 0. Cas impossible. c) 1 < 2 et 1 < 2 entrane 2 < 4 donc 2 < 1, mais 2 1. Cas impossible. d) 1 < 2 et 2 < 0 entrane 3 < 2 donc 0 < 2, mais 2 0. Cas impossible. e) 2 < 1 et 2 < 1 entrane 4 < 2 donc 1 < 2, mais 2 1. Cas impossible. f) 0 < 1 et 0 < 1 entrane 0 < 2 donc 0 < 2, mais 2 0. Cas impossible.

Ce corps n'est pas ordonn. NB : en fait on n'a utilis que la structure de groupe ordonn. On voit que ce groupe ne peut pas tre totalement ordonn.


"Dans un anneau totalement ordonn, pour tout lment a, le carr a2 est suprieur ou gal 0."

exemple 42

C'est videmment une proprit bien connue et souvent utilise dans les corps ordonns usuels (rationnels, rels). Remarquer que cela exclut que le corps des complexes soit un corps ordonn, quelle que soit la structure d'ordre qu'on pourrait y dfinir : on devrait avoir les ingalits :

12 > 0, i2 > 0,

soit : 1 > 0,

1 > 0, d'o : 0 > 0.

exemple 43 ( traiter) Utiliser ce rsultat pour prouver que Z/3Z ne peut pas tre un corps ordonn. Gnraliser un corps Z/pZ.

# rponse

On devrait avoir : 1 > 0, donc 1 < 0.

(cf. le cas des complexes). Mais 1 = 2 = 1 + 1 donc -1 > 0. Dans le cas gnral, 1 = p 1 = 1 + 1 + + 1 > 0, on conclut de mme.


"Il existe un unique corps totalement ordonn (R, +, ) ayant la proprit suivante : Toute partie non vide majore de R a une borne suprieure dans R."

exemple 44

L'ensemble : E = {x R | x2 < 3},

est major, par 2 par exemple : si x > 2, x2 > 4, donc x n'appartient pas E. Il en rsulte (comme R est totalement ordonn) que si x est dans E, alors x 2. Soit b la borne suprieure de E. C'est un nombre positif puisque 0 est dans E. Si b2 3, on tudie les deux autres cas :

b2 < 3, b2 > 3.

Dans le premier cas, b est le plus grand lment de E. Or, on peut trouver n assez grand pour que (b + 1

n)2 < 3 , donc (b + 1

n) est un lment de E,

ce qui est une contradiction. Dans le second cas, b n'est pas un lment de E. On peut trouver n assez grand pour que (b 1

n)2 > 3, donc (b 1

n) est un majorant de E infrieur

b, ce qui est galement une contradiction. Il en rsulte que b2 = 3. L'existence d'une borne suprieure entrane l'existence d'une racine carre pour 3. On montrerait de la mme faon l'existence d'une racine n-me. (Les arguments dvelopps ci-dessus reposent sur le fait que R est archimdien, ce que nous vrifierons en exercice, cf. exercice 18.)


exemple 45 ( traiter) L'existence de bornes suprieures entrane l'existence de nombres irrationnels, c'est--dire n'appartenant pas Q. Vrifier, par un raisonnement par l'absurde, que la borne suprieure b ci-dessus ne peut tre gale une fraction irrductible p

q.

On montrera que p est divisible par 3 (raisonner dans le corps Z/3Z), puis, aprs simplification, que q est galement divisible par 3, d'o une contradiction.

# rponse

On devrait avoir : p2 = 3 q2, donc,

p2 = 0 dans le corps Z/3Z, donc p = 0 dans le corps Z/3Z.

Il existe un entier p' tel que : p = 3 p', d'o,

3 p'2 = q2, et par le mme raisonnement q est divisible par 3, ce qui contredit le fait que la fraction p

q est irrductible.

On trouve par cet argument trs classique que 3 n'est pas un nombre rationnel.


"Partie entire d'un rel : pour tout rel a, il existe un unique entier n tel que n a < n+1, cet entier est appel la partie entire de a, et note E(a), ou [a]."

exemple 46

La partie entire n'est pas la partie "avant la virgule" dans l'criture d'un rel, du moins dans le cas des rels ngatifs :

E( 12, 345) = 13, E(11, 0034) = 11.

exemple 47 ( traiter) Partie entire et oprations ; en prenant d'abord des exemples, voir si les relations suivantes sont vraies ou non :

E( a) = E(a), E(a + b) = E(a) + E(b),

E(a.b) = E(a).E(b).

# rponse

Pour la premire : E( 12, 345) = 13,

E(12, 345) = 12. La relation est donc fausse. Pour la seconde :

E(0, 6) = 0, E(0, 7) = 0, E(1, 3) = 1.

La relation est donc fausse en raison des retenues. Pour la dernire :

E(2, 5) = 2,


E(2, 6) = 2, E(6, 5) = 6.

La relation est galement fausse.

Dveloppement dcimal d'un rel, l'ordre n : pour tout rel a, et tout entier n, il existe un unique rationnel Dn tel que 10nDn est entier, et Dn a < Dn + 10n, ce nombre

rationnel est appel le dveloppement dcimal l'ordre n de a.

exemple 48

On fera la mme remarque que pour la partie entire, en ce qui concerne les rels ngatifs :

a = 1, 23456 ; D2(a) = 1, 24 ;

b = 0, 6543 ; D2(a) = 0, 65.

exemple 49 ( traiter) La partie entire est un cas particulier de dveloppement dcimal. On peut donc prvoir que l'criture du dveloppement dcimal d'une somme, d'un produit, d'un oppos n'est pas immdiate. Illustrer ce phnomne, pour les dveloppements l'ordre 2, par des exemples.

# rponse

Exemple 1 : D2( 1, 2367) = 1, 24,

D2(1, 2367) = 1, 23 D2( 1, 2367) . Exemple 2 :

D2(1, 278) = 1, 27,


D2(0, 356) = 0, 35, D2(1, 634) = 1, 63 1, 62.

Exemple 3 : D2(1, 278) = 1, 27 D2(0, 356) = 0, 35.

Ici, le produit des dveloppements dcimaux n'est pas un dveloppement dcimal l'ordre 2 :

1, 27 0, 35 = 0, 4445. D'ailleurs :

D2(0, 4445) = 0, 44 D2(1, 278 0, 356) = D2(0, 454968) = 0, 45.

"Dans R, les intervalles sont les segments, les sections finissantes ou commenantes, et R."

exemple 50

L'ensemble : E = {x R | x2 < 3},

utilis plus haut est un intervalle. Si y et x sont des lments de E, avec x < y, et si z est un rel vrifiant :

x < z < y, alors on doit distinguer diffrents cas. () x 0. On peut lever ces ingalits au carr membre membre (R est un corps ordonn), d'o :

x2 < z2 < y2 < 3, donc z est dans E. () y 0. On obtient des ingalits quivalentes en multipliant par 1 :

x > z > y 0, on conclut comme dans le premier cas en levant au carr.


() x < 0 < y. On procdera de mme selon la position de z par rapport 0. Cet intervalle born est un segment :

E = ] 3 , 3 [.

exemple 51 ( traiter) Soit F l'ensemble :

F = {x R | x 0, et x2 + x 2}. Vrifier que c'est une section finissante. Dterminer min(F).

# rponse

C'est un intervalle ; si x est dans F et x' > x, alors : x'2 + x' x2 + x 2,

donc x' est galement un lment de F. Cette partie est borne infrieurement (par 0) et non borne suprieurement (tout rel suprieur 2 est dans F), c'est donc une section finissante. On voit que 1 est un lment de F, et qu'un rel strictement infrieur 1 n'est pas dans F, puisque :

0 x < 1 0 x2 < 1 x + x2 < 1. Donc 1 = min(F) et :

F = [1 ,.[ (not le plus souvent [1 , +[).


indications pour rsoudre - mthode - lexique

3 Pour Comprendre et Utiliser

3-1 noncs des exercices

Majorer, minorer, chercher le plus grand (ou plus petit) lment d'un ensemble ordonn, la borne suprieure (infrieure). Savoir raisonner dans un ensemble totalement ordonn, non totalement ordonn. Utiliser la monotonie des applications. Reconnatre un intervalle, un segment. Ensembles bien ordonns. Faire une rcurrence.

exercice 1

Soit E un ensemble ordonn. Dans E soient A et B des parties majores. 1) On suppose d'abord que A et B ont un plus grand lment () ainsi que A B et A B. Quelle relation y-a-t-il entre max(A B), max(A B), max(A) et max(B) ? ()() 2) Si on suppose que A et B ont une borne suprieure dans E, ainsi que A B et A B, tablir des relations entre supE(A B), supE(A B), supE(A), supE(B).()()

exercice 2

Soient E et F des ensembles ordonns. On note les relations d'ordre dans ces deux ensembles. 1) On appelle ordre produit sur E F la relation dfinie par :



(x, y) P (s, t) si (x s et y t). Dmontrer que cette relation est bien une relation d'ordre. On suppose ici E et F totalement ordonns (), (E F, P) est-il totalement ordonn ? () Cette dfinition s'tend sans difficult un produit quelconque d'ensembles ordonns. 2) On appelle ordre lexicographique sur E F la relation dfinie par :

(x, y) L (s, t) si (x s et x s) ou (x = s et y t). Dmontrer que cette relation est bien une relation d'ordre.() Si on suppose E et F totalement ordonns, montrer que (E F, L) est totalement ordonn.() 3) Un exemple : N N. On munit N de la relation d'ordre usuelle. On considre d'une part l'ordre lexicographique, et d'autre part l'ordre produit. Pour ces deux ordres respectivement, quelle est la section finissante ferme () [(3, 4) , [, la section commenante () ], (3, 4)] , le segment ferm () [(1, 2) , (7, 6)]. On prcisera dans chaque cas si ces ensembles sont finis ou infinis. Le segment [(3, 4) , (5, 2)] est-il dfini ? On note p et q les projections de N N sur N :

p(x, y) = x, q(x, y) = y. Ces applications sont-elles monotones () (on distinguera le cas de P de celui de L.) 4) Un autre exemple : Z Z. On munit Z de la relation d'ordre usuelle, et Z Z de l'ordre lexicographique. Soit A = {(n, m) | n 4, m 2}. Quel est l'ensemble des minorants de A ? L'ensemble A a-t-il un plus petit lment ? () L'ensemble compl-mentaire de A a-t-il un plus grand lment ? L'ensemble A est-il un intervalle () ?



Un lment de (Z Z, L) a-t-il toujours un prdcesseur ? un successeur ? () L'ensemble (Z Z, L) est-il bien ordonn ? () (). Vrifier que les parties de la forme [a , [ Z sont des intervalles.

exercice 3

Soit (E, ) un ensemble totalement ordonn. Examiner les conjectures ()suivantes ()() : 1) Toute partie finie non vide de E est borne. 2) Toute partie borne non vide de E est finie. 3) Toute partie non vide majore de E admet un plus grand lment.

exercice 4

Sur la notion de "treillis". Un ensemble ordonn est un treillis si la proprit suivante est vraie : "toute partie 2 lments a une borne suprieure et une borne infrieure". Parmi les exemples d'ensembles ordonns tudis jusqu'ici, certains sont des treillis. Citez-les. () 1) Dmontrer que le produit de deux ensembles totalement ordonns, muni de l'ordre produit, est un treillis.() 2) Dans un treillis, dmontrer que toute partie finie non vide a une borne suprieure et une borne infrieure.( ) 3) Dfinir une bijection croissante entre le treillis des parties de {1, 2, 3}, ordonn par l'inclusion, et le treillis form du cube {0, 1}3, ordonn par l'ordre produit (l'ensemble {0, 1} tant ordonn par 0 1). () La bijection rciproque est-elle croissante ? 4) Gnraliser : pour chaque entier naturel n, dfinir une bijection croissante n entre P({1, 2, , n}) et {0, 1}n. () Si pri dsigne la projection de {0, 1}n sur son facteur numro i :

pri : (a1, a2, , an) ai,



caractriser l'application compose pri o de P({1, 2, , n}) dans {0, 1}.

exercice 5

Dans cet exercice, on note En le n-cube {0, 1}n. L'ensemble {0, 1} tant ordonn par 0 1, on ordonne En par l'ordre lexicographique. 1) On tudie d'abord le cas n = 3. On associe chaque lment (a0, a1, a2) de E3 l'entier :

b3(a0, a1, a2) = a2 + 2a1 + 4a0. Quelles sont les valeurs prises par b3 ? Vrifier que b3 est une bijection croissante de E3 sur le segment [0 , 7] de l'ensemble N. A quoi correspond la bijection rciproque ? () Est-elle croissante ? 2) Gnraliser : dfinir une application injective bn de En dans N. Dterminer quelle est son image.

exercice 6

Sur la notion d'arbre. Un arbre est un ensemble ordonn fini o toute partie 2 lments a une borne infrieure, et aucune partie 2 lments non comparables n'a de majorant. On appelle "feuille" un lment de l'arbre qui n'a pas d'lment plus grand que lui. On appelle "nud" les autres lments. Vrifier que lorsqu'on supprime une feuille dans un arbre, l'ensemble complmentaire est encore un arbre. 1) Dessiner tous les arbres 3, 4, 5 lments.() 2) Dmontrer que, dans un arbre, toute partie non vide a une borne infrieure (). En particulier, l'ensemble a un plus petit lment (expliquer pourquoi ?). On l'appelle la "racine" de l'arbre.



3) Dmontrer que, dans un arbre, toute partie non vide majore est totalement ordonne (). Dduire que toute partie non vide majore a un plus grand lment. () Dmontrer que, dans un arbre, tout lment, sauf le plus petit, a un prdcesseur (). 4) Soit a un lment de l'arbre (A, ). Expliquer pourquoi l'ensemble :

B(a) = {x A | x a}, est un ensemble non vide totalement ordonn. Le nombre d'lments de B(a) est appel la "hauteur" de a, note h(a). Dmontrer que deux lments a et b, tels que a b et h(a) = h(b) ne sont pas comparables () (). Calculer h(pred(x)) en fonction de h(x). 5) On suppose (par commodit) que dans l'arbre A, il n'y a pas plus de 10 nuds ou feuilles de hauteur donne. On numrote les lments de A de la manire suivante, par rcurrence : la racine est numrote 1. Les lments de hauteur 1 sont numrots 10 19 (au maximum). Pour les lments de hauteur 2, on numrote de 100 109 ceux qui sont prcds par 10, etc. Plus prcisment, 10 u(pred(x)) + 9 u(x) 10 u(pred(x)). tablir la relation () : 2 10h(x) 1 u(x) 10h(x). Vrifier qu'on dfinit ainsi une bijection croissante u de A sur un ensemble totalement ordonn. On remarquera que A n'est, en gnral, pas totalement ordonn. Appliquer cette mthode, par exemple, aux arbres dessins au dbut.

exercice 7

tudier la conjecture () suivante : Soit f : (E, ) (F, ) une bijection croissante.

La bijection rciproque g de f est une application croissante ().



exercice 8

Quelques proprits lmentaires des applications monotones (croissantes pour fixer les ides). On pourra utiliser, pour tester les rponses, les trois applications suivantes : il n'est pas interdit d'imaginer d'autres applications si ncessaire.

f1 : N N, x 2x, f2 : R+ N, x E(x) (partie entire),

f3 : R+ R+, x x 1+E(x). Soit f : (E, ) (F, ) une application croissante entre des ensembles ordonns. tudier les conjectures () suivantes : 1) Si A est une partie de E qui a un plus grand lment, alors f(A) a un plus grand lment et max(f(A)) = f(max(A)).( ) 2) Si A est une partie de E qui a une borne suprieure () dans E, alors f(A) a une borne suprieure dans F, et supF(f(A)) = f(supE(A)) ()( ). 3) On suppose E totalement ordonn. Soit a E. On suppose que le successeur de a existe, ainsi que le prdcesseur. Dans ce cas, f(a) a un successeur et succ(f(a)) = f(succ(a)) (). De mme, f(pred(a)) = pred(f(a)). 4) Supposons de plus f surjective : si E est Bien Ordonn (), alors F aussi. Si E est NBO () alors F aussi.

Calculer dans un anneau, un corps.

exercice 9

Quelques proprits lmentaires des anneaux et corps () () : 1) Soit (K, +, ) un ensemble muni de deux lois internes. On suppose que (K, +) est un groupe, on note 0 son lment neutre. On suppose que (K{0}, ) est un groupe.



On suppose enfin que la loi est distributive par rapport + gauche et droite. Dmontrer que (K, +, ) est un corps.()() 2) Dans un anneau () (A, +, ), on note 1 l'lment neutre de , et 1 son oppos. tablir les galits :

(1) a = a (1), a a = (a) (a).

3) Dans un anneau commutatif, tablir la "formule du binme" : a, b (a + b)n = an + Cn1 b.an1 + + Cnp bp.anp + + bn.

4) Si l'anneau n'est pas commutatif, dvelopper (a + b)2, (a + b)3.

exercice 10

Quelques proprits des anneaux Z/nZ () : 1) Soit n un naturel strictement plus grand que 1. Vrifier que la relation (dite de congruence modulo n) :

x R y si x y est divisible par n, est une relation d'quivalence sur Z. On dit que x est congru y modulo n. On note Z/nZ l'ensemble quotient. 2) Vrifier que l'addition et la multiplication de Z sont compatibles () avec la congruence modulo n. On en dduira que le quotient est un anneau commutatif. 3) Premier exemple : n = 5. crire la table de multiplication de Z/5Z {0}. Rechercher les diviseurs de 0 (), les lments nilpotents (), les lments inversibles (). Cet anneau est-il un corps ? 4) Deuxime exemple : n = 6. Rpondre aux mmes questions.



5) Troisime exemple : n = 8. Rpondre aux mmes questions. Ces rsultats seront repris en arithmtique et on verra un nonc gnral. 6) Dans chacun de ces anneaux, rsoudre les quations ()() :

X2 = 1, X2 = 1,

X2 4 X+ 1 = 0, Xn1 = 1.

exercice 11

Quelques exemples d'anneau obtenus par extension de Z, et de corps obtenus par extension de Q.() Soit t un complexe, non rationnel. On pose :

Z[t] = {a + bt | a, b Z}, Q[t] = {a + b t | a, b Q}.

1) Soit x un lment de Q[t]. Dmontrer qu'il s'crit de manire unique sous la forme x = a + b t, avec a, b des rationnels.() On suppose que t est solution d'une quation du second degr coefficients entiers du type :

t2 + pt + q = 0, Calculer en fonction de t, p, q les expressions de t2, t3, t4. Dmontrer que Z[t] et Q[t] sont des anneaux. () 2) Exemple de l'anneau Z[i], et de Q[i]. Chercher les lments de Z[i] inversibles dans cet anneau (). On a vu que Q[i] est un corps (exemple 34). 3) Exemple de l'anneau Z[ 3 ], et de Q[ 3 ]. On suppose a et b rationnels. Montrer que le produit (a + b 3 )(a b 3 ) est un rationnel et qu'il ne peut tre nul que si a et b sont nuls. En dduire que Q[ 3 ] est un corps.()



4) Trouver des couples d'entiers (a, b), avec b 0, tels que a2 3 b2, soit gal 1 ou 1 (). Dduire, dans Z[ 3 ], des exemples d'lments inversibles (), non entiers. 5) On revient au cas gnral. Dmontrer que t est inversible dans Q[t], donner l'expression de son inverse. () Soit t' l'autre racine de X2 + p X + q = 0. Pourquoi est-elle diffrente de t ? Montrer que cette racine appartient Z[t]. On suppose a et b rationnels. Montrer que le produit (a + bt)(a + bt') est un rationnel et qu'il ne peut tre nul que si a et b sont nuls. En dduire que Q[t] est un corps.()

exercice 12

Endomorphismes () de Q. 1) Soit f une application de Z dans lui-mme. On suppose qu'elle vrifie les proprits :

f(a + b) = f(a) + f(b), f(ab) = f(a)f(b). Calculer f(0), f(a), f(k.a) pour k et a entiers relatifs. Supposer f(1) = 0. Dmontrer que f(x) = 0 pour tout x. Supposer f(1) 0. Dmontrer que f(1) = 1, puis que f est l'identit de Z. 2) On suppose maintenant que f est un homomorphisme d'anneaux () de Q dans lui-mme, ayant les mmes proprits. Dmontrer que f est l'identit de Q.()

exercice 13

Sur la notion de noyau () d'un homomorphisme. (Le dbut a dj t propos dans le volume 1, il est repris ici comme prliminaire.)



1) Soit h : A --. B un homomorphisme de groupes (). On note indiffremment e l'lment neutre de A et de B, et par un point (".") l'opration de A et de B. On appelle H l'ensemble :

H = {a A | h(a) = e}. Dmontrer que H est un sous-groupe de A. On l'appelle le "noyau" de h. Vrifier que si u H, pour tout g A, g.u.g1 H. Dmontrer que h est injectif () si et seulement si son noyau ne contient que l'lment neutre.() 2) Soit maintenant h : A B un homomorphisme d'anneaux ()( ). C'est en particulier un homomorphisme de groupes, et il a un noyau H, qui est un sous-groupe de (A, +). On note + et les oprations d'anneaux. Dmontrer que H a la proprit suivante () :

si a A et u H, alors a u H. (On y reviendra en arithmtique.) 3) Dduire de ce qui prcde qu'un homomorphisme de corps est nul ou injectif.()

Utiliser l'ordre dans un groupe, un anneau, un corps.

exercice 14

Quelques proprits des groupes commutatifs ordonns.() Soit (G, +, ) un groupe commutatif ordonn. On note 0 son lment neutre, et pour tout lment x de G, x son symtrique. Prliminaire : a- Dmontrer que pour tout triplet d'lments de G, (g, h, k), on a l'implication :

si g < h alors g + k < h + k.



b- Dmontrer que pour tout quadruplet d'lments de G, (g, h, k, j), on a l'implication :

si g < h et k < j alors g + k < h + j. (c'est--dire que la relation x R y si x y et x y, est compatible avec +)

1) On suppose que dans G tout lment est comparable () 0. On pose :

G+ = {g G | g > 0}, G = {g G | g < 0}.

Dmontrer que si g est un lment de G+, alors g est un lment de G(), et rciproquement, et que G+ et G sont des parties stables () pour + (). En dduire que si G est un groupe fini, son ordre () est impair. Dmontrer que G est totalement ordonn (). 2) On suppose que G est un groupe fini, d'ordre strictement suprieur 1. Dmontrer que G n'est pas totalement ordonn (). 3) On suppose maintenant G totalement ordonn. Dmontrer que dans G, aucun lment non nul n'est d'ordre fini, en particulier aucun sous-groupe non trivial () n'est fini (). On suppose de plus G {0}. Dmontrer que G n'a pas de plus grand lment, ni de plus petit lment. 4) On suppose G totalement ordonn. Donner un exemple o G+ a un plus petit lment (), et un exemple o G+ n'a pas de plus petit lment, mais a une borne infrieure (). On suppose que G+ a un plus petit lment, soit a. Dmontrer que a = max(G). On pose :

H = {g G| a > g}. Dmontrer que H a un plus petit lment, qui est a + a = 2a.



On suppose que G+ n'a pas de plus petit lment, mais a une borne infrieure. Dmontrer que infG(G+) = 0.

exercice 15

Quelques proprits des anneaux commutatifs totalement ordonns ()(). Soit (A, +, , ) un anneau commutatif totalement ordonn. On note 0 l'lment neutre de +, 1 celui de , a le symtrique pour + de a, a1 le symtrique pour de a. (A, +, ) est un groupe commutatif totalement ordonn. On utilisera les rsultats de l'exercice prcdent qui s'y appliquent, ainsi que les notations. 1) Dmontrer que 1 > 0. Plus gnralement, vrifier qu'un lment idempotent () est dans A+(). Soit (a, b, c) un triplet de A. On suppose que a > b et que c est un lment inversible suprieur 0. Dmontrer que a c > b c. 2) Soit a un lment inversible () de A, on suppose que a est dans A+. Dmontrer que a1 est galement dans A+ (). Soit (a, b) un couple d'lments inversibles de A+. On suppose a > b. Dmontrer b1 > a1. Si a > 1, dmontrer que a1 < 1, et 0 < a1. 3) On suppose que A est un corps ordonn. Expliquer pourquoi, si min(A+) existe alors min(A+) 1. Dmontrer qu'il existe un lment suprieur 1, en dduire que 1 n'est pas le plus petit lment de A+. On veut dmontrer que A+ n'a pas de plus petit lment. On fait un raisonnement par l'absurde : supposons que min(A+) existe, soit a cet lment. Dduire que A a un plus grand lment. Conclure.



Calculer dans le corps ordonn des rels : chercher une borne suprieure (ou infrieure), majorer, minorer, utiliser les intervalles.

exercice 16

Quelques relations lmentaires () sur les bornes suprieures () dans R. (On pourra crire des relations analogues pour les bornes infrieures.) Par convention, les bornes suprieures sont calcules dans R. Dans cet nonc, A et B sont des parties non vides majores de R. 1) Discuter l'existence de sup(A B), sup(A B) et tablir leurs relations avec sup(A), sup(B). 2) On dsigne par A + B l'ensemble :

{a + b | a A, b B}. Dmontrer l'existence de sup(A + B). Cette borne suprieure est-elle gale sup(A) + sup(B) ? (). 3) On suppose de plus que A et B sont des parties de R+. On dsigne par A.B l'ensemble :

{a.b | a A, b B}. Dmontrer l'existence de sup(A.B), et comparer sa valeur avec sup(A).sup(B).

exercice 17

Proprits importantes de R. Il s'agit ici d'tablir quelques proprits "connues" de R, partir de sa seule caractrisation c'est --dire d'tre un corps ordonn dans lequel :

Toute partie non vide majore () a une borne suprieure. 1) Prliminaire : Soit A un sous-ensemble non vide de R form d'entiers. On suppose que A admet une borne suprieure S dans R.



Expliquer () pourquoi il existe exactement un lment de A appartenant :

]S 12 , S]. Soit N cet lment. Dmontrer que N = max(A), puis que S = N (). 2) R est archimdien (). Soit a un rel positif, non nul, et b un rel quelconque. Soit A le sous-ensemble de R :

A = {n | n.a b}. A peut-il tre vide ? Si A n'est pas vide, dmontrer qu'il a une borne suprieure, puis que cette borne suprieure est un plus grand lment. Soit N = max(A). Dmontrer que (N + 1).a > b. Conclure que R est archimdien (). 3) Dduire de la question prcdente que pour tout rel x il existe () un unique entier relatif n vrifiant :

n x < n + 1. (Il s'agit de la partie entire, dont on prouve ainsi l'existence partir des proprits de base de R.) 4) Soit G un sous-groupe de (R, +). On utilise les notations et rsultats de l'exercice 14. On suppose que G+ a un plus petit lment, soit a. Dmontrer que G = Z.a.

exercice 18

On vrifie que les proprits de dfinition de R impliquent que Q est "de manire naturelle" un sous-corps de R, distinct de R. 1) On dfinit une application de Z dans R en posant :

(n) = n.1 (dfini par rcurrence). Dmontrer que cette application est un homomorphisme injectif de groupes additifs ().



2) On dfinit une application de Q dans R en associant une fraction pq

le rel (p).(q)1. Pourquoi (q) est-il inversible dans R ? Vrifier que les images de deux fractions quivalentes () par sont bien gales. Dmontrer que est un homomorphisme de corps injectif (). 3) On dmontre dans cette question que la borne suprieure dans R de :

{x | x2 3, x > 0}, n'est pas un rationnel. Soit S cette borne suprieure. On veut dmontrer d'abord que S2 = 3.

Si S2 < 3, dmontrer qu'il existe () un entier n tel que (S + 1n

)2 < 3. Pourquoi est-ce contradictoire avec la dfinition de S ?

Si S2 > 3, dmontrer qu'il existe un entier n tel que (S 1n

)2 > 3. Pourquoi est-ce contradictoire avec la dfinition de S ? On s'efforcera de rdiger les arguments partir des proprits de base de R (existence de borne suprieure) et des proprits qui en ont t tires dans les exercices prcdents (R archimdien ()). On sait maintenant que S2 = 3. Rappeler pourquoi ce n'est pas un rationnel.

exercice 19

Quelques exemples de recherche de borne suprieure ou de borne infrieure(). On rdigera le plus prcisment possible les dmonstrations. Il est conseill de s'aider de dessins pour formuler des conjectures () sur les bornes. Si une borne est un lment de l'ensemble, on le signalera.



1) L'ensemble tudi est :

A = n2 + n 1n2 + 2

n N

.

Montrer que pour n assez grand (qu'on prcisera), les lments de A sont compris entre deux entiers naturels conscutifs (). En dduire que A est born, et donner un minorant et un majorant de A (). Dterminer la borne suprieure et la borne infrieure de A (). 2) L'ensemble tudi est :

B =n + sin(n2 )

n +1n N

.

Montrer que B est born, et donner sa borne suprieure et sa borne infrieure (). 3) L'ensemble tudi est l'ensemble C des modules des nombres complexes situs dans la partie du plan dfinie par :

M = z C 1 > Re(z) Im(z)}{ . Reprsenter M. Dire quelles sont les bornes de C (au vu du dessin), puis dmontrer que ces conjectures sont vraies ().

exercice 20

Soient I et J des parties non vides de R. On suppose dans tout l'exercice que J domine I, c'est--dire que pour tout x de I et tout y de J, x y. On pourra prendre des exemples pour explorer cette situation et celles constitues par les hypothses complmentaires ci-dessous. 1) Dmontrer que supR(I) et infR(J) existent (). Quelle relation y-a-t-il entre ces deux rels ? Dmontrer que I J a au plus un lment (). 2) Donner un exemple () o supR(I) = infR(J), et un exemple () o :

supR(I) < infR(J).



3) Examiner les conjectures suivantes : () si I J = , alors supR(I) < infR(J),

si I J , alors supR(I) = infR(J) = max(I) = min(J). 4) On suppose I J , et que I et J sont des intervalles. La runion I J est-elle un intervalle ? Examiner la rciproque : si I, J, et I J sont des intervalles, alors I J . () 5) On suppose que I J = , et I J = R. Dmontrer que () :

supR(I) = infR(J).



3-2 Corrigs des exercices

exercice 1-C

1) Soit a = max(A) et b = max(B), c = max(A B), d = max(A B). Les lments a et b sont des lments de A B donc sont infrieurs au plus grand lment de cet ensemble :

a d et b d. Si max(a, b) existe, on crira :

max(a, b) d. De la mme faon, c est un lment de A et un lment de B, il est donc infrieur aux plus grands lments de ces ensembles :

c a et c b. Si min(a, b) existe, on crira :

c min(a, b). (QC-1) L'hypothse faite sur A B est-elle superflue ? Autrement dit, si max(A) et max(B) existent, max(A B) existe-t-il toujours ? On cherchera des exemples (ou contre-exemples) dans un ensemble totalement ordonn (R par exemple) et dans un ensemble non totalement ordonn (N*, |) par exemple. 2) Le raisonnement est un peu diffrent, il faut bien savoir le faire : Soit a' = supE(A), b' = supE(B), c' = supE(A B), d' = supE(A B). L'lment a' est le plus petit des majorants () de A. Comme A est une partie de A B, tout majorant de A B est un majorant de A. La borne suprieure d' est donc un majorant de A, donc d' a'. De mme d' b'. Bien noter qu'on n'utilise pas a' A, qui n'est pas toujours vrai. ()

Ici encore, si max(a', b') existe : max(a', b') d'.



Par un raisonnement analogue, on obtient c' a' et c' b'. (QC-2) Examiner la question analogue QC-1.

exercice 2-C

1) La vrification ne pose aucun problme puisqu'il s'agit de vrifier sparment pour chaque composante. Un graphique illustre bien cette relation d'ordre ( entre un plus petit et un plus grand).

Cette relation est l'vidence non totale, puisqu'il faut que la comparaison soit dans le mme sens pour les deux coordonnes :

par exemple (1, 2) (3, 4), mais (1, 2) n'est pas comparable () (2, 1).

2) La relation L est une relation d'ordre.



Soient x, y, z, t des lments de l'ensemble. Rflexivit :

(x, y) L (x, y) car x = x et y y. Antisymtrie :

si (x, y) L (z, t), et (z, t) L (x, y), deux cas sont examiner : x z, alors x < z et z < x ce qui est contradictoire,

x = z et y t d'une part, x = z et t y d'autre part d'o t = y, donc (x, y) = (z, t).

Transitivit : (x, y) L (z, t) et (z, t) L (u, v).

Diffrents cas sont examiner : x < z, et z < u, d'o x < u et (x, y) L (u, v),

x < z, et z = u, t v, d'o x < u et (x, y) L (u, v), x = z, y t, et z < u, d'o x < u et (x, y) L (u, v),

x = z, y t, et z = u, t v, d'o x = u, y v, et (x, y) L (u, v). Dans ce cas par exemple (1, 2) L (3, 4) et (2, 1) L (1, 2) car 2 > 1. De faon gnrale, soit (x, y) et (u, v) des couples, comme est totale, on a l'un des cas : x u :

si x < u alors (x, y) L (u, v), si x = u alors si y v , (x, y) L (u, v) et sinon (x, y) L (u, v).

x u :

si x > u alors (x, y) L (u, v), le cas x = u a dj t vu.

La relation d'ordre L est totale.



3) Pour l'ordre produit, la section finissante est le produit : [2 , [ [3 , [.

C'est un ensemble infini. Dans le cas de l'ordre lexicographique, la section finissante est galement un ensemble infini. Ce n'est pas un produit :

{2} [3 , [ [3 , .[ N. Pour l'ordre produit, la section commenante est le produit :

[0 , 3] [0 , 4]. C'est un ensemble fini. Pour l'ordre lexicographique, la section commenante () n'est pas un ensemble fini : {3} [0 , 4] [0 , 2] N. Le segment [(1, 2) , (7, 6)], pour l'ordre produit est l'ensemble fini :

[1 , 7] [2 , 6]. Le segment ferm, pour l'ordre lexicographique, est un ensemble infini :

{1} [2 , [ [2 , 6] N {7} [0 , 6]. Bien entendu, le segment [(3, 4) , (5, 2)] n'est pas dfini dans l'ordre produit, puisque les extrmits ne sont pas comparables (). Dans le cas de l'ordre produit :

si (x, y) P (x', y') alors p(x, y) p(x', y') et q(x, y) q(x', y'). Ces deux applications sont monotones croissantes (). Dans le cas de l'ordre lexicographique :

si (x, y) L (x', y') alors p(x, y) p(x', y'), mais q(x, y) et q(x', y') peuvent tre dans un ordre quelconque.

L'application p est croissante, q n'est pas monotone. 4) A = {(m, n) | n 4, m 2} : Les minorants () de A sont infrieurs (2, 4), donc de la forme (x, y) avec :

x < 2 ou x = 2, y 4.



L'lment ( 2, 4) est le plus petit lment de A : dans A les lments (u, v) vrifient u 2, et v 4. Les minorants de (2, 4) sont donc les minorants de A. Le complmentaire de A n'est pas major, puisqu'il contient des lments d'abscisse aussi grande qu'on veut, en particulier il n'a pas de plus grand lment. Non, A n'est pas un intervalle () : entre (2, 4) et (1, 4) il y a une infinit d'lments qui n'appartiennent pas A : {1} ] , 4].

Un prdcesseur () de (a, b) est un lment (a', b') tel que : (a', b')



exercice 3-C

1) Dans un ensemble totalement ordonn, une partie finie F non vide a un plus grand et un plus petit lment. On peut le voir par rcurrence sur le nombre d'lments : soit n le nombre d'lments de F. Si n = 1 c'est vident. Supposons la proprit vraie pour un ensemble n 1 lments, soit a un lment de F. La partie F \ {a} a n 1 lments, soit b son plus petit lment et c son plus grand lment. E est totalement ordonn, donc soit a < b soit a b. Dans le premier cas, a = min(F), sinon, b = min(F). De mme a et c sont comparables, donc si a > c, max(F) = a, sinon max(F) = c. 2) Soit a un minorant de la partie F, et b un majorant. La partie F est contenue dans le segment [a , b]. Il est donc quivalent de voir si, dans E, tout segment ferm est fini. C'est vrai dans N, par exemple. Par contre, on a vu que ce n'est pas vrai dans Z Z, ordonn par l'ordre lexicographique. 3) L encore, on voit que ce n'est pas vrai dans Z Z, ordonn par l'ordre lexicographique, ainsi {1} Z est major, par (2, 0) par exemple, et n'a pas de plus grand lment.

exercice 4-C

Exemples : a) tout ensemble totalement ordonn est un treillis. b) si E est un ensemble, P(E), ordonn par inclusion, est un treillis. La borne suprieure de {A, B} est l'union A B, la borne infrieure est l'intersection A B. 1) Si E et F sont des ensembles totalement ordonns, soit (x, y) et (z, t) des lment de E F, et A ={(x, y), (z, t)}.



On peut faire des dessins. Distinguons les cas :

() x z et y t, alors (x, y) = min(A), (z, t) = max(A) ; () x z et t y, un majorant (u, v) de A vrifie :

x u, z u, y v, t v. En particulier (z, y) est un majorant, et c'est le plus petit.

De mme, (x, t) est le plus grand minorant. Les autres cas reviennent changer les rles des deux lments. 2) On dmontre cette proprit par rcurrence. Elle est vraie par dfinition pour les parties deux lments (ainsi que pour celles un lment). Supposons la proprit vraie pour toute partie n 1 lments. Soit F une partie ayant n lments. Soit a un lment de F, on note G la partie n 1 lments dfinie par :

G = F \ {a}, et b = inf(G), c = sup(G) (par convention, les bornes sont dfinies dans E). La partie {a, b} a une borne infrieure, soit b'. Cet lment b' est infrieur a et b donc tout lment de F, c'est un minorant de F. Soit x un minorant de F. Cet lment vrifie :

x a, et : y G, x y, donc, par dfinition de b :

x b. Cet lment x est donc un minorant () de {a, b}, donc x b'. On voit que b' est le plus grand minorant de F, c'est--dire sa borne infrieure. On prouve de la mme faon que F a une borne suprieure, qui est :

c' = sup({a, c}).



3) Comparons les structures ordonnes de ces deux ensembles (qui ont bien le mme nombre d'lments). On voit qu'elles sont semblables ("isomorphes"). Les reprsentations suggrent la dfinition suivante pour une application 3 de P({1, 2, 3}) dans {0, 1}3, qui respecte l'ordre, c'est--dire qui est croissante.

(0, 0, 0), {1} (1, 0, 0), {2} (0, 1, 0), {3} (0, 0, 1),

{1, 2} (1, 1, 0), {1, 3} (1, 0, 1), {2, 3} (0, 1, 1),

(1, 2, 3) (1, 1, 1). En vue de la gnralisation demande dans la question suivante, on remarque que, si pri dsigne la projection sur le i-me facteur :

pri((a1, a2, a3)) = ai, la bijection u ci-dessus se caractrise par :

pri(3(F)) = 1 si i F, et 0 sinon.(i = 1, 2, 3). La bijection rciproque, soit v, est galement croissante :

v((a1, a2, a3)) = {i | ai 0}. 4) On gnralise en caractrisant l'application n entre P({1, 2, , n}) et {0, 1}n par la mme relation que ci-dessus :

pri(n(F)) = 1 si i F, et 0 sinon.(i = 1, 2, , n). La bijection rciproque est, comme la question 3) :

v((a1, , ai, , an)) = {i | ai 0}.

exercice 5-C

1) tableau des valeurs :



(0, 0, 0) 0 (1, 0, 0) 4 (0, 0, 1) 1 (1, 0, 1) 5 (0, 1, 0) 2 (1, 1, 0) 6 (0, 1, 1) 3 (1, 1, 1) 7

Il est clair qu'il s'agit d'une bijection croissante. La bijection rciproque, qui est galement croissante, correspond l'criture d'un entier en base 2 : par exemple 101 est l'criture de 5, 11 l'criture de 3. Comme de coutume, le chiffre de poids le plus fort est gauche. 2) On gnralise l'application en posant :

bn (a0 ,a1,,an 1) = a i2n1ii = 0

i = n1

.

C'est une application strictement croissante : si x et y sont des n-uples, avec x 2pp =0

p =k 1

,

la somme ci-dessus est donc bien strictement positive, et l'application est injective. L'image de {0, 1}n par cette application est le segment d'entiers :

[0 , 2n 1 ]. La bijection rciproque correspond l'criture d'un entier au plus gal 2n 1 sous forme binaire.



exercice 6-C

Soit A un arbre, et f une feuille. Soit B le complmentaire de f dans A. Si {a, b} est une partie de B, c'est une partie de A. Elle a une borne infrieure dans A, soit c. Cet lment c est dans B puisque f n'a pas d'lment plus grand que lui, donc c'est la borne infrieure de {a, b} dans B. Si les lments a et b ne sont pas comparables, la partie {a, b} n'a pas de majorant dans A, donc a fortiori pas de majorant dans B. 1) On dessine les arbres de proche en proche partir de cette remarque. 2) Soit A un arbre et A' une partie non vide de A. On raisonne par rcurrence sur le nombre d'lments de A'. Par dfinition, si A' a deux lments, la proprit est vraie. Supposons que A' a n lments, et supposons la proprit vraie pour n 1. Soit f un lment de A', et B' le complmentaire de {f} dans A'. Soit r la borne infrieure de B'. L'ensemble {f, r} a une borne infrieure, qui est la borne infrieure de A'. Appliquons cette proprit l'arbre A. Il a une borne infrieure, qui est en mme temps un lment de A, donc un minimum (). 3) Soit B une partie majore de l'arbre A. On fait un raisonnement par l'absurde : supposons qu'il existe dans B deux lments, soient a et b, non comparables (). Alors la partie {a, b} n'a pas de majorant, ce qui contredit l'hypothse sur B. Ces lments n'existent donc pas : B est totalement ordonn (). Comme il s'agit d'une partie finie, elle a donc un plus grand lment.

Soit f un lment de l'arbre A. Si f n'est pas le plus petit lment de A, l'ensemble B(f) des minorants de {f} n'est pas gal {f}. L'ensemble B(f) \ {f} est non vide et major, donc il a un plus grand lment, soit g. Cet lment g vrifie :

g < f, et il n'y a pas d'lment entre g et f, puisque g est le plus grand des minorants stricts de f. Il en rsulte que g est le prdcesseur () de f.



4) L'ensemble B(f) est non vide et major donc totalement ordonn. On raisonne par l'absurde : supposons que a et b vrifient a b, h(a) = h(b), et de plus a b. Dans ce cas, b est un lment de B(b) mais pas de B(a). Il en rsulte que B(a) B(b) et B(a) B(b), donc h(b) > h(a) d'o une contradiction. 5) Il faut montrer que l'application dfinie est strictement croissante. Soient f et f' deux lments distincts comparables de l'arbre, par exemple f f'. La hauteur de f' est donc strictement plus grande que celle de f. Or :

10 u(pred(x)) + 9 u(x) 10 u(pred(x)), donc, par rcurrence : 2 10h(x) 1 u(x) 10h(x),

donc : u(f') > u(f).

On a ainsi tabli une bijection croissante entre un ensemble non totalement ordonn (en gnral) et un ensemble totalement ordonn (partie de N).

exercice 7-C

A la lumire de l'exercice prcdent, on voit que cette conjecture est fausse. On a un contre-exemple avec E non totalement ordonn, et F totalement ordonn. Examiner de ce point de vue d'autres exemples vus prcdemment. (QC-1) Supposer de plus E totalement ordonn. Que devient cette conjecture ?

exercice 8-C

1) Soit y = f(x), un lment de f(A), x tant un lment de A. On a : x max(A), donc f(x) f(max(A)).



De plus max(A) est un lment de A donc f(max(A)) est un lment de f(A). 2) Soit y = f(x), un lment de f(A), x tant un lment de A. On a :

x supE(A), donc f(x) f(supE(A)), donc : supE(A) est un majorant de f(A).

Est-ce le plus petit majorant ? Soit b un majorant de f(A) on ne voit pas bien comment enchaner pour comparer b et f(supE(A)). Il y a deux difficults : F n'tant pas suppos totalement ordonn, b et f(supE(A)) ne sont pas ncessairement comparables () ; f n'tant pas suppose surjective (), on ne peut pas comparer dans E. Cherchons un contre-exemple avec les applications ci-dessus :

f1 ne convient pas, c'est une situation correspondant la question 1) f3 n'est pas surjective, soit A = [0 , 1[. On a :

sup(A) = 1, f3 (1) = 1, f3(A) = [1 , 0[, sup(f3(A)) = 0.

Dans ce cas, f3(A) a bien une borne suprieure, mais ce n'est pas l'image de la borne suprieure de A. Remarquer que les ensembles sont totalement ordonns. (QC-1) Que peut-on dire de f2 ? (QC-2) Reprendre la question en supposant f surjective et E, et F totalement ordonns. Identifier la difficult qui subsiste. 3) On sait que succ(a) > a, donc f(succ(a)) f(a). En l'absence d'hypothse d'injectivit () sur f, on ne sait pas si f(succ(a)) f(a). On ne peut donc conclure. On voit la mme difficult pour l'image du prdcesseur. Cherchons un contre-exemple ; pour une application croissante non injective de N dans N, on peut prendre :

g : n E(n/3). On voit que :



g(0) = g(1) = 0, donc g(succ(0)) succ(g(0)), g(4) = g(3) = 1, donc g(pred(4)) pred(g(4)).

(QC-3) reprendre la question en supposant de plus f injective. 4) Soit B une partie non vide de F. Comme f est surjective,

B = f*(f*(B)).

La partie non vide f*(B) de E a un plus petit lment, donc son image aussi. L'ensemble F est Bien Ordonn (). Soit b un lment de F. On suppose que b n'est pas min(F). Il a un antcdent, soit a. Si a est min(E), tout lment de E est suprieur a, donc tout lment de F est suprieur b, ce qui est faux. Donc a admet un prdcesseur, soit a' :

a' < a, il n'y a pas d'lment entre a' et a. Sans hypothse d'injectivit sur f, on ne sait pas si b' = f(a') < f(a) = b.

Supposons que f est injective. S'il existe b" strictement compris entre b' et b, soit a" un antcdent de b". Comme E est totalement ordonn, a" est comparable a :

a a" est impossible car cela entrane b b" alors que b" < b, donc : a" < a.

De mme, on tablira que a' < a". Or a' est le prdcesseur de a, donc a" n'existe pas, et donc b" n'existe pas. Donc si f(a') f(a), f(a') est bien le prdcesseur de f(a). Si f(a') est gal f(a), f(a) n'a pas toujours de prdcesseur : reprendre l'application :

g : n E(n/3), on voit que g(2) n'a pas de prdcesseur, puisque c'est 0, alors que 2 a un prdcesseur. Remarquer toutefois que sur cet exemple g(2) est le plus petit lment.


indications p

Documents

Daniel Alibert - Cours Et Exercices Corrigés - Volume 2