Ensemble

- 1 -

2013 - Grard Lavau - http://lavau.pagesperso-orange.fr/index.htmVous avez toute libert pour tlcharger, imprimer, photocopier ce cours et le diffuser gratuitement. Toute diffusion titre onreux ou utilisation commerciale est interdite sans accord de l'auteur.Si vous tes le gestionnaire d'un site sur Internet, vous avez le droit de crer un lien de votre site vers mon site, condition que ce lien soit accessible librement et gratuitement. Vous ne pouvez pas tlcharger les fichiers de mon sitepour les installer sur le vtre.

ENSEMBLES, STRUCTURES ALGEBRIQUESPLAN

I : Vocabulaire1) Rgles usuelles et notations2) Logique3) Introduction la dmonstration4) Fonctions, injections, surjections5) Ensembles finis6) Relation d'quivalence7) Relation d'ordre

II : Structures algbriques1) Loi de composition interne2) Dfinition d'un groupe3) Sous-groupe4) Anneaux et corps

Annexe : les axiomes

I : VocabulaireOn rassemble ci-dessous un certain nombre de notions, introduites en cours d'anne. Une tudeexhaustive et directe de l'ensemble du chapitre serait particulirement indigeste. Il vaut mieux serfrer tel ou tel paragraphe le moment venu.

1 Rgles usuelles et notationsi) A, B et C tant les parties d'un ensemble E, on note :

A B = {x | x A ou x B} (runion de A et B)A B = {x | x A et x B} (intersection de A et B)

A = {x E | x A} (complmentaire de A)On prouvera en exercices les rgles usuelles suivantes :

A (B C) = (A B) (A C)A (B C) = (A B) (A C)

(A B) = A B

(A B) = A BA B

B

A

Ces rgles s'appliquent une runion ou une intersection quelconque, finie ou non. Si I dsigne unensemble quelconque d'indices, on pose :

x iI Ai i, x Ai (x est dans l'un des Ai. signifie "il existe")

- 2 -

x iI Ai i, x Ai (x est dans tous les Ai. signifie "quel que soit")EXEMPLE :

n *

[1n

, 1] = ]0,1].

n *

[1 1n

, 1] = {1}, alors que n *

[1 1n, 1[ =

dsigne l'ensemble vide, ne possdant aucun lment.

ii) On appelle diffrence de A et B la partie note A B (ou A \ B) dfinie par{x E | x A et x B}. On a A B = A B.

iii) Toutes les parties de E, depuis l'ensemble vide jusqu' E luimme, forment un ensembleappel ensemble des parties de E et not (E). Par exemple, si E = {1, 2, 3}, (E) = {, {1}, {2},{3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.Si E possde n lments, (E) en possde 2n. En effet, pour dfinir une partie A de E, il suffit dechoisir si chaque lment de E appartient ou non A, ce qui fait 2n choix possibles (deux choixpossibles par lment : il est dans A ou il n'est pas dans A). On a donc, en notant Card(E) le nombred'lments de E :

Card( (E)) = 2Card(E)

iv) Etant donn deux ensembles E et F, on note E F l'ensemble des couples (x, y), o x est lmentde E et y lment de F. Par exemple, l'ensemble des couples de rels est not , ou

2.L'ensemble des n-uplets ou n-listes (x1, x2, ..., xn) d'lments de E est not En. L'ensemble des suites(xi)iI d'lments de E, indices par un ensemble I fini ou non, est not EI.

2- LogiqueUne proposition mathmatique P est une phrase pouvant prendre les valeurs vrai ou faux. Parexemple, dans les entiers :

P : n, m, m = n2 est vraiQ : n, m, n = m2 est faux

Etant donn une proposition, le travail du mathmaticien consiste dterminer si elle est vraie oufausse. S'il arrive dmontrer qu'elle est vraie, cette proposition est un thorme.

On est amen regrouper diverses propositions de la faon suivante :

a) la conjonction : "P et Q" est une proposition qui sera vraie si et seulement si les deuxpropositions P et Q sont simultanment vraies.

b) la dijonction : "P ou Q" est une proposition qui est vraie si et seulement si au moins une des deuxpropositions P ou Q est vraie. Les deux peuvent tre vraies. le "ou" a un sens inclusif. (Il existe un"ou" exclusif, mais qui n'est pas utilis de faon usuelle).

- 3 -

c) l'quivalence : "P Q" est vraie si et seulement si P et Q sont simultanment vraies ousimultanment fausses, autrement dit, si P et Q ont mme valeurs de vrit. Par exemple :

x = ey x > 0 et y = ln(x)

L'quivalence peut s'appliquer des propositions fausses. Par exemple, si on veut montrer qu'uneproposition P est fausse, on peut chercher une proposition Q quivalente P et montrer que Q estfausse.

d) l'implication logique : "P Q" est vraie si et seulement si P est fausse ou Q est vraie. Cettenotion est la plus difficile matriser, contrairement ce qu'on peut penser au premier abord.Prenons un exemple pour illustrer ce fait. Considrons un circuit lectrique en srie constitu d'ungnrateur de courant, d'un interrupteur et d'une lampe.

lampe

interrupteur

gnrateur

L'interrupteur peut tre ouvert ou ferm ; la lampe peut tre allume ou teinte.Soit P la proposition : la lampe est allume.Soit Q la proposition : l'interrupteur est ferm.

Quelle est la relation d'implication logique entre P et Q ? A-t-on P Q ? Q P ? A-t-onl'quivalence P Q ? Prcisons qu'on ne recherche pas une relation causale, telle que le conoit lephysicien. Nous cherchons une relation logique permettant de faire une dduction.

Il y a trois situations possibles :

interrupteur ouvert interrupteur ferm interrupteur ferm lampe teinte lampe allume lampe teinte

situations les plus courantes situation inhabituelle mais pas impossible : lampe grille, voltage trop faible, ...Une seule situation est impossible :

- 4 -

interrupteur ouvert lampe allume.

La seule implication logique est la suivante :P Q : si la lampe est allume, alors l'interrupteur est ferm.

L'implication Q P (si l'interrupteur est ferm, alors la lampe est allume) correspond certes uneexplication causale de l'allumage de la lampe, mais n'est possible que dans un monde idal et parfaito les lampes ne tombent jamais en panne, et ne constitue en rien une consquence logique.

On rflchira au fait que toutes les phrases qui suivent ont la mme signification :P Q lampe allume interrupteur ferm

non(Q) non(P) (contrapose) interrupteur ouvert lampe teinte

si P alors Q si la lampe est allume, alors on en dduit que l'interrupteur est ferm.

P est suffisant pour Q il suffit que la lampe soit allume pouril suffit P pour avoir Q conclure que l'interrupteur est ferm.

P seulement si Q la lampe est allume seulement sil'interrupteur est ferm.

Q est ncessaire pour P il faut que l'interrupteur soit fermil faut Q pour avoir P pour que la lampe soit allume.

non(P) ou Q la lampe est teinte, ou l'interrupteurest ferm

Il rsulte de cela que l'implication est vrifie dans les trois cas suivants (correspondant nos troisdessins) :

P est vrai et Q est vraiP est faux et Q est vraiP est faux et Q est faux

Ainsi, si P est faux, Q est quelconque et il n'y a rien montrer. La seule chose montrer est doncbien que, si P est vrai, alors Q est vrai.

L'implication est fausse dans le seul cas suivant :P est vrai et Q est faux

Il ne peut y avoir d'implication, puisque l'hypothse est vrifie, mais pas la conclusion.

- 5 -

La rciproque de l'implication P Q est Q P. Elle peut tre vraie ou fausse, indpendamment dela valeur de vrit de P Q. Dans notre exemple, la rciproque est fausse. Toutes les phrases quisuivent sont quivalentes Q P. Elles sont donc fausses, le contre-exemple tant donn par letroisime dessin :

Q P interrupteur ferm lampe allume

non(P) non(Q) (contrapose) lampe teinte interrupteur ouvert

si Q alors P si l'interrupteur est ferm, alors lalampe est allume.

Q est suffisant pour P il suffit que l'interrupteur soit ferm il suffit Q pour avoir P pour conclure que la lampe est allume.

Q seulement si P l'interrupteur est ferm seulement si la lampe est allume.

P est ncessaire pour Q il faut que la lampe soit allume pouril faut P pour avoir Q conclure que l'interrupteur est ferm.

non(Q) ou P l'interrupteur est ouvert, ou la lampe est allume

Enfin, dire que P Q et Q P, c'est dire que P Q.

