Daniel Alibert - Cours et exercices corrigés, volume 1

  • Upload
    walanta

  • View
    243

  • Download
    4

Embed Size (px)

DESCRIPTION

Chaque volume comprend des rappels de cours sans démonstration, et des exercices corrigés.Volume 1 : ensembles, applications, relations, logique élémentaire

Citation preview

  • Daniel ALIBERT cours et exercices corrigs volume 1 1

    Daniel ALIBERT

    Ensembles, applications. Relations d'quivalence. Lois de composition (groupes). Logique lmentaire.

    Objectifs :

    Dmontrer que deux ensembles sont gaux, matriser les oprations lmentaires ensemblistes (union, intersection, complmentaire), utiliser les applications (dfinition, image d'une partie, image rciproque), caractriser et utiliser l'injectivit, la surjectivit, la bijectivit. Utiliser les relations d'quivalence, classes d'quivalence, compatibilit de structures avec une relation, passage au quotient. Utiliser la structure de groupe. Dans un nonc mathmatique, identifier les connecteurs 'ou' et 'et', les quantificateurs, savoir crire une rciproque, la ngation d'une proposition, une contrapose, savoir ce qu'est un contre-exemple, quel est son rle.

  • Daniel ALIBERT cours et exercices corrigs volume 1 2

  • Daniel ALIBERT cours et exercices corrigs volume 1 3

    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.

  • Daniel ALIBERT cours et exercices corrigs volume 1 4

    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

  • Daniel ALIBERT cours et exercices corrigs volume 1 5

    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).

  • Daniel ALIBERT cours et exercices corrigs volume 1 6

    Table des matires

    1 A Savoir ........................................................................ 9 1-1 Ensembles ..................................................... 9 1-2 Applications ................................................ 11 1-3 Relations d'quivalence ............................... 12 1-4 Lois de composition - structures ................. 14 1-5 Logique lmentaire .................................... 17

    2 Pour Voir .................................................................... 25 2-1 Ensembles ................................................... 25 2-2 Applications ................................................ 31 2-3 Relations d'quivalence ............................... 41 2-4 Lois de composition - structures ................. 48 2-5 Logique lmentaire .................................... 58

    3 Pour Comprendre et Utiliser ...................................... 61 3-1 noncs des exercices ................................. 61 3-2 Corrigs des exercices ................................. 81 3-3 Corrigs des questions complmentaires .. 127

    4 Pour Chercher ........................................................... 141 4-1 Indications pour les exercices ................... 141 4-2 Mthodes ................................................... 147 4-3 Lexique ...................................................... 153

  • Daniel ALIBERT cours et exercices corrigs volume 1 7

  • Daniel ALIBERT cours et exercices corrigs volume 1 8

    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. Seule la partie 1-5 (logique lmentaire), qui n'est pas toujours expose dans les cours, a t un peu dveloppe, avec un objectif utilitaire cependant. Vous trouverez des exemples dans la partie 2 * Pour Voir.

    1-1 Ensembles

    Dfinition Un ensemble est dfini en extension quand on donne la liste des lments :

    H = {1, 2, pi, 12}.

    Dfinitions Un ensemble est dfini en comprhension quand on donne une proprit caractrisant les lments : par exemple

    A = {x Q | il existe un rel tel que 2 = x}

    A partir de deux ensembles, E et F, on peut dfinir un autre ensemble :

  • Daniel ALIBERT cours et exercices corrigs volume 1 9

    Le produit cartsien de E et F, not E F est l'ensemble des couples (x,y) forms d'un lment x de E et d'un lment y de F. Attention, un couple est ordonn : le couple (x, y) n'est pas le couple (y, x) (sauf si x = y). On dfinit plus gnralement le produit cartsien d'une famille d'ensembles : E F G H, par exemple, est le produit des 4 ensembles E, F, G, H.

    galit de deux ensembles : soient A et B des ensembles. Ils sont gaux s'ils ont les mmes lments. Inclusion d'un ensemble dans un autre : A B si tout lment de A est lment de B.

    Si A B et B A, alors A = B. Les oprations les plus courantes entre deux ensembles sont : L'intersection : A B a pour lments les lments qui appartiennent A et B La runion : A B a pour lments les lments qui appartiennent A ou B Le passage au complmentaire : si E est un ensemble et si A E, les lments de CE(A) sont les lments de E qui ne sont pas lments de A

    Les sous-ensembles d'un ensemble E sont les lments d'un nouvel ensemble, not P(E), qui est l'ensemble des "parties de E".

  • Daniel ALIBERT cours et exercices corrigs volume 1 10

    Dfinition

    Une relation d'un ensemble E dans un ensemble F est une proprit des lments de E F. Si la proprit est vraie pour le couple (x, y), on dit que "x est en relation avec y", et l'on crit souvent "x R y". Dans le cas contraire, on dit que "x n'est pas en relation avec y". La lettre R dsigne alors la relation et symbolise la phrase "est en relation avec" (une autre lettre que R peut videmment tre utilise). Le sous-ensemble de E F form des couples (x, y) vrifiant x R y est le graphe de la relation R.

    1-2 Applications

    Les applications sont des relations particulires, celles qui vrifient : "pour tout x de E il existe un unique y de F tel que

    x est en relation avec y" Cet lment y de F est appel l'image de x par l'application. Si f dsigne cette application, on crit :

    y = f(x). L'application identique de E, note IdE, est l'application de E dans E qui associe tout x de E l'lment x lui-mme. Si y = f(x), l'lment x est appel un antcdent de y. Si f est une application de E dans F, et g une application de F dans G, on dfinit une application compose de f et g, note gof, par :

    gof (x) = g(f(x)).

  • Daniel ALIBERT cours et exercices corrigs volume 1 11

    Dfinition

    Soit f une application de E dans F, et A une partie de E, A' une partie de F. On appelle image directe de A par f et l'on note f

    *(A) (ou f(A)) le

    sous-ensemble de F dfini par : f* (A) = {y F | il existe x A tel que f(x) = y}.

    On appelle image rciproque de A' par f, et l'on note f*(A') (ou f -1(A')) le sous-ensemble de E dfini par :

    f*(A') = {x E | f(x) A'}.

    Dfinition

    Soit f : E --. F une application. On dit que f est injective si pour tout x et tout y de E on a l'implication :

    f(x) = f(y) x = y. On dit que f est surjective si pour tout x' de F, il existe au moins un x de E tel que :

    f(x) = x'. On dit qu'une application f est bijective si elle est la fois injective et surjective. Si f est bijective, il existe une application rciproque de f, c'est--dire une application :

    g : F --. E telle que gof = IdE , et fog = IdF. L'application rciproque de f est gnralement note f -1.

  • Daniel ALIBERT cours et exercices corrigs volume 1 12

    1-3 Relations d'quivalence

    Dfinition

    Soit R une relation de E dans lui-mme. 1- R est rflexive si pour tout x de E, x R x est vrai. 2- R est symtrique si pour tout x et tout y de E on a l'implication

    x R y y R x. 3- R est antisymtrique si pour tout x et tout y de E on a l'implication

    (x R y et y R x) x = y. 4- R est transitive si pour tout x, tout y, tout z de E on a l'implication

    (x R y et y R z) x R z. Une relation rflexive, symtrique et transitive est appele une relation d'quivalence.

    Dfinition

    Soit E un ensemble, muni d'une relation d'quivalence R. Pour tout lment x de E, on appelle classe d'quivalence de x et l'on note C(x) le sous-ensemble de E form des lments y tels que x R y soit vrai. Ces lments y sont dits quivalents x.

    Proprit

    Si x et y sont quivalents, alors C(x) = C(y), et la rciproque est vraie.

  • Daniel ALIBERT cours et exercices corrigs volume 1 13

    Proprit

    Les sous-ensembles C(x) forment une partition de E, ce qui signifie que : a. C(x) C(y) est soit vide soit gal C(x) et C(y). b. La runion des sous-ensembles C(x) est E. c. Aucune des parties C(x) n'est vide. Rciproquement, la donne d'une partition de E dfinit une relation d'quivalence sur E.

    Dfinition

    L'ensemble des classes d'quivalence, sous-ensemble de l'ensemble P(E) des parties de E, est appel l'ensemble quotient de E par la relation R. Il est souvent not E/R. L'application de E dans E/R, qui un lment x associe sa classe d'quivalence, est l'application canonique de passage au quotient. Cette application est surjective. Si est une classe d'quivalence, tout lment de E dont la classe est est appel un reprsentant de .

    1-4 Lois de composition - structures

    Parmi les applications, on distingue les lois de composition, ou oprations.

    Dfinition

    Soient E et F des ensembles, une loi de composition est une application : F E . E.

  • Daniel ALIBERT cours et exercices corrigs volume 1 14

    Si E F, on dit que c'est une loi externe, ou encore que F opre sur E. Sinon on parle de loi interne. Pour des raisons de commodit dans les calculs, on note ce type d'application de la manire suivante :

    (x, y) . x T y, ou x y par analogie avec x + y par exemple.

    Dfinitions

    Soit E un ensemble et T une loi de composition interne dans E. On dit que T est associative si pour tout x, tout y, tout z de E on a l'galit :

    (x T y) T z = x T (y T z). On dit que T est commutative si pour tout x et tout y de E on a l'galit :

    x T y = y T x. Un lment neutre pour T est un lment, soit e, tel que pour tout x de E on a l'galit :

    e T x = x T e = x.

    Proprit

    Il ne peut y avoir qu'un lment neutre au plus pour une opration donne. On l'appelle encore lment unit, ou zro, selon la loi T.

    Dfinition

    Si T admet un lment neutre e, on dit qu'un lment x de E admet x' pour symtrique pour T si l'galit suivante est vraie :

    x T x' = x' T x = e.

  • Daniel ALIBERT cours et exercices corrigs volume 1 15

    Cet lment est alors unique, on le note souvent sym(x).

    Dfinition

    Si E admet une autre loi de composition interne, soit , on dit que la loi est distributive sur la loi T (ou par rapport la loi T) si pour tout x, tout y E on a les galits :

    x (y T z) = (x y) T (x z), et (y T z) x = (y x) T (z x).

    Dfinition

    Soit (E, T) un ensemble muni d'une loi de composition interne. On dit que (E, T) est un groupe si : 1- T est associative, 2- T admet un lment neutre, 3- tout lment de E a un symtrique pour T. Si de plus T est commutative, on dit que (E, T) est un groupe commutatif, ou ablien. Soit (G, T) un groupe et H une partie de G. On dit que H est stable par T si pour tout couple (x, y) d'lments de H, x T y est un lment de H. Si H est stable par T, on dit que H est un sous-groupe de (G, T) si (H, T) est lui-mme un groupe.

    Proprit

    Soit (G, T) un groupe, et H une partie de G. Pour que H soit un sous-groupe de (G, T), il faut et il suffit que les proprits suivantes soient vrifies : 1) H est non vide. 2) Pour tout x et tout y de H l'lment x T sym(y) appartient H.

  • Daniel ALIBERT cours et exercices corrigs volume 1 16

    Dfinition

    Soient (G, T), et (H, ) des ensembles, munis de lois internes. On appelle homomorphisme de G vers H une application :

    f : G . H telle que pour tout x et tout y de G on ait :

    f(x T y) = f(x) f(y). On parlera en particulier d'homomorphisme de groupes.

    Dfinition

    Soit E un ensemble sur lequel sont dfinies la foi une loi interne et une relation d'quivalence R. On dit que R et sont compatibles si pour tous les couples (x, y), (z, t) de E, la proprit suivante est vraie :

    si x R y, et z R t, alors x z R y t.

    Proprit

    Dans la situation prcdente, on peut dfinir une loi interne sur l'ensemble quotient E/R en posant pour des classes C(x), C(z) :

    C(x) T C(z) = C(x z). Si est associative (resp. commutative) on vrifie facilement que T l'est galement. Si (E, ) est un groupe, (E/R, T) l'est galement.

    1-5 Logique lmentaire

    La connaissance de quelques rgles de base de logique aide viter les erreurs de raisonnement les plus grossires. Elle permet galement

  • Daniel ALIBERT cours et exercices corrigs volume 1 17

    souvent de commencer la recherche d'une solution en tant capable d'attaquer un problme sous diffrents angles. Le premier point consiste savoir lire avec prcision un nonc mathmatique pour bien comprendre comment s'articulent les diffrentes hypothses, conditions etc.

    1-5-1 nonc universel, nonc existentiel

    Un modle frquent d'nonc est le suivant : si "A", alors "B"

    schmatis par une implication : A B.

    Dans ce modle, A reprsente une ou plusieurs conditions, ou hypothses, ventuellement relies par des connecteurs logiques (et, ou), B reprsente une ou plusieurs conclusions galement relies par des connecteurs. Par ailleurs, ces conditions portent sur des objets mathmatiques (nombres, fonctions) et dcrivent des proprits que ces objets peuvent satisfaire (ou non). L'nonc :

    si "A", alors "B" est alors vrai si pour tout objet x vrifiant l'hypothse A, la conclusion B est galement vrifie : autrement dit, si on passe en revue les diffrents cas possibles (A(x) vrai ou faux, B(x) vrai ou faux) l'nonc est vrai si et seulement si il n'y a pas de cas x o A(x) est vrai et B(x) faux.

  • Daniel ALIBERT cours et exercices corrigs volume 1 18

    Dfinition

    S'il existe un cas x o A(x) est vrai et B(x) faux, on dit que x est un contre-exemple l'nonc :

    si "A", alors "B". On appellera exemple de cet nonc un cas x o A(x) est vrai et B(x) vrai, et non-exemple un cas o A(x) est faux, quelle que soit la valeur de B(x). Un nonc vrai peut avoir des exemples ou des non-exemples mais pas de contre-exemple.

    L'nonc : si "A", alors "B"

    contient donc (souvent de manire implicite) une condition sur les cas possibles : dans tous les cas o A(x) est vrai, alors B(x) doit tre vrai galement. On dit que cet nonc contient un quantificateur universel (tous les cas). On note ce quantificateur ("pour tout", ou "quel que soit"). On crira par exemple :

    x, A(x) B(x). On lira "pour tout x, si A(x) est vrai alors B(x) est vrai" ou "quel que soit x, A(x) implique B(x)".

    tant donne une proprit P, on peut galement vouloir exprimer qu'il y a au moins un cas o cette proprit est vraie (par exemple une quation a une solution au moins, une fonction est drivable en un point au moins).

  • Daniel ALIBERT cours et exercices corrigs volume 1 19

    Cette affirmation utilise un quantificateur existentiel, not , "il existe" : x, P(x).

    On lira "il existe au moins un x tel que P(x) est vrai".

    Il est indispensable, la lecture d'un nonc, d'identifier clairement s'il s'agit d'un nonc universel, ou d'un nonc existentiel. Les techniques utiliser pour dmontrer cet nonc seront diffrentes.

    1-5-2 Connecteurs. Ngation. Tables de vrit

    Les conditions composes de plusieurs affirmations doivent tre analyses pour savoir, en fonction de la vrit ou de la fausset des diffrentes affirmations, dans quel cas elles sont vraies ou fausses.

    Un moyen simple est d'utiliser les tables de vrit :

    Pour "A ou B" :

    A ou B A = V A = F B = V V V B = F V F

    qui se lit : si A est vrai et B vrai, "A ou B" est vrai, si A est vrai et B est faux, "A ou B" est vrai etc.

  • Daniel ALIBERT cours et exercices corrigs volume 1 20

    Pour "A et B" :

    A et B A = V A = F B = V V F B = F F F

    Il est frquent d'avoir utiliser la ngation d'un nonc P : "P est faux", souvent crit "non(P)" :

    P = V P = F non(P) F V

    Si la condition P est compose, il faut savoir crire non(A et B), et non(A ou B). "non(A ou B)" :

    non(A ou B) A = V A = F B = V F V B = F V V

    On voit que cette table correspond non(A) et non(B). Les conditions non(A ou B) et "non(A) et non(B)" sont donc vraies, ou fausses, dans les mmes cas. On dit qu'elles sont quivalentes.

    De la mme faon, on vrifie que "non(A et B)" et "non(A) ou non(B)" sont quivalentes.

  • Daniel ALIBERT cours et exercices corrigs volume 1 21

    La ngation d'un nonc universel : pour tout x, P(x) , ou encore x, P(x)

    est un nonc existentiel : il existe x tel que non(P(x)), ou encore x, non(P(x)).

    Inversement, si l'nonc est existentiel : il existe x tel que P(x) ou encore x, P(x)

    on crira sa ngation : pour tout x, non(P(x)), ou encore x, non(P(x)).

    Un cas rencontr frquemment est celui de "pour tout x, A(x) implique B(x)". On crira que cet nonc est faux en crivant qu'il admet un contre-exemple :

    il existe un x tel que A(x) et non(B(x)).

    Enfin pour un nonc o plusieurs propositions sont "enchsses" les unes dans les autres, on procdera par paliers : Par exemple :

    pour tout x, il existe y tel que P(x,y). On note Q(x) la proprit pour x : "il existe y tel que P(x, y)", et on crit dans un premier temps la ngation de "pour tout x, Q(x)", soit "il existe x tel que non(Q(x))". La ngation de Q(x) est "pour tout y, non(P(x,y))". On obtient alors :

  • Daniel ALIBERT cours et exercices corrigs volume 1 22

    Il existe x tel que pour tout y, non(P(x, y)).

    On verra des applications dans le volume consacr aux limites par exemple, ou sur les fonctions continues

    1-5-3 transformation de propositions

    A partir d'un nonc "si A alors B", on peut crire d'autres propositions :

    La rciproque de cet nonc est "si B alors A". Sa vrit est indpendante de celle de "si A alors B". Les tables des exemples de ces noncs sont :

    A B A = V A = F B = V E n-E B = F c-E n-E

    B A A = V A = F B = V E c-E B = F n-E n-E

    On voit bien que l'existence d'un contre-exemple pour l'un de ces noncs n'entrane rien de tel pour l'autre (change n-E c-E). La contrapose de "si A alors B" est "si non(B) alors non(A)". Ces noncs sont quivalents :

    A B A = V A = F B = V E n-E

  • Daniel ALIBERT cours et exercices corrigs volume 1 23

    B = F c-E n-E

    non(B) non(A) A = V A = F B = V n-E n-E B = F c-E E

    Les contre-exemples correspondent aux mmes cas pour ces deux noncs (A vrai et B faux). Ils sont donc vrais, ou faux, simultanment, donc quivalents. On observera que bien des rsultats se dmontrent en passant par une dmonstration de la contrapose. Du point de vue des tables de vrit :

    A B A = V A = F B = V V V B = F F V

    B A A = V A = F B = V V F B = F V V

    non(B) non(A) A = V A = F B = V V V B = F F V

    On se gardera bien de confondre "implication" et "causalit".

  • Daniel ALIBERT cours et exercices corrigs volume 1 24

    Terminons par un mot sur le raisonnement par l'absurde : pour dmontrer une proposition, on suppose que la conclusion est fausse. Si la conjonction de l'hypothse et de la ngation de la conclusion conduit un rsultat contradictoire avec certaines hypothses, ou avec des faits mathmatiques connus, on conclut que l'hypothse auxiliaire niant la conclusion est fausse.

  • Daniel ALIBERT cours et exercices corrigs volume 1 25

  • Daniel ALIBERT cours et exercices corrigs volume 1 26

    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. La correction de ces questions est donne immdiatement.

    2-1 Ensembles

    "A partir de deux ensembles, E et F, on peut dfinir un autre ensemble, le produit cartsien de E et F, not E F. C'est l'ensemble des couples (x,y) forms d'un lment x de E et d'un lment y de F."

    exemple 1

    Soient a, b, c, d, , des nombres distincts, E = {1, 2, 3}, F = {a, b, c}, E F = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c), (3, a), (3, b), (3, c)}. Les lments de E F, dans {0, 1, 2, 3, 4} {a, b, c, d, }, sont nots "X".

    a b c d 0 1 X X X 2 X X X 3 X X X 4

  • Daniel ALIBERT cours et exercices corrigs volume 1 27

    exemple 2 ( traiter) Soient a, b, c, d, e, des nombres distincts, et :

    A = {a, b, d, e}, B = {b, c, d}. Les ensembles suivant sont-ils des sous-ensembles de A B.

    P1 = {(a, b), (b, a), (a, c), (b, c)}, P2 = {(a, c), (b, c), (c, c)} P3 = {(d, b), (e, b), (d, d), (e, d)}.

    # rponse

    Voici des graphiques pour mieux voir : l'ensemble A B est repr par des "X" (en gras) , les lments de P1, P2, P3, sont des "X" (souligns). Les lments communs sont la fois en gras et souligns "X".

    P1 a b c d e a X X X b X X X X c

    d X X X e X X X

    P1 n'est pas une partie de A B : (b, a) n'est pas dans A B.

    P2 a b c d e a X X X b X X X c

    X d X X X

  • Daniel ALIBERT cours et exercices corrigs volume 1 28

    e X X X P2 n'est pas une partie de A B : (c, c) n'est pas dans A B.

    P3 a b c d e a X X X b X X X c

    d X X X e X X X

    P3 est une partie de A B.

    exemple 3

    Soient x, y, z, t, u des nombres distincts, et E = {x, y, z, t, u}. Soit F = {x, z, u}. On voit facilement que F F est une partie de E E.

    x y z t u x X X X X X y X X X X X z X X X X X t X X X X X u X X X X X

    Soit A = {x, t}, B = {y, t, u}. A B est une partie de E E.

  • Daniel ALIBERT cours et exercices corrigs volume 1 29

    x y z t u x X X X X X y X X X X X z X X X X X t X X X X X u X X X X X

    exemple 4 ( traiter) {(x,x), (x,y), (x,u), (t,x), (t,y), (t,u), (x, z), (u, t)}= G. L'ensemble G est -il une partie de E E ? Est-il le produit cartsien de deux sous-ensembles de E ?

    # rponse

    L'ensemble G est bien une partie de E E. Pour savoir si G est un produit cartsien, il faut "projeter" G sur E par les deux projections (de E E dans E) :

    (a, b) a (a, b) b

    ou encore considrer l'ensemble des "premires coordonnes", soit P et l'ensemble des "secondes coordonnes", soit S, et voir si G = P S.

    x y z t u x X X X X X y X X X X X

  • Daniel ALIBERT cours et exercices corrigs volume 1 30

    z X X X X X t X X X X X u X X X X X

    P = {x, t, u}, et S = E. Si G est un produit cartsien, G = P S. Ce n'est pas le cas, donc G n'est pas le produit cartsien de parties de E.

    "Les sous-ensembles d'un ensemble E sont les lments d'un nouvel ensemble, not P(E), qui est l'ensemble des parties de E."

    exemple 5

    E = {1, 2, 3}. P(E) = {, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

    Ne pas oublier la partie vide, ni la partie pleine. L'ensemble E a trois lments, l'ensemble P(E), 8 lments.

    exemple 6 ( traiter) Soient a, b, c, d des lments distincts. Ecrire P({a, b, c, d}). Combien y a-t-il d'lments ? Essayer de deviner une formule donnant le nombre de parties d'un ensemble qui a n lments.

    # rponse

    Dans P({a, b, c, d}), on a : une partie zro lments, ,

    quatre parties un lment, {a}, {b}, {c}, {d},

  • Daniel ALIBERT cours et exercices corrigs volume 1 31

    quatre parties trois lments, six parties deux lments, une partie quatre lments.

    Nombre de parties : 1 + 4 + 4 + 6 + 1 = 16. Un ensemble n lments a 2n parties : on le vrifie par rcurrence.

    "Une relation d'un ensemble E dans un ensemble F est une proprit des lments de E F."

    exemple 7

    A = {1, 2, 3, 4, 5, 6, 7, 8, 9} ; R est la relation de A dans A dfinie par x R y si x + y est divisible par 3. Le graphe de R dans A A est donn par le tableau (par convention, le premier terme figure dans la colonne de gauche, le second dans la ligne du haut). Par exemple 2R1 puisque 2 + 1 = 3, on a mis une X dans la ligne de 2, colonne de 1.

    xOy

    1 2 3 4 5 6 7 8 9

    1 X X X 2 X X X 3 X X X 4 X X X 5 X X X

  • Daniel ALIBERT cours et exercices corrigs volume 1 32

    6 X X X 7 X X X 8 X X X 9 X X X

    exemple 8 ( traiter) Q = P({1, 2, 3}). Ecrire le graphe de la relation R dans Q dfinie par :

    A R B si A B = .

    # rponse

    AOB

    {1} {2} {3} {1,2} {2,3} {1,3} {1,2,3} X X X X X X X X {1} X X X X {2} X X X X {3} X X X X {1,2} X X {1,3} X X {2,3} X X {1,2,3} X

  • Daniel ALIBERT cours et exercices corrigs volume 1 33

    2-2 Applications

    "Les applications sont des relations particulires, celles qui vrifient : pour tout x de E, il existe un unique y de F tel que x soit en relation avec y."

    exemple 9

    Les relations prsentes ci-dessus ne sont pas des applications. Avec les conventions utilises dans ces tableaux, il faut vrifier que dans chaque ligne il y a un et un seul lment.

    E = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. La relation de E dans E qui s'crit x R y si :

    x y est divisible par 3 et y < 3 se reprsente dans le tableau suivant (x repre la ligne, y la colonne) :

    xOy

    0 1 2 3 4 5 6 7 8 9

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

  • Daniel ALIBERT cours et exercices corrigs volume 1 34

    Il y a bien un et un seul terme dans chaque ligne. C'est une application de E dans E. On voit bien qu'il ne faut pas confondre "application" et "formule".

    exemple 10 ( traiter) F = { 3, 2, 1, 0, 1, 2, 3, 4, 5, 6}. On utilise la mme relation que ci-dessus :

    x y est divisible par 3 et y < 3. Reprsenter le graphe de cette relation. Est-ce une application ?

    # rponse

    Le graphe est reprsent ci-contre.

    xOy

    3 2 1 0 1 2 3 4 5 6

    3 X X 2 X X 1 X X 0 X X 1 X X 2 X X 3 X X 4 X X 5 X X 6 X X

    Ce n'est donc pas une application : il y a deux termes dans chaque ligne.

  • Daniel ALIBERT cours et exercices corrigs volume 1 35

    "Soit f une application de E dans F, et A une partie de E, A' une partie de F. On appelle image directe de A par f et on note f

    *(A) le sous-ensemble de F dfini par f

    *(A) = { y

    F | il existe x A tel que f(x) = y }. On appelle image rciproque de A' par f, et on note f*(A') (ou f -1(A')) le sous-ensemble de E dfini par : f*(A') = { x E | f(x) A' }."

    exemple 11

    Sur le dessin suivant on figure l'image d'une partie de E, et l'image rciproque d'une partie de F. L'application de E dans F consiste projeter orthogonalement. L'image rciproque de B est forme de tous les points "au-dessus de B". L'image de A est forme des points "au-dessous de A".

  • Daniel ALIBERT cours et exercices corrigs volume 1 36

    exemple 12 ( traiter) Reprsenter sur un dessin analogue f*(f

    *(A)) et f

    *(f*(B)).

    # rponse

    Les points de f*(f*(B)) sont les points de B "au-dessous" de points de

    f*(B). Les points de f*(f*(A)) sont les points "au-dessus" d'un point de F

    image d'un point de A. On voit clairement sur cet exemple un cas o B f

    *(f*(B)) et A f*(f

    *(A)).

  • Daniel ALIBERT cours et exercices corrigs volume 1 37

    "Soit f : E --. F une application, On dit que f est injective si pour tout x et tout y de E on a l'implication f(x) = f(y) x = y."

    exemple 13

    L'application schmatise l'exemple prcdent n'est, bien sr, pas injective. La notion d'application injective est en troite liaison avec la question de l'unicit des solutions d'une quation. Ainsi soit A = [1000 , 2000] un intervalle de N. On associe un lment x de A un lment y de N : y est le reste de la division de x par 1234. Cette application de A dans N est injective : supposons que x et x' aient le mme reste dans la division par 1234 :

    x = 1234 q + y x' = 1234 q' + y

    donc x x' = 1234 (q q'), et a fortiori | x x' | = 1234 | q q' |. Or | x x' | est au plus gal 1000, donc | q q' | est un entier positif ou nul infrieur 1, c'est--dire 0, donc x = x'.

    exemple 14 ( traiter) Soit b un rel strictement positif. On dfinit une application f de [0 , +[ dans R, par :

    f(x) = x2 + bx 1. Cette application est-elle injective ?

    # rponse

    On cherche si, tant donn un rel y, l'quation en x : x2 + bx 1 = y

  • Daniel ALIBERT cours et exercices corrigs volume 1 38

    a une seule solution, ou aucune. Si x et x' sont des solutions : x'2 + bx' 1 = y x2 + bx 1 = y

    soit : x'2 x2 + b(x' x) = 0.

    Si x x', on peut simplifier par x x', d'o : x + x' + b = 0.

    Or x et x' sont positifs ou nuls, et b est strictement positif, donc cette galit est fausse. Il n'est donc pas possible que x et x' soient distincts. L'application est injective. (NB : exemple de raisonnement par l'absurde.)

    "On dit que f est surjective si pour tout x' de F il existe au moins un x de E tel que f(x) = x'."

    exemple 15 L'application de l'exemple 11 n'est pas surjective : certains points de F ne sont "au-dessous" d'aucun point de E. L'application de l'exemple 13 n'est pas surjective, puisque y est ncessairement infrieur 1234. Il est clair que la surjectivit dpend du choix de l'ensemble o l'application prend ses valeurs. La surjectivit est troitement lie l'existence de solutions des quations : pour l'application f de l'exemple 14, il faut chercher pour quelles valeurs de y relles l'quation en x :

    x2 + bx 1 = y a des solutions positives.

  • Daniel ALIBERT cours et exercices corrigs volume 1 39

    Le discriminant est b2 + 4 + 4y. Il y a au moins une solution relle si :

    y 1 b2

    4.

    La somme des racines tant b, donc ngative, il n'y a de solution positive ou nulle que si le produit est ngatif ou nul (racines de signes opposs) soit si 1 + y 0. En rsum, il y a une solution positive ou nulle si et seulement si y 1. On dira donc que si l'ensemble d'arrive de l'application est [ 1 , + [ l'application est surjective. Si cet ensemble est R, elle n'est pas surjective.

    "Soit R une relation de E dans lui-mme ; R est rflexive si pour tout x de E, x R x est vrai ; R est symtrique si pour tout x et tout y de E on a l'implication x R y y R x ; R est antisymtrique si pour tout x et tout y de E on a l'implication (x R y et y R x) x = y ; la relation R est transitive si pour tout x, tout y, tout z de E on a l'implication (x R y et y R z) x R z ."

    exemple 16

    E = {a, b, c, d, e}. On tudie la relation dont le graphe est :

    a b c d e a X X b X X c X X X d X X e X X

    Elle n'est pas rflexive : (c, c) n'est pas dans le graphe.

  • Daniel ALIBERT cours et exercices corrigs volume 1 40

    Elle n'est pas symtrique : (c, b) est dans le graphe mais pas (b, c). Enfin elle n'est pas transitive : (a, c) est dans le graphe, (c, e) aussi, mais pas (a, e). Si on veut complter le graphe pour obtenir celui d'une relation rflexive, il faut adjoindre (c, c) (toute la diagonale de E E, c'est--dire les lments (z, z), z quelconque dans E, doit tre contenue dans le graphe d'une relation pour qu'elle soit rflexive. On obtiendrait le tableau suivant (X pour le nouveau point) :

    a b c d e a X X b X X c X X X X d X X e X X

    Cette nouvelle relation n'est pas symtrique : (c, b) figure mais pas (b, c). Pour la complter, il faut s'assurer que pour tout point figurant dans le graphe, le point symtrique par rapport la diagonale figure galement. On ajoute le point (X) au tableau :

    a b c d e a X X b X X X c X X X X d X X

  • Daniel ALIBERT cours et exercices corrigs volume 1 41

    e X X

    Cette nouvelle relation n'est toujours pas transitive : (a, c) et (c, e) mais pas (a, e). Si on veut la complter pour obtenir une relation d'quivalence, il faut remplir toutes les cases : (a, c), (c, b), (c, e), sont dans le graphe donc (a, b), (a, e) aussi. Comme (b, d) est dans le graphe, (a, d) aussi. On raisonne de mme pour b, c, puis d, et e.

    exemple 17 ( traiter) La relation tudie plus haut (exemple 10) : F = {3, 2, 1, 0, 1, 2, 3, 4, 5, 6}, et x R y si x y est divisible par 3 et y < 3 est-elle une relation symtrique, rflexive, transitive ? Examiner aussi la "mme" relation, sur G = {3, 2, 1, 0, 1, 2} : x R y si x y est divisible par 3.

    # rponse

    Le graphe de R sur F est :

    xOy

    3 2 1 0 1 2 3 4 5 6

    3 X X 2 X X 1 X X 0 X X 1 X X

  • Daniel ALIBERT cours et exercices corrigs volume 1 42

    2 X X 3 X X 4 X X 5 X X 6 X X

    Elle n'est pas rflexive : 3 R 3 n'est pas vrai, par exemple. Elle n'est pas symtrique : 3 R ( 3) par exemple, mais pas ( 3) R 3. Elle est transitive ; on peut le vrifier sur le graphe (mais c'est long) ou par un raisonnement.

    Si x y est divisible par 3 et y est infrieur 3, et si y z est divisible par 3 et z infrieur 3, alors

    x z = (x y) + (y z) est divisible par 3 et z infrieur 3. En restriction G, on obtient le graphe en effaant les quatre dernires lignes et colonnes :

    xOy

    3 2 1 0 1 2

    3 X X 2 X X 1 X X 0 X X 1 X X 2 X X

    Cette relation est rflexive, et symtrique. Le raisonnement prcdent subsiste, donc la relation est galement transitive sur G.

  • Daniel ALIBERT cours et exercices corrigs volume 1 43

    C'est une relation d'quivalence sur G.

    2-3 Relations d'quivalence

    "Soit E un ensemble, muni d'une relation d'quivalence R. Pour tout lment x de E, on appelle classe d'quivalence de x et on note C(x) le sous-ensemble de E form des lments y tels que xRy soit vrai."

    exemple 18

    Construction de l'ensemble Z des entiers relatifs partir de l'ensemble N des entiers naturels (voir plus loin, exemple 20). On utilise la relation suivante sur N N :

    (m, n) R (m', n') si m + n' = n + m'. C'est une relation d'quivalence ; elle est :

    rflexive : (m, n) R (m, n) car m + n = n + m. symtrique : si (m, n) R (m', n') alors m + n' = n + m' donc

    m' + n = n' + m ; donc (m', n') R (m, n).

    transitive : si (m, n) R (m', n') et (m', n') R (m", n") m + n' = n + m'

    m' + n" = n' + m" soit, par addition,

  • Daniel ALIBERT cours et exercices corrigs volume 1 44

    m + n' + m' + n" = n + m' + n' + m" et, par simplification, m + n" = n + m" ;

    donc (m, n) R (m", n"). La classe d'quivalence de (0, 0) est forme de tous les couples (m, m). Plus gnralement, la classe de (a, b), avec a > b, est forme des couples (m, n) vrifiant :

    a + n = b + m, donc m = a b + n ;

    C((a,b))= {(a b + n, n), n N}. De mme si a < b :

    C((a, b)) = {(m, b a + m), m N}.

    exemple 19 ( traiter) Sur le produit Z Z*, form des couples d'entiers relatifs (p, q) avec q 0, on dfinit de manire analogue une relation R en posant :

    (p, q) R (p', q') si pq' = p'q. Vrifier que c'est une relation d'quivalence. Expliciter quelques classes d'quivalences : par exemple C((0, 1)), C((1, 3)), C((2, 1)).

    # rponse

    Vrification :

  • Daniel ALIBERT cours et exercices corrigs volume 1 45

    rflexivit : (a, b) R (a, b) puisque ab = ab ; symtrie : si (a, b) R (c, d) alors ad = bc, donc cb = da, et :

    (c, d) R (a, b) ; transitivit : si (a, b) R (c, d) et (c, d) R (e, f) alors :

    ad = bc cf = de, donc, par multiplication,

    adcf = bcde. Comme d n'est pas nul, on peut simplifier :

    acf = bce. (1) Si c = 0, alors a = 0 puisque ad = bc et d 0 ; de mme e = 0 donc :

    af = be (= 0). (2) Si c 0, on simplifie acf = bce par c d'o af = be. Dans tous les cas la transitivit est vrifie. On a bien dfini une relation d'quivalence. C((0, 1)) : (a, b) R (0, 1) quand a = 0, b tant quelconque, non nul.

    C((0, 1)) = {(0, b), b Z*} C((1, 3)) : (a, b) R (1, 3) quand b = 3a, a tant quelconque, non nul.

    C((1, 3)) = {(a, 3a), a Z*} C((2, 1)) : (a, b) R (2, 1) quand a = 2b, b tant quelconque, non nul.

    C((2, 1)) = {(2b, b), b Z*}

  • Daniel ALIBERT cours et exercices corrigs volume 1 46

    "L'ensemble des classes d'quivalence, sous-ensemble de l'ensemble P(E) des parties de E, est appel l'ensemble quotient de E par la relation R, souvent not E/R."

    exemple 20

    Nous reprenons les deux exemples ci-dessus, pour reconnatre les ensembles quotients. En fait, nous allons reconnatre qu'il y a une bijection naturelle de ces ensembles quotients avec des ensembles connus. (NB : On peut adopter un autre point de vue et considrer que la dfinition des ensembles "connus" que nous allons mettre en vidence est justement d'tre ces ensembles quotients : c'est ce que l'on fait lorsqu'on construit Z partir de N, et Q partir de Z.) Pour la relation (m, n) R (m', n') si m + n' = m' + n, on voit qu'il n'y a dans chaque classe qu'un point tel que m = 0.

    Ces points sont les entiers naturels n m pour les classes C((m, n)), avec m < n, ce sont les entiers ngatifs n m pour les classes C((m, n)), si m > n. On obtient de cette manire une bijection entre l'ensemble des classes d'quivalence (ensemble quotient) et l'ensemble des entiers relatifs Z :

    N N/R. Z C((m, n)) n m.

    On voit que N se ralise comme une partie de Z en identifiant n avec C((0,n)). NB : on aurait pu choisir de prendre l'intersection des classes, prolonges en droites, avec l'axe des abscisses. Cela correspondrait C((m, n)) (m n). C'est souvent ce choix qui est fait ; dans ce cas, on identifie n avec C((n, 0)).

  • Daniel ALIBERT cours et exercices corrigs volume 1 47

    exemple 21 ( traiter) De manire analogue, tablissez une bijection entre l'ensemble quotient de la deuxime relation et l'ensemble des rationnels.

    # rponse Pour Z Z*, et la relation (p, q) R (p', q') si pq' = p'q, on peut chercher dans une classe donne s'il y a un reprsentant de la forme (x, 1) :

    (p, q) R (x, 1) si qx = p. Donc si q divise p, x est le quotient. Sinon, x n'existe pas. Par extension, mme si q ne divise pas p, on fera correspondre la classe de (p, q) le rationnel p

    q. C'est bien une application puisque quel que soit

    le reprsentant d'une classe, le rationnel pq

    est le mme. Elle est bien

    bijective. Graphiquement, on peut faire correspondre une classe (points aligns avec (0, 0)) l'intersection de la droite avec la droite d'quation y = 1. Lorsque la classe correspond un entier relatif, l'intersection a une abscisse entire, sinon, ce n'est pas un entier mais un rationnel non entier.

    2-4 Lois de composition - structures

    "Soit E un ensemble et T une loi de composition interne dans E. On dit que T est associative si pour tout x, tout y, tout z de E on a l'galit (x T y) T z = x T (y T z)."

    exemple 22

    Certaines oprations lmentaires ne sont pas associatives.

  • Daniel ALIBERT cours et exercices corrigs volume 1 48

    Elles demandent des prcautions particulires dans l'utilisation des parenthses, pour viter les erreurs. Ainsi l'exponentiation (lvation une puissance), dans N par exemple :

    si n T m = nm, 2 T (3 T 4) = 281 (2 T 3) T 4 = 212.

    exemple 23 ( traiter) Examiner de ce point de vue les oprations suivantes :

    soustraction dans Z, division dans R*.

    # rponse

    Ces deux oprations ne sont pas associatives. On trouve facilement des contre-exemples :

    (1 2) 3 = 4, et 1 (2 3) = 2,

    123

    =

    32

    , et

    123

    =

    16

    .

  • Daniel ALIBERT cours et exercices corrigs volume 1 49

    "Soit (E,T) un ensemble muni d'une loi de composition interne. On dit que (E,T) est un groupe si 1- T est associative, 2- T admet un lment neutre, 3- Tout lment de E a un symtrique pour T."

    exemple 24

    Vous avez dj rencontr de nombreux groupes : (Z, +), (Q, +), (R, +), Penser qu'il y a d'autres exemples que les ensembles de nombres : soit E l'ensemble des rotations de centre O (centre du pentagone) qui "conservent" le pentagone rgulier, c'est--dire le transforment (globalement) en lui-mme. Si T dsigne la composition des applications, il est clair que (E, T) est un groupe : la compose de deux rotations conservant le pentagone le conserve, donc la loi est bien interne, la composition est associative, l'application identique conserve le pentagone, si une rotation conserve le pentagone, la rotation d'angle oppos le conserve galement. Remarquer qu'il n'a pas t ncessaire de connatre les rotations qui appartiennent E pour tablir ce rsultat.

    exemple 25 ( traiter) Soit A = {1, 2, 3}. On appelle S3 l'ensemble des bijections de A dans A. On reprsente une telle bijection en crivant (a, b, c) si a est l'image de 1, b l'image de 2 et c l'image de 3 ({a, b, c} = {1, 2, 3} bien entendu). Ecrire l'ensemble des lments de S3, et vrifier que cet ensemble est bien un groupe pour la composition des applications.

  • Daniel ALIBERT cours et exercices corrigs volume 1 50

    # rponse

    On tablit la liste des lments sans difficult : la mthode employe est d'crire d'abord l'application identique (3 lments fixes), puis les bijections avec exactement 1 lment fixe (il n'y en a pas avec exactement 2 lments fixes, bien entendu), puis celles sans lment fixe. Pour plus de facilit dans l'criture de la table de composition, on leur donne des noms.

    I = (1, 2, 3) t1 = (1, 3, 2) t2 = (3, 2, 1) t3 = (2, 1, 3) s = (2, 3, 1) u = (3, 1, 2)

    Il n'y en a pas d'autre puisque 1 donne 1, 2, ou 3. S'il donne 1, alors 2 donne 2 (I) ou 3 (t1) ; s'il donne 2, alors 2 donne 1 (t3) ou 3 (s), s'il donne 3, alors 2 donne 2 (t2) ou 1 (u). On peut faire le mme raisonnement que ci-dessus pour le pentagone. On peut aussi crire une table de composition, analogue une table de multiplication : dans la ligne correspondant la bijection f, et dans la colonne correspondant la bijection g, on figure la compose fog (attention : l'ordre compte).

    I t1 t2 t3 s u I I t1 t2 t3 s u t1 t1 I s u t2 t3 t2 t2 u I s t3 t1 t3 t3 s u I t1 t2

  • Daniel ALIBERT cours et exercices corrigs volume 1 51

    s s t3 t1 t2 u I u u t2 t3 t1 I s

    Pour remplir ce tableau, on applique successivement deux bijections : par exemple t1ou (d'abord u, puis t1) est gal t3.

    (1, 2, 3) (3, 1, 2) (2, 1, 3) Sur cette table on vrifie que la loi est interne, qu'il y a un lment neutre (I), et que chaque lment a un symtrique (lui-mme pour t1, t2, t3, u pour s et inversement). Pour l'associativit, il est bien prfrable de revenir un raisonnement gnral sur l'associativit de la composition.

    exemple 26 ( traiter) La mme table peut tre obtenue partir d'un groupe de transformations gomtriques : chercher quelles sont les transformations (isomtries) qui conservent un triangle quilatral, et voir qu'elles forment un groupe ayant la mme table que S3 (on dit que ces groupes sont isomorphes). Identifier quelles transformations correspondent t1, t2, t3, s, u.

    # rponse Les transformations du plan qui conservent ce triangle sont l'application identique (Id), les symtries par rapport aux trois hauteurs (s1, s2, s3), la rotation R d'angle 2pi

    3, et la rotation R2 d'angle 4pi

    3.

    On vrifie que, pour la composition des isomtries du plan, cet ensemble de transformations a bien la mme table que S3 ; on peut identifier les

  • Daniel ALIBERT cours et exercices corrigs volume 1 52

    symtries s1, s2, s3 aux bijections t1, t2, t3 (dans n'importe quel ordre), puis R s (ou u) et R2 u (ou s) selon le premier choix : par exemple si s1 correspond t1, s2 t2, s3 t3, et si s2os1 = R, on identifiera R u, R2 s. Une mthode facile consiste nommer 1, 2, 3 les sommets du triangle et observer comment chaque transformation gomtrique permute l'ensemble {1, 2, 3}.

    exemple 27 ( traiter) Un mme ensemble peut tre un groupe pour des oprations diffrentes. Par exemple, vrifier que Z est un groupe pour l'opration & :

    p & q = p + q si p est pair, et p & q = p q sinon. Est-ce un groupe commutatif ?

    # rponse

    associativit : p & (q & r) = p + (q & r) si p est pair, p & (q & r) = p + (q + r) si p et q sont pairs, dans ce cas, (p & q) & r = (p + q) & r = (p + q) + r puisque p + q est pair, p & (q & r) = p + (q r) si p est pair et q impair, dans ce cas, (p & q) & r = (p + q) r puisque p + q est impair, p & (q & r) = p (q & r) si p est impair, p & (q & r) = p (q + r) si p est impair et q pair, dans ce cas, (p & q) & r = (p q) r puisque p q est impair. p & (q & r) = p (q r) si p et q sont impairs, dans ce cas, (p & q) & r = (p q) + r puisque p q est pair.

  • Daniel ALIBERT cours et exercices corrigs volume 1 53

    Dans tous les cas, l'associativit est vrifie. lement neutre : p & 0 = p et 0 & p = p (0 est pair). symtrique : si p est pair, p & ( p) = 0 donc ( p) est le symtrique ; si p est impair, p & p = 0, donc p est le symtrique. Pour la commutativit, on trouve facilement un contre-exemple :

    2 & 3 = 2 + 3, 3 & 2 = 3 2.

    "Soit (G,T) un groupe et H une partie de G. On dit que (H,T) est un sous-groupe de (G,T) si (H,T) est lui-mme un groupe."

    exemple 28

    Les exemples vus ci-dessus sont des sous-groupes de quelques groupes gnraux qu'il faut bien reconnatre car, dans de nombreux cas, les groupes utiliss sont des sous-groupes. exemple 24 : les groupes de nombres sont en gnral des sous-groupes de (C, +), ou (C*, ). exemple 24, 25, 26 : l'ensemble des bijections d'un ensemble E dans lui-mme est un groupe pour la composition. Les bijections qui "conservent" une partie A de l'ensemble E forment un sous-groupe (qu'on appelle le stabilisateur de A). Par contre, il existe des proprits qui se conservent par composition (continuit, drivabilit) mais pas ncessairement par rciproque (drivabilit). Un sous-ensemble form de bijections ayant une telle proprit ne formera pas ncessairement un sous-groupe : on y reviendra.

  • Daniel ALIBERT cours et exercices corrigs volume 1 54

    exemple 29 ( traiter) Reprendre l'exemple du groupe S3 (exemple 25). Chercher tous ses sous-groupes. Indication : un sous-groupe doit contenir au moins l'lment neutre, et s'il contient un autre lment, il contient son symtrique. Distinguer les cas en fonction du nombre d'lments.

    # rponse

    Reproduisons la table du groupe.

    I t1 t2 t3 s u I I t1 t2 t3 s u t1 t1 I s u t2 t3 t2 t2 u I s t3 t1 t3 t3 s u I t1 t2 s s t3 t1 t2 u I u u t2 t3 t1 I s

    Sous-groupe un lment : ce ne peut-tre que {I}. Sous-groupe deux lments : I, et f gal son symtrique {I, t1}, {I, t2}, {I, t3}. Sous-groupe trois lments : I, f et son symtrique, les composs de f doivent tre galement dans le sous-groupe ; {I, s, u} est un exemple. Si un sous-groupe contient deux lments distincts de {t1, t2, t3}, il contient ncessairement u et s. Il n'y a donc pas d'autre possibilit.

  • Daniel ALIBERT cours et exercices corrigs volume 1 55

    Sous-groupe quatre lments : I, et trois parmi les cinq autres. Compte tenu de la table, s'il y a t1 et s ou u, il y a tous les lments. Ce cas est impossible, de mme pour cinq lments. Sous-groupe six lments : S3 lui-mme. Ce groupe a donc six sous-groupes :

    {I}, {I, t1}, {I, t2}, {I, t3}, {I, s, u}, {I, t1, t2, t3, s, u}.

    NB : la thorie montre que le nombre d'lments d'un sous-groupe est un diviseur du nombre d'lments du groupe. Il ne pouvait donc pas y avoir de sous-groupes quatre ou cinq lments.

    "Soit (G, T) un groupe, et H une partie de G. Pour que (H, T) soit un sous-groupe de (G, T), il faut et il suffit que les proprits suivantes soient vrifies :1) H est non vide, 2) Pour tout x et tout y de H l'lment x T sym(y) appartient H."

    exemple 30

    Soit H le sous-ensemble de (Z, +) form de tous les multiples de 11 : 0 est dans H donc H n'est pas vide ;

    si x et y sont des multiples de 11, x y aussi. Conclusion : H est un sous-groupe de Z.

    exemple 31 ( traiter) Soit a un rel et Fa le sous-ensemble de (R3, +) dfini par :

    Fa = {(x, y, z) | 2x y + z = a }. Pour quelles valeurs de a ce sous-ensemble est-il un sous-groupe ?

  • Daniel ALIBERT cours et exercices corrigs volume 1 56

    # rponse

    Pour tout a, Fa est non vide. Si (x, y, z) est un point de ce plan, et (x', y', z') un autre point :

    2x y + z = a 2x' y' + z' = a

    d'o par soustraction : 2(x x') (y y') + (z z') = 0.

    Il en rsulte que la seule valeur qui

    convienne est a = 0. On pouvait le voir galement en vrifiant que l'lment neutre (0, 0, 0) est un lment de Fa.

    "Soient (G, T), et (H,) des groupes. On appelle homomorphisme de groupes de G vers H une application f : G --. H telle que pour tout x et tout y de G on ait f(x T y) = f(x) f(y)."

    exemple 32

    Les fonctions usuelles exponentielle et logarithme sont des homomorphismes de groupes, rciproques l'un de l'autre.

    exp : (R, +) --. (R+*, x) exp(t1+t2) = exp(t1) x exp(t2)

    Log : (R+*, x) --. (R, +) Log(a x b) = Log(a) + Log(b).

    exemple 33 ( traiter) Soit f : (Z, +) --. (Z, +) un homomorphisme de groupe.

  • Daniel ALIBERT cours et exercices corrigs volume 1 57

    On pose m = f(1). Calculer f(2), f(1) ; dmontrer que f est compltement dfini par la donne de f(1). Ecrire la forme gnrale des endomorphismes de (Z, +).

    # rponse

    f(2) = f(1+1) = f(1) + f(1), f(2) = 2m.

    On sait que l'image par un homomorphisme de groupes du symtrique d'un lment est le symtrique de l'image de cet lment.

    f( 1) = f(1) f( 1) = m.

    On vrifie par rcurrence que pour tout n entier relatif, f(n) = nm : n 0 d'abord ;

    f(0) = 0 = 0 m. si on suppose vrai que f(n) = nm,

    f(n + 1) = f(n) + f(1) f(n + 1) = nm + m

    f(n + 1) = (n + 1)m. Pour n < 0, on utilise la remarque faite ci-dessus sur l'image du symtrique. La forme gnrale des endomorphismes de (Z, +) est donc f(x) = ax, a tant un entier relatif quelconque.

  • Daniel ALIBERT cours et exercices corrigs volume 1 58

    2-5 Logique lmentaire

    "nonc universel, nonc existentiel."

    exemple 34

    Considrons l'nonc : "Il n'y a pas de plus grand lment dans N"

    C'est une proprit des entiers naturels, valable pour tous les entiers, donc un nonc universel :

    "Pour tout lment de N, il y a un lment plus grand que cet lment" L'nonc s'analyse donc comme un nonc existentiel enchss dans un nonc universel. En criture symbolique :

    n, n N, p, p N, p > n.

    exemple 35 ( traiter) Ecrire symboliquement, en reconnaissant nonc existentiel et nonc universel, la proprit :

    "L'ensemble des nombres premiers a un plus petit lment"

    # rponse

    C'est d'abord un nonc existentiel puisqu'il affirme l'existence d'un objet. Cet objet est caractris par une proprit en rfrence un ensemble, donc valable pour tous les lments de l'ensemble, c'est--dire une proprit universelle. On crira (P dsigne l'ensemble des nombres premiers) :

  • Daniel ALIBERT cours et exercices corrigs volume 1 59

    m, m P, x, x P, m x.

    "Ngation d'un nonc universel, ou existentiel."

    exemple 36

    "Tout rationnel est un nombre dcimal" Symboliquement, on crit :

    x, x Q x D. La ngation s'crit :

    x, x Q et x D, soit x, x Q et y, y D, y x.

    De manire plus dtaille, le premier nonc s'crit :

    (p, q), (p, q) Z Z*, (m, n), (m, n) Z N, pq

    =

    m

    10n.

    Sa ngation :

    (p, q), (p, q) Z Z*, (m, n), (m, n) Z N, pq

    m

    10n.

    C'est, bien entendu, la ngation qui est vraie : par exemple 1/3 n'est pas un dcimal, puisque 3 n'est pas un diviseur de 10.

    exemple 37 ( traiter) Ecrire la ngation de l'nonc :

    "Les rels positifs ou nuls ont deux racines carres relles distinctes"

  • Daniel ALIBERT cours et exercices corrigs volume 1 60

    # rponse

    L'nonc s'crit : x, x R+, (a, b), (a, b) R R, a b, x = a2 et x = b2 .

    Sa ngation : x, x R+, (a, b), (a, b) R R, a b, x a2 ou x b2 .

    "Certains rels positifs ou nuls n'ont pas deux racines carres relles distinctes". (cet nonc est vrai, penser x = 0).

  • Daniel ALIBERT cours et exercices corrigs volume 1 61

    indications pour rsoudre - mthode - lexique

    3 Pour Comprendre et Utiliser

    3-1 noncs des exercices Dmontrer que deux ensembles sont gaux, matriser les oprations lmentaires ensemblistes (union, intersection, complmentaire), utiliser les applications (dfinition, image d'une partie, image rciproque), caractriser et utiliser l'injectivit, la surjectivit, la bijectivit.

    exercice 1

    Soit E un ensemble. A toute partie A de E, on associe une application, note 1A , de E dans {0, 1} :

    si x A, 1A(x) = 1, sinon, 1A(x) = 0. Cette application est la "fonction caractristique" de A. Elle permet, inversement, de retrouver A :

    A = 1A*({1}). 1) Soient A et B des parties de E. Etablir les noncs suivants : ()

    si A B, alors 1A 1B ; si C = A B, alors 1C = 1A 1B ; si D = CE(A), alors 1D = 1 1A.

  • Daniel ALIBERT cours et exercices corrigs volume 1 62

    indications pour rsoudre - mthode - lexique

    2) La rciproque () du premier nonc est-elle vraie ? ()

    3) Ecrire une relation entre la fonction caractristique de l'union A B et les fonctions caractristiques de A et de B. ( )

    4) A l'aide des fonctions caractristiques, dmontrer les galits : CE(A B) = CE(A) CE(B).

    ( C) = (A B) (A C). Examiner par cette mthode d'autres relations semblables.

    5) La fonction (1A 1B) est-elle la fonction caractristique d'une partie de E ? Si oui, laquelle ? Mmes questions pour |1A 1B |.

    exercice 2

    Soit E un ensemble. A tout couple (A, B) de parties de E vrifiant A B, on associe une application A,B de E dans {0, 1, 2} par :

    A,B (x) = 0 si x B A,B (x) = 1 si x B et x A

    A,B (x) = 2 si x A.

    1) Soit C une partie de E. On suppose que A C et B C. Etablir la relation () :

    A,B .A,C = (A,BC)2

    2) Avec les mmes hypothses, calculer A,BC. ()

  • Daniel ALIBERT cours et exercices corrigs volume 1 63

    indications pour rsoudre - mthode - lexique

    3) Exprimer C(B),C(A) en fonction de A,B (C(X) dsigne ici le complmentaire de X dans E).

    4) Dduire de ce qui prcde des expressions de AA',B et AA',B, si A et A' sont des parties de B ().

    exercice 3

    Soient E et F des ensembles et f une application de E dans F. (Cf. exercice 1 pour les notations.) 1) Soient B et B' des parties de F. Exprimer 1f*(B) l'aide de 1B et de f (). Quelle relation pouvez-vous en dduire entre f*(B B') et f*(B) f*(B') ?

    2) Soit A une partie de E, dmontrer () : 1f(A) o f 1A

    3) Soit A une partie de E. On tudie quelle condition sur A il existe une partie B de F telle que :

    1B o f = 1A. Exemple : si E = Z, A = 2N, F = N, et f est dfinie par f(n) = n2. La partie B existe-t-elle () ?

  • Daniel ALIBERT cours et exercices corrigs volume 1 64

    indications pour rsoudre - mthode - lexique

    Dmontrer que si B existe, alors B f*(A). Cette partie B est-elle

    unique ? Dmontrer que si B existe, alors A f*(f

    *(A)), et rciproquement.

    Pour conclure, dmontrer que B existe si et seulement si A = f*(f*(A)).

    exercice 4

    Soit E un ensemble, P(E) l'ensemble des parties de E. 1) Si A est une partie de E, non vide, et distincte de E. Les applications suivantes de P(E) dans lui-mme sont-elles injectives, surjectives () ? ()

    u : X A X, i : X A X.

    2) Soit f une application de E dans un ensemble F, on note : P(f) : P(E) . P(F),

    X f*(X)

    et Q(f) : P(F) . P(E)

    Y f*(Y) les applications "image directe" et "image rciproque". Examiner quelles conditions ces applications sont injectives, surjectives ().

  • Daniel ALIBERT cours et exercices corrigs volume 1 65

    indications pour rsoudre - mthode - lexique

    exercice 5 Dans cet nonc, on tudie une application f de l'ensemble N des entiers naturels, dans lui-mme : l'application f associe un entier p l'entier p2 + p. 1) Si B1 est le sous-ensemble de N form des entiers impairs, f*(B1) est l'ensemble vide. Pourquoi () ? 2) Si B2 est le sous-ensemble form des entiers pairs, f*(B2) est l'ensemble N. Pourquoi () ? 3) crire en extension ()() : a- f

    *({1, 2, 3, 5, 7, 11}) ()

    b- f*({2, 4, 6, 8, 10, 12, 14}) () c- f*(f

    *({1, 2, 3, 5, 7, 11})

    d- f*(f*({2, 4, 6, 8, 10, 12, 14}))

    exercice 6

    Dans cet exercice, on tudie une application f de l'ensemble R des nombres rels dans le segment [1 , 1] ; l'application f associe un rel x le nombre sin(x).

    1) Vrifier les noncs suivants ()() : Si A1 = [0 , pi], alors f*(A1) = [0 , 1]. Si A2 = [0 ,

    3pi4

    [, alors f*(A2) = [0 , 1].

  • Daniel ALIBERT cours et exercices corrigs volume 1 66

    indications pour rsoudre - mthode - lexique

    2) Y a-t-il des sous-ensembles de R ayant une infinit d'lments dont l'image directe par f est un sous-ensemble ayant un seul lment ? () 3) Y-a-t-il des sous-ensembles de [1 , 1] ayant une infinit d'lments dont l'image rciproque par f est un sous-ensemble ayant un seul lment ?

    exercice 7

    1) A l'aide des exemples et exercices que vous avez tudis (), discuter les conjectures () suivantes portant sur une application f : E . F. a) Pour tout sous-ensemble A de E, f*(f

    *(A)) = A.

    b) Pour tout sous-ensemble B de F, f*(f*(B)) = B.

    2) Ces galits correspondent deux inclusions (). Dans chaque cas, prouver l'une des deux inclusions. Donner un contre-exemple montrant que l'autre inclusion n'est pas toujours vrifie.

    3) Parmi les applications figurant dans les exemples proposs, citer une application injective. Vrifier que pour ce cas l'nonc a) est vrai. Dmontrer, de faon gnrale, que la conjecture a) est vraie pour toute application injective ().

    4) Parmi les applications figurant dans les exemples proposs, citer une application surjective.

  • Daniel ALIBERT cours et exercices corrigs volume 1 67

    indications pour rsoudre - mthode - lexique

    Vrifier que pour cet exemple l'nonc b) est vrai. Dmontrer, de faon gnrale, que la conjecture b) est vraie pour toute application surjective ().

  • Daniel ALIBERT cours et exercices corrigs volume 1 68

    indications pour rsoudre - mthode - lexique

    Reconnatre un groupe. Caractriser un sous-groupe, utiliser un homomorphisme de groupes. Calculs dans un anneau, un corps.

    exercice 8

    Quelques proprits lmentaires des groupes () : 1) Dans un groupe, il existe un unique lment neutre (), et pour un lment donn, un unique symtrique (). Rappeler la dmonstration de ces deux rsultats lmentaires ().

    2) Dans un groupe, on peut simplifier membre membre par un facteur commun. Pourquoi () ?

    3) Dans un groupe (G, T), expliquer trs prcisment comment on peut rsoudre une quation du premier degr (a et b sont donns, x est l'inconnue) :

    a T x = b.

    4) Rciproquement, soit G un ensemble dans lequel on a dfini une loi interne associative () note T. On suppose que pour tout couple (a, b) de G, les quations en x :

    a T x = b, et x T a = b ont une solution unique. Dmontrer que (G, T) est un groupe ().

  • Daniel ALIBERT cours et exercices corrigs volume 1 69

    indications pour rsoudre - mthode - lexique

    exercice 9

    Soit (G, T) un groupe, dont l'lment neutre est not e. On dfinit la puissance d'un lment du groupe par rcurrence :

    si g G, alors g0 = e, g(n+1) = gn T g pour n 0, et

    gn = sym(g-n) pour n < 0. Attention, malgr la notation, il n'est pas sous-entendu que la loi T soit commutative.

    1) Soit n un naturel. L'application g gn est-elle un homomorphisme () de groupes () ? Donner un exemple, et le cas chant un contre-exemple ().

    2) On dit qu'un lment g de G est d'ordre fini s'il existe un naturel n strictement positif tel que gn = e. Si un lment n'est pas d'ordre fini, on dit qu'il est d'ordre infini. Si g est d'ordre fini, montrer qu'il existe une infinit d'exposants m tels que gm = e. On appelle alors "ordre de g" le plus petit naturel strictement positif p tel que gp = e.

    3) Exemple 1 : G = {z C | |z| = 1}, la loi tant la multiplication. Chercher des lments de G d'ordre 2, 3, 5. Dans chaque cas, quels sont les autres exposants m correspondant gm = 1 () ?

  • Daniel ALIBERT cours et exercices corrigs volume 1 70

    indications pour rsoudre - mthode - lexique

    4) On veut dmontrer que si p est l'ordre de g, alors gm = e si et seulement si m est un multiple de p. Pour un tel exposant, soit m, m p, effectuer la division de m par p :

    m = pq + r. Calculer gr. En dduire que r = 0 ().

    5) Exemple 2 : Dans le plan on choisit une direction de droites. L'ensemble D est l'ensemble form de l'application identique, des symtries par rapport une droite de la direction choisie, et des translations perpendiculaires cette direction. L'opration est la composition des applications. Vrifier qu'on a bien affaire un groupe. Les lments de ce groupe sont-ils d'ordre fini ? Si deux lments sont d'ordre fini, leur compos est-il toujours d'ordre fini () ?

    6) Exemple 3 : Soit l'ensemble des complexes z pour lesquels il existe un entier n non nul vrifiant zn = 1. (Ensemble des racines de l'unit.) Montrer que (M, ) est un groupe.

    7) On suppose que G est un ensemble fini ; soit n le nombre de ses lments. On dit que n est l'ordre de G. Dmontrer que, dans G, tout lment est d'ordre infrieur ou gal n ().

    8) Rciproquement, si dans un groupe tout lment est d'ordre fini, le groupe est-il d'ordre fini ?

  • Daniel ALIBERT cours et exercices corrigs volume 1 71

    indications pour rsoudre - mthode - lexique

    exercice 10

    Soit un groupe (G, T). Voici quelques exemples "standard" de sous-groupes de (G, T). 1) Soit H un sous-ensemble non vide, fini, stable (c'est--dire que si a H et b H, alors a T b H.) Dmontrer que H est un sous-groupe de G. ()()

    2) Soit a G et C(a) = {an | n Z}. Dmontrer que C(a) est un sous-groupe de G.

    3) Soit Z(G) = {g G | h G, g T h = h T g}. Dmontrer que Z(G) est un sous-groupe de G.

    4) Soit g G et S(g) = {h G | g T h = h T g}. Dmontrer que S(g) est un sous-groupe de G.

    exercice 11

    Quelques proprits lmentaires des homomorphismes ().

    1) Soit f : (G, T) . (H, ) un homomorphisme de groupes. Vrifier que l'image de l'lment neutre () de G est l'lment neutre de H (). Soit a un lment de G, vrifier que l'image du symtrique de a par f est le symtrique de f(a).

    2) Soit h : (G, T) . (H, ) un homomorphisme de groupes, bijectif.

  • Daniel ALIBERT cours et exercices corrigs volume 1 72

    indications pour rsoudre - mthode - lexique

    Dmontrer que h est un isomorphisme, c'est--dire que l'application rciproque g de h est galement un homomorphisme ().

    3) Soit (G, T) un groupe, et (H, ) un ensemble non vide muni d'une loi de composition interne (). On suppose qu'il existe une application u surjective () u : G. H, telle que u(a T b) = u(a) u(b), quels que soient a et b dans G. Dmontrer que (H, ) est un groupe ().

    exercice 12

    Sur la notion de noyau () d'un homomorphisme.

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

    H = {a A | h(a) = e}. 1) Dmontrer que H est un sous-groupe de A (). On l'appelle le "noyau" de h.

    2) Soit u H, vrifier que si g A, alors g.u.g -1 H.

    3) Dmontrer que h est injectif si et seulement si son noyau ne contient que l'lment neutre ().

    4) Soit b un lment de B. On suppose que l'quation :

  • Daniel ALIBERT cours et exercices corrigs volume 1 73

    indications pour rsoudre - mthode - lexique

    h(x) = b a au moins une solution, soit a. Dcrire l'ensemble des solutions l'aide de a et de H.

    5) Exemple : A est l'ensemble des fonctions d'une variable relle deux fois drivables, drives continues, muni de l'addition usuelle ; B est l'ensemble des fonctions continues, galement muni de l'addition ; enfin, h est l'application qui une fonction u associe la fonction u" u' u (ici, u' dsigne la drive premire et u" la drive seconde). Vrifier que h est un homomorphisme de groupes, et chercher son noyau, puis chercher les solutions de h(u) = 2.exp (fonction exponentielle). Retrouver ainsi une rgle connue ().

  • Daniel ALIBERT cours et exercices corrigs volume 1 74

    indications pour rsoudre - mthode - lexique

    Reconnatre une relation d'quivalence. Utiliser l'ensemble quotient.

    exercice 13

    Dans un groupe (G, ), soit H un sous-ensemble. On dfinit une relation sur G par :

    x R y si x y -1 H.

    1) Dmontrer que R est une relation d'quivalence () si et seulement si H est un sous-groupe de G.() Cette relation est-elle compatible () avec () ?

    On suppose maintenant que R est une relation d'quivalence. On note G/H l'ensemble quotient de G par la relation R.

    2) Soit g G. On pose : H g = {h g | h H}.

    Dmontrer que H g est la classe d'quivalence () de g pour la relation R ().

    3) Soient g1 et g2 des lments de G. Vrifier que l'application u de G dans G :

    x x g1 -1 g2 est une bijection ()(), et que l'image de la classe de g1 par u est la classe de g2.

  • Daniel ALIBERT cours et exercices corrigs volume 1 75

    indications pour rsoudre - mthode - lexique

    4) On suppose de plus que G est un groupe fini. Dduire de ce qui prcde que le nombre d'lments d'un sous-groupe quelconque de G est un diviseur du nombre d'lments de G ().

    exercice 14

    Soit (G, ) un groupe, et H un sous-groupe de G. On suppose que H vrifie la proprit :

    g G, h H, g -1 h g H.

    1) Dmontrer que la relation d'quivalence dfinie dans l'exercice 13 est compatible avec la loi ().

    2) Soit c : G . G/H l'application qui associe g sa classe d'quivalence. Dmontrer que c est un homomorphisme de groupes (), et que H est le noyau de c (cf. 12-1).

    exercice 15

    On considre la relation suivante, dfinie sur R : a R b si il existe un entier relatif k vrifiant a b = 2kpi.

    1) Dmontrer que R est une relation d'quivalence.

    2) Montrer qu'il y a un seul reprsentant de chaque classe dans [0 , 2pi[, puis tablir une bijection () entre l'ensemble quotient et l'ensemble :

  • Daniel ALIBERT cours et exercices corrigs volume 1 76

    indications pour rsoudre - mthode - lexique

    {z C | |z| = 1}, ensemble qu'on notera S1. On notera p l'application qui en rsulte entre R et S1 par composition avec l'application canonique de passage au quotient (). 3) Vrifier que les applications sin et cos se factorisent par p, c'est--dire qu'il existe des applications S et C de S1 dans R telles que :

    sin = Sop, cos = Cop.

    Dmontrer que p est surjective. Les applications S et C sont-elles injectives ?

    exercice 16

    Soit E un ensemble. On appelle "prordre" sur E une relation sur E transitive et rflexive. On note un prordre sur E. 1) Soit R la relation sur E dfinie par :

    x R y si (x y et y x). Dmontrer que R est une relation d'quivalence. 2) Soient c(x) et c(y) des classes d'quivalence. Vrifier qu'on dfinit bien une relation sur E/R () en posant :

    c(x)

  • Daniel ALIBERT cours et exercices corrigs volume 1 77

    indications pour rsoudre - mthode - lexique

    Etablir une bijection () entre l'ensemble quotient () et un ensemble connu (). 4) Exemple 2 : Dans C* = C {0}, la relation z t si ||z|| ||t|| est une relation de prordre. Soit z un complexe. Quels sont les complexes quivalents z pour la relation associe au prordre ? Etablir une bijection entre l'ensemble quotient et un ensemble connu ().

  • Daniel ALIBERT cours et exercices corrigs volume 1 78

    indications pour rsoudre - mthode - lexique

  • Daniel ALIBERT cours et exercices corrigs volume 1 79

    indications pour rsoudre - mthode - lexique

    Dans un nonc mathmatique, identifier les connecteurs, les quantificateurs. Transformer un nonc : contrapose, rciproque. Ngation d'un nonc. Raisonnement par l'absurde.

    exercice 17

    Ecrire la ngation () des noncs suivants : P, Q, R dsignent des propositions mathmatiques quelconques. Ecrire les rponses l'aide de P, non(P), Q, non(Q), , et, ou . On pourra d'abord transformer les noncs proposs. ()

    1) Si non(P) alors non(Q). 2) Si P alors non(Q). 3) Si (P et Q) alors (R et S). 4) Si l'intersection de deux ensembles est vide, l'un des deux au moins est vide (). 5) (m, n) Z Z, (u, v) Z Z, mu + nv = 1. ()

    exercice 18

    Soient P et Q des propositions dpendant d'un objet x. Dans chaque cas, vrifier si les noncs proposs sont quivalents () ().

    1) () x, [P(x) ou Q(x)]. () [ x, P(x)] ou [ x, Q(x)].

  • Daniel ALIBERT cours et exercices corrigs volume 1 80

    indications pour rsoudre - mthode - lexique

    2) () x tel que [P(x) ou Q(x)]. () [ x tel que P(x)] ou [ x tel que Q(x)].

    3) () x, non[P(x) ou Q(x)]. () [ x, non P(x)] ou [ x, non Q(x)].

    4) () x tel que non[P(x) ou Q(x)]. () [ x tel que non P(x)] ou [ x tel que non Q(x)].

    exercice 19

    Une relation transitive et symtrique est rflexive. Voici un raisonnement prouvant cet nonc (faux !). Ecrire ce raisonnement en explicitant compltement les quantificateurs et trouver l'erreur de raisonnement ().

    Soit E un ensemble, et R une relation transitive et symtrique. Pour un x de E, on a :

    x R y y R x (par symtrie) ; on a donc :

    x R y et y R x d'o x R x (par transitivit).

    exercice 20

    Utiliser la contrapose : prouver les noncs suivants, en les remplaant par leur contrapose ().

  • Daniel ALIBERT cours et exercices corrigs volume 1 81

    indications pour rsoudre - mthode - lexique

    1) Proprit d'un rationnel a : [ h Q* , | a | h] [a = 0].

    2) Proprit d'un couple de rationnels (a, b) : [ n N*, a 1

    n b ] [a b].

    3) Proprit d'un rationnel a. Si a > 0, alors, pour tout rationnel b > 0,

    il existe un entier n tel que n x a > b.

    exercice 21

    Soit : f : { 1, 2, 3 } { 1, 2, 4, 5 }. N

    dfinie par : f(x, y) = xy.

    Examiner les noncs suivants. Pour chaque nonc de la forme "si A, alors B", on classera () l'ensemble des couples (x, y) de {1, 2, 3} {1, 2, 4, 5} en "exemple", "contre-exemple", "non-exemple". Ensuite, on dcidera s'il est vrai ou faux () .

    1) Si x + y = 4 , alors f(x,y) = 4 . 2) Si f(x, y) = 1 , alors x = y . 3) Si f(x,y) = 8 , alors x = 2 . 4) Ngation de (3) (prciser cet nonc). 5) Contrapose de (2) (prciser cet nonc).

  • Daniel ALIBERT cours et exercices corrigs volume 1 82

    indications pour rsoudre - mthode - lexique

    6) Si f(x, y) = 4 et x > 1 , alors y = 2 . 7) Si f(x, y) = 1 et x 2 , alors y = 1 . 8) Ngation de (7) (prciser cet nonc). 9) Contrapose de (7) (prciser cet nonc). 10) Si f(x, y) = 9, alors x + y = 2. 11) Si f(x, y) = 9, alors x + y = 20.

    3-2 Corrigs des exercices

    exercice 1-C

    1) Les relations sont toutes simples dmontrer. Il s'agit de comparer des applications (). Dmontrons compltement la premire : Soit x dans E. Si x A, 1A(x) = 1. Comme A B, x B donc 1B(x) = 1. Si x A, et x B, 1A(x) = 0, et 1B(x) = 1. Enfin, si x B, alors x A donc 1A(x) = 1B(x) = 0. Dans tous les cas, 1A(x) 1B(x).

    2) La rciproque s'crit : si 1A 1B , alors A B.

    L'hypothse signifie que pour tout x, 1A(x) 1B(x). Soit en particulier x A. Il en rsulte que 1A(x) = 1, et comme une fonction caractristique ne prend que les valeurs 1 ou 0, on a galement 1B(x) = 1, donc x B. La rciproque est bien vraie.

  • Daniel ALIBERT cours et exercices corrigs volume 1 83

    indications pour rsoudre - mthode - lexique

    (QC-1) Examiner galement les rciproques des autres noncs.

    3) Si A et B sont disjoints (), il est clair qu'on obtient une fonction gale 0 en dehors de A et B, et 1 dans A ou B, avec 1A + 1B. Par contre si A et B ne sont pas disjoints, on voit que 1A + 1B prend la valeur 2 dans A B. Il faut donc retrancher 1A B . On trouve donc :

    1A B = 1A + 1B 1A . 1B .

  • Daniel ALIBERT cours et exercices corrigs volume 1 84

    indications pour rsoudre - mthode - lexique

    4) Pour la relation : CE(A B) = CE(A) CE(B),

    les fonctions caractristiques des deux membres s'crivent : 1C(A B)= 1 1A B = 1 1A.1B , 1C(A) C(B) = 1C(A) + 1C(B) 1C(A).1C(B), = 1 1A + 1 1B (1 1A)(1 1B), = 2 1A 1B (1 1A 1B + 1A.1B),

  • Daniel ALIBERT cours et exercices corrigs volume 1 85

    indications pour rsoudre - mthode - lexique

    = 1 1A.1B. Elles sont bien gales. On procde de mme pour l'autre relation. On pourra faire de mme pour les relations suivantes :

    CE(A B) = CE(A) CE(B), A (B C) = (A ) (A C).

    5) La fonction f = 1A 1B prend les valeurs suivantes : si x A et x B, f(x) = 1 ;

    si x B et x A, f(x) = 1 ; si x A B, f(x) = 0 ; si x A B, f(x) = 0.

    Bien entendu, certains de ces cas peuvent ne pas exister, selon les ensembles A et B. On voit que pour que f soit une fonction caractristique, il faut que le deuxime cas n'existe pas, c'est--dire que B soit une partie de A. Si B A, l'application 1A1B est la fonction caractristique du complmentaire de B dans A : considrer l'ensemble des points x pour lesquels la valeur est 1.

    Pour |1A 1B|, il n'y a pas de difficult : les valeurs prises sont 1 et 0. Il s'agit bien de la fonction caractristique d'une partie de E :

    C = { x E | |1A 1B|(x) = 1 }. On voit qu'il s'agit de l'ensemble des lments de E qui appartiennent A mais pas B, ou B mais pas A. On appelle cette partie de E la "diffrence symtrique de A et B", elle s'crit A B ; on voit que :

  • Daniel ALIBERT cours et exercices corrigs volume 1 86

    indications pour rsoudre - mthode - lexique

    A B = CA B(A B). (QC-2) Plus gnralement, si F et G sont des parties de E, vrifiant F G, crire la fonction caractristique de CG(F). En remarquant qu'une fonction caractristique est gale son carr, retrouver le rsultat prcdent. (QC-3) Dans la situation o E est un ensemble fini, on peut compter les parties de E en comptant les applications de E dans {0, 1}. Retrouver ainsi le rsultat connu (cf. exemple 6).

    exercice 2-C

    1) Les hypothses impliquent que A B C. Si x A alors A,B(x) = 2 et A,C(x) = 2 et A,BC(x) = 2.

    Si x A et x B C alors chaque valeur est 1. Si x A, x B et x C alors A,B(x) = 1, A,C(x) = 0, A,BC(x) = 0. Si x A, x B et x C alors A,B(x) = 0, A,C(x) = 1, A,BC(x) = 0.

    Si x B C alors A,B(x) = 0, A,C(x) = 0, A,BC(x) = 0. La relation est vrifie pour chaque lment de E.

    2) En reprsentant les valeurs correspondant (A, B), (A, C), (A, B C), on observe que la somme A,B + A,C concide avec A,BC sauf dans B C. La diffrence vaut 2 dans A et 1 dans B C. On en dduit la formule

    A,BC = A,B + A,C A,BC .

    3) Par dfinition :

  • Daniel ALIBERT cours et exercices corrigs volume 1 87

    indications pour rsoudre - mthode - lexique

    C(B),C(A) (x) = 0 si x C(A), c'est--dire si x A, C(B),C(A) (x) = 1 si x C(B) et x C(A), c'est--dire si x B et x A, C(B),C(A) (x) = 2 si x C(B) soit x B. On voit immdiatement que C(B),C(A) (x) = 2 A,B (x). 4) Calcul de AA',B . Par "passage au complmentaire", il suffit de connatre : C(B),C(AA') = C(B),C(A)C(A'). (C(B),C(A)C(A'))2 = C(B),C(A) . C(B),C(A') = (2 A,B).(2 A',B) Donc, selon la relation de la premire question,

    AA',B = 2 (2 A, B ).(2 A' ,B ). Calcul de AA',B . On procde de la mme manire. Par passage au complmentaire : C(B),C(AA') = C(B),C(A)C(A') = C(B),C(A) + C(B),C(A') C(B),C(A) C(A') = 2 A,B + 2 A',B (2 A,B ).(2 A' ,B ). Donc :

    AA', B = A,B + A',B + (2 A,B ).(2 A' ,B ). 2.

  • Daniel ALIBERT cours et exercices corrigs volume 1 88

    indications pour rsoudre - mthode - lexique

    (QC-1) Si E est un ensemble fini, on peut donc compter les couples de parties (A, B) telles que A B, en comptant les applications de E dans {0, 1, 2}. Quel est le rsultat ? (QC-2) La fonction A,B s'exprime l'aide de 1A et 1B (voir exercice prcdent). Trouver cette formule, et dmontrer les relations proposes partir de celles de l'exercice prcdent ().

    exercice 3-C

    1) Soit x dans E. Si x f*(B), c'est--dire f(x) B, alors 1f*(B)(x) = 1 ; si f(x) B, alors 1f*(B)(x) = 0. Il en rsulte que 1f*(B)(x) = 1B (f(x)) quel que soit x dans E. D'o la relation :

    1f*(B) = 1B o f . D'aprs l'exercice 1, et ce qui prcde : 1f*(B)f*(B') = 1f*(B) . 1f*(B'), = (1B o f) . (1B' o f), = (1B . 1B') o f, = 1BB' o f, = 1f*(BB'). D'o l'galit :

    f*(B) f*(B') = f*(B B'). 2) Il suffit de calculer :

    Si x A, f(x) f(A) donc 1f(A) (f(x)) = 1, et 1f(A) o f (x) = 1A(x). Si x A, 1A(x) = 0, donc l'ingalit est vraie.

    (QC-1) Compte tenu de (exercice 1, 1-2)), (re)trouver une relation d'inclusion.

  • Daniel ALIBERT cours et exercices corrigs volume 1 89

    indications pour rsoudre - mthode - lexique

    3) Pour l'exemple propos, on voit que 1A(2) = 1 puisque 2 est un lment de A. Par contre 1A( 2) = 0. Pourtant, comme f(2) = f(2), si B existait, on aurait l'galit :

    1B(f(2)) = 1B(f( 2)). Pour cet exemple, B n'existe pas. Supposons que B existe, et soit y dans f

    *(A). Soit x dans A tel que

    y = f(x). On a donc : 1B(y) = 1B(f(x)) = 1A(x) = 1

    donc y est dans B, d'o l'inclusion. La relation ne caractrise pas B de faon unique, puisqu'elle ne porte que sur la valeur de 1B(y) pour y dans f*(A). Supposons que B existe, et soit x' dans f*(f

    *(A)). Alors f(x') est dans

    f*(A), donc dans B :

    1B(f(x')) = 1 1A(x') = 1

    donc x' est dans A, d'o l'inclusion. Rciproquement, les mmes calculs montrent que si f*(f

    *(A)) A, alors

    B existe, puisqu'il suffit de prendre B = f*(A) :

    si x A, f(x) f*(A), si x A, x f*(f

    *(A)) donc f(x) f

    *(A).

    Comme on a toujours l'inclusion A f*(f*(A)), on voit que B existe si et

    seulement si A = f*(f*(A)).

  • Daniel ALIBERT cours et exercices corrigs volume 1 90

    indications pour rsoudre - mthode - lexique

    exercice 4-C

    1) Pour l'application u : injectivit : Soit X et Y des parties de E, supposons :

    u(X) = u(Y), c'est--dire que A X = A Y. Est-ce que cela entrane l'galit de X et Y () ? Etudions, par exemple, l'inclusion de X dans Y. Soit x un lment de X, il en rsulte que x est un lment de A X, donc de A Y, donc On voit qu'on ne peut pas ncessairement conclure que x est un lment de Y, s'il est un lment de A. Ceci peut guider pour un contre-exemple :

    E = N, A = 2N (nombres pairs), X = {2, 4, 7}, Y = {2, 6, 7} Vrifier que ce cas montre que u n'est pas injective.

    (QC-1) Trouver une proprit des parties de E qui permet de conclure que si u(X) = u(Y) alors X = Y, pour X et Y ayant cette proprit ().

    surjectivit : Soit Y une partie de E. Existe-t-il une partie X telle que Y = u(X). On voit que ce sera vrai si et seulement si Y contient A. Conclusion : u n'est pas surjective.

    Pour l'application i : injectivit : On procde de mme.

    Supposons que i(X) = i(Y), c'est--dire que A X = A Y ; ceci ne permet pas de conclure que X = Y, bien entendu.

  • Daniel ALIBERT cours et exercices corrigs volume 1 91

    indications pour rsoudre - mthode - lexique

    Un contre-exemple : E = N, A = 2N (nombres pairs), X = {2, 4, 7}, Y = {2, 4, 5}.

    L'application i n'est pas injective.

    (QC-2) Trouver une proprit des parties de E qui permet de conclure que si i(X) = i(Y) alors X = Y, pour X et Y ayant cette proprit ().

    surjectivit : Soit Y une partie de E. Peut-on trouver une partie X telle que i(X) = Y, soit A X = Y ? Il est clair que cela exige que Y soit une partie de A. Puisque A E, l'quation i(X) = Y n'a pas toujours une solution, donc i n'est pas surjective.

    2) Pour l'application P(f). injectivit : Soient A et B des parties de E. On suppose f

    *(A) = f

    *(B).

    Est-ce que cela implique A = B ? On teste sur l'application de l'exemple 11. Il est vident sur que A peut tre diffrent de B. Un contre-exemple numrique : E = N, F = N, f(n) est le reste de la division de n par 3.

    A = {1, 2, 3, 4}, B = {0, 1, 5}, f*(A) = {1, 2, 0} = f

    *(B).

    (QC-3) Quelle proprit de f permet de conclure l'injectivit de P(f) ?

    surjectivit :

  • Daniel ALIBERT cours et exercices corrigs volume 1 92

    indications pour rsoudre - mthode - lexique

    Soit Y une partie de F. Existe-t-il une partie X de E telle que f

    *(X) = Y ?

    Comme f*(X) f

    *(E), on voit qu'une condition ncessaire () est que

    Y soit une partie de f*(E).

    Ceci n'est pas toujours vrifi, donc P(f) n'est pas surjective, en gnral.

    (QC-4) A partir de cette remarque, donner une proprit de f qui entrane que P(f) est surjective.

    Pour l'application Q(f), injectivit : Soient X et Y des parties de F telles que f*(X) = f*(Y). Peut-on en conclure que X = Y ? Le mme exemple montre que non. Pour un contre-exemple numrique : E = N, F = N, f(n) est le reste de la division de n par 3, X = {1, 3, 4, 5},

    Y = {1, 6, 7}, et f*(X) = f*(Y) = {3m + 1 | m N }. NB : 3, 4, 5, 6, 7 ne sont pas des restes de division par 3. Ils n'appartiennent pas f

    *(N). L'application Q(f) n'est pas injective en

    gnral (voir aussi l'exercice 7). surjectivit : Soit A une partie de E. Peut-on trouver une partie X de F vrifiant l'galit :

    f*(X) = A.

  • Daniel ALIBERT cours et exercices corrigs volume 1 93

    indications pour rsoudre - mthode - lexique

    Sur l'exemple 12, on voit bien que les parties 'images rciproques" ont un "aspect" particulier. On peut donc penser que l'quation ci-dessus n'a pas de solution quel que soit A. Un contre-exemple numrique :

    E = N, F = N, f(n) est le reste de la division de n par 3, A = {1}. Si A = f*(X), A = {t N | f(t) X},

    en particulier, f(1) = 1 est un lment de X, donc 4, 7, , 3n+1, pour tout n sont des lments de f*(X), qui n'est donc pas gal A. L'application Q(f) n'est pas surjective.

    (QC-5) On peut, comme pour P(f), rflchir des proprits de f qui impliquent que Q(f) est injective, ou surjective.

    exercice 5-C

    1) Cela signifie que les quations f(x) = b n'ont pas de solution si b est impair. Il est quivalent de dmontrer que l'application f ne prend que des valeurs paires. Or f(x) = x(x + 1) et si x est pair x(x + 1) est pair, si x est impair, x + 1 est pair donc x(x + 1) est pair.

    2) Cela signifie que tout entier n est solution d'une quation f(x) = b, o b est un entier pair. Plus prcisment, un entier n est solution de l'quation f(n) = b, pour b = n2 + n.

  • Daniel ALIBERT cours et exercices corrigs volume 1 94

    indications pour rsoudre - mthode - lexique

    (QC-1) A-t-on dmontr dans cette question que f est une bijection () de N sur l'ensemble des entiers pairs ? (QC-2) Plus gnralement, pour une application f : E F, si B1 et B2 forment une partition () de F, alors f*(B1) et f*(B2) forment une partition de E. Pourquoi ?

    3) f*({1, 2, 3, 5, 7, 11}) = {f(1), f(2), f(3), f(5), f(7), f(11)}

    = {2, 6, 12, 30, 56, 132}.

    f*({2, 4, 6, 8, 10, 12, 14}) : Rsoudre x2 + x = b, b prenant les valeurs 2, 4, 6, 8, 10, 12, 14, et x tant entier positif ; on note que x et x+1 sont des diviseurs de b, l'un pair, l'autre impair, conscutifs. b = 2, x = 1 ; b = 4, pas de solution (pas de diviseur impair) ; b = 6, x = 2 ; b = 8, pas de solution ; b = 10, diviseurs 1, 2, 5, et 10 donc pas de solution ; b = 12, diviseurs 1, 2, 3, 4, 6, 12, x = 3 ; b = 14, diviseurs 1, 2, 7, 14 donc pas de solution.

    f*({2, 4, 6, 8, 10, 12, 14}) = {1, 2, 3}.

    f*(f*({1, 2, 3, 5, 7, 11}) : Rsoudre x2 + x = b, b prenant le