e) la ngationLa ngation d'une proposition P est note "non(P)". La ngation d'une proposition P vraie serafausse et la ngation d'une proposition P fausse sera vraie.

La ngation de "P et Q" est "non(P) ou non(Q)". En effet, dire que "P et Q" est fausse, c'est direqu'une au moins des deux propositions est fausse.

La ngation de "P ou Q" est "non(P) et non(Q)". En effet, nier le fait qu'au moins une des deuxpropositions est vraie, c'est dire qu'elles sont toutes deux fausses.

La ngation de "P Q" est "P et non(Q)". En effet, nous avons vu que "P Q" est synonyme de"non(P) ou Q". La ngation est donc bien "P et non(Q)". Dire que l'implication est fausse, c'est direqu'on a l'hypothse P, mais pas la conclusion Q.

La ngation de "P Q" est "(P et non(Q)) ou (Q et non(P))".

La ngation de " x, P(x)" est " x, non(P(x))". En effet, dire qu'il est faux que P soit vraie pour toutx, c'est dire que P est faux pour au moins un x.

La ngation de " x, P(x)" est " x, non(P(x))". En effet, dire qu'il n'existe aucun x vrifiant P, c'estdire que tous les x vrifient la ngation de P.

- 6 -

Il rsulte des deux derniers cas que, pour prendre la ngation d'une proposition enchanant lesquantificateurs et , il suffit de lire la proposition de gauche droite, de changer les en , dechanger les en puis de prendre la ngation de ce qui reste.Exemple : la ngation de :

x, > 0, > 0, y, y x < f(x) f(y) < est :

x, > 0, > 0, y, y x < et f(x) f(y) (La premire proposition si mystrieuse exprime la continuit d'une fonction f en tout point x. Ladeuxime exprime la non-continuit de f en un point x)

On notera enfin que : x A, P(x) est une abrviation pour : x, x A P(x)

et a donc pour ngation : x, x A et non(P(x)), ce qu'on abrge en : x A, non(P(x))

De mme, la ngation de x A, P(x) est x A, non(P(x)).

On utilisera au besoin des parenthses pour lever toute ambigut. Par exemple, dans les entiers, lesdeux propositions suivantes ont des sens diffrents. La premire est vraie, la seconde est fausse.

n, [( m, mn pair) n pair] n, [ m (mn pair n pair)]

En effet, dans la premire proposition, n tant donn, on suppose que mn est pair pour tout entier m,en particulier pour m = 1. Donc n est pair. Dans la deuxime proposition, n tant donn, on supposeque c'est l'implication mn pair n pair qui est vraie pour tout m. Or cette implication est faussepour m = 2 et n = 3 par exemple. n = 3 ne vrifie donc pas la condition demande.

3- Introduction la dmonstrationLorsqu'un mathmaticien, aprs des heures, des jours, voire des annes de labeur, pense qu'uneproprit est vraie, il fait une conjecture. Pour tre certain que cette proprit soit vraie et pour lafaire valider par l'ensemble de la communaut mathmatique ou scientifique, il faut unedmonstration. La dmonstration n'est donc pas la tche essentielle du travail du mathmaticien, maisson achvement. Dans une moindre mesure, on demande la mme chose l'tudiant scientifique. Cedernier, apprenti mathmaticien, a parfois du mal mettre en forme une dmonstration. Ceparagraphe peut lui donner quelques procds mthodiques.

La dmarche dmonstrative repose sur une liste de connaissances appele voluer. Cette listecomprend tous les axiomes et thormes connus du dmonstrateur, mais peut galement voluer parajout de proprits au cours de la dmonstration. Le dmonstration doit dmontrer une proposition,c'est dire une phrase mathmatique que le dmonstrateur pense tre vraie. Nous avons vu dans leparagraphe prcdent qu'une proposition peut tre construite partir de proprits lmentaires enutilisant itrativement conjonction (et), disjonction (ou), implication (), et ngation (non).L'quivalence () quant elle, n'est que la conjonction de deux implications ( et ). A cela, onajoute les quantificateurs existentiel () et universel ().

Il convient d'abord de clairement sparer ce qu'on sait ou suppose vrai (thormes, dfinitions, maisaussi hypothses diverses, qu'on regroupera sous le terme gnral de liste des connaissances), de laconclusion laquelle on veut arriver. Par ailleurs, il convient de savoir qu'une dmonstration neconsiste pas forcment partir de l'hypothse, puis par une suite de dductions logiques, arriver

- 7 -

la conclusion. On peut bien sr partir de l'hypothse pour en dduire diverses proprits en esprantque l'une d'elles finira par tre la conclusion cherche, mais on peut aussi partir de la conclusion pourtrouver des proprits partir desquelles la conclusion se dduit, en esprant ainsi remonterjusqu'aux hypothses. On peut galement oprer simultanment les deux dmarches jusqu' tombersur une proprit faisant le lien entre les deux. Ci-dessous, P est une proprit pouvant servir dejonction entre une progression venant de l'hypothse et une progression venant de la conclusion :

P112 P1 P11 P111 ... ... Q11 Q1 hypothse P2 ... etc... ... P ... ... Q22 Q2 conclusion

P3 P31

Sens dans lequel s'opre la recherche Sens dans lequel s'opre la recherchede nouvelles proprits qui se dduisent de nouvelles proprits d'o dcoulede l'hypothse la conclusion

Il convient galement de distinguer ce qu'il faut faire pour montrer une conjecture, de ce qu'il fautfaire pour utiliser une proprit dj prouve ou une hypothse, et faisant donc partie de la liste desconnaissances. On donne donc pour chaque connecteur logique (et, ou, non, implique) :q d'une part une rgle qui permet de montrer une proprit possdant ce connecteur, et doncd'ajouter cette proprit la liste des connaissances (rgle dite d'introduction).q d'autre part une rgle qui permet d'utiliser une proprit possdant ce connecteur et faisant partiede la liste de connaissances, soit pour montrer une autre proprit, soit pour remplacer dans la listedes connaissances la proprit par une ou d'autres proprits. Une fois utilise, la proprit enquestion peut en gnral tre limine de la liste de connaissances (rgle dite d'limination), sauf sielle doit tre utilise plusieurs fois.q Enfin, la rgle nonant le principe du raisonnement par l'absurde.

Certaines de ces rgles paratront triviales. D'autres le sont beaucoup moins. Par ailleurs, plusieursapproches diffrentes peuvent tre possibles pour aboutir la mme conclusion. Nous notons par A,B, C... des proprits prouver, et par P, Q, R... des proprits dj prouves donc faisant partie dela liste des connaissances (la classification ci-dessous constitue le fondement de la logique classique.Une telle classification est par exemple utilise par des logiciels d'assistants de preuves).

(Rgles d'introduction) POUR MONTRER...(i) ...une conjonction A et B : montrer A et montrer B.

(ii) ...une disjonction A ou B : montrer A ou montrer B.

(iii) ...une implication A B : ajouter A comme hypothse sa liste de connaissances (autrementdit, supposer A) et montrer B.

(iv) ...une ngation non(A) : ajouter A comme hypothse sa liste de connaissance et montrer qu'onaboutit une contradiction. A est alors ncessairement faux. Autrement dit, non(A) est synonyme deA contradiction.

- 8 -

(v) ... x A(x) : exhiber un lment t bien choisi et montrer A(t).

(vi) ... x A(x) : montrer A(u), u tant un symbole quelconque non encore utilis par ailleurs.

(Rgles d'limination) POUR UTILISER...(a) ...une conjonction P et Q : ajouter P la liste des connaissances et ajouter Q.

(b) ...une disjonction P ou Q : en dduire la validit de R en montrant P R et Q R (mthode dedisjonction des cas). Pour montrer par exemple qu'une suite monotone (i.e. croissante oudcroissante) borne converge, il suffit de montrer qu'une suite croissante borne converge et qu'unesuite dcroissante borne converge.

(c) ...une implication P Q : ajouter Q la liste des connaissances condition que P y soit dj.

(d) ...une ngation non(P) : dduire une contradiction si P fait galement partie de la liste desconnaissances. Autrement dit, une contradiction est un synonyme de (P et non(P)).

(e) ... x P(x), ajouter P(u) la liste des connaissances, u tant un symbole quelconque non djutilis par ailleurs. u dsigne ici l'lment particulier qui vrifie la proprit P. On prendra garde nepas choisir un u intervenant dans une autre proprit.

(f) ... x P(x), ajouter P(t) la liste des connaissances, t tant un objet choisi notre gr.

LE RAISONNEMENT PAR L'ABSURDEEn logique classique, on ajoute la rgle suivante, dite de raisonnement par l'absurde.Pour montrer P, ajouter non(P) la liste des connaissances et montrer une contradiction. Autrementdit, si non(P) contradiction, on a prouv P. Cette rgle s'appelle galement simplification de ladouble ngation, puisque non(P) contradiction est synonyme de non(non(P)).

Cette rgle est utilise implicitement dans :q Le tiers exclu : pour toute proprit P, on a (P ou non(P)). En effet, dans le cas contraire, onaurait non (P ou non(P)), c'est--dire non(P) et non(non P) ce qui est contradictoire. Donc on a bienP ou non(P).

q La contraposition : si (non(P) non(Q)) alors (Q P). En effet, supposons que l'on aitnon(P) non(Q) et que Q soit vrai. Il s'agit de montrer que P est vrai. Raisonnons par l'absurde etsupposons non(P). On a alors non(Q) d'aprs la premire implication. Ayant Q et non(Q), on aboutit une contradiction. Donc non(P) est absurde et P est vrai.

En mathmatiques classiques, toutes les dmonstrations mathmatiques utilisent ces principes, etuniquement ces principes.

EXEMPLE 1 :Montrer que : n , [n2 impair n impair]D'aprs (vi), nous allons montrer que n2 impair n impair, n tant un nombre quelconque. D'aprs(iii), nous allons supposer que n2 est impair et montrer que n est impair.

- 9 -

On sait ou on suppose que : On veut montrer que :

n2 est impair n est impair

Raisonnons par l'absurde. Nous allons supposer n non impair (i.e. n pair) et arriver unecontradiction. Si on y parvient, on aura prouv que n est effectivement impair.

On sait ou on suppose que : On veut montrer :

n2 est impair

n pairune contradiction

On utilise la dfinition de la parit :n pair p , n = 2p (dfinition de la proprit "tre pair")

On sait ou on suppose que : On veut montrer :

n2 est impair

p

, n = 2pune contradiction

On a n = 2p (utilisation implicite de (e)) donc n2 = 4p2 qui est pair et non impair. On a bien obtenuune contradiction. CQFD.

On notera que la dmonstration utilise le fait que n est pair. La plupart des tudiants partent den

2 = 2p + 1, dmarche gnralement voue l'chec.

EXEMPLE 2 :Toute suite relle croissante majore converge (il convient de lire cet exemple aprs avoir acquis lesconnaissances sur les rels et la notion de borne suprieure. cf le chapitre Suites dans le fichierSUITES.PDF). Bien entendu, dans le chapitre Suites, nous allons plus vite au but, mais on pourra serendre compte que la dmonstration est base sur une application des principes (i) (vi) et (a) (f),ce que nous dveloppons ci-dessous de faon outrageusement dtaille. Insistons sur le fait que lemathmaticien ne dveloppe jamais explicitement dans ses moindres dtails une telle dmarche. Cedveloppement a seulement pour but de mettre jour les utilisations souvent implicites des ditsprincipes.

Il s'agit de montrer que : (un), [ (un) est croissante et (un) est majore (un) converge ]

D'aprs (vi) et (iii), on a :

- 10 -


(un) est croissanteet (un) est majore

(un) converge

On traduit chaque proprit (croissance, majoration, convergence) :


n un un+1M n un M

l > 0 N n N, l < un < l +

Nous avons un thorme d'existence de la borne suprieure (cf le chapitre Suites dans le fichierSUITES.PDF) qui dit : M n un M Sup {un, n } existe. L'application de la rgle (c)donne donc, en abrgeant la liste des connaissances (ce que nous ferons plusieurs fois pour allger) :


n un un+1Sup(un) existe

l > 0 N n N, l < un < l +

Nous allons prendre l = Sup {un, n } (application de la rgle (v)). C'est videmment le travail dumathmaticien de faire le bon choix de l et il n'y a hlas aucune mthode automatique pour cela ).On peut simplement dire qu'on cherche un rel particulier l et que le seul dont on ait connaissance, part les termes de la suite, c'est la borne suprieure. D'o l'ide de prendre l = Sup(un).


n un un+1l = Sup(un)

> 0 N n N, l < un < l +

D'aprs la rgle (vi), nous prenons > 0 quelconque. Comme la formulation > 0 ... est uneabrviation de , > 0 ..., la rgle (iii) ajoute la condition > 0 aux hypothses. Nousremplaons galement l = Sup(un) par la dfinition de la borne suprieure :


n un un+1n un l

> 0 m l < um > 0

N n N, l < un < l +

- 11 -

Le pouvant tre choisi notre gr selon la rgle (f), nous prendrons = . L aussi, le choix du relve de l'intuition du mathmaticien ...


n un un+1 n un l

m l < um > 0

N n N, l < un < l +

Nous appliquons la rgle (v) en choisissant N = m (le m de la liste des connaissances).


n un un+1 n un l

m l < um > 0

n m, l < un < l +

Nous prenons n quelconque suprieur ou gal m en application de la rgle (vi). Comme n m ...est une abrviation de n, n m ..., d'aprs (iii), on ajoute n m nos hypothses, et plutt quen dont le symbole est dj utilis dans la liste des connaissances, nous noterons cet entier p :


n un un+1 n un l

m l < um > 0p m

l < up < l +

Dans la deuxime proprit de la liste des connaissances, nous choisissons (rgle (f)) n = p.


n un un+1 up l

m l < um > 0p m

l < up < l +

Nous appliquons la rgle (e) la troisime proprit de la liste des connaissances. m dsigne unlment sur lequel nous n'avons aucune possibilit de choix.

- 12 -


n un un+1 up l

l < um > 0p m

l < up < l +

Enfin, dans la premire proprit de la liste des connaissances, nous choisissons (rgle (f) itreplusieurs fois) n = m, n = m+1, ... n = p1, n = p.


um um+1 ... up1 up up l

l < um > 0p m

l < up < l +

Ce qu'on peut encore crire :


l < um um+1 ... up1 up l > 0

l < up < l +

Ou encore plus brivement :


l < up l > 0

l < up < l +

La conclusion montrer est bien vraie puisque l l + .

On aura remarqu que le choix de tel ou tel lment x au gr du dmonstrateur se manifeste :ou bien dans la liste des connaissances sur une proprit du type x P(x) (rgle (f))ou bien dans la conclusion montrer sur une proprit du type x A(x) (rgle (v))

En effet, dans le premier cas, la proprit P(x) tant vraie pour tout x, on est libre de l'appliquer au xque l'on veut.Dans le second cas, puisqu'on doit montrer la proprit A(x) pour un certain x, on peut choisir le xqui nous parat rpondre la question (c'est l la partie la moins vidente), et, si notre choix a tjudicieux, parvenir prouver A(x) pour ce x bien choisi.

- 13 -

A l'inverse, le dmonstrateur n'a aucune libert de choix sur l'lment x qui intervient :dans la liste des connaissances sous la forme x P(x) (rgle (e))dans la conclusion montrer sous la forme x A(x) (rgle (vi))

Dans le premier cas, on suppose l'existence d'un x vrifiant P(x) mais ce x nous est impos.Dans le second cas, on ne peut se contenter de montrer A(x) pour un x de notre choix puisqu'il s'agitde montrer A(x) pour tous les x.

La comprhension de ce mcanisme est essentielle pour mener bien des dmonstrations correctes etpour savoir sur quels lments on peut faire un choix.

4 Fonctions, injections, surjectionsa) Fonction :Une fonction f (ou application) d'un ensemble E dans un ensemble F tablit une relation entre leslments de E et ceux de F. Tout lment x de E est associ un unique lment de F, not f(x). f(x)est l'image de x par f. Si y est dans F et s'il existe x dans E tel que y = f(x), x est un antcdent de ypar f. Certains lments y de F peuvent n'tre l'image d'aucun lment de E, et certains lments y deF peuvent tre l'image de plusieurs lments de E, d'o les dfinitions d'injection et de surjection dansla suite du paragraphe.

La partie G de E F gale {(x, y), y = f(x)} s'appelle graphe de f. On note (E, F) (ou parfois FE)l'ensemble des applications de E dans F.

Si on dispose d'une application f de E dans F et d'une application g de F dans H, on peut dfinir lacompose g o f de E dans H par : (g o f)(x) = g(f(x)).

L'application identique IdE est l'application de E dans E dfinie par IdE(x) = x.

Si A est inclus dans E, la restriction de f A est l'application f|A de A dans F dfinie par f|A(x) = f(x).La seule diffrence entre f et f|A est l'ensemble de dfinition des applications : f est dfinie sur E alorsque f|A est dfinie sur A.Inversement, si E est inclus dans H et s'il existe une application g de H dans F telle que g|E = f, on ditque g est un prolongement de f H.

b) Injection :Une fonction f d'un ensemble E dans un ensemble F est dite injective (one to one en anglais) si :

x E, x' E, x x' f(x) f(x')ou encore (ce qui est plus couramment utilis) :

x E, x' E, f(x) = f(x') x = x'Si f est injective, l'quation f(x) = y a au plus une solution, quel que soit y.

Si f et g sont injectives, alors g o f l'est. En effet :(g o f)(x) = (g o f)(x')

(g(f(x)) = g(f(x')) (dfinition de g o f) f(x) = f(x') (injectivit de g) x = x' (injectivit de f)

- 14 -

c) Surjection :Une fonction est dite surjective (onto) si :

y F, x E, y = f(x)Si f est surjective, l'quation f(x) = y a au moins une solution, quel que soit y.

Si f et g sont surjectives, alors g o f l'est. En effet : z, y, z = g(y) (surjectivit de g)

z, y, x, z = g(y) et y = f(x) (surjectivit de f) z, x, z = g(f(x)) z, x, z = (g o f)(x) (dfinition de g o f)

d) bijection :f surjective et injective est dite bijective.Si f est bijective, l'quation f(x) = y a exactement une solution x, quel que soit y. On peut alors dfinirla fonction rciproque f1 de f par l'quivalence :

y = f(x) x = f1(y).On a alors f(f1(y)) = f(x) = y ce qu'on crit encore f o f1 = IdF et f1(f(x)) = f1(y) = x ce qui s'critf1 o f = IdE.

Si f et g sont bijectives, alors g o f l'est et (g o f)1 = f1 o g1. En effet :z = (g o f)(x)

z = g(f(x)) g1(z) = f(x) f1(g1(z)) = x x = (f1 o g1)(z)

S'il existe une application g de F dans E telle que f o g = IdF et g o f = IdE, alors f et g sont bijectiveset rciproques l'une de l'autre. En effet, la seule solution x possible l'quation y = f(x) est x = g(y).C'est bien une solution puisque f(g(y)) = y. Il n'y en a pas d'autre puisque :

y = f(x) g(y) = g(f(x)) = xOn notera que l'on a besoin des deux relations f o g = IdF et g o f = IdE pour prouver l'existence etl'unicit. La premire relation f o g = IdF montre l'existence de la solution et prouve que f estsurjective. La seconde relation g o f = IdE montre l'unicit de la solution et prouve que f est injective.

EXEMPLE 1 : L'application x sin(x) est :injective si l'ensemble de dpart est [ pi2,

pi2]

surjective si l'ensemble d'arrive est [1,1]

EXEMPLE 2 :Pour n entier naturel, notons [[1, n ]] l'ensemble des entiers de 1 n. Alors il existe une bijectionentre [[1, n ]] et [[1, p ]] si et seulement si n = p.

EXEMPLE 3 : il n'existe aucune bijection entre E et (E), que E soit fini ou non. C'est clair si E estfini avec n lments, puisque E et (E) n'ont pas le mme nombre d'lments (n et 2nrespectivement), plus dlicat montrer si E est infini. Pour cela, nous allons montrer que, quelles quesoient les fonctions f de E dans (E) et g de (E) dans E, on a f o g Id (E). Il est par contre tout

- 15 -

fait possible d'avoir g o f = IdE. Il suffit pour cela de prendre f(x) = {x} et g(A) = un lment donnde A pour A non vide.

Pour montrer que :(1) f o g Id (E)

nous allons modifier cette proposition jusqu' obtenir une affirmation manifestement vraie dont (1)dcoule. La difficult essentielle est de bien comprendre qu'un lment de E a pour image par f unepartie de E, et qu'une partie de E a pour image par g un lment de E. On peut dj crire que (1)quivaut :

(2) A E, f o g(A) A

On crit ensuite le fait que les deux parties A et f o g(A) sont diffrentes, savoir l'appartenance lapremire partie ne saurait tre quivalente l'appartenance l'autre partie :

(3) A E, x, non [x A x f o g(A)](On aurait pu crire aussi qu'il existe un x dans la premire partie et pas dans la seconde, moins quex soit dans la seconde et pas dans la premire, ce qui est strictement identique la formulation ci-dessus).

Comment trouver ce x partir de A ? Nous ne connaissons qu'un seul lment de E en liaison avecA, c'est x = g(A). Pour que (3) soit vrifi, il suffit donc d'avoir :

(4) A E, non [g(A) A g(A) f o g(A)]

La prcdente proposition sera elle-mme vrifie si :(5) A E, x, non [x A x f (x)]

Il suffit en effet d'appliquer (5) au x particulier gal g(A) pour retrouver (4).

On peut aussi crire (5) sous la forme quivalente :(6) A E, x, [x A x f (x)]

Or cette dernire proposition est vraie si l'on choisit prcisment A = {x | x f(x)}. On a alors lachane de dduction suivante :

(6) vrai (5) (4) (3) (2) (1).

Une variante ainsi que des consquences de cet exemple sont prsentes en annexe.

e) image directe d'une partie :Soit A une partie de E. L'image de A par f est l'ensemble not f(A) dfini par :

f(A) = {y F | x A, y = f(x)}Autrement dit :

y f(A) x A, y = f(x)f(A) est l'ensemble des images des lments de A.

EXEMPLE : si f est la fonction sinus, alors f([0,3pi4 ]) = [0,1]

f) image rciproque :Soit B une partie de F. L'image rciproque de B par f est l'ensemble not f1(B) dfini par :

f1(B) = {x E | f(x) B}Autrement dit :

- 16 -

x f1(B) f(x) Bf1(B) est l'ensemble des antcdents des lments de B.

EXEMPLE : si f est la fonction sinus, f1([0,1]) = n

[2npi, 2npi + pi]

On prendra garde que cette partie est dfinie mme si f n'est pas bijective, que f1({y}) est l'ensemble(ventuellement vide ou constitu de plus d'un lment) des antcdents de y, et que la notationf1(y), elle, n'est tolre que si f est bijective ; on dsigne ainsi l'antcdent unique de y.

EXEMPLE :Toujours avec f = sin, f1({0}) = {npi, n } = pi .f1(0) n'existe pas.

EXERCICES :i) Comparer f(A B) et f(A) f(B)On prouve que : A, B, f(A B) f(A) f(B)

On pourra chercher quelle condition on a : A, B, f(A B) = f(A) f(B)

On trouvera qu'une condition ncessaire et suffisante est f injective.

ii) Comparer f(A B) et f(A) f(B)Il y a galit

iii) Comparer f( A) et f(A)En gnral, ils sont diffrents. On prouve que :

f injective A, f( A) f(A)f surjective A, f(A) f( A)

iv) Procder de mme pour les images rciproques.Il y a toujours galit.

v) Comparer B et f(f1(B)).On a toujours f(f1(B)) BUne condition ncessaire et suffisante pour que :

B, f(f1(B)) = Best que f soit surjective

vi) Comparer A et f1(f(A)).On a toujours A f1(f(A)).Une condition ncessaire et suffisante pour que :

A, A = f1(f(A))est que f soit injective

vii) Soit f : E F g : F G

- 17 -

h : G HMontrer que : g o f surjectif g surjectif g o f injectif f injectif g o f et h o g bijectifs f, g et h bijectifs

viii) Donnons un exemple d'application f et g telles que f et g soient non bijectives, mais o g o f l'est.

f : n n+1g : 0 0 n n1 pour n non nul.

5 Ensembles finisNous nonons ci-dessous un certain nombre de proprits sur les ensembles finis, sans chercher les justifier outre mesure.

E est un ensemble fini s'il existe une bijection de [[1, n ]] sur E, o l'on note [[1, n ]] l'ensemble desentiers de 1 n. n est le cardinal de E, not Card(E).

Une partie de est finie si et seulement si elle est majore. Si n est le cardinal de cette partie, ilexiste une bijection strictement croissante et une seule entre cette partie et [[1, n ]]. 1 est l'image del'lment le plus petit, 2 l'image du suivant, etc...

Card() = 0

Si E' est inclus dans E, alors Card(E') Card(E), avec galit si et seulement si E' = E.

Si f est une application de E dans F et si Card(E) = Card(F) (fini), alors, il y a quivalence entreinjective, surjective et bijective. En effet, compte tenu de l'galit entre Card(F) et Card(E), on a :

f injective Card(E) = Card(f(E)) Card(F) = Card(f(E))or f(E) est inclus dans F, donc f(E) = F puisqu'ils ont mme nombre d'lments, et f est surjective.De mme :

f surjective f(E) = F Card(F) = Card(f(E)) Card(E) = Card(f(E))donc deux lments distincts de E ne peuvent avoir deux images identiques. f est donc injective.Ces remarques sont fausses si E et F sont des ensembles infinis.

La runion de deux parties finies est finie et l'on a :Card(A B) = Card(A) + Card(B) Card(A B)

puisque la somme Card(A) + Card(B) compte deux fois (une fois de trop) les lments deCard(A B). Evidemment, si A et B sont disjoints (i.e. A B = ), on a Card(A B) = Card(A)+ Card(B).On pourra de mme rflchir que :Card(A B C) = Card(A) + Card(B) + Card(C) Card(A B) Card(A C) Card(B C)

+ Card(A B C)

On a :Card(E F) = Card(E) Card(F)

- 18 -

Le cardinal de l'ensemble (E, F) des applications de E dans F est gal (Card(F))Card(E). En effet,pour chaque lment de E, il y a Card(F) choix possibles pour son image. Ainsi, le nombred'applications de E dans {0, 1} est gal 2Card(E) de mme que Card( !! (E)), ce qui s'explique par lefait que chaque partie A de E est caractrise par une unique application de E dans {0,1}, appele safonction indicatrice, que nous noterons 1A. Cette fonction est dfinie par :

1A(x) = 1 si x A = 0 si x A

Il y a donc autant de parties dans E que de fonctions de E dans {0,1}.

Si Card(E) = n, le nombre de bijections de E est gal n!. En effet, il y a n choix possibles pourl'image du premier lment de E, mais seulement n1 pour le suivant, n2 pour le suivant, etc...jusqu'au dernier o il ne restera plus qu'un seul choix possible. Les bijections d'un ensemble finis'appellent aussi permutations de cet ensemble.

6- Relation d'quivalenceSoit E un ensemble. Une relation binaire "" sur E est une fonction de E E valeurs boolennes(vrai ou faux). Si x et y sont deux lments de E, x ## y peut tre vrai ou faux. Un exemple frquentest constitu des relations permettant de relier des lments partageant une proprit commune. Ils'agit des relations d'quivalence.

a) Exemples et dfinition :Voici des exemples de relations d'quivalence :

q Dans un ensemble quelconque, l'galit est une relation d'quivalence triviale. La propritcommune est d'tre identique.

q Dans l'ensemble des droites affines du plan, D // D' (D est parallle D') si et seulement si D et D'ont mme vecteur directeur. La proprit commune D et D' est d'avoir une mme direction.

q Dans $$ , soit p un nombre donn. Pour tout couple (n, m) de %% 2, on pose :n m mod p k, n = m + kp

On dit que n est congru m modulo p. La proprit commune n et m est d'avoir mme reste dansla division euclidienne par p.

q Dans && , soit un rel. On dispose d'une dfinition analogue :x y mod k, n = m + k

Un exemple classique intervient avec = 2pi pour les mesures des angles.

q Dans '' (( *, on considre la relation ab' = ba' entre deux couples (a, b) et (a', b'). La propritcommune est de reprsenter le mme rationnel ab =

a'

b'.

Formellement, une relation )) sur un ensemble E sera une relation d'quivalence si elle vrifie lesproprits suivantes. Elle est : rflexive symtrique

- 19 -

transitive

i) La rflexivit s'applique aux relations vrifiant : x E, x ** x

ii) La symtrie s'applique aux relations vrifiant : x E, y E, x ++ y y ,, x

iii) La transitivit s'applique aux relations vrifiant : x E, y E, z E, [ x -- y et y .. z] x // z

EXERCICE :Vrifier que les relations donnes dans les exemples sont toutes des relations d'quivalence.

b) Partition et classes d'quivalence :Une partition d'un ensemble E est une famille (Ai)iI vrifiant :

i, Ai i, j, i j Ai Aj = iI Ai = E

Une partition permet de dfinir une relation 00 de la faon suivante :x 11 y i, x Ai et y Ai

22

dfinit la relation "appartenir au mme Ai". Une telle relation

Rciproquement, une relation d'quivalence permet de dfinir une partition de E.

DEFINITIONSoit 33 une relation d'quivalence sur un ensemble E. La classe d'quivalence Cx d'un lment x estl'ensemble {y E | y 44 x}.La classe de x rassemble tous les lments en relation avec x (qui ont mme proprit que x pour larelation donne). On peut vrifier que :

a) x Cxb) x 55 y Cx = Cyc) non(x 66 y) Cx Cy =

En effet :a) rsulte de la rflexivit.b) rsulte de la transitivit et de la symtrie rsulte du a) et de la dfinition des classes d'quivalencec) se prouve par l'absurde. Si z est lment de Cx Cy, alors on a z 77 x et z 88 y, donc, en

utilisant la symtrie et la transitivit, x 99 y. est vident.

- 20 -

En consquence, les classes d'quivalences sont non vides, disjointes deux deux, et leur runion estgale E. Elles forment une partition de E.

EXEMPLE : Un exemple fondamental de relation d'quivalence intervient en Physique dans ledomaine de la thermodynamique. Il est tellement banal qu'il faut se forcer se poser la question desavoir pourquoi cette proprit est vrifie. Considrons trois corps A, B et C, chacun en quilibrethermique. On dira que A et B ont mme temprature si, lorsque A et B sont mis en contact, aucunchange thermique n'a lieu entre eux. Supposons que A et B aient mme temprature, et que B et Caient mme temprature. Peut-on dire que A et C ont mme temprature ? On doit prendreconscience que la rponse oui donne cette question ne doit pas reposer sur une utilisationsyntaxique du vocabulaire (A et B ont mme temprature, B et C ont mme temprature donc A et Cont mme temprature), mais sur des expriences physiques rptes. Ces expriences, nous leseffectuons plus ou moins consciemment tous les jours, et la rponse ces expriences est positive.Le physicien pose alors comme principe que cette rgle est universellement respecte. C'est leprincipe zro de la thermodynamique, qui exprime donc le fait que la proprit "avoir mmetemprature" est une relation d'quivalence. Ce principe, pour tre nonc, n'a pas besoin de dfinirce qu'est la temprature. Il nonce simplement le rsultat attendu d'un protocole exprimental entretrois corps A, B et C. C'est seulement une fois ce principe pos qu'on peut dfinir la tempraturecomme reprsentant la classe d'quivalence de corps mutuellement en quilibre thermique. Pourdfinir prcisment et mesurer cette temprature, on choisit un corps de rfrence A (en gnralmodlis par un gaz parfait) partir duquel on dfinit la temprature de A, puis la temprature detout corps en quilibre thermique avec A. Ainsi, la notion de temprature devient une notion drived'un principe premier bas sur l'existence a priori d'une relation d'quivalence entre corps, postulesur des rsultats exprimentaux.

7 Relation d'ordreLa suite du paragraphe est rserve aux MPSIUn autre exemple de relation est donn par les relations permettant de classer les lments entre eux.Il s'agit des relations d'ordre.

a) Exemple et dfinition :Considrons les trois exemples suivants

i) dans :: l'infriorit x yii) dans ;; (E) l'inclusion A Biii) dans

- 21 -

ou bien x est avant y (et ventuellement, x = y). Du fait de l'antisymtrie et de la transitivit, il estimpossible d'avoir un cycle d'lments distincts vrifiant x1 BB x2, x2 CC x3, ..., xn1 DD xn,xn EE x1.

Voici un dernier exemple : dans l'ensemble des mots sur un alphabet (un mot est une suite finie delettres de l'alphabet), l'ordre alphabtique ou lexicographique est une relation d'ordre. Cette relationexiste dans de nombreux langages de programmation :

'ABBC' 'ABC' est vrai'ABBC' 'ABB' est faux

Remarque : si on dfinit une relation dans FF , GG ou HH , il n'en est pas de mme dans II . Pourquoi ?Les relations dfinies sur les ensembles de nombres prsentent une certaine compatibilit avec leslois + et dfinies sur ces ensembles. En particulier, on a :

a 0 et b 0 a + b 0 et ab 0.Si l'on avait, sur JJ , une relation du type i 0, alors, en effectuant le produit avec lui-mme, onobtiendrait 1 0, Puis en multipliant de nouveau par i, on aurait i 0, ce qui est contradictoireCela ne veut pas dire qu'il est impossible de dfinir une relation d'ordre sur KK , mais que cette relationne prsentera aucun caractre de compatibilit avec les lois + et .

Exercice : dfinir une relation d'ordre sur LL .

b) Ordre total, ordre partiel :On remarquera une diffrence entre d'une part la relation d'ingalit dans MM ou l'ordrelexicographique, et d'autre part, l'inclusion ou la relation de divisibilt.

Dans le premier cas, pour tout lment x et y, l'une des deux proprits x NN y ou y OO x estvrifie, ce qui n'est pas vrai dans le second cas. Par exemple, on n'a pas 2 | 3, ni 3 | 2. De mme{1,2} n'est pas inclus dans {3}, pas plus que {3} n'est inclus dans {1,2}. On parle respectivementd'ordre total et partiel.

Une relation d'ordre PP sur un ensemble E est dit d'ordre total si : x E, y E, x QQ y ou y RR x

Dans le cas contraire, SS est une relation d'ordre partiel : x E, y E, non(x TT y) et non(y UU x)

c) Majorant, minorant, maximum, minimum :q Soit E muni d'une relation d'ordre VV . Une partie A de E est minore par a (a est un minorant deA) si :

x A, a WW xA est majore par b (b est un majorant de A) si :

x A, x XX b

- 22 -

Exemple : [0,1] est major par 2, et minor par 1.

q Soit E muni d'une relation d'ordre YY . Une partie A de E admet un minimum a (ou plus petitlment) si :

a A et x A, a ZZ xa est donc un minorant de A, luimme lment de A.

A admet un maximum b (ou plus grand lment) si :b A et x A, x [[ b

b est donc un majorant de A, luimme lment de A.

Exemples :0 est le minimum de [0,1] (avec la relation usuelle) et 1 est son maximum.]0,1] n'admet pas de minimum, mais admet 1 comme maximum.]0,1[ n'admet ni maximum ni minimum.

est le minimum de \\ (E) pour la relation d'inclusion. E est le maximum.Si A est l'ensemble de tous les singletons de E, A n'admet ni minimum, ni maximum.

Pour la relation de divisibilit de ]] , 1 est le minimum, il n'y a pas de maximum.Fin de partie rserve aux MPSI

II : Structures algbriquesDbut de partie rserve aux MPSI

1 Loi de composition internea) Dfinition :Soit E un ensemble. On appelle loi de composition interne de E, note par exemple *, une oprationqui permet d'associer, deux lments quelconques de E a et b, un troisime lment not a * b.

Exemples : Les lois de compositions internes les plus courantes sont :+ dans ^^ , __ , `` , aa ou bb . dans les mmes ensembles. dans les mmes ensembles./ dans cc *, dd *, ou ee *.div (division entire) dans ff * ou gg *.o dans l'ensemble des applications de E dans E. dans l'ensemble E = hh () des parties d'un ensemble . dans l'ensemble des parties d'un ensemble. (produit vectoriel) dans l'espace euclidien orient de dimension 3

b) Associativit :Soit E un ensemble muni d'une loi de composition interne note *. Cette loi est dite associative si :

a E, b E, c E, (a * b) * c = a * (b * c)

- 23 -

L'intrt d'une telle notion est que les parenthses deviennent inutiles, la notation a * b * c valantindiffremment l'une ou l'autre des expressions. Les lois suivantes, dans les ensembles du paragrapheprcdent, sont associatives : +, , o, , . Les lois suivantes ne le sont pas : , /, div, .

On notera que l'absence de parenthses dans l'criture :7 5 1 = 1

signifie implicitement qu'une convention est adopte pour distinguer entre (7 5) 1 et 7 (5 1),la convention tant ici que le calcul se fait de gauche droite, mais rien ne nous aurait empch deprendre la convention inverse : faire les calculs de droite gauche. Ce qui aurait conduit au rsultat,qui nous parat faux : 7 5 1 = 3 !!Quant la notation a/b/c, elle est viter, aucune convention n'ayant t dfinie son sujet.

c) Commutativit :Soit E un ensemble muni d'une loi de composition interne note *. Cette loi est dite commutativesi :

a E, b E, a * b = b * a

L'intrt d'une telle notion est que l'ordre dans lequel les lments sont placs est indiffrent. Les loissuivantes, dans les ensembles du paragraphe prcdent, sont commutatives : +, , , . Les loissuivantes ne le sont pas : o (sauf si les fonctions sont dfinies sur un ensemble possdant un seullment), , /, div, .

Dans le cas d'une loi * commutative et associative, l'expression suivante possde un sens : *i I xi

o I est un ensemble fini d'indices. Par exemple, si I = {1,...,n}, l'expression prcdente est gale x1* x2 * ... * xn, l'ordre des termes tant indiffrent.

Exemples :

i=1

n

xi dsigne la somme des lments xi

i=1

n

xi dsigne le produit des lments xi

i I

Ai dsigne l'intersection des parties Ai

i I

Ai dsigne la runion des parties Ai

On notera, que, si I et J sont deux ensembles disjoints d'indices, on a : *i I J xi = *i I xi * *i J xi (i)

Quelle formule donner si I et J ne sont pas disjoints ? Si l'un des ensembles est vide ? O retrouveton des conventions analogues ? (penser 0! par exemple)

d) Elment neutre :Soit E muni d'une loi interne *. On dit que e est lment neutre de la loi * si :

- 24 -

a E, a * e = e * a = a

EXEMPLES :Le neutre de + est 0. Celui de est 1. Celui de o est Id. Celui de est (l'ensemble entier). Celuide est . et / n'ont pas d'lments neutres. Si * est associative, commutative, et admet unlment neutre e, alors la formule (i) nous conduit poser :

*i xi = e

Le neutre, s'il existe est unique. En effet, si e et e' sont deux neutres, on a :e * e' = e car e' est neutree * e' = e' car e est neutre

donc e = e'.

e) Elment symtrique :Soit E muni d'une loi *, et d'un lment neutre e. On appelle symtrique d'un lment x un lment x'tel que :

x * x' = x' * x = e

EXEMPLES :Le symtrique de x pour + est x (appel oppos de x).Le symtrique de x non nul pour est 1

x (appel inverse de x)

Le symtrique de f bijective pour o est f1 (appel rciproque)

Il n'y a en gnral pas de symtrique pour et .

et /, n'ayant aucune proprit particulire, apparaissent ici comme symtrisations des oprations +et .

Le symtrique, s'il existe, et si la loi est associative, est unique. En effet, si x' et x" sont deuxsymtriques de x, alors on a :

x' * x * x" = (x' * x) * x" = e * x" = x" = x' * (x * x") = x' * e = x'.

donc x' = x". Ce symtrique est souvent not x1.

EXERCICE : Si * est associative, commutative, admet un lment neutre e, et si tout lment admetun symtrique, alors on a, avec I et J quelconques :

*i I J xi = *i I xi * *i J xi * [ *i I J xi]1

2 Dfinition d'un groupeUn ensemble (G,*) est un groupe si :

i) G est non vide.ii) * est une loi de composition interne.iii) * est associative.iv) * admet un lment neutre e.

- 25 -

v) tout x de G admet un symtrique x'.

Si, en outre, * est commutative, le groupe est dit commutatif ou ablien (Niels Abel, mathmaticiennorvgien, 1802-1829).

On note parfois la loi du groupe multiplicativement (ab au lieu de a * b) ou additivement (a + b aulieu de a * b), mais la notation additive est rserve aux groupes commutatifs. a * a * ... * a est alorsnot an dans le cas multiplicatif ou na dans le cas additif.

Les axiomes des groupes permettent de simplifier les quations. Ainsi :a * x = a * y x = y (composer gauche par le symtrique de a)x * a = y * a x = y (composer droite par le symtrique de a)

EXEMPLE 1 :On peut citer le groupe des complexes de module 1, le groupe des racines nme complexes de l'unit,le groupe des similitudes directes du plan. Voici d'autres exemples.

EXEMPLE 2 :Voici quelques groupes deux lments :

{,Id} o est une symtrie, muni de la loi o.U2 = {+1,1} muni du produit (groupe des racines carres de l'unit, ou rgle des signes).ii

/2 jj = {0,1} muni de la loi +. Dans cet ensemble, on pose 1 + 1 = 0.{Croissance, Decroissance} muni de la loi o, et de la rgle donnant le sens de variation de la

compose de deux fonctions monotones.{true,false} (en programmation), muni de la loi xor (ou exclusif).

Tous ces groupes sont en fait identiques au suivant :Groupe deux lments {a,e}. La table d'opration de ce groupe est :

* a e

a e a

e a e

On a ncessairement a2 = e car si a2 = a, en simplifiant par a, on obtient a = e.

La correspondance se fait de la faon suivante : Groupe * a e {,Id} o Id {+1,1} 1 +1kk

/2 ll + 1 0 {Croissance, Dcroissance} o Decroissante Croissante {true,false} xor true false

Tous ces groupes sont dits isomorphes. Un thorme dmontr pour l'un d'entre eux l'est pour tous.Par exemple : la valeur d'un produit en fonction de la parit du nombre de a est a si ce

nombre est impair, e si ce nombre est pair. Ce rsultat se traduit de la faon suivante dans quelquessituations courantes :

2p = Id et 2p+1 = pour une symtrie Le produit d'un nombre pair de termes ngatifs est positif, le produit d'un nombre impair de

termes ngatifs est ngatif.

- 26 -

La compose d'un nombre pair de fonctions dcroissantes et d'un nombre quelconque defonctions croissantes est croissante ; La compose d'un nombre impair de fonctions dcroissantes etd'un nombre quelconque de fonctions croissantes est dcroissante.

EXEMPLE 3 :L'exemple suivant n'est pas un groupe :

* a e

a a a

e a e

On trouve cependant cette situation dans les cas suivants : {a, e} * a emm

/2 nn 0 1 {f paire, f impaire} o paire impaire {true, false} or true false {false, true} and false true {, } {, }

Ici, a est dit absorbant.

EXEMPLE 4 : Groupes trois lments :Quels sont les groupes trois lments ?Il n'y en a qu'un :

* a b ea b e ab e a be a b e

Pour le remplir, on remarque que, pour chaque lment y, l'application : x G yx G estbijective. Chaque lment du groupe apparat donc une fois et une seule dans chaque ligne y. Demme, l'application x xy est bijective, donc chaque lment du groupe apparat une fois et uneseule dans chaque colonne y. En outre ab = b est impossible car cela implique, en simplifiant par b,que a = e. De mme ab = a est impossible, donc ab = e, etc... Il est alors facile de complter letableau.

Tous les groupes trois lments sont donc isomorphes. En voici quelques exemples : G * a b e

oo 3 ={1,j,j2} j j2 1 o j est une racine cubique complexe de l'unit. pp 3 est le groupe des racines cubiques del'unit.

{1,,2} o 2 Id o est une rotation de 2pi/3

- 27 -

qq

/3 rr + 1 2 0 constitu des lments {0,1,2} o le calcul se fait modulo 3 (i.e. un multiple de 3 prs).

EXEMPLE 5 :Quels sont les groupes 4 lments ?On n'en trouve que deux :

* a b c ea e c b ab c a e bc b e a ce a b c e

* a b c ea e c b ab c e a bc b a e ce a b c e

Le premier n'est autre que ( ss /4 tt ,+), c'est dire le groupe des lments {0,1,2,3} o les calculs sefont modulo 4, ou encore le groupe uu 4 des racines quatrimes complexes de l'unit : G * c a b e vv 4 = {1,1,i,i} i 1 i 1 groupe des racines quatrime de l'unit.ww

/4 xx + 1 2 3 0

Le second est ( yy /2 zz )2 : G * a b c e ( {{ /2 || )2 + (1,0) (0,1) (1,1) (0,0)

Ce dernier groupe se trouve galement dans la situation suivante : considrons un matelas. Il peuttre laiss dans la position initiale (Id). On peut le tourner dans le sens de la longueur (). On peut letourner dans le sens de la largeur (). On peut lui faire un demitour plat (). {Id,,,} n'estautre que le second groupe.

EXEMPLE 6 :}}

n groupe des racines nme de l'unit dans ~~ , muni du produit

/n = {0, 1, 2, ..., n1} o les calculs se font modulo n.

3 Sous-groupeDfinition : Soit (G,*) un groupe et G' une partie de G. On dit que G' est un sousgroupe de G si,muni de la loi *, (G',*) est un groupe. Il suffit de vrifier les proprits suivantes :

q G' est non videq G' est stable pour * (ce qui signifie que * est une loi interne G') :

- 28 -

x G', y G', x * y G'q G' est stable par passage au symtrique : x G', x1 G'

Il est inutile de vrifier que G' dispose d'un lment neutre. En effet, si e est le neutre de G, onmontre que e est galement neutre de G'. En effet :

G' est non vide, donc il existe x lment de G'x G' donc x1 G'x G' et x1 G' donc x * x1 G' donc e G' x G, e * x = x * e = x donc ceci reste vrai a fortiori pour x dans G'

L'associativit tant vraie dans G est a fortiori vraie dans G'. Il en est de mme de l'ventuellecommutativit.

On montre aisment que l'intersection de deux ou plusieurs sousgroupes est luimme un sousgroupe.

EXEMPLE 1 : Dans le plan 2, considrons les applications qui au vecteur (x,y) associe le vecteur(x',y') = (ax + by, cx + dy), avec ad bc 0, ce qu'on note :

x'y' = a bc d xyL'ensemble de ces applications, muni de la loi de composition o, forme un groupe appel groupelinaire.L'ensemble des applications pour lesquelles ad bc = 1 en forme un sousgroupe.L'ensemble des applications orthogonales (rotations et symtries) forme un sousgroupe de ce sous-groupe appel groupe orthogonal.L'ensemble des rotations forme luimme un sousgroupe du groupe orthogonal.

EXEMPLE 2 : l'ensemble des nombres pairs forme un sousgroupe de ( ,+).

4 Anneaux et corpsUn anneau (A, +, ) est un ensemble non vide muni de deux lois + et vrifiant les propritssuivantes :

(A, +) est un groupe commutatif. Son neutre est not 0. est une loi associative possdant un lment neutre, et distributive par rapport l'addition,

i.e. : a, b, c, a (b + c) = ab + ac et (b + c) a = ba + ca

Le produit peut ne pas tre commutatif. Un exemple non commutatif est donn par l'anneau desmatrices carres.

0 est ncessairement absorbant. Soit x un lment quelconque. On a :x 0 = x (0 + 0) = x 0 + x 0

0 = x 0 en simplifiant par x 0De mme, 0 x = 0.

0 ne peut donc avoir de symtrique pour le produit. Si tout lment non nul admet un symtriquepour le produit, l'ensemble considr est un corps ; on rserve en gnral cette appellation au cas o,de plus, le produit est commutatif.

- 29 -

A' est un sous-anneau de A si A' est inclus dans A, si (A', +, ) est un anneau ; on convient galementque le neutre de A et de A' est identique.

EXEMPLES : ( , +, ) est un anneau. Les matrices carres munies de la somme et du produit des matrices

forment un anneau. ( , +, ) est un corps, sous-corps de , lui-mme sous-corps de . Les fractions rationnelles de

polynmes, de la forme PQ o P et Q sont des polynmes (avec Q 0) forment un corps. Considrons les quatres oprations lmentaires +, , et /, ainsi que la fonction . Partant des

rationnels, construisons de proche en proche de nouveaux nombres en itrant les oprations

prcdentes. On obtient ainsi par exemple les nombres 2 ou 1 + 52 ou

2 2 + 2 + 2 + 2. En continuant indfiniment, on forme un corps appel corps desnombres constructibles. On peut montrer que, dans le plan, les points coordonnesconstructibles dans un repre orthonorm sont prcisment les points constructibles la rgle etau compas partir de l'origine du repre et des vecteurs de base. (Cela rsulte du fait quel'intersection d'un cercle et d'une droite conduit une quation du second degr, dont la rsolution

ne fait appel qu'aux oprations +, , , / et ). On a montr au XIXme que les nombres pi, 3 2ou cos(pi9) ne sont pas constructibles, rendant impossible la rsolution de problmes millnairesposs pas les Grecs Anciens, celui de la quadrature du cercle, de la duplication du cube ou de latrisection de l'angle.

Considrons l'ensemble 4 = {0, 1, , } avec les lois commutatives + et dfinies comme suit :0 est le neutre de la somme1 est le neutre du produit2 = = 1 2 = 1 + = 1 + = + = 1

Ces oprations donnent 4 une structure de corps. 4 est le seul corps quatre lments. En cequi concerne la somme, sa structure de groupe est isomorphe celle de /2 /2 avecl'isomorphisme suivant :

4 /2 /2 0 (0,0)1 (1,1) (0,1) (1,0)

mais il n'y a pas d'isomorphisme pour le produit. 4 est un corps, ce que n'est pas /2 /2 (On a = 1 mais (0,1) (1,0) = (0,0) et non (1,1)).

Fin de partie rserve aux MPSI

L'annexe qui suit ne fait pas partie du programme de mathmatiques de CPGE. Elle est destine des tudiants (plutt de deuxime anne ou au-del) qui s'intresseraient aux fondements desmathmatiques.

- 30 -

Annexe : les axiomes

Qu'est-ce qu'un axiome ?D'Alembert crit, dans son Encyclopdie (1788) :

Axiome : En Mathmatiques, on appelle axiomes des propositions videntes par elles-mmes, et qui n'ont pas besoin de dmonstrations. Telles sont les propositionssuivantes : le tout est plus grand que la partie ; si deux grandeurs gales on ajoutedes grandeurs gales, les sommes seront gales ; si deux figures tant appliques l'unesur l'autre se couvrent parfaitement, ces deux figures sont gales en tout.Thorme : c'est une proposition qui nonce et dmontre une vrit.

Notre conception moderne des axiomes ne correspond plus des notions dclares videntes parelles-mmes. On fait actuellement reposer une thorie mathmatique sur des notions primitives (nondfinies) et les axiomes ne servent qu' dcrire les rgles d'utilisation de ces notions primitives. Voicides exemples modernes d'axiomes et de notions primitives :

i) La notion d'ensemble et d'appartenance est une notion primitive. On ne cherchera dfinirni l'une ni l'autre.

ii) Frege, en 1893, avait propos comme axiome le suivant : tant un prdicat quelconque,il existe un ensemble A tel que, pour tout x, x appartient A si et seulement si (x) est vrai. Russel,en 1902, proposa de prendre comme prdicat : (x) x x. D'aprs Frege, il existe alors unensemble A tel que :

x, x A x xCette quivalence est vraie en particulier lorsque x = A, ce qui donne :

A A A Ace qui contradictoire. Cet exemple prouve qu'on ne peut pas prendre n'importe quoi pour axiome, enparticulier en ce qui concerne la construction des ensembles.

Voici quelques axiomes actuellement en vigueur :q La runion d'une famille d'ensemble (indice par un ensemble) est un ensemble.q La famille constitue des parties d'un ensemble est un ensemble.q Il existe un ensemble infiniq Le principe de rcurrence dans q Le 5me postulat d'Euclide en gomtrie euclidienne : par un point donn, il passe une parallle une droite donne et une seule. Le rejet de cet axiome conduit d'autres types de gomtries.q L'existence de la borne suprieure dans

Un axiome curieux, l'axiome du choix :Considrons la proposition suivante :Soit f une application injective de E dans F. Alors il existe une application surjective g de F dans Etelle que g o f = Id.

Dmonstration :q Soit a un lment quelconque de E. On pose :

i) si y appartient f(E), g(y) = x o x est l'unique lment tel que y = f(x).ii) si y n'appartient pas f(E), on pose g(y) = a.

On alors g surjective et g o f = Id

Considrons maintenant la proposition suivante :

- 31 -

Soit f une application surjective de E dans F. Alors il existe une application injective g de F dans Etelle que f o g = Id.

Dmonstration :q Pour tout y de F, f1({y}) est non vide. Soit g(y) un lment de cette partie. Alors g est injective etf o g = Id

Il y a une diffrence fondamentale entre ces deux dmonstrations. La premire ne fait appel qu'auchoix arbitraire d'un unique lment a, alors que la seconde fait appel au choix simultan et arbitraired'un nombre quelconque et ventuellement infini d'lments g(y). La possibilit d'un tel choix a tvivement contest au dbut du XXme sicle et ncessite un axiome : l'axiome du choix. Ce dernierest galement li la question de munir un ensemble d'un "bon ordre" ; un ensemble est dit bienordonn si toute partie non vide admet un plus petit lment. Un exemple typique d'ensemble bienordonn est . Par contre, n'est pas bien ordonn avec l'ordre usuel. Cantor pensait que toutensemble pouvait tre muni d'un bon ordre, et la ncessit d'une dmonstration s'est pos. On peut sedemander en effet comment il peut tre possible de munir par exemple d'un bon ordre. Au dbutdu sicle, on pensa avoir montr l'impossibilit de munir d'un bon ordre. Mais Zermelo prouva lecontraire en utilisant pour la premire fois ce qui allait devenir l'axiome du choix :Soit (Ai)iI une famille d'ensembles non vides, indice par un ensemble I quelconque et soit A larunion des Ai. Alors il existe une application f de I dans A telle que :

i I, f(i) Ai.La fonction f permet de choisir un lment not f(i) dans chaque Ai. D'autres formulationsquivalentes sont possibles. Par exemple, le produit

i I Ai est non vide.

On montre que cet axiome permet de munir d'un bon ordre, sans qu'on puisse cependantl'expliciter, et ceci choqua bon nombre de mathmaticiens qui le rejetrent. Cependant, d'autresthormes, dont les noncs paraissaient vraisemblables la communaut mathmatique ncessitentl'axiome du choix. En voici quelques-uns :q Soit E et F deux ensembles. Alors ou bien il existe une injection de E dans F ou bien il existe uneinjection de F dans E. (Thorme de Cantor, quivalent l'axiome du choix)q Soit E un espace vectoriel. Alors il existe une base sur E.q Tout ensemble inductif admet un lment maximal. (Un ensemble est inductif si toute partietotalement ordonne est majore). (Thorme de Zorn, quivalent l'axiome du choix).

Certains rsultats cependant sont prouvs au moyen de l'axiome du choix et fortement contraires l'intuition :q Lebesgue a dvelopp une thorie de l'intgration trs puissante. Toutes les fonctions usuelles sontmesurables au sens de Lebesgue. Les seuls exemples non mesurables qui ont t dcouvertsncessitent l'axiome du choix.q La sphre unit peut tre dcompose en quatre parties isomtriques A, B, C, D avec D galementisomtrique A B. (D est donc la fois le quart et la moiti de la sphre). (Thorme deHausdorf, extrmement choquant).q Dans le mme ordre d'ide, deux ensembles borns quelconques de 3 d'intrieur non videpeuvent tre partitionns en deux familles finies respectives (Ai) et (Bi) de faon que Ai soitisomtrique Bi. (Thorme de Banach-Tarski).

- 32 -

q Il existe des fonctions de dans telle que f(x + y) = f(x) + f(y), avec f diffrente des fonctionslinaires ax. Cependant aucune de ces fonctions ne peut tre explicite.

La nature de l'axiome du choix est donc complexe. Affirmant l'existence d'un objet, il ne peutcependant dfinir explicitement cet objet. Bien plus, une telle explicitation est impossible puisque lerejet de l'axiome supprimerait la seule possibilit de valider son existence.

Ces questions sont lies la nature de la notion de l'existence en mathmatiques. Il y a deux notionsdiffrentes, l'une est l'existence explicite, fournissant le moyen de construire l'objet (par exemple,tant donns deux entiers, on peut dterminer explicitement le plus petit multiple commun de cesdeux entiers), l'autre est une existence purement formelle ne fournissant aucun moyen de dfinirexplicitement l'objet (des exemples ont t donns prcdemment). Les mathmatiques usuelles nefont aucune distinction entre ces deux notions d'existence, ce qu'on peut juger regrettable carl'existence formelle a une utilit et une efficacit bien moins grande que l'existence explicite. Avouonscependant que les branches des mathmatiques cherchant apporter une distinction entre ces deuxnotions d'existence (logique intuitionniste, analyse constructive) sont difficiles aborder.

On peut nanmoins reconnatre cette qualit l'existence formelle : elle prouve qu'il est vain dedpenser ces efforts montrer l'inexistence de l'objet considr. Considrons par exemple uneproprit donne sur les entiers (par exemple, celle d'tre un nombre parfait [gal la somme de sesdiviseurs autres que lui-mme] impair et posons-nous la question de savoir si cette proprit estvrifie par au moins un entier. Il y a alors trois possibilits.

i) Aucun entier ne vrifie la propritii) Il existe au moins un entier vrifiant la proprit et on peut donner sa valeur (existence

explicite)iii) Il existe au moins un entier vrifiant la proprit mais on ne peut donner sa valeur

(existence formelle), soit parce que cette valeur est trop grande pour pouvoir tre calcule, soit parcequ'on ignore un procd de calcul de cette valeur, soit mme parce que cette existence repose sur unaxiome. Si on se trouve dans ce cas, cela montre qu'il est inutile de chercher prouver i).u

Documents

Ensemble