Méthodologie des mathématiques L1 — Université Paris-Est

Méthodologie des mathématiques

L1 — Université Paris-Est Marne-la-Vallée

2015 – 2016

Magdalena KOBYLANSKIMiguel MARTINEZ

2

Organisation du travail et contrôledes connaissances

Apprentissage du coursComment apprendre le cours ?

1. Relire : relire rapidement le cours dans ses trois versions : les notes manuscrites prises en amphi,la version imprimée du cours projeté, le polycopié.

2. Synthèse : être capable de dire quelles sont les notions abordées en cours en 30 secondes chrono.3. Repérage : quels sont les définitions, les propositions et théorèmes.4. Comprendre : quels sont les enjeux des notions, théorèmes et propositions abordés. Pouvoir en

parler en moins de 2 minutes en termes non techniques. Tout lien, toute idée de lien même farfelueest bienvenue.

5. Apprendre : savoir par coeur les définitions, à la virgule près. Ici, pas de place pour l’à peu près.6. Relire encore : maintenant on rentre dans la technique et on est prêt pour la relecture fouillée

des démonstrations...7. Repérer encore : repérer la structure de la démonstration, les notions et les propositions utilisées,

les idées principales, la structure logique, et une fois encore faire des liens : pourquoi cette structurede preuve, est-ce qu’elle fait penser à une preuve, où sont les di�cultés techniques...

8. Apprendre encore : refaire les démonstrations un stylo à la main. Imaginez que c’est vous leprofesseur et que vous êtes en train d’expliquer la démonstration.

Séances de TDComment préparer la séance de Travaux Dirigés ?1. Apprendre le cours. Chaque chargé de TD est libre de vous interroger à tout moment, à l’oral

ou par écrit, sur le cours. Ces interrogations peuvent être notées et cette note peut rentrer dansle contrôle continu. Les définitions indiquées doivent en particulier être connues sur le bout desdoigts.

2. Exercices Wims. Des exercices interactifs simples sont proposées et si vous n’avez pas réussi àfaire ceux qui sont demandés, le chargé de TD a le droit de ne pas vous accepter.

3. Exercices du polycopié. Certains exercices du polycopié doivent être préparés et rédigés à l’écrit.Les exercices ⌥ sont des exercices faciles, qui peuvent être fait sans aide.Les exercices F sont à traiter obligatoirement en TD.

3

4

Exercices WimsPour chaque chapitre du cours, des exercices Wims vous sont proposés sur la plate-forme d’enseigne-

ment en ligne. Ils sont répartis en 3 niveaux de di�culté.

– Ceux de niveau basique sont des exercices d’application directe du cours. Vous devez les fairejuste après le cours en amphi, et avant le TD associé. Ils vous aideront à apprendre certainsconcepts de base du cours.

– Ceux de niveau intermédiaire demandent plus de savoir-faire et de réflexion et nécessitent souventde prendre un papier et un crayon. Ils sont associés à des exercices de la feuille de TD marqués W .Ces exercices sont à faire après avoir vu les exercices correspondants en TD. Cela vous permettrade vérifier que vous les avez bien assimilés.

Contrôle des connaissancesLes connaissances sont contrôlées lors des partiels du lundi matin. Le programme des contrôles est

communiqué la semaine qui précède. Ils portent à la fois sur les cours, les TD et les exercices Wims.— Toutes les définitions, les propositions, et tous les théorèmes sont à connaître.— Les démonstrations des énoncés F sont également exigibles.

Par ailleurs chaque chargé de TD est libre d’organiser des interrogations écrites.

Chapitre 1

Ensembles

“Personne ne pourra nous chasser du paradis que Cantor a créé pour nous.”Hilbert – 1925

Le langage ensembliste est depuis Cantor celui utilisé par les mathématiciens. Aujourd’hui, toute lathéorie mathématique est construite à partir de la théorie des ensembles. Ces derniers constituent donc lanotion première des mathématiques : tous les autres objets mathématiques sont définis (ou peuvent l’être)à partir des ensembles, de quelques axiomes, et des règles de la logique.

Nous utilisons la théorie na’ive des ensembles.

1.1 DéfinitionsEnsemble

Un ensemble est une collection d’objets tous définis et tous distincts qui peuvent être des objetsbien réels (par exemple les étudiants de cet amphi) ou des objets abstraits (comme des nombres, desfonctions...). En général, on note les ensembles avec une majuscule A, B,...

Les objets constituants un ensemble sont appelés les éléments, on les note en général à l’aide d’uneminuscule a, x... et on écrit : “a œ A” pour dire que “a est un élément de l’ensemble A”.

Un ensemble qui ne contient qu’un élément, disons a, est le singleton {a}. C’est un objet mathé-matique qui est di�érent de l’élément a.

Description d’un ensemble – Afin de décrire un ensemble on utilise des accolades. Par exemple{1, 2} se lit “l’ensemble dont les éléments sont 1 et 2”. C’est le même ensemble que {2, 1}, ou encore quel’ensemble {1, 1, 2}.

— Les ensembles peuvent être décrits en extension. Dans ce cas entre les accolades on énumèretous les éléments. C’est possible quand les éléments de l’ensemble ne sont pas trop nombreux. Parexemple on considère : A = {0, 2, 4, 6}.

— Ils peuvent être décrits aussi en compréhension. Après l’accolade, on se donne une variable quiva décrire les éléments de l’ensemble, puis on indique les propriétés de cette variable.L’ensemble Aprécédent peut ainsi s’écrire {n, n est un entier pair et n Æ 6}.

— Enfin, les ensembles peuvent être représentés sous forme paramétrique. En notant I = {0, 1, 2, 3},on peut ainsi écrire A = {2n, n œ I}. Plus généralement, si I est un ensemble et si pour tout i œ I,ai est un élément d’un ensemble E, alors l’ensemble A = {ai, i œ I} est un sous-ensemble de Eparamétré par l’ensemble I.

Question 1.1. Combien d’éléments possède un ensemble A = {ai, i œ I} paramétré par I = {1, 2, 3, 4, 5} ?Un ensemble peut-il toujours être paramétré ?

5

6 CHAPITRE 1. ENSEMBLES

Variable de description – Notons que l’ensemble {n œ N, n Æ 5} est le même que l’ensemble{m œ N, m Æ 5}. On dit que la variable qui décrit l’ensemble est liée ou muette. En informatiquecette notion correspond à la notion de variable locale. Sinon on parle de variable libre ou parlante et eninformatique de variable globale.

Pour éviter toute confusion, il conviendrait de choisir pour chaque variable, même muette, une lettreou un symbole di�érent. En pratique, on ne respecte pas toujours cette règle, car les symboles dont ondispose ne sont pas bien nombreux.

Les ensembles de nombres sont N l’ensemble des entiers naturels, Z l’ensemble des entiers relatifs, Ql’ensemble des rationnels, R l’ensemble des réels, C l’ensemble des complexes. L’ensemble des nombrespairs est noté 2N, il est défini de manière paramétrique par {2k, k œ N}. Plus généralement, l’ensemble desmultiples de l’entier n s’écrit nN = {nk, k œ N} : dans cette écriture, la variable k est liée, et la variable nest libre. L’ensemble des entiers impairs ne dispose pas de notation particulière, on montre qu’il peut êtreparamétré comme {2n + 1, n œ N}.

L’ensemble vide – Si on considère l’ensemble A = {n œ 2N, n > 2, n premier}, on s’aperçoit que Ane contient aucun élément. On dit que A est l’ensemble vide, que l’on note ÿ.

Partie d’un ensemble, inclusion – Soit A et B deux ensembles. On dit que B est une partie ou unsous-ensemble de A si et seulement si tous les éléments de B sont des éléments de A. On note alors B µ Aet on dit aussi B est inclus dans A.

Par convention ÿ µ A, pour tout ensemble A.

Exemple 1.1. Montrer l’inclusion suivante : 6N µ 3N.

L’ensemble des parties d’un ensemble – Soit E un ensemble. L’ensemble des parties d’un ensemblenoté canoniquement P(E) est l’ensemble constitué par tous les sous-ensembles de E. Cette notation estcommunément admise.

On peut considérer une partie R de P(E). C’est aussi un ensemble d’ensembles. Les éléments de Rsont donc des parties de E. On désigne souvent ce genre d’ensembles avec des majuscules cursives.

1.2 Les opérations sur les ensemblesEgalité d’ensembles – Deux ensembles A et B sont égaux, et on note A = B si et seulement si chaqueélément de A est aussi dans B et chaque élément de B est dans A. Autrement dit si et seulement si A µ Bet B µ A.

Exemple 1.2. Montrer que {2p + 4q, p œ N, q œ N} = 2N.

L’union fi – L’union A fi B, de deux ensembles A et B, est l’ensemble

A fi B = {x, x œ A ou x œ B}.

Nota Bene : le “ou” du mathématicien est le “ou” inclusif. Ainsi x œ AfiB signifie que x est soit uniquementdans A, soit uniquement dans B, soit encore dans les deux à la fois.L’union est associative : pour tous ensembles A, B, C, on a (AfiB)fiC = Afi(B fiC) et commutative :pour tous ensembles A, B on a A fi B = B fi A.

Soit R un ensemble de parties de E. La réunion des parties de R notéet

AœR A est l’ensemble deséléments x appartenant à au moins l’un des A dans R. Autrement dit

€

AœRA = {x, il existe A œ R vérifiant x œ A} .

Lorsque R est donné comme un ensemble indexé par un ensemble I, R = {Ai, i œ I}, l’union ci-dessuss’écrit €

iœI

Ai = {x, il existe un indice i œ I vérifiant x œ Ai} .

1.2. LES OPÉRATIONS SUR LES ENSEMBLES 7

Remarque 1.1. La variable i est liée par l’opérateur fi, on dit aussi qu’elle est muette : le fait de remplaceri par j ne change rien : fiiœIAi = fijœIAj .

L’intersection fl – L’intersection A fl B de deux ensembles A et B est l’ensemble A fl B = {x, x œA et x œ B}.L’intersection est associative : pour tous A, B, C, (A fl B) fl C = A fl (B fl C) et commutative : pour tousA, B, A fl B = B fl A.

Si R un ensemble de parties de E. On noteu

AœR A et l’ensemble des éléments qui sont dans tous lesA œ R à la fois : ‹

AœRA = {x, pour tout A œ R, x œ A}.

Si R = {Ai, i œ I} est un ensemble de parties indicées par l’ensemble I, l’intersection précédente s’écritalors ‹

iœI

Ai = {x, pour tout i œ I, x œ Ai}.

Remarque 1.2. A nouveau, tout comme pour l’union, la variable i est liée par l’opérateur fl. Le fait deremplacer i par j ne change rien : fliœIAi = fljœIAj .

Exemple 1.3. Montrer que {2n, n œ N} fl {2m + 1, m œ N} = ÿ.Montrer que 6N fl 4N = 12N.

Di�érence d’ensembles, complémentaire – La di�érence A \ B de deux ensembles (qui se lit Amoins B) est l’ensemble A \ B = {x, x œ A et x /œ B}.

Lorsque A est une partie de X, l’ensemble X \ A s’appelle le complémentaire de A dans X. Il estaussi noté {XA. S’il n’ y a pas d’ambigu’ité sur l’ensemble X, le complémentaire de A est assi noté {Aou Ac. (On évitera la notation A réservée, en général, à une autre notion mathématique).

Proposition 1.1. Soit X un ensemble et A et B des parties de X.a. (Ac)c = A, b. (A fi B)c = Ac fl Bc, c. (A fl B)c = Ac fi Bc.

Exemple 1.4. Montrer que l’ensemble I des nombres impairs, défini comme le complémentaire dans Ndes entiers pairs c’est-à-dire I := (2N)c = N \ 2N est égal à l’ensemble {2n + 1, n œ N}.

Di�érence symétrique � – La di�érence symétrique A�B de deux ensembles A et B est l’ensembleA�B = (A \ B) fi (B \ A) = (A fi B) \ (A fl B). Il correspond au “ou” exclusif.La di�érence symétrique est associative : pour tous A, B, C, (A�B)�C = A�(B�C) et commutative :pour tous A, B, A�B = B�A.

Recouvrement d’un ensemble – Soit X un ensemble. On dit qu’un ensemble R de parties de X estun recouvrement de X si X =

tAœR A.

Partition d’un ensemble – Soit X un ensemble non vide. Un recouvrement R de X est une partitions’il est constitues de parties non vides de X deux à deux disjointes (si A et B sont dans R avec A ”= B,alors A fl B = ÿ) .

Le produit cartésien ◊ – Soient A et B deux ensembles non vides. Le produit cartésien de A et deB est l’ensemble

A ◊ B = {(a, b), a œ A, b œ B}.

Un élément (a, b) de A ◊ B est appelé couple. L’ordre des coordonnées dans ce couple est fondamental !On note A2 le produit cartésien A ◊ A. Par exemple on utilise souvent la notation R2 pour l’ensemble

R ◊ R.Question : Ecrire en extension l’ensemble {1, 2} ◊ {0, 1}.

Plus généralement soient n œ N et A1, ...,An des ensembles non vides, le produit cartésien de A1, ...,An est l’ensemble A1 ◊ · · · ◊ An = {(a1, ..., an), a1 œ A1, ..., an œ An}. Un élément (a1, ..., an) est appelén-uplet.


Le produit cartésien a été inventé par René Descartes (1596 – 1650), alors qu’il avait 25 ans. Il lerapporte dans ses mémoires.

“Le 10 novembre 1619 rempli d’enthousiasme je trouvai le fondement d’une scienceadmirable...” – René Descartes, Olympiques, fragments

Il raconte alors comment il s’enferme dans son poêle et conçoit sa méthode. La légende raconteque, alité, il regarde le plafond au plâtre fissuré et imagine un système de coordonnées, permettantde décrire lignes, courbes et figures géométriques par des couples de nombres arithmétiques, dontil ne reste qu’à analyser les propriétés.

1.3 ExercicesExercice 1.1. ⌥ On considère les sous-ensembles de N suivants :

A = {n œ Nú, n Æ 7}, B = {n œ N, n /œ 2N, n Æ 7}, C = {n œ 2Nú, n Æ 7}, D = {n œ 3Nú, n Æ 7}.

1. Ecrire ces ensembles en extension.2. Déterminer B fl D, C fl D .3. Déterminer B fi C, C fi D. Une des ces réunions est-elle disjointe ?4. Déterminer C�D.5. Déterminer {AB, {AC et {AD.

Exercice 1.2. Les notations ?, {?} désignent-elles le même ensemble ? Dans chaque cas, préciser si ?est un élément ou une partie de l’ensemble considéré.

Exercice 1.3. Soit Q l’ensemble des quadrilatères du plan. On considère les sous-ensembles suivants :A l’ensemble des quadrilatères ayant un angle droit P l’ensemble des parallélogrammesL l’ensemble des losanges T l’ensemble des trapèzesR l’ensemble des rectangles C l’ensemble des carrés.

1. Quelles sont les relations d’inclusion existant entre ces ensembles.2. Déterminer A fl L, A fl P , L fl R.

Exercice 1.4. ⌥ On considère les ensembles suivants :A = {1, 2, 5} , B = {{1, 2}, 5} , C = {{1, 2, 5}} , D = {?, 1, 2, 5} , E = {5, 1, 2} ,F = {{1, 2}, {5}} , G = {{1, 2}, {5}, 5} , H = {5, {1}, {2}} .1. Quelles sont les relations d’égalité ou d’inclusion existant entre ces ensembles ?2. Donner le nombre d’éléments de chacun de ces ensembles.3. Déterminer A fl B, G fi H, E\G.4. Quel est le complémentaire de A dans D ?

Exercice 1.5. W Description d’ensembles avec les opérations ensemblistes.

Soient E un ensemble et A, B et C trois sous-ensembles de E. Exprimer les ensembles suivants en utilisantles opérations ensemblistes.

1. L’ensemble des éléments de E qui appartiennent à A ou à B et qui n’appartiennent pas à C.2. L’ensemble des éléments de E qui n’appartiennent ni à A ni à B et qui appartiennent à C.

Exercice 1.6. Soit A et B deux sous-ensembles de �. Montrer que A et B sont disjoints si et seulementsi Ac fi Bc = �.

Exercice 1.7. F Soit A, B et C trois sous-ensembles de �. Montrer les formules suivantes :1. A fl (B fi C) = (A fl B) fi (A fl C),2. A fi (B fl C) = (A fi B) fl (A fi C),

1.3. EXERCICES 9

3. (A fi B) \ C = (A \ C) fi (B \ C),4. (A fl B) \ C = (A \ C) fl (B \ C) = (A \ C) fl B = (B \ C) fl A,

Exercice 1.8. Soit A, B, C deux sous-ensembles de �. Justifier les formules suivantes à l’aide de dessins,proposer des étapes de démonstration :

1. A�B = B�A, Ac�Bc = A�B,2. (A�B)�C = A�(B�C),3. (A�B)c = Ac�B = A�Bc,4. Déterminer A�Ac, et A��.

Exercice 1.9. Soit A et B deux sous-ensembles de �.1. Exprimer les ensembles A fl B, A fi B, A\B, en utilisant uniquement l’intersection et le complé-

mentaire.2. Même problème en utilisant uniquement la réunion et le complémentaire.3. Même problème en utilisant uniquement la di�érence et le complémentaire.

Exercice 1.10. Donner les éléments de P({0, 1, 2}), de P(P({1})).

Exercice 1.11. Soit A et B deux sous-ensembles de �, tels que A ”µ B, B ”µ A, A fi B ”= �, A fl B ”= ?.Ecrire une partition de � formée de quatre éléments construits à partir de A et B et des opérationsélémentaires sur les ensembles.

Exercice 1.12. ⌥ Trouver toutes les partitions de {1, 2, 3}.

Exercice 1.13. ⌥ Représenter graphiquement et écrire en extension les ensembles{0, 2} ◊ {1, 2, 3}, {0, 2} ◊ {1, 2, 3} \ {1, 2, 3} ◊ {0, 2} et ({0, 2} ◊ {1, 2, 3})�({1, 2, 3} ◊ {0, 2}).

Exercice 1.14. W Représentation graphique d’ensembles de couples d’entiers.

Représenter graphiquement les ensembles suivants.1. E = {(i, j) œ N2, 1 Æ i Æ 12, 1 Æ j Æ 10, ≠4 < i + j < 12}.

2. F = {(i, j) œ N2, 1 Æ i Æ 9, 1 Æ j Æ 7, ≠4 < i ≠ j < 11}.

Exercice 1.15. F1. Représenter graphiquement les ensembles suivants.

(a) A1 = {(p, q) œ {0, ..., n}2, p + q = n},B1 = {(p, q) œ {1, ..., 10}2, p ≠ q = 5},C1 = {(p, q) œ {≠5, ..., 5}2, p + q = 2}.

(b) A2 = {(p, q) œ {0, ..., n}2, p + q Æ n},B2 = {(p, q) œ {1, ..., 10}2, p ≠ q Ø 5},C2 = {(p, q) œ {≠5, ..., 5}2, p + q Ø 2, p ≠ q Æ 1}.

(c) A3 = {(x, y) œ [0, 1]2, x + y Æ 1},B3 = {(x, y) œ [1, 5] ◊ [≠5, 5], |x ≠ y| Ø 5},C3 = {(x, y) œ R2, x + y Ø 2, x ≠ 2y Æ 1}.

2. Écrire les trois premiers ensembles sous forme paramétrique avec un seul paramètre.


Chapitre 2

Applications

2.1 DéfinitionSoient E et F deux ensembles. Une application f de E dans F notée f : E æ F associe à chaque

élément de E un et un seul élément de F . E est l’ensemble de départ et F l’ensemble d’arrivée. Six œ E on note f(x) l’unique élément de F en relation avec x par f . On dit que f(x) est l’image de x, etque x est un antécédent de y = f(x).

Remarque – La notion de fonction, telle qu’elle est définie plus haut, est une notion première. Ornous avons dit que la seule notion première dans la construction mathématique est la notion d’ensemble.Sauriez-vous définir la notion de fonction à l’aide des ensembles ?

On peut remarquer que la donnée de f : E æ F revient à la même chose que la donnée de songraphe {(x, f(x)), x œ E} qui est une partie bien particulière du produit cartésien E ◊ F . Il su�t alors decaractériser les parties de E ◊ F qui sont des graphes d’applications.

Notations – On écrit : f : E æ F ; x ‘æ y. Dans ce cas la variable y dépend de la variable libre x parl’application f . On écrit aussi f : E æ F x ‘æ f(x).

Exemple 2.1. Il arrive que f soit donnée par une formule (par exemple f1 : N æ N x ‘æ x2), ou pardeux formules f2 : Z æ Z définie par f2(x) = x2 si x Ø 0, et f2(x) = ≠x2 sinon.

Bien entendu, lorsque les ensembles de départ et d’arrivée changent, l’application n’est plus la même.Ainsi f3 : Z æ Z x ‘æ x2 est une application di�érente de l’application f1.

Exemples – Les exemples qui suivent définissent des applications bien connues et les notations qui lesdésignent sont largement admises par la communauté mathématique.

1. L’application identité d’un ensemble E, notée canoniquement IdE est l’application

IdE : E æ E, x ‘æ x.

2. Si E est un ensemble et A une partie de E l’application indicatrice de A, est définie par

1A : E æ {0, 1} x ‘æ;

1 si x œ A0 sinon .

11

12 CHAPITRE 2. APPLICATIONS

3. Si E est un ensemble et a, b sont deux éléments de E, la transposition de a et b est l’applicationtab : E æ E définie par

tab(x) =

Y_]

_[

b si x = a,

a si x = b,

x si x /œ {a, b}.

Question 2.1. Un élément x de E peut-il posséder plusieurs images par f ? Un élément y de F possède-t-ilnécessairement un antécédent par f ? Peut-il en posséder plusieurs ?

L’ensemble des applications de E dans F – On note F E l’ensemble des applications de E dans F .On a donc F E = {f, f : E æ F}.

2.2 Opération sur les applicationsEgalité d’application – On dit que deux application f : E æ F et f Õ : EÕ æ F Õ sont égales si ellesont même ensemble de départ et d’arrivée (E = EÕ et F = F Õ) et si, pour tout x œ E, f(x) = f Õ(x).

Exemple 2.2. Soit E un ensemble et a, b des éléments de E. Montrer que tab = tba et que IdE = taa.

Restriction – Soit f : E æ F une application et A une partie non vide de E. La restriction de f à A,notée f|A est l’application de A dans F qui à x œ A associe f(x) : f|A : A æ E x ‘æ f(x).

Exemple 2.3. On considère les applications f1, f2, f3 définies dans l’exemple 2.1. A-t-on f3|N = f1 ?A-t-on f2|N = f1|N ?

Corestriction – Soit f : E æ F une application et B une partie non vide de F . La corestriction de fà B, notée f |B ne peut être définie que si f(E) µ B. C’est alors l’application de E dans B qui à x œ Eassocie f(x) : f |B : E æ B x ‘æ f(x).

Exemple 2.4. On considère les applications de l’exemple 2.1. Montrer que f2|N|N = f1.

Prolongement – Soit f : E æ F une application, EÕ un ensemble contenant E et F Õ un ensemblecontenant F . Une application g : EÕ æ F Õ est un prolongement de f à EÕ, si l’on a g

|F|E = f . Notons que

si A µ E µ EÕ, il y a une seule restriction de f à A mais de nombreux prolongements de f à EÕ.

Exemple 2.5. On considère les applications de l’exemple 2.1. Construire un prolongement de f1 de Zdans Z qui soit di�érent de f2 et de f3.

Composition d’applications – Soient E, F, G trois ensembles, et f : E æ F , g : F æ G. La composéede f et de g est l’application g ¶ f : E æ G qui à tout x de E associe g ¶ f(x) = g(f(x)).

Proposition 2.1. (La composition d’application est associative). Soient E, F, G, H des ensembles etf : E æ F , g : F æ G, h : G æ H des applications. Alors (h ¶ g) ¶ f = h ¶ (g ¶ f).

Question 2.2. Soit E un ensemble possédant au moins 3 éléments distincts a, b, c. Déterminer tab ¶ tbc(c)et tbc ¶ tab(c). La loi de composition de EE est-elle commutative ?Montrer que pour toute application f : E æ E on a f ¶ IdE = IdE ¶ f = f .

2.3 Image directe, image réciproqueSoient E et F deux ensembles et f : E æ F . Soient A une partie de E et B une partie de F .

L’image directe de A par f notée f(A) est l’ensemble des images par f des éléments de A c’est-à-dire :

f(A) = {f(a), a œ A} = {y, il existe a œ A tel que y = f(a)}.

2.4. INJECTIONS, SURJECTIONS, BIJECTIONS 13

L’image réciproque de B par f notée f{≠1}(B) est l’ensemble des antécédents par f des éléments deB :

f{≠1}(B) = {x œ E, f(x) œ B}.

Question 2.3. Si A possède un seul élément, f(A) peut-elle être vide ? Posséder deux éléments ou plus ?Si A possède deux éléments, combien f(A) peut-elle posséder d’éléments ? Si B possède un seul élément,f{≠1}(B) peut-elle être vide ? Posséder deux éléments ou plus ? f{≠1} peut-elle être vue comme uneapplication ? Si oui préciser son ensemble de départ et d’arrivée.

Proposition 2.2. F Soit f : E æ F une application1. pour toutes parties A, B de E,

a. Si A µ B, alors f(A) µ f(B), b. f(A fi B) = f(A) fi f(B), c. f(A fl B) µ f(A) fl f(B),2. pour toutes parties A, B de F ,

a. f{≠1}(A fi B) = f{≠1}(A) fi f{≠1}(B), b. f{≠1}(A fl B) = f{≠1}(A) fl f{≠1}(B),c. f{≠1}(Ac) = (f{≠1}(A))c.

2.4 Injections, surjections, bijectionsSoient E et F des ensembles et f : E æ F une application.L’application f est une injection de E dans F (ou plus simplement une injection) si chaque image n’a

qu’un seul antécédent (autrement dit les éléments de l’ensemble d’arrivée F ont tous 0 ou 1 antécédent).La définition que l’on retiendra, la plus pratique dans les démonstrations, est la suivant :

f : E æ F est injective si et seulement si, pour tout x, xÕ œ E, si f(x) = f(xÕ) alors x = xÕ.

L’application f est une surjection de E sur F (ou plus simplement une surjection) si f(E) = F ,autrement dit si chaque élément de l’ensemble d’arrivée F a au moins un antécédent. On retiendra commedéfinition

f : E æ F est surjective si et seulement si, pour tout y œ F, il existe x œ E tel que f(x) = y.

L’application f est une bijection de E sur F (ou plus simplement une bijection) si elle est à la foisinjective et surjective. Autrement dit chaque élément y de F possède un et un seul antécédent.

Question 2.4. Soit f : E æ F une application. Que peut-on dire de la corestriction de f à f(E) ?Qu’entend-on par “toute injection est bijective sur son image” ? Est-ce vrai ?

Proposition 2.3. F La composée de deux injections est injective. La composée de deux surjections estsurjective.

Proposition 2.4. F Soient E, F, G des ensembles, i : E æ F et s : F æ G des applications.1. Si s ¶ i est surjective alors s est surjective.2. Si s ¶ i est injective alors i est injective.

Théorème 2.5. F Une application f : E æ F est bijective si et seulement si il existe une applicationg : F æ E telle que g ¶ f = IdE et f ¶ g = IdF .De plus l’application g est unique ; c’est la bijection réciproque de f notée f≠1.

Nota Bene – Il faut bien distinguer f{≠1}(B) l’image réciproque d’une partie B de F , définie pourtoute application qu’elle soit ou non injective, surjective... et la bijection réciproque f≠1 d’une appli-cationbijective f . Remarquons d’ailleurs que f≠1 est une application de F dans E, alors que f{≠1}, quis’applique à des ensembles, peut être vue comme une application de P(F ) dans P(E). Dans ce cours, nousutilisons deux notations distinctes car les deux objets sont bien totalement di�érents, mais en général lanotation f≠1(B) est aussi utilisée pour désigner l’ensemble f{≠1}(B).


2.5 ExercicesExercice 2.1. F On considère l’application f : Z ◊ Zú æ Z définie par f(p, q) = pq.

1. Déterminer f({2, 4} ◊ {1, 2}). L’application f est-elle injective ?2. Déterminer f{≠1}({0}), f{≠1}({2}). L’application f est-elle surjective ?3. Démontrer que f({2} ◊ Zú) = 2Zú.4. Démontrer que f(2Z ◊ 3Zú) = 6Z.

Exercice 2.2. W Images directe et réciproque (d’une fonction de R dans R)

Soit f : R æ R , x ‘æ x2. Tracer le graphe de f . Déterminer graphiquement les ensembles1. f([≠4, ≠1]) , f([≠4, 2]) , f(] ≠ 2, 3[).2. f{≠1}({≠1}), f{≠1}({0}), f≠1({1}).3. f{≠1}(] ≠ Œ, 3]) , f{≠1}([≠2, +Œ[) , f{≠1}(] ≠ 2, 0] fi [1, 5[).

Exercice 2.3. W Fonction non-injective

Soit la fonction f : R2 æ R2, (x, y) ‘æ (2x ≠ y, y2). Montrer que cette fonction n’est pas injective.

Exercice 2.4. W Fonction non-surjective

Soit la fonction f : R2 æ R2, (x, y) ‘æ (3 sin(x)+1, x+y). Montrer que cette fonction n’est pas surjective.

Exercice 2.5. FOn considère les applications f et g définies par :

f :;

N2 ≠æ N(n, m) ‘≠æ m + n

et g :;

N ≠æ N2

n ‘≠æ (n, n + 1)1. L’application f est-elle injective ? surjective ?2. L’application g est-elle injective ? surjective ?3. On note P ={2n ; n œ N} l’ensemble des entiers naturels pairs et I ={2n + 1 ; n œ N} l’ensemble

des entiers naturels impairs. Démontrer que f(P ◊ P) = P.

4. Déterminer f(I ◊ I).

Exercice 2.6. FOn considère les applications f et g définies par :

f :;

[0, 1]2 ≠æ [0, 1](x, y) ‘≠æ xy

et g :;

[0, 1] ≠æ [0, 1]2x ‘≠æ (x, 1

x+1 )

1. L’application f est-elle injective ? surjective ?2. L’application g est-elle injective ? surjective ?

Exercice 2.7. F On considère l’application f : E æ F définie par f(x) = x2 où E et F sont deux partiesde R.Dans chacun des cas suivants f est-elle injective, surjective, bijective ?Justifier votre réponse.(a) E = F = N, (b) E = Z, F = N, (c) E = Q, F = R+, (d) E = [≠1, 1] , F = [0, 1] et (e) E = F = R+.

Exercice 2.8. Soit f : x ‘æ cos x. Choisir des ensembles A et B pour que f : A æ B soit1. une application injective non surjective ?2. une application surjective, non injective ?3. une bijection ?

Exercice 2.9. W Fonctions indicatrices

E un ensemble. Pour toute partie A de E, on considère la fonction indicatrice de A définie par 1A : E æ{0, 1}; x ‘æ

I1 si x œ A

0 si x /œ A.

2.5. EXERCICES 15

1. Montrer que si E possède plus de deux éléments, 1A n’est pas injective. A quelle condition sur Aest-elle surjective ?

2. Montrer que, si pour tout x œ E, 1A(x) Æ 1B(x), alors A µ B. En déduire que 1A = 1B si etseulement si A = B.

3. On munit {0, 1} des opérations arithmétiques + et ◊ définies dans l’exercice ??. Soient A et Bdeux parties de E. Montrer que(a) Pour tout x œ E 1AflB(x) = 1A(x)1B(x).(b) Montrer que 1AfiB = 1A + 1B ≠ 1A1B .(c) Montrer que 1Ac = 1 ≠ 1A.(d) Déterminer 1A\B à l’aide de 1A et 1B et refaire l’exercice 1.7.

4. (a) Déterminer 1A—B à l’aide de 1A et 1B .(b) Refaire l’exercice 1.8.

5. On considère l’application � : P(E) æ {0, 1}E , A ‘æ 1A.(a) L’application � est-elle bijective ? (On pourra utiliser le 2.)(b) Traduire les propriétés des questions 3. et 4. à l’aide de �.

(Par exemple 3a. s’écrit �(A fl B) = �(A)�(B).)

Exercice 2.10. Pour chacune des fonctions suivantes, indiquer s’il s’agit d’une bijection, si non indiquezun contre-exemple à l’injectivité ou la surjectivité et si oui déterminer la bijection réciproque

1. Soit E un ensemble non vide, IdE : E æ E, x ‘æ x.2. f1 : N æ N, n ‘æ n + 1, f2 : Z æ Z, n ‘æ n + 1.3. g1 : R2 æ R2, (x, y) ‘æ (x + y, x ≠ y),

g2 : R2 æ R3, (x, y) ‘æ (x + y, x ≠ y, x + 2y),g3 : R2 æ R2, (x, y) ‘æ (2x + 4y, x + 2y).

4. h : R2 æ R ◊ [0, +Œ), (x, y) ‘æ (x + y2, y2).5. „ :]0, +Œ) ◊ [0, 2fi[æ Cú, (r, ◊) ‘æ rei◊.

Exercice 2.11. Soit E, F deux ensembles et f une application de E dans F . Montrer que1. pour toutes parties A, B de E, et pour tout ensemble {Ai, i œ I}, de parties de E,

(a) f(A fi B) = f(A) fi f(B),(b) f(A fl B) µ f(A) fl f(B),(c) f(fliœIAi) µ fliœIf(Ai)

2. pour toutes parties A, B de F , et pour tout ensemble {Bi, i œ I}, de parties de F ,(a) f{≠1}(A fi B) = f{≠1}(A) fi f{≠1}(B),(b) f{≠1}(A fl B) = f{≠1}(A) fl f{≠1}(B),(c) f{≠1}(fliœIBi) = fliœIf{≠1}(Bi).

3. soit A une partie de E et B une partie de F .(a) Comparer A et f{≠1}(f(A)). Comparer à nouveau lorsque f est injective.

En déduire une caractérisation de l’injectivité.(b) Comparer B et f(f{≠1}(B)). Comparer à nouveau lorsque f est surjective.

En déduire une caractérisation de la surjectivité.(c) Comparer f(Ac) et [f(A)]c, f{≠1}(Bc) et

#f{≠1}(B)

$c. Y-a-t-il des hypothèses sur f qui per-mettent d’avoir des cas d’inclusion ou d’égalité ?

Exercice 2.12. F Soit i : E æ F et s : F æ G deux applications. Démontrer que :1. Si s ¶ i est injective alors i est injective.2. Si s ¶ i est surjective alors s est surjective.3. Si s ¶ i est injective et i surjective alors s est injective.4. Si s ¶ i est surjective et s est injective alors i est surjective.


5. Soit f : E æ E une application. Que peut on dire de f si elle vérifie f ¶ f = IdE ?

Exercice 2.13. F1. On considère l’application Ï : N æ Z définie par Ï(n) = n

2 si n est pair et Ï(n) = ≠ n+12 sinon.

Montrer que Ï est bijective.2. On considère l’application f : N◊Zú æ Zú définie par f(p, n) = 2p(2n+1) pour (p, n) dans N◊Zú.

Montrer que f est bijective.

Exercice 2.14. Soient f et g les deux applications ainsi définies :

f : N ◊ Zú ≠æ Q(p, q) ‘≠æ r = p

q

et g : Q ≠æ N ◊ Zú

r ‘≠æ (p, q) avec r = pq fraction irréductible.

f et g sont-elles injectives ? surjectives ? bijectives ?

Exercice 2.15. A l’aide des deux exercices précédents construire une surjection de N sur Q.

Exercice 2.16. Soit n œ Nú. On reprend les notations de l’exercice ?? du chapitre 1. On note „n

l’application Z æ Zn définie pour tout a œ Z par „n(a) = r où r est le reste de la division euclidienne dea par n.

1. Montrer que „n est surjective.2. Montrer que pour pour tout a, b œ Z on a „n(a + b) = „n(a) + „n(b).3. Montrer que „

{≠1}n ({0}) = nZ. (Rappel : nZ = {nk, k œ Z}.)

4. Montrer que n est pair ssi „2(n) = 0.

A propos des mathématiques

Nature ?Le livre de la Nature est écrit en langagemathématique – Galileo Galilei

Langage ?Le livre de la Nature n’est pas écrit en lan-gage mathématique, c’est plutôt le langagemathématique qui est le seul qui nous per-mette de décrire la nature logiquement. –Ingrid Daubechies

ImaginationL’imagination est plus importante que laconnaissance. – Albert Einstein

Abstraction...Les mathématiques sont un outil parfaite-ment adapté pour traiter de tout conceptabstrait, et elles ne connaissent aucune li-mite dans ce domaine. – Paul Dirac

Compréhension ?En mathématiques, on ne comprend pas leschoses, on s’y habitue – John Von Neu-mann

Pour l’honneur de l’esprit humain .... . . Monsieur Fourier avait l’opinion quele but principal des mathématiques étaitl’utilité publique et l’explication des phé-nomènes naturels. Un philosophe tel quelui aurait dû savoir que le but unique dela Science, c’est l’honneur de l’esprit hu-main et que, sous ce titre, une question denombres vaut bien une question de systèmedu monde. – Gustav Jacobi

OrdonnerLe savant doit ordonner ; on fait la Scienceavec des faits comme une maison avec despierres ; mais une accumulation de faitsn’est pas plus une science qu’un tas depierres n’est une maison. – Henri Poincaré

Utilité ?... une bonne partie des mathématiques de-venues utiles se sont développées sans au-cun désir d’être utiles, dans une situationoù personne ne pouvait savoir dans quelsdomaines elles deviendraient utiles. Il n’yavait aucune indication générale qu’elles leseraient. C’est vrai de toute la science. –John Von Neumann

CuisineLa science a eu de merveilleuses applica-tions, mais la science qui n’aurait en vueque les applications ne serait plus de lascience, elle ne serait plus que de la cui-sine. – Henri Poincaré

Machines ?Le danger réel n’est pas que les ordinateurscommencent à penser comme les humains,mais que les humains commencent à pen-ser comme des ordinateurs. – Sydney Har-ris

MachineSoit les mathématiques sont trop grandespour l’esprit humain, soit l’esprit humainest plus qu’une machine. – Kurt G’odel

ArtLes meilleurs travaux des mathématicienssont de l’art, un art très perfectionné, dé-fiant les rêves les plus secrets de l’imagi-nation, clairs et limpides. Le génie mathé-matique et le génie artistique se touchentl’un l’autre. – G’osta Mittag-Le�er

DéfinitionEn mathématiques, les noms sont arbi-traires. Libre à chacun d’appeler un opé-rateur auto-adjoint un “éléphant” et unedécomposition spectrale une “trompe”. Onpeut alors démontrer un théorème suivantlequel “tout éléphant a une trompe”. On n’apas le droit de laisser croire que ce résultata quelque chose à voir avec de gros ani-maux gris. – Gerald Sussman

ProblèmesSi la logique est l’hygiène du mathémati-cien, ce n’est pas elle qui lui fournit sanourriture ; le pain quotidien dont il vit, cesont les grands problèmes. – André Weil

BonheurSi je suis malheureux, je fais des mathé-matiques pour devenir heureux.Si je suis heureux, je fais des mathéma-tiques pour le rester. – Alfred Rényi

17


Bref historique de la naissance des mathématiques

La démonstration mathématique est sans doute au contact de la géométrie (quisignifie étymologiquement “mesurer la terre”). Elle est apparue pour la première fois enGrèce antique et constitute un des apports majeurs de cette civilisation. Thalès (624–546avant JC) démontre quelques théorèmes géométriques. Eudoxe (408–55 avant JC) et Théétèted’Athènes (417–369 avant JC) énoncent des théorèmes sans les démontrer. Aristote (384–322avant JC) précise la notion de définition : les objets doivent être définis à partir de notionselles-mêmes bien définies en remontant ainsi jusqu’à quelques notions premières.

La notion de démonstration mathématique est vraiment née avec les Éléments d’Eu-clide (300 avant JC). C’est lui qui a introduit la méthode axiomatique, toujours utiliséeaujourd’hui. Les notions premières qu’il utilise sont : les points, les droites, et la relation unpoint p appartient à la droite �. Puis il définit les axiomes (en Grec “axios” signifie “quelquechose de valable”), au nombre de cinq. Toutes les propositions et théorèmes en découlent parimplication logique. Les Élèments d’Euclide se devait d’être lus par toute personne éduquéejusqu’à la moitié du XXè siècle. En plus des théorèmes classiques de la géométrie, comme lethéorème de Pythagore, on trouve, dans les Éléments une preuve de la nature irrationnellede

Ô2 et la preuve qu’il y a une infinité de nombres premiers.

Une autre source des mathématiques provient de l’école indienne qui nous a donnénotamment le système de chi�re décimal (en particulier le zéro comme chi�re et commenombre) et qui fut la première à appréhender l’infini.

C’est à l’Islam médiéval que l’on doit ensuite les nouvelles avancées en mathéma-tiques. Les démonstrations précédentes données par les Grecs sont largement géométriques.L’arithmétique et l’algèbre que les mathématiciens de l’Islam médiéval ont développées, per-mettent des démonstrations plus générales et s’a�ranchissent du cadre géométrique parfoiscontraignant. On peut citer entre autre Abu Ja’far Muhammad ibn Musa Al-Khwarizmi (780– 850) reconnu comme le père de l’algèbre mais aussi de l’algorithmique.

La production mathématique est considérable et en croissance constante. Sur le site “arXiv.org” onrecense environ 20 000 dépôts d’article rien qu’en 2012 ! Bien sûr, tous ces articles ne seront pas forcémentpubliés dans des revues avec commité de lecture, mais le chi�re est impressionnant.

Que trouve-t-on dans un article de mathématiques ? Au niveau du fond, nous ne nous hasarderonspas à définir plus précisément le contenu. La forme de l’article, elle, est plus facile à décrire. Un articlecommence par une introduction qui situe la problématique abordée, puis un rappel des définitions et desrésultats déjà connus, des exemples, puis des propositions, des lemmes, un ou plusieurs théorèmes, parfoisquelques corollaires, puis bien sûr les démonstrations. L’article se conclut par une bibliographie.

2.5. EXERCICES 19

Petit Lexique

Théorème : Un théorème est un énoncé mathématique important qui a été démontré àpartir des axiomes, d’autres propositions mathématiques déjà démontrées, en utilisant les règlesde déduction logique. La démonstration du théorème établie sa vérité. Comme la plupart desthéorèmes s’énoncent comme une implication :“Si les hypothèses sont vérifiées, alors les conclusionssont vraies”, la démonstration permet de déduire les conclusions à partir des hypothèses. Dès lorsle théorème constitue une assertion logique : il est toujours vrai.

Bien qu’un théorème puisse toujours s’écrire en langage formel, par exemple dans le langagedu calcul des propositions ou du calcul des prédicats, les théorèmes se formulent souvent en françaiscourant.

Les théorèmes se situent au coeur de la construction mathématique et leur esthétiqueest très importante. Ils sont décrits comme “trivials”, “di�ciles”, “profonds” ou “beaux”. Cesjugements subjectifs ne varient pas seulement suivant la personne, mais aussi au cours du temps.Ainsi, une démonstration peut être simplifiée, mieux comprise et un théorème jugé di�cile devientfacile. D’autre part, un théorème profond peut s’exprimer simplement, mais sa démonstration peutnécessiciter des interactions subtiles entre di�érents domaines des mathématiques.Démonstration : On appelle démonstration mathématique une suite déductive qui permetde démontrer une proposition qui s’écrit généralemnt sous la forme “Si A, alors B” La partie A del’énoncé s’appelle les hypothèses de la proposition et B les conclusions.

Au cours de la démonstration on peut utiliser des résultats déjà démontrés comme des théo-rèmes. En principe, on peut remonter les arguments jusqu’aux arguments de base appelés axiomes.Les démonstrations mathématiques sont déductives, et en ce sens se distinguent des preuves em-piriques (c’est-à-dire par généralisation à partir d’exemples). La démonstration d’une a�rmationdoit montrer qu’elle est toujours vraie. Un seul contre-exemple permet de l’invalider.

Toutefois, en pratique, ces arguments ne sont pas totalement formalisés, et restent en partiinformels, et s’adaptent à l’auditoire qu’ils visent à convaincre. Ils peuvent bien sûr être facilementtransformés en arguments complètement formalisés, ce qui les rendraient bien plus di�cilementcompréhensibles et bien moins facile à vérifier (sauf pour un cyborgue). De plus, de nombreuxmathématiciens préfèrent souvent les démonstrations qui, en plus de démontrer le théorème, ex-pliquent d’une manière ou d’une autre pourquoi il est vrai.Assertion : Du latin adsertio, de adserere, a�rmer. Statut d’une phrase dans laquelle lesujet parlant énonce une vérité, déclare un fait (par opposition à l’interrogation, à l’exclamation, àl’injonction). En logique, une assertion est une phrase considérée comme vraie, mais pas forcémentdémontrée.Axiome : Il s’agit d’une assertion première, accéptée sans démonstration et considérée commefondamentale. Historiquement ces assertions étaient considérées comme évidente, mais aujourd’huielles sont plutôt considérées comme des assertions qui caractérisent le sujet d’étude.Définition : Une définition est également accéptée sans démonstration, puisqu’elle donnesimplement la signification d’un terme à l’aide de concepts connus. La nouvelle notion doit toutefoisêtre définie sans ambig’uité. De définitions en définitions on remonte ainsi jusqu’à des notionspremières. Dans la reconstruction des mathématiques qui a été faite au cours du XXè siècle, lanotion première est celle d’ensembles.Proposition (mathématique) : C’est le terme utilisé pour qualifier une assertion mathé-matique démontrée, mais qui n’a pas l’importance d’un théorème.Proposition (logique) : c’est une phrase qui ne peut être que vraie ou fausse.Lemme : C’est une proposition technique, parfois di�cile, mais qui n’a pas d’autre d’applica-tion que de permettre la démonstration d’un théorème.Il arrive qu’avec le temps, ce qui semblait un résultat intermédiaire apparaisse comme une propo-sition fondamentale et devienne un théorème. Cependant, pour des raisons historiques, le nom delemme lui reste accolé. On peut citer ainsi le lemme de Gauss.


Corollaire : C’est une proposition qui découle clairement (donc sans démonstration oupresque) d’un théorème établi.Conjecture : Il s’agit d’une assertion non démontrée, et que les mathématiciens cherchentà démontrer. Poser une conjecture est un processus fondamental dans les mathématiques tellesqu’elles se font.Les conjectures les plus célèbres qui ont étés démontrées récemment sont, sans doute, le grandthéorème de Fermat et la conjecture de Poincaré.

- Pierre de Fermat (né vers 1600, mort en 1665) indique en marge d’une traduction de l’arith-métique de Diophante que l’équation xn + yn = zn n’a pas de solutions entières pour n Ø 3,mais que la marge est trop petite pour en contenir la démonstration. Après 350 ans defiévreuses recherches n’aboutissant au mieux qu’à des résultats partiels, la démonstrationa été donnée par Wiles en 1994. Publiée en 1995, elle fait près de 110 pages et utilise desthéories complexes tel l’algèbre modulaire, inventés dans la deuxième moitié du XXè.

- ou encore le théorème de Perelman-Poincaré (conjecturé par Poincaré en 1904 , démontrépar Perelman en 2003). La conjecture de Poincaré est plus di�cile à appréhender. Ellecaractérise toutes les surfaces pouvant être transformées par des déformations continues (quine déchirent ni ne recollent la surface) en l’hypersphère de dimension 3 : “Soit une variétécompacte V simplement connexe, à 3 dimensions, sans bord. Alors V est homéomorphe àune hypersphère de dimension 3.”

En 2000, le Clay Mathematical Institute à repris sept défis mathématiques réputésinsurmontables et a proposé un prix d’un million de dollars pour chacun d’eux. Ce sontles 7 prix du millénaire. La conjecture de Poincaré était l’un d’eux. Perelman (né à SaintPetresbourg en 1966) poste sur arXiv en 2002 une série de trois articles qui en donne lapreuve. Il n’a jamais fait publié ses articles dans des revues et a refusé tous les prix qui luiont été décernés.

Chapitre 3

Logique classique et démonstrationsmathématiques

Logique (gr. ⁄o“oÎ, logos, intelligence, parole, pensée). Selon la définition classique c’est la sciencede la formulation claire et juste de la pensée, des règles correctes de déduction et de la production depreuves. Vue sous cet angle, la logique et la rhétorique constituent un segment de la philosophie. La logiquecontemporaine, grâce à sa méthode formelle, a très largement étendu son champ, notamment à traversson interaction avec les mathématiques, son application à la théorie des preuves et à l’informatique.

La logique classique, aussi appelée logique élémentaire ou calcul de logique classique, est le systèmeformel constitué du calcul des propositions et du calcul des prédicats (ou des quantificateurs). Ce calculporte sur des phrases logiques, c’est à dire des phrases qui ne peuvent être que vraies ou fausses. Lalogique classique est en ce sens sans nuances, elle n’a que deux valeurs de vérité possible, on dit qu’elle estbimodale et obéit au principe du tiers exclu (à la di�érence de certaines logiques multimodales développéesà partir du XXè siècle).

Dans le calcul des propositions, les phrases, ou propositions, sont représentées par des inconnues (sou-vent notée à l’aide des lettres : p, q, r...). A l’aide des connecteurs logiques “et”, “ou”, “non”, “implique”, onconstruit des propositions complexes, encore appelées formules logiques. L’un des buts essentiel du calculde la logique est d’obtenir des méthodes permettant de déterminer la valeur de vérité de l’énoncé complexeen fonction de celles des propositions qui la composent. Le but ultime est d’obtenir et de démontrer desassertions, c’est à dire des propositions toujours vraies.

Dans le calcul des prédicats, les constituants élémentaires des phrases sont les prédicats, c’est-à-diredes propositions p(x), q(x, y)... dépendantes de variables x, y, ..., ces variables étant quantifiées à l’aide desquantificateurs existentiels ÷ et universels ’. On écrit ainsi des formules logiques complexes en utilisantles quantificateurs, les prédicats et les connecteurs logiques. Le premier objectif est d’abord de savoir sousquelles conditions la formule complexe est une proposition, puis de décrire toutes les propositions qui sonttoujours vraies, c’est-à-dire qui constituent des assertions. La première étape est résolue en regardant laformule logique et en vérifiant qu’elle est bien écrite. C’est la question de la syntaxe, ou l’aspect syntaxiquede la logique qui est alors en question. On aborde ensuite la question du sens, qui en logique se résume àla question “la proposition est-elle vraie ou fausse ?”.

Ces deux questions trouvent leur analogue en informatique. En e�et lorsqu’on écrit un programmedeux questions se posent. D’abord, le programme va-il tourner ? (un bon compilateur qui vérifie la syn-taxe permet d’aider dans la résolution de ce genre de problème). Ensuite, le programme, lorsqu’il tourne,répond-il bien aux attentes ? Cette question correspond à l’aspect sémantique de la logique. C’est d’ailleursles preuves de programme qui apportent une réponse complètement satisfaisante à cette question fonda-mentale pour la sécurité.

La logique classique permet aussi de clarifier la structure des démonstrations. En e�et, chaque assertionlogique correspond à un raisonnement déductif parfaitement infaillible, ainsi l’un des buts de la logique

21

22 CHAPITRE 3. LOGIQUE CLASSIQUE ET DÉMONSTRATIONS MATHÉMATIQUES

classique est également de décrire tous les raisonnements déductifs incontestables.

La logique classique contient donc toutes les lois élémentaires de raisonnement découvertes depuisl’antiquité ainsi que des lois plus récentes concernant les quantificateurs. Ce calcul est su�sant pourdécrire tous les raisonnements utilisés en mathématiques et tous les raisonnements déductifs. En tant quetel, il forme un domaine fermé de la logique.

Mais comment en logique démontre-t-on une proposition complexe ? Il existe deux méthodes. La pre-mière est dite sémantique. Une proposition peut être vue comme une fonction à valeurs dans l’ensemblebooléen {faux, vrai} ou {0, 1}. Ainsi la valeur d’une proposition complexe peut être calculée en fonctiondes valeurs des propositions élémentaires qui la composent. Ce calcul peut se faire à l’aide de table devérité. Toutefois, la méthode sémantique atteint rapidement ses limites en pratique. Il faut en e�et pouvoirénumérer toutes les interprétations, or elles sont en nombre exponentiel des propositions élémentaires.

La deuxième méthode consiste à se donner un certain nombre de règles de déduction, et à validerles formules qui peuvent être déduites à partir d’elles. C’est la méthode déductive. Elle correspond auxdémonstrations mathématiques. Fort heureusement les formules qui sont possibles à démontrer par l’unedes méthode le sont aussi par l’autre, et vice-versa. Ces résultats sont démontrés mais ils dépassent lecadre du cours. Nous nous contenterons d’utiliser la méthode sémantique pour préciser la signification desconnecteurs logiques “non”, “ou”, “et”, “ =∆ ”. Puis nous passerons rapidement à la méthode déductive.

3.1 Connecteurs logiques et calcul des propositionsLa négation – La négation de l’assertion A est l’assertion non A qui est fausse quand A est vraie etvraie sinon. Ceci se résume par la table de vérité suivante

A 0 1non A 1 0

Proposition 3.1. L’assertion non(non(A)) a la même vérité que A.

La conjonction – A et B est vraie dans le cas ou A et B sont toutes les deux vraies. Elle est faussedans le cas contraire.

A 0 0 1 1B 0 1 0 1

A et B 0 0 0 1

Proposition 3.2. - L’assertion “A et B” a la même vérité que “B et A” (commutativité) ;- L’assertion “A et (B et C)” a la même vérité que “(A et B) et C” (associativité).

La disjonction – A ou B est fausse dans le cas ou A et B sont tous deux fausses. Elle est vraie si l’undes deux, ou les deux sont vraies.

A 0 0 1 1B 0 1 0 1

A ou B 0 1 1 1

Proposition 3.3. - L’assertion “non(A et B)” a la même vérité que “non(A) ou non(B)” ;- L’assertion “non(A ou B)” a la même vérité que “non(A) et non(B)”.

Corollaire 3.4. - L’assertion “A ou B” a la même vérité que “B ou A” (commutativité) ;- L’assertion “A ou (B ou C)” a la même vérité que “(A ou B) ou C” (associativité).

Proposition 3.5. (distributivité)- L’assertion “A ou (B et C)” a la même vérité que “(A ou B) et (A ou C)” ;- L’assertion “A et (B ou C)” a la même vérité que “(A et B) ou (A et C)”.

3.1. CONNECTEURS LOGIQUES ET CALCUL DES PROPOSITIONS 23

L’implication – “A =∆ B”, se lit “si A, alors B” ou bien “A implique B” ou encore “pour B, il su�tA”, “pour A, il faut B”, autrement dit “A est vraie est une condition su�sante pour que B soit vraie” ou“B est vraie est une condition nécessaire pour que A soit vraie”.

L’implication “A =∆ B” n’est fausse que dans le cas où “A et nonB” est vraie. Sa table de véritéest donc la suivante

A 0 0 1 1B 0 1 0 1

A =∆ B 1 1 0 1

Proposition 3.6. “A =∆ B” a la même vérité que “nonA ou B”.

Remarque 3.1. — L’implication logique n’est pas commutative, ni associative. En particulier laformule “(A =∆ B =∆ C)” n’a a priori pas de sens ; elle pourrait signifier (A =∆ B) =∆ Cou A =∆ (B =∆ C).

— Attention, l’implication logique est assez loin de ce qu’on entend par “implication” dans le quotidien.En particulier ce n’est pas la relation de causalité.

La négation de l’implication “A =∆ B” est “A et nonB”.La réciproque de l’implication “A =∆ B” est “B =∆ A”, leurs vérités sont indépendantes.La contraposée de l’implication “A =∆ B” est “nonB =∆ nonA”, ces deux propositions ont mêmevérité.

Proposition 3.7. - “A =∆ (B et C)” a même vérité que “(A =∆ B) et (A =∆ C)” ,- “(A ou B) =∆ C” a même vérité que “(A =∆ C) et (B =∆ C)” ,- “A =∆ (B ou C)” a même vérité que “(A et non(B)) =∆ C”.

L’équivalence – “A ≈∆ B”, se lit “A est équivalent à B” ou bien “A si et seulement si B” ou encore“A est une condition nécessaire et su�sante pour B”, elle à même vérité que “(A =∆ B) et (B =∆ A)”.

Question 3.1. — Quelle est la table de vérité de l’équivalence ?— L’équivalence est-elle associative ?— Est-ce-que “(A ≈∆ B) ≈∆ C” a la même vérité que “(A ≈∆ B) et (B ≈∆ C)” ?— Qu’entend-on en pratique lorsqu’on écrit une suite d’équivalence (pour résoudre un système par

exemple) ?

3.1.1 Quelques règles de déductionDans ce paragraphe, nous énonçons quelques assertions, qui sont les règles de déductions le plus souvent

utilisées dans les démonstrations mathématiques déductives. Ces assertions peuvent soit être démontréesà partir des tables de vérité (calcul sémantique et ce sont alors des théorèmes), soit être admises commeaxiomes.

Tiers-exclu : A ou (non A).

Modus ponens : Si A et si (A =∆ B), alors B.

Contraposée : Si (non B =∆ nonA), alors (A =∆ B). Et plus généralement,

Déduction de l’absurde : Si ((A et nonB) =∆ (R et nonR)), alors (A =∆ B).

3.1.2 Comment réinvestir tout ceci dans les démonstrations mathématiques ?On veut utiliser A =∆ B pour montrer B. Au cours de la rédaction, on vérifie les hypothèses A,on dit que A =∆ B est un théorème, et on en déduit B.


On veut montrer l’implication “A =∆ B”. Les méthodes utilisées le plus couramment sont— la méthode directe : On suppose A, [on raisonne ... et on déduit] donc B. Conclusion : on a

A =∆ B.— par contraposition : On suppose non B, [on raisonne ... et on déduit] donc non A . On conclut

que, par contraposée, on a A =∆ B.— par l’absurde : On suppose, par l’absurde, A et nonB, on en déduit deux propositions R et nonR :

contradiction. On en conclue que l’on a A =∆ B.

Démonstration d’implications logique plus complexes. On peut adapater ce qui précède pouravoir une idée de la manière dont on démontre par exemple la proposition ((A et B) =∆ C). Ecrire cequ’on peut appeler un “algorithme de démonstration” permet d’avancer dans l’analyse du point de mathsqu’il faut vraiment démontrer. Ainsi, en déroulant par écrit la méthode choisie pour la démonstration, onse rapproche aussi de notre objectif.

Par exemple, on veut montrer la proposition (F) : ((A et B) =∆ C). On écrit :

Démonstration. On suppose A et B, montrons C ....[on fait des raisonnements divers mais justes... et onconclut] donc C. Ainsi, la proposition (F) est démontrée. ⇤

Démonstration d’une alternative. La démonstration d’une alternative (A =∆ (B ou C)) dérogeun peu à cette règle générale. Car une fois que l’on a supposé A, que diable voulons nous démontrer, B ouC ? Pour ne pas se retouver dans l’incapacité d’avancer devant ce choix, il peut être pratique de supposer(A et non B) et, en raisonnant d’en déduire C. On en conclut (d’après la Proposition 3.7) que A =∆ (Bou C).

CQFD - et la démonstration est achevée.CQFD, également écrit C.Q.F.D. ou c.q.f.d., est l’abréviation de “ce qu’il fallait démontrer”. Elle se

place à la fin d’une démonstration mathématique pour indiquer que le résultat attendu a été démontré.L’expression équivalente en latin est QED, “quod erat demonstrandum”.

Toutefois, les abréviations CQFD et QED sont largement délaissées dans la littérature mathématique.Les auteurs préfèrent l’utilisation de symboles pour marquer la fin des démonstrations, nous utiliseronsles carrés ⇤ à cette fin.

3.2 Quantificateurs et calcul des prédicatsPrédicats – A la di�érence des propositions logiques qui sont soient vraies, soit fausses, les prédicatssont des phrases logiques dépendantes d’une ou plusieurs variables x, y.... Cette ou ces variables fixées, onobtient une proposition logique.

Par exemple “x est blond”, “y porte un chapeau”, “x Ø 0”, “x Ø y”, “x a le numéro de téléphone dey”. On les note P (x), Q(x, y)...

Syntaxe :

1. Si “P (x)” est un prédicat portant sur la variable x, “(nonP (x))” est un prédicat portant sur x.2. Si “P (x)” et “Q(y)” sont des prédicats portant sur des variables x, y, et si ⇤ est la conjonction, la

disjonction ou l’implication logique, alors “P (x) ⇤ Q(y)” est une formule logique valide, c’est unprédicat portant sur les variables x et y.

Quantificateurs – En grammaire le quantificateur est un mot qui exprime une quantité : un peu,beaucoup, de nombreux, presque tous, aucun... Il existe donc de nombreuses nuances et parfois des zonesde flou.

En logique classique, il n’existe que deux quantificateurs. Le quantificateur existentiel ÷ qui se lit “ilexiste au moins un” et le quantificateur universel ’ qui se lit “pour tout”. Ce ne sont pas des abréviations.Leur utilisation est soumise à des règles très strictes. Leur usage est réservé avant tout aux définitions,celles-ci ne pouvant tolérer aucune d’ambigu’ıté. On en trouve aussi parfois, bien que rarement, dans

3.2. QUANTIFICATEURS ET CALCUL DES PRÉDICATS 25

des énoncés de propositions et théorèmes. Les quantificateurs n’ont leur place que dans des formulessymboliques, et pas au milieu des phrases écrites en français ; notons qu’une démonstration écrite pourêtre lue par des humains ne doit pas se réduire à une suite de formules. . .

Ces quantificateurs portent sur des variables x, y, ... et sont suivies par des prédicats portant sur lesmêmes variables...

Syntaxe :

1. Si p(x) est un prédicat portant sur la variable x, (’x, p(x)) est une formule valide et (÷x, p(x))aussi. Ce ne sont plus des prédicats portant sur x, mais de simples propositions logiques. On ditque ces formules sont fermées. Ainsi, les quantifiateurs lient la variable sur laquelle ils portent :dans la formule logique “(’x, p(x))” la variable x est liée. On dit aussi dans ce cas que la variablex est muette, ce qui se comprend par le fait que “(’x, p(x))” a exactement la même significationque “(’y, p(y))”

2. Souvent, si E est un ensemble, on écrit “’x œ E, p(x)”, qui est une manière concise d’écrire“’x, (x œ E =∆ p(x))”. Lorsque cette proposition est vraie et si x œ E, on est alors assuré d’avoirp(x).

Variables libres (parlantes), variables liées (muettes) – Considérons le prédicat suivant :

P1 : ’x œ A, x Ø 3.

Ce prédicat fait intervenir deux variables (x et A). La variable x, liée par le quantificateur ’x, peut êtreremplacée par n’importe quelle autre variable sans changer le sens de l’expression : on pourrait tout aussibien écrire

P2 : ’y œ A, y Ø 3,

et, suivant la valeur de A, P1 et P2 seront soit vraies toutes les deux soit fausses toutes les deux.En revanche la variable A est libre : suivant la façon dont A est choisi P1 peut être vraie ou fausse.De même, dans l’expression {n, n œ N, n Æ 5}, la variable n désigne un élément quelconque, et la

notation {m, m œ N, m Æ 5} désigne exactement le même ensemble : l’ensemble des entiers naturels pluspetits (au sens large) que 5. Dans cette expression en français, n n’intervient pas, c’est pour cela que l’ondit que la variable est muette.

On l’a vu, les symboles ’x, ÷x, {x, ...}, fii ont pour e�et de lier la variable sur laquelle ils portent, ou dela rendre muette. C’est aussi le cas des opérateurs de sommation

qnk=1 ak,

s 10 f(x)dx, ou de limxæa f(x).

Négation – La négation de “’x P (x)” est “÷x non P (x)”. Par conséquent, la négation de “÷x P (x)” est“’x non P (x)”.La négation de “’x œ E, P (x)” est “÷x œ E, nonP (x)”. La négation de “÷x œ E, P (x)” est “’x œ E, nonP (x)”.

On pourrait donc n’utiliser qu’un seul quantificateur, par exemple ’, puisque “÷x P (x)” a la mêmesignification que “non(’x non P (x))”. Cependant, cela ne simplifierait pas la compréhension du texte !

Conjonction – La proposition logique “(’x P (x)) et (’x Q(x))” est équivalente à “’x (P (x) et Q(x))”.Attention toutefois car “((÷x P (x)) et (÷x Q(x)))” est équivalent à “÷x ÷xÕ (P (x) et Q(xÕ))” et non à“÷x (P (x) et Q(x))”

Pour s’en convaincre, considérer les proposition “P (x) : x joue bien au foot” et “Q(x) : x est bon enméthodologie des mathématiques”

Disjonction – “(’x P (x)) ou (’x Q(x))” n’est pas équivalent à “’x (P (x) ou Q(x))”, mais à “(’x,forallxÕ P (x) ou P (xÕ))”.“(÷x P (x)) ou (÷x Q(x))” est équivalent à “÷x (P (x) ou Q(x))”.

Commutativité des quantificateurs lorsque ceux sont les mêmes – La proposition “’x ’y p(x, y)”a la même signification que “’y ’x p(x, y)”. On écrit parfois, par économie, “’x, y, p(x, y)”.


Non-commutativité des quantificateurs di�érents – Attention, lorsqu’on écrit plusieurs quanti-ficateurs à la suite les uns des autres, ceux qui viennent en n-ième position dépendent de ceux qui lesprécèdent. Changer leur position change complètement le sens de la formule.

Pour s’en convaincre, considérer, par exemple, le prédicat P (x, y) :“x a le numéro de téléphone de y”,puis interprétrer les propositions suivantes :

(p1) ’x ’y P (x, y) (p2) ’x ÷y P (x, y) (p3) ÷y ’x P (x, y) (p4) ÷y ’x P (y, x)

Un exemple – La notion de continuité d’une fonction f : R æ R en a œ R est fondamentale en analyse.Cette définition s’énonce formellement de la manière suivante :

’Á œ]0, Œ[ ÷– œ R ’x œ R (|x ≠ a| Æ – =∆ |f(x) ≠ f(a)| Æ Á) .

Comment écrit-on formellement que f n’est pas continue en a ?

3.2.1 Comment réinvestir tout ceci dans les démonstrations mathématiques ?Tout comme le calcul des propositions, dont il est une extension, le calcul des prédicats donne au ma-

thématicien un algorithme de preuve. Toutefois, il est rare que la question d’un exercice soit textuellementla phrase :

Montrer que ’a œ R, ’Á œ]0, Œ[, ÷– œ R, ’x œ R, (|x ≠ a| Æ – =∆ |f(x) ≠ f(a)| Æ Á) .

On vous demandera plutôt de montrer que f est continue sur R, la formule logique ci-dessus étant préci-sément la définition de la continuité de f sur R.

Il est donc absolument fondamental de connaître parfaitement les définitions formelles.

Question 3.2. Réecrire en les formalisant à l’aide des quantificateurs et des connecteurs logiques, lesnotions d’inclusion et d’égalité d’ensembles, d’union et d’intersection de familles d’ensembles, d’injection,de surjection.

Ainsi on peut vous demander de montrer une propriété p dont la définition s’écrie formellement“’x, P (x)”. Pour démontrer p on écrit :ù Soit x [c’est à dire que l’on fait parler x] ..... [on raisonne, et le but est d’arriver à montrer].... doncP (x).ù[On conclut en disant :] On a donc montré (’x, P (x)), donc p.

Si la propriété q à démontrer a pour définition formelle “÷x, Q(x)”, la démonstration demande souventplus d’initiatives. En e�et, ce qu’il faut faire, c’est “construire” le x en question à l’aide de toutes lesvariables libres (ou parlantes) et de toutes les autres données dont on dispose. Au cours de cette démons-tration il convient d’écrire : “on pose x = ...” puis on vérifie que Q(x) est satisfait. On conclut par “on abien montré (÷x, Q(x)), donc q.”

Soulignons toutefois que la manière dont on réussit à définir le x en question afin de pouvoir écrire“posons x = . . .” n’est pas forcément constructive au sens propre. Ce n’est le cas que si toutes lesopérations faites pour y arriver le sont.

3.3 ExercicesLogique propositionnelleExercice 3.1. ⌥ Ecrire les négations des propositions suivantes

(a) (A ou B). (b) (A et non(B)). (c) (non(A ou B)).

Exercice 3.2. ⌥ Ecrire les négations, contraposées et réciproques des implications suivantes :

3.3. EXERCICES 27

non(A) ∆ non(B), non(B) ∆ (non(A) ou C), (A et B) ∆ (C ou D).

Exercice 3.3. ⌥ (Propositions fausses et valeur de vérité d’une implication)1. Chacune des propositions suivantes est-elle vraie ou fausse ?

1 = 2, 1 = 3, (1 = 2) ∆ (1 = 3), 2 + 2 = 4.

2. Montrer, en utilisant la méthode déductive, que (1 = 2) ∆ (1 = 3).3. Montrer de même que (1 = 2) ∆ (2 + 2 = 4).

Exercice 3.4. F Correct ou non ? Utiliser la méthode déductive.1. Je sais que ((P1 et P2) =∆ P3), j’en conclus P1 =∆ P3.2. Je sais que ((P1 ou P2) =∆ P3), j’en conclus P1 =∆ P33. Je sais que (P1 =∆ P3), j’en conclus (P1 ou P2) =∆ P3.4. Je sais que (P1 =∆ P3), j’en conclus (P1 et P2) =∆ P3.

Exercice 3.5. ⌥ Compléter avec il faut, il su�t ou il faut et il su�t, puis écrire la proposition en utilisantune implication.

1. Soit n œ Z. Pour qu’il existe m appartenant à Z tel que m2 = n, · · · que n soit positif ou nul.2. Soit x œ R. Pour qu’il existe t appartenant à R tel que t2 = x, · · · que x soit positif ou nul.3. Pour qu’un quadrilatère soit un carré, · · · que ses diagonales soient perpendiculaires.4. Soit f : R æ R une fonction dérivable. Pour que f soit strictement croissante,· · · que f Õ(x) > 0

pour tout x appartenant à R.

Exercice 3.6. W Conditions nécessaire et suffisante.

Soient a et b deux entiers. Compléter les phrases suivantes par ni nécessaire ni su�sante, nécessaire,su�sante ou nécessaire et su�sante.

1. Le fait que ab soit impair est une condition .......................................... pour que a + b soit pair.2. Le fait que a + b soit impair est une condition .......................................... pour que ab soit pair.

Logique des prédicats, quantificateursExercice 3.7. ⌥(négation du OU et du ET) Soit x un réel. Nier les propositions suivantes :

1. x = 1 ou x = ≠1.2. 0 Æ x Æ 1 (ce qui veut dire par définition : 0 Æ x et x Æ 1).3. x = 0 ou (x2 = 1 et x Ø 0).

Exercice 3.8. (Contraposées) Écrire la contraposée des implications suivantes.1. P1(n) : n est premier ∆ n = 2 ou n est impair.2. P2(x, y) : xy ”= 0 ∆ (x ”= 0 et y ”= 0.)3. P3(x, y) : x ”= y ∆ [(x + 1)(y ≠ 1) ”= (x ≠ 1)(y + 1)].

Montrer que P1(n) est vraie pour tout n œ N, et que P2(x, y) et P3(x, y) sont vraies pour tout (x, y) œ R2.

Exercice 3.9. Montrer que pour tout (x, y) œ R2, les propriétés suivantes sont vraies :1. si x2 + y2 Æ 1 alors x Æ 1 et y Æ 1.2. si x œ [≠1, 1] et y œ [≠1, 1] alors x3 + y3 Æ 3.3. si x2 + 2x Ø 0 alors x Ø 0 ou x Æ ≠2.4. si x Ø 1 ou x Æ ≠1 alors x2 Ø 1/4.5. si xy Ø 1 alors x Ø 1 et y Ø 1.6. Si x Ø ≠2 alors x2 + 2x Ø 0.

Exercice 3.10. ⌥ (compréhension et négation d’implications)Dire si les propositions suivantes sont vraies ou fausses, et les nier.


1. Pour tous réels x, si x Ø 3, alors x2 Ø 5.2. Pour tout entier naturel n, si n > 1, alors n Ø 2.3. Pour tous réels x, si x > 1, alors x Ø 2.4. Pour tous réels x, x2 Ø 1, est équivalent à x Ø 1.

Mêmes questions en remplaçant “Pour tous réels“ par “Il existe un réel”, et “Pour tout entier naturel”par “Il existe un entier naturel”.

Exercice 3.11. 1. Écrire en utilisant le langage formel les phrases suivantes :(a) Le carré de tout nombre réel est positif.(b) Un nombre entier divisible par 10 est divisible par 5.(c) Il existe un nombre impair divisible par 2.(d) Le produit de deux nombres réels est positif si et seulement s’ils sont de même signe.(e) Les deux seules solutions de l’équation x2 ≠ 5x + 6 = 0 sont 2 et 3.

2. Les propositions précédentes sont-elles vraies ?

Exercice 3.12. W Quantificateurs.

Les propositions suivantes sont-elles vraies ou fausses ?1. ’x œ R, ÷y œ Z, |x ≠ y| < 1.2. ÷x œ Z, ÷y œ R, |x ≠ y| < 1/2.3. ÷x œ R, ’y œ Z, |x ≠ y| > 1.

Exercice 3.13. ⌥ (ordre des quantificateurs, importance de l’ensemble auquel appartiennent les éléments)Les propositions suivantes sont-elles vraies ou fausses ?1. Pour tout entier naturel n, il existe un réel x tel que x > 2n.2. Il existe un réel x tel que, pour tout entier naturel n, x > 2n.3. Pour tout réel x, pour tout réel y, si x2 = y2 alors x = y.4. Pour tout réel positif x, pour tout réel positif y, si x2 = y2 alors x = y.

Exercice 3.14. ⌥ (compréhension d’énoncés avec quantificateurs, importance de l’ordre). A l’université X.il y a trois étudiants : Alice, Bernard et Cécile et quatre matières : méthodologie, calculus, programmationet anglais. Les résultats des étudiants sont les suivants :

méthodologie calculus programmation anglais moyenneAlice 12 9 18 13 13

Bernard 18 15 6 13 13Cécile 9 17 13 13 13

Soit E = {Alice, Bernard, Cécile} l’ensemble des étudiants. Soit F = {méthodologie, calculus, pro-grammation, anglais} l’ensemble des matières. Pour tout x dans E et tout y dans F , on désigne par P (x, y)l’expression : “l’étudiant x a la moyenne (10 ou plus) dans la matière y”. Oralement, exprimer en françaiscourant les propositions suivantes. Justifier si elles sont vraies ou fausses.

1. ’x œ E, ’y œ F , P (x, y)2. ÷x œ E, ÷y œ F , P (x, y)3. ÷x œ E, ’y œ F , P (x, y)4. ’y œ F , ÷x œ E, P (x, y)5. ÷y œ F , ’x œ E, P (x, y)6. ’x œ E, ÷y œ F , P (x, y).Par exemple, la première proposition se lit “Pour tout élément x de E, pour tout élément y de F , x

a la moyenne dans la matière y”. En français courant, on dirait “Tous les étudiants ont la moyenne danstoutes les matières”. C’est faux, puisque Bernard n’a pas la moyenne en programmation.

3.3. EXERCICES 29

Exercice 3.15. F Soient A, B, I, E, F, Ai, des ensembles et f : E æ F une application. Relier la notionà sa définition formelle.

1. A µ B a. ’x x œ A ≈∆ x œ B.2. A = B b. ’x x œ A =∆ x œ B.

3.€

iœI

Ai c. {x, ’i œ I x œ Ai}.

4.‹

iœI

Ai d. {x, ÷i œ I x œ Ai}.

5. f est injective e. ’x, xÕ œ E f(x) = f(xÕ) =∆ x = xÕ.6. f est surjective f. ’y œ F, ÷x œ E, y = f(x).7. pour A µ E, f(A) g. {y œ F, ÷x œ A, f(x) = y}.8. pour B µ F, f{≠1}(B) h. {x œ E, f(x) œ B}.

i. {f(x), x œ A}.

Exercice 3.16. W Négation.

Soient deux fonctions f : R ◊ R æ R et g : R ◊ R æ R. Ecrire la négation des propositions suivantes.1. ’x Æ 0, ’y œ R, f(x, y) = 0 ou g(x, y) = 0.2. ÷x œ R, ’y > 0, f(x, y) Æ 0 ∆ g(x, y) > 0.

Exercice 3.17. 1. Traduire en langage ordinaire les phrases logiques suivantes.(a) (’n œ N)(÷m œ N) m > n. (b) (÷m œ N)(’n œ N) m > n.(c) (’x œ Q)(’z œ Q)(÷y œ Q) x < y < z. (d) (’n œ N) [n > 3 ∆ n > 6].(e) (’n œ N)(÷m œ N) m Æ n. (f) (’n œ N)(÷p œ N) n = 2p + 1.(g) (’x œ R) x < 2 ∆ x2 < 4.

2. Écrire en utilisant le langage de la logique la négation de chacune des propositions précédente.3. Parmi les propositions et leurs négations, lesquelles sont vraies, lesquelles sont fausses ? (Justifier)

Exercice 3.18. Soit f1, f2 et f3 trois fonctions de R dans R. Pour chacune des propositions suivantes,écrire sa négation. Illustrer chaque propriété et sa négation par un graphique.

1. (’i œ {1, 2, 3})(÷a œ R) fi(a) = 1.

2. (÷i œ {1, 2, 3})(’a œ R) fi(a) = 1.

3. (÷a œ R)(’i œ {1, 2, 3}) fi(a) = 1.

4. (’a œ R)(÷i œ {1, 2, 3}) fi(a) = 1.

Exercice 3.19. F Soit (un)nœN une suite de nombres réels.Quelles sont les négations des assertionssuivantes ?

1. La suite (un)nœN est croissante.2. La suite (un)nœN est décroissante.3. La suite (un)nœN est monotone4. La suite (un)nœN est bornée.5. La suite (un)nœN tend vers +Œ.

Exercice 3.20. F Soit f une fonction réelle définie sur un intervalle I. Ecrire en langage formel lespropositions suivantes :

1. f est strictement croissante sur I.2. f est strictement monotone sur I.3. f n’est pas strictement croissante sur I.

Exercice 3.21. (raisonnement par l’absurde)1. En raisonnant par l’absurde, montrer que si un entier q > 1 divise l’entier n > 0, alors q ne divise

pas n + 1.

2. On note P l’ensemble des nombres premiers. On suppose que P est fini, il existe donc p1, ..., pn telsque P = {p1, ..., pn}. Montrer que pour tout i, pi ne divise pas p1 · · · pn + 1.


3. Conclure.

Exercice 3.22. Montrer que si p est un nombre premier alors Ôp n’est pas rationnel.

Chapitre 4

Relations

Soient E et F deux ensembles non vides. Une relation binaire R de E dans F est une partie de E ◊ F .On note xRy si (x, y) œ R.

Par exemple E est l’ensemble de personnes vivant en France et F est l’ensemble des nombres à 10chi�res. Pour x œ E et y œ F on dit que xRy lorsque x a pour numéro de téléphone y. On voit toutde suite que la relation R n’est pas forcément surjective à gauche : il peut y avoir une personne sansnuméro de téléphone. Elle n’est pas non plus surjective à droite, ni injective à droite ou à gauche, car toutnuméro à 10 chi�res n’est pas forcément a�ecté, il peut y avoir des personnes ayant plusieurs numéros detéléphones ou des numéros correspondants à plusieurs personnes.

Nous allons nous intéresser plus spécifiquement à des relations binaires sur un ensemble, c’est à dired’un ensemble E dans lui-même. Un exemple de relation R sur l’ensemble E des personnes peut être définipar xRy si x possède le numéro de téléphone de y. On voit bien que les propriétés de

— réflexivité : pour tous x , xRx,— symétrie : pour tous x, y, si xRy alors yRx,— transitivité : pour tous x, y, z, si xRy et si yRz alors xRz,

sont des propriétés intéressantes. Si elles sont satisfaites toutes les trois, la relation est une relationd’équivalence.

4.1 Relations d’équivalenceUne relation binaire R sur l’ensemble non vide E (c’est à dire de E dans E) est une relation d’équi-

valence si elle est(i) réflexive : ’x œ E, xRx,(ii) symétrique : ’x, y œ E, xRy =∆ yRx,(iii) transitive : ’x, y, z œ E, (xRy et yRz) =∆ xRz.

L’exemple fondamental est le suivant. Soit E un ensemble non vide et A (que l’on peut toujoursécrire {Ai, i œ I}) une partition de E. La relation R définie par

xRy ssi ÷A œ A, x, y œ A, (autrement dit (÷i œ I, x, y œ Ai)) (4.1)

est une relation d’équivalence (on pourra penser que E est l’ensemble des étudiants de l’amphi, partitionnéen classes de TD ; deux étudiants sont en relation s’ils sont dans la même classe de TD).

La congruence modulo n : Soit n œ Nú. On définit sur Z la relation de congruence modulo n notée ©mod (n) par

a © b mod (n) ssi n divise (a ≠ b) (4.2)

31

32 CHAPITRE 4. RELATIONS

La relation d’équipotence : On définit la relation d’équipotence © définie sur n’importe quelle familled’ensembles E entre deux ensembles quelconques A et B par

A © B ssi il existe une bijection f : A æ B (4.3)

C’est une relation d’équivalence sur les ensembles. Si A est équipotent à B on dit aussi que A et B ontmême cardinal.

La relation “ont la même image par f” : Soit f : E æ F une application. La relation définie surE par

’x, y œ E, xRf y ssi f(x) = f(y) (4.4)est une relation d’équivalence sur E.

Classe d’équivalenceSoit E un ensemble muni d’une relation d’équivalence R. Soit a œ E. La classe de a, notée a est la

partie de E définie par a = {x œ E, xRa}.

Lemme 4.1. F Pour tout a, b œ E on a : a = b ssi aRb.

La proposition ci-dessous indique que les classes d’équivalence sont soit identiques soit disjointes.

Proposition 4.2. F ’a, b œ E si a fl b ”= ÿ, alors a = b.

Question 4.1. Soit f : E æ F une application, et Rf la relation d’équivalence sur E définie par (4.4).Pour x œ E, déterminer x la classe d’équivalence de x à l’aide de f{≠1}.

Ensemble quotientSoit E un ensemble non vide muni d’une relation d’équivalence R. L’ensemble quotient de E par R,

noté E/R, est l’ensemble dont les éléments sont les classes d’équivalence pour R.

E/R = {x, x œ E}.

Quel nom donner à une classe ? Vu la manière dont l’ensemble quotient est défini, on n’a pas donnéun nom unique aux éléments de E/R. Prenons l’exemple de la relation “est dans le même TD” qui est unerelation d’équivalence sur l’amphi. Si Alice, Bernard et Chloé sont dans le même TD, ce TD s’appelle aussibien le TD d’Alice que le TD de Bernard ou celui de Chloé, et bien qu’il porte des noms di�érents, c’esttoujours bien le même TD ! Comment faire pour qu’un TD donné porte un seul nom, bien déterminé ?Une possibilité est d’élire un délégué par TD, par exemple Chloé dans notre cas, et de décider que leTD s’appelle le TD de Chloé. On peut aussi carrement décider de nommer ce TD “Chloé”. Bien sûr ilfaudra ensuite comprendre, lorsqu’on parle de Chloé, s’il sagit de l’étudiante ou de son TD. Le contexteest normalement là pour lever toute ambig’uité.

Question 4.2. Décrire Z/nZ, l’ensemble quotient pour la relation de congruence modulo n ?

Dans l’exemple fondamental, E/R = A. En particulier l’ensemble quotient de l’amphi par la relation“est dans le même TD” est l’ensemble des classes de TD. Ainsi E/R est une partition de E. Le théorèmesuivant montre que c’est toujours le cas.

Théorème 4.3. F Soit E un ensemble non vide et R une relation d’équivalence sur E. Alors E/R ={x, x œ E} forme une partition de E.

De plus la relation définie par cette partition est bien la relation R. C’est en cela que l’exemplefondamental porte bien son nom !

Applications passant au quotientEtant donné une relation R sur un ensemble E. On cherche à savoir sous quelle condition une appli-

cation f : E æ F peut passer au quotient, c’est à dire définir une application f : E/R æ F et qui portela même information.

4.2. RELATIONS D’ORDRE 33

Un exemple instructif Disons, sans perdre beaucoup de généralité, que E est l’ensemble les étudiantsde l’amphi et que la relation R est la relation “sont dans le même TD”. On cherche à savoir à quellecondition une application définie sur E ne permet pas de définir une application sur l’ensemble E/R desTDs qui dise la même chose. Regardons quelques exemples.

- Si on associe à chaque étudiant sa note au dernier contrôle de méthodo, on définit bien une applicationf : E æ [0, ..., 20]. Mais on ne voit pas comment fabriquer une application f de l’ensemble des classes deTDs dans [0, ..., 20] et qui dise la même chose. Pour le TD d’Adèle, Bernard et Chloé, quelle note choisir ?Celle d’Adèle, celle de Bernard ou de Chloé ? On dit que f ne passe pas au quotient.

- Maintenant, si à chaque étudiant on associe par exemple le nom de son professeur de TD en méthodo,on obtient alors une application g de E dans l’ensemble P des professeurs, et on peut définir aussil’application qui à une classe de TD associe un professeur de TD en méthodo. Cette nouvelle applicationdit la même chose que l’application g. On dit que cette nouvelle application est l’application quotient deg et on la note g : E/R æ P .

On voit clairement qu’une application sur E passe au quotient si elle est constante sur chacun desTDs. Plus généralement :

Proposition 4.4. Soit E un ensemble non vide muni d’une relation d’équivalence R. Une application gde E dans un ensemble F passe au quotient si et seulement si

’x, y œ E, xRy =∆ g(x) = g(y)

et l’application quotient de g par R est l’application notée g : E/R æ F définie par g(x) = g(x) pour toutx œ E.

Question 4.3. Soit E un ensemble non vide muni d’une relation d’équivalence R.— Trouver une condition sur une loi de composition interne (c’est-à-dire une application F : E ◊E æ

E) pour qu’elle passe au quotient ?— Même question pour une relation L sur E.

Autour de la relation “ont la même image par f”Proposition 4.5. Soit f : E æ F et on munit E de la relation Rf “a la même image par f”. Montrerque f passe au quotient, et vérifier que f : E/Rf æ F est injective et qu’elle est bijective sur f(E).

On a déjà vu que toute relation d’équivalence peut être vue comme définie par une partition, lapartition de ses classes d’équivalence. On va voir maintenant que toute relation déquivalence R sur Epeut être vue également comme une relation du type “ont la même image par f”.

Proposition 4.6. Toute relation d’équivalence R sur E peut s’écrire comme une relation “a la mêmeimage par f” pour une certaine application f .

Il faut donc définir un ensemble d’arrivée et une application f de E sur cet ensemble de telle manièreque la relation R soit identique à la relation Rf “ont la même image par f”.

Question 4.4. Peut-on choisir F = E/R ? Comment définir f ? Vérifier ensuite que R est bien la mêmerelation que Rf . Y a-t-il d’autres choix possibles pour F ?

4.2 Relations d’ordreUne relation binaire R sur E (c’est-à-dire de E dans E) est une relation d’ordre si elle est

(i) réflexive : ’x œ E, xRx,(ii) antisymétrique : ’x, y œ E, (xRy et yRx) =∆ x = y,(iii) transitive : ’x, y, z œ E, (xRy et yRz) =∆ xRz.

Une relation d’ordre est souvent notée Æ. Si Æ est une relation d’ordre sur E on dit que (E, Æ) est unensemble ordonné.


Ordre total ou partiel

Un ordre Æ sur E est total, si deux éléments quelconques peuvent toujours se comparer :

’x, y œ E, (x Æ y) ou (y Æ x).

Si un ordre n’est pas total, on dit qu’il est partiel.

Question 4.5. La relation Ø est-elle une relation d’ordre sur R ? Et qu’en est-il de < ?

Exemple 4.1. 1. La relation divise, notée “|”, définie sur Nú par (a | b ssi il existe un entier n tel queb = na), est une relation d’ordre sur Nú.

2. Soit E un ensemble. La relation d’inclusion est une relation d’ordre sur l’ensemble P(E) des partiesde E.

Majorant, plus grand élément, élément maximal

Soit (E, Æ) un ensemble ordonné et soit A une partie de E.Un élément m de E est un majorant de A s’il est plus grand que tous les éléments de A :

m est un majorant de A si (’a œ A, a Æ m).

Si A possède un majorant, on dit que A est majoré :

A est majoré si (÷m œ E, ’a œ A, a Æ m).

Si m appartient à A et si m est un majorant de A, on dit que m est le plus grand élément de A :

m est le plus grand élément de A si ((m œ A) et (’a œ A, a Æ m)).

Un élément m de E est un élément maximal de A s’il appartient à A et si personne n’est plus grand quelui :

m est un élément maximal de A si ((m œ A) et (’a œ A, ( a Ø m =∆ a = m))).

On définit de même les notions de minorant, plus petit élément, élément minimal.

Bon ordre

Un ensemble (E, Æ) est bien ordonné, si toute partie non vide de E admet un plus petit élément.

Proposition 4.7. Tout ensemble bien ordonné est totalement ordonné.

Diagramme de Hasse pour les ensembles finis

Le diagramme de Hasse est une représentation visuelle très pratique d’un ordre sur un ensemble fini.si x Æ y on va dessiner x en dessous de y en le liant par une arrête. On obtient ainsi un graphe orientésuivant la verticale (la flèche est en générale sous-entendue).

Pour ne pas charger le shémas on ne représentepas toute la relation d’ordre mais uniquement sa ré-duction réflexive transitive : si x Æ y Æ z on nereprésente que les arrêtes entre x et y et entre y et zmais pas celle entre x et z. On ne représente pas nonplus l’arrête de réflexivité qui est sous-entendue.

Dans le diagramme ci-dessous on a trois élémentsmaximaux et un un élément minimal qui est aussiun minorant.

4.3. EXERCICES 35

4.3 ExercicesExercice 4.1. ⌥ Soit X = {1, 2, 3, 4}. Sur X on considère la relation R dont le graphe est l’ensemble Gsuivant :

G = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 4), (3, 4), (4, 2), (4, 3), (4, 4)}.

Cette relation est-elle réflexive ? symétrique ? antisymétrique ? transitive ?

Exercice 4.2. ⌥ Soit X = {0, 1, 2}. Les graphes suivants définissent-ils une relation d’équivalence surX ? Pourquoi ?�1 = {(0, 0), (0, 1), (1, 0), (1, 1)} ; �2 = {(0, 0), (0, 1), (1, 0), (1, 1), (2, 2)} ;�3 = {(0, 0), (0, 1), (1, 0), (1, 1), (1, 2), (2, 2)} ; �4 = {(0, 0), (0, 1), (1, 0), (1, 1), (1, 2), (2, 1), (2, 2)} ;�5 = {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)}. 1

Exercice 4.3. ⌥ Dans chacun des cas suivants, la relation définie sur C est-elle ou non une relationd’équivalence ? Indiquez pourquoi. 2

1. ’z, zÕ œ C, zR1zÕ ≈∆ |z| = |zÕ| ;2. ’z, zÕ œ C, zR2zÕ ≈∆ |z|/zÕ = 1 ;3. ’z, zÕ œ C, zR3zÕ ≈∆ ez = ezÕ ;4. ’z, zÕ œ C, zR4zÕ ≈∆ |z ≠ zÕ| = 1 ;

Exercice 4.4. F Soient E et F deux ensembles et f : E æ F une application. On définit la relation Rf

sur E en posant, pour tous éléments x, y de E :

xRf y ≈∆ f(x) = f(y).

Montrer que R est une relation d’équivalence.

Exercice 4.5. ⌥ Dans chacun des cas suivants la relation R, définie sur N, est-elle ou non une relationd’équivalence ? Indiquez pourquoi. 3

1. ’n, m œ N, nRm ≈∆ n|m ;2. ’n, m œ N, nRm ≈∆ n2 = m2 ;3. ’n, m œ N, nRm ≈∆ n2 ≠ m2 = 2nm + 2n ;4. ’n, m œ N, nRm ≈∆ n2 + m2 = 2nm.

Exercice 4.6. ⌥ Soit E un ensemble non vide et x un élément fixé de E. On considère la relation Rdéfinie sur P(E) successivement par

1. ’A, B œ P(E), ARB ≈∆ A = B ;2. ’A, B œ P(E), ARB ≈∆ A µ B ;3. ’A, B œ P(E), ARB ≈∆ A fl B = ÿ ;4. ’A, B œ P(E), ARB ≈∆ x œ A fi B ;

Pour chacune des relations préciser si elle est réflexive, symétrique, antisymétrique, transitive, totale.

Lesquelles sont des relations d’équivalences ? des relations d’ordre ?

Exercice 4.7. Soit P l’ensemble des nombres premiers strictement supérieurs à 2. On considère sur cetensemble P la relation R définie par :

pRq ≈∆ p + q

2 œ P.

Cette relation est-elle réflexive ? symétrique ?Déterminer 3 = {n œ P, n Æ 20, 3Rn} et 7 = {n œ P, n Æ 20, 7Rn}. La relation est-elle une relationd’équivalence ?

1. oui pour �1, �2 et �5.

2. seules 1,3 sont des relations d’équivalence.

3. seules 2 et 4 sont relations d’équivalence.


Exercice 4.8. F Soit R une relation d’équivalence sur un ensemble X. Si a un élément de X on note ala classe d’équivalence de a. Montrer que

’a, b œ X, aRb ≈∆ a = b.

Exercice 4.9. On définit une relation R sur R en posant, pour tous réels x et y :

xRy ≈∆ x2 ≠ y2 = x ≠ y.

1. Montrer que R est une relation d’équivalence.2. Déterminer et représenter dans R2 les classes d’équivalence des réels 0, 1, 1/2.

Exercice 4.10. On dit qu’une relation R sur un ensemble X est circulaire lorsque pour tous a, b et c deX :

(aRb et bRc) =∆ cRa.

1. Montrer qu’une relation est une relation d’équivalence si et seulement si elle est réflexive et circu-laire.

2. Donner un exemple de relation circulaire qui ne soit pas une relation d’équivalence.

Exercice 4.11. FF Soit n œ Nú. On définit une relation de congruence modulo n, notée “© mod (n)”sur Z en posant, pour tous entiers a, b

a © b mod (n) ≈∆ n divise a ≠ b.

1. Montrer que © mod (n) est une relation d’équivalence.2. Montrer que a © b mod (n) ssi a et b ont le même reste dans leur division euclidienne par n.3. Déterminer les classes d’équivalence 0 et 1 de 0 et de 1.4. On fixe n = 6. Décrire les classes d’équivalences de Z/6Z.5. Montrer que pour tout a, b, aÕ, bÕ œ Z, si a © aÕ mod (6) et b © bÕ mod (6) alors (a + b) © (aÕ + bÕ)

mod (6) et (ab) © (aÕbÕ) mod (6).6. En déduire que l’on peut définir des opérations internes ü et ¢ sur Z/6Z par a ü b = a + b et

a ¢ b = a ◊ b. Ecrire les tables de ces lois ?7. Mêmes questions pour n = 5.

Exercice 4.12. Sur R2, on définit E par :

(x, y)E(xÕ, yÕ) lorsque x2 + y2 = xÕ2 + yÕ2.

Montrer que E est une relation d’équivalence sur R2. Décrire la partition de R2 par les classes d’équivalencepour E .

Exercice 4.13. FF Dans N, on définit une relation π en posant, pour tous m, n de N :

m π n lorsqu’il existe k œ Nú tel que n = km.

1. Montrer que π est une relation d’ordre partiel sur N.2. Soit A = {4, 5, 6, 7, 8, 9, 10}. Pour π, A possède-t-il un plus grand élément ? un plus petit élément ?

des éléments maximaux ? des éléments minimaux ? Lorsque la réponse est oui, précisez les. (Onpourra tracer le diagramme de Hasse).

3. L’ensemble Nú possède-t-il un plus grand élément ? Un plus petit élément ?4. Qu’en est-il pour N ?5. Pour π, quels sont les éléments minimaux de N ?

Exercice 4.14. On définit dans Nú une relation π en posant, pour tous x, y de Nú :

x π y ≈∆ ÷n œ Nú, y = xn.

Montrer que π est une relation d’ordre sur Nú.

4.3. EXERCICES 37

Exercice 4.15. Soient E et F deux ensembles et f : E æ F une application. Soit S une relation sur F .On définit une relation R sur E en posant, pour tous éléments x, y de E :

xRy ≈∆ f(x)Sf(y).

1. Montrer que si S est une relation d’équivalence, alors R est une relation d’équivalence.2. Montrer que si S est une relation d’ordre et f est injective, alors R est une relation d’ordre.

Exercice 4.16. Soit E un ensemble et R une relation réflexive et transitive sur E.1. Montrer que la relation E définie sur E par :

aEb ≈∆ (aRb et bRa)

est une relation d’équivalence.2. On définit sur E/E une relation π par :

A π B lorsqu’il existe a œ A et b œ B tels que aRb.

Montrer que π est une relation d’ordre sur E/E .

Exercice 4.17. (ordre lexicographique)Soit (E, Æ) et (F, Æ) des ensembles totalement ordonnés.1. FF On considère sur E◊F la relation définie de la manière suivante. Pour a = (a1, a2), b = (b1, b2)

dans E ◊ FaR2b ≈∆ (a1 < b1) où (a1 = b1 et a2 Æ b2).

Montrer que R2 définit un ordre total sur E ◊ F .2. Soit n > 2. On définit par récurrence la relation Rn sur En de la manière suivante. Pour a =

(a1, a2, ..., an), b = (b1, b2, ..., bn) dans En

aRnb ≈∆ (a1 < b1) où (a1 = b1 et (a2, ..., an)Rn≠1(b2, ..., bn).

Vérifier qu’il s’agit bien d’un d’ordre total.3. On considère l’ensemble X des mots finis sur E c’est à dire :

X = {x, ÷n œ Nú, x = (x1, · · · , xn) œ En} =€

nœNú

En

et on définit la relation S sur X de la manière suivante. Soit a = (a1, · · · , ap), b = (b1, · · · , bq) dansX, on note m le plus petit des deux entiers p et q,

aSb ≈∆ ((a1, ..., am)Rm(b1, ..., bm) et (a1, ..., am) ”= (b1, ..., bm))ou ((a1, ..., am) = (b1, ..., bm) et m < q (c’est-à-dire p < q)).

Montrer que S définit un ordre total sur X.

Exercice 4.18. Soit E un ensemble et A une partie de E. On définit une relation R sur l’ensemble P(E)des parties de E en posant, pour tous ensembles X, Y éléments de P(E) :

XRY ≈∆ A fl X = A fl Y.

1. Montrer que R est une relation d’équivalence sur P(E).2. Expliciter les classes ?, E et A.3. Soit X un élément de P(E). Montrer que si B = A fl X, B est l’unique élément de X qui soit

contenu dans A.4. Pour tout X dans P(E)/R on pose f(X) = A fl X. Montrer que f elle bien une application et

qu’elle est bijective sur P(A).


Chapitre 5

L’ensemble N, ensembles finis etcardinaux

L’ensemble des entiers naturels N est sans doute le premier ensemble de nombres qui vient à l’esprit.C’est lui qui permet de compter des objets. Il est muni de deux opérations + et ◊ et de la relation d’ordreÆ. Il est aussi muni de la division euclidienne. Beaucoup de choses peuvent être dites sur N, et beaucoupde choses restent à dire.

Mais quelles propriétés caractérisent cet ensemble ? Pour répondre à cette question, interressons nousà la propriété de récurrence. Qu’est-ce que cette propriété ? Quand on veut démontrer un grand nombre depropositions, disons p0, p1,.....p1000 plutôt que de faire 1001 démonstrations, on peut parfois n’en faire quedeux : d’abord on montre une propriété initiale p0, puis on montre une propriété d’hérédité : pour tout n,si pn, alors pn+1. On a donc démontré pn quel que soit l’élément n dans l’ensemble I = {0, .., 1000}. Maispourquoi s’arrêter à 1000 ? On voit bien qu’on a alors démontré la propriété pour tous les entiers.

Quels sont les ensembles I qui permettent des démonstrations par récurrence ? Il faut pouvoir initialiser,passer au suivant, et enfin être sur que si la démonstration d’une propriété a été initialisée, et l’héréditéa été montrée, alors toutes les propriétés pi sont vraie pour i dans I.On peut montrer qu’un tel ensemble, s’il est infini, est nécessairement en bijection avec N.

Pour construire N à partir de la théorie des ensembles, G. Peano (1858 –1932) a proposé de postuleraxiomatiquement l’existence d’un ensemble N, d’un élément 0, et d’une application S : N æ N tels que :

1. 0 œ N.2. S est bijective sur Nú = N \ {0}.3. ’P µ N, si (0 œ P ) et si (’n œ N, n œ P ∆ S(n) œ P ) alors P = N.

L’application S est appelée l’application “successeur” : pour tout n œ N, S(n) est appelé successeur de n.

A partir de ces trois axiomes uniquement, on peut construire les opérations + et ◊ et l’ordre sur Net vérifier toutes les propriétés habituelles concernant ces opérations. Cette construction est proposée enProblème en annexe.

5.1 Propriétés fondamentales de NThéorème 5.1. F (Théorème fondamental de N)

1. Toute partie non vide de N possède un plus petit élément.2. Toute partie non vide majorée de N possède un plus grand élément.

39

40 CHAPITRE 5. L’ENSEMBLE N, ENSEMBLES FINIS ET CARDINAUX

Démonstration. Soit A une partie non vide de N. Si 0 œ A, c’est fini. Supposons que 0 /œ A et supposons parl’absurde que A ne possède pas de plus petit élément. Considérons l’ensemble B = {n œ N, ’a œ A, n < a}des minorants de A qui ne sont pas dans A. On a 0 œ B et si n est dans B alors, n + 1 ne peut être dansA sinon ce serait le minimum de A. Ainsi n + 1 œ B. Par récurrence B = N et A est vide, ce qui estcontradictoire.

Théorème 5.2. (Division euclidienne) Soit b œ Nú. Pour tout a œ N, il existe des uniques entiers q, rdans N tels que a = bq + r et tels que 0 Æ r Æ b ≠ 1.

Le nombre q est appelé le quotient de la division euclidienne de a par b et r le reste.

La question de la représentation des nombres est un point important du début de l’histoire des ma-thématiques. Quels symboles (ou chi�res) utilise-t-on pour coder les nombres ? Autrement dit, commentles chi�re-t-on ? C’est également une question importante en informatique.

Théorème 5.3. Soit b un entier supérieur ou égal à 2, appelé la base. Pour tout entier n œ Nú, il existeun unique entier p œ N et des uniques entiers a0, ..., ap dans {0, ...., b ≠ 1} tels que ap ”= 0 et tels que

n = bpap + bp≠1ap≠1 + ... + b0a0.

On note [n]b = apap≠1...a0b, et on dit que l’on a écrit n en base b.

5.2 Cardinaux d’ensembles finisOn dit que deux ensembles E et F sont équipotents et on note E © F s’il existe une bijection de

E sur F . Il est facile de voir que © possède les propriétés de réflexivité, de symétrie et de transitivité.Cependant dire qu’il s’agit d’une relation d’équivalence entre ensembles est un peu délicat. En e�et, onvoudrait la définir sur l’ensemble de tous les ensembles, qui malheureusement n’existe pas. Puisqu’un telensemble n’existe pas, on ne peut donc pas le partitionner en classe d’équivalence pour cette relation. Enrevanche, on peut considérer cette relation sur n’importe quel ensemble d’ensembles.

Etude de la relation d’équipotence sur les ensembles {1, ..., n} La première chose à vérifier estque pour tous nombres entiers n et m, s’il existe une bijection de {1, ..., n} dans {1, ..., m}, alors n = m.On va commencer par comparer n et m dans le cas de l’existence d’une injection, d’une surjection et d’unebijection entre les deux ensembles.

Proposition 5.4. 1. ’n, m œ N. S’il existe une injection de {1, ..., n} dans {1, ..., m} alors n Æ m.2. ’n, m œ N. S’il existe une surjection de {1, ..., n} sur {1, ..., m} alors n Ø m.3. ’n, m œ N. S’il existe une bijection de {1, ..., n} sur {1, ..., m} alors n = m.

Le troisième point permet vérifier que

Corollaire 5.5. Si E est un ensemble et s’il existe un entier n tel que E est en bijection avec {1, ..., n},l’entier n est unique.

Comment fait-on pour compter les éléments d’un ensemble ? On égrène la suite des entiers à partir de1 en associant à nombre à chaque élément de l’ensemble qu’on compte, (c’est à dire qu’on est en train deconstruire une application), en prennent soin de ne pas compter deux fois le même élément (l’applicationdoit être injective) et de compter tous les éléments (l’application doit être surjective). Le nombre d’élémentsde l’ensemble correspond au nombre n pour lequel on s’est arrêté. Le corollaire précédent assure que sil’on compte à nouveau, on retrouvera bien n. On peut donc définir les notions suivantes.

Ensembles finis et cardinal Un ensemble E est fini s’il existe un entier n tel que E est en bijectionavec {1, ..., n}. On dit alors que n est le cardinal de E. Par convention l’ensemble vide est dit fini decardinal 0. Si un ensemble E n’est pas fini, il est dit infini.

Lemme 5.6. Soit E et F des ensembles. Si E et fini et si E © F alors F est fini et Card(E) = Card(F ).

On arrive ensuite à montrer que toute partie de {1, .., n} est finie et a moins de n éléments, et qu’ellen’en a n que si elle lui est égale.

5.2. CARDINAUX D’ENSEMBLES FINIS 41

Lemme 5.7. Soit A une partie de {1, ..., n}. Alors1. L’ensemble A est fini et Card(A) Æ n ;2. Si Card(A) = Card(E), alors A = E.

On arrive enfin à montrer que toute partie d’un ensemble fini donné est finie et, sauf si elle lui estégale, elle a strictement moins d’éléments que l’ensemble considéré. Ce qui s’énonce de la façon suivante :

Proposition 5.8. Soit E un ensemble fini et A une partie de E. Alors1. L’ensemble A est fini ;2. Card(A) Æ Card(E) ;3. Si Card(A) = Card(E), alors A = E.

Remarque 5.1. (Un principe général) Ce résultat peut se généraliser en disant qu’un ensemble quis’injecte dans un autre est plus petit, et aussi qu’un ensemble qui se surjecte sur un autre est plus grand.Dans ce cours on ne démontre ce résultat que dans des cas particuliers. Ainsi :

Proposition 5.9. F Soit f : E æ F une application.1. On suppose F fini et f injective, alors

a. E est fini ; b. Card(E) Æ Card(F ) ; c. si Card(E) = Card(F ), alors f est bijective.2. Si E est fini et si f est surjective, alors

a. F est fini ; b. Card(E) Ø Card(F ) ; c. si Card(E) = Card(F ), alors f est bijective .

En particulier, lorsque E = F , nous obtenons le résultat suivant :

Corollaire 5.10. Soit E un ensemble fini, et f : E æ E. Il y a équivalence entre1. f est injective 2. f est surjective, 3. f est bijective.

Question 5.1. En utilisant l’application n ‘æ n + 1, montrer que N est infini.

Des notations très pratique Dans le cas ou l’on ajoute deux nombre, l’ordre dans la somme ne changepas le résultat. Et ceci reste vrai tout que l’on fait des sommes finies. Toutefois, cette commutativitégénéralisée s’exprime comme une invariance par permutation de l’ordre des termes dans la somme.

Proposition 5.11. Soit (ai)iœI une famille de nombres indexée par un ensemble fini de cardinal n. Pour

toute bijection „ : {1, ..., n} æ I, on définit la somme S(„) =nÿ

k=1a„(k). Cette somme est indépendante de

„, on la noteÿ

iœI

ai, c’est la somme des ai sur l’ensemble fini I.

Cette proposition permet d’obtenir la formule suivante

Si E est fini et A µ E alors, Card(A) =q

xœE 1A(x).

E�ectivement, pour compter les éléments de A, on fait défiler tous les éléments de E un à un et onrajoute un si x est dans A, 0 sinon. Cette notation permet de démontrer très simplement de nombreusesformules

Proposition 5.12. 1. Si A est fini et B µ A, alors Card(A) = Card(B) + Card(A\B).2. Si r est fini et si (Ai)i=1,..,r est une famille finie d’ensembles finis deux à deux disjoints, alors

Card!fiiœ{1,..,r}Ai

"=

rÿ

i=1Card(Ai).

3. Si E est fini et si A = {Ai}iœI est une partition de E alors, I est fini, chaque Ai est fini et

Card(E) =ÿ

iœI

Card(Ai).


On sait aussi calculer des cardinaux d’union non disjointes, mais alors il faut connaitre en plus lescardinaux des diverses intersections

Proposition 5.13. 1. Si A et B sont finis, Card(A fi B) = Card(A) + Card(B) ≠ Card(A fl B).2. Si A, B, C sont finis,

Card(A fi B fi C) = Card(A) + Card(B) + Card(C) ≠ Card(A fl B) ≠ Card(A fl C) ≠ Card(B fl C)+ Card(A fl B fl C).

3. Si r est fini et si (Ai)i=1,..,r est une ensemble fini d’ensembles finis

Card!fiiœ{1,..,r}Ai

"=

rÿ

i=1Card(Ai) ≠

ÿ

(i,j),i<j

Card(Ai fl Aj) + .... + (≠1)r≠1Card(A1 fl ... fl Ar).

Nous allons dresser quelques corollaires du cardinal d’une partition. Rappelons que lorsqu’on a unerelation d’équivalence sur un ensemble E, les classes d’équivalences forment une partition de cet ensemble.Ainsi on obtient :

Corollaire 5.14. Soient E un ensemble fini et R une relation d’équivalence sur E. Alors l’ensemblequotient E/R est fini et

Card(E) =ÿ

aœE/RCard(a)

Etant donné une application f : E æ F , la relation Rf “ont la même image par f”. On sait que f(E)est en bijection avec E/R et que E/R =

Óf{≠1}({y}), y œ f(E)

Ô. Par suite, on obtient le résultat suivant.

Corollaire 5.15. Soit E un ensemble fini et f : E æ F une application, alors f(E) est fini et

Card(E) =ÿ

yœf(E)Card(f{≠1}({y})).

La proposition suivante donne le cardinal de nombreux ensembles finis.

Proposition 5.16. Soient A et B des parties finies de cardinal repectif a et b,1. Card(A ◊ B) = ab, où A ◊ B est le produit cartésien de A par B,2. Card(BA) = ba, où BA est l’ensemble des applications de A dans B,3. Card({f : A æ B injectives}) = b!

(a≠b)! , aussi appelé nombre d’arrangements de A dans B.

4. Card({f : A æ A bijectives}) = a!, les bijections de A sont aussi appelées des permutations.5. Card(P(A)) = 2Card(A), où P(A) est l’ensemble des parties de A.6. Card(Pk(A)) =

!ak

"= a!

k!(a≠k)! , où Pk(A) est l’ensemble des parties à k éléments de A.

Exercice 5.1. 1. Quel est le cardinal de l’ensemble {1, ..., 47} ◊ {≠7, ..., 11} ?2. Quel est le cardinal de l’ensemble {≠7, ≠5, 2, 68}4 ◊ {3, ..., 8}6 ?3. Quel est le cardinal de l’ensemble {(x1, ..., x8) œ {≠1, ..., 8}8, ’i ”= j, xi ”= xj} ?4. Quel est le cardinal de l’ensemble {f : {5, ..., 10} æ {≠17, ≠15, ≠7, ≠5, ≠4, 5, 6, 12, 13}} ?

5.3 DénombrementsDans cette partie du cours, nous allons introduire les notions d’arrangements avec ou sans répétitions et

la notion de combinaisons. Ces notions permettent d’interpréter les cardinaux de la proposition précédente.Fixons E un ensemble de n éléments. Nous allons choisir dans cette ensemble k éléments de di�érentesmanières.

5.3. DÉNOMBREMENTS 43

Arrangements avec répétition Tirage dans l’ordre avec remise de k éléments dans E = {e1, ..., en}de cardinal n.

Représentation mathématique : L’ensemble des arrangements avec répétition de k éléments parmiles n éléments de E = {e1, ..., en} peut se représenter par

1. E{1,...,k} = {f : {1, ..., k} æ E}l’ensemble des applications de {1, ...., k} dans {e1, ..., en}

2. {(x1, ..., xk) œ Ek}l’ensemble des k-uplet d’éléments (non distincts)

Le nombre d’arrangements avec répétition de k parmi n que l’on peut faire vaut nk.

Cette formule peut se comprendre à l’aide d’un arbre des choix successifs, puisque le premier élément estchoisi parmi n éléments , le second parmi n ... et le dernier et k-ième encore parmi n éléments.

Arrangements Tirage dans l’ordre sans remise de k éléments dans E de cardinal n.Exemple : tirage du tiercé dans l’ordre

Représentation mathématique : L’ensemble des arrangements (sans répétition) de k éléments parmiles n éléments de E = {e1, ..., en} peut se représenter par

1. {f : {1, ..., k} æ E, i ”= j =∆ f(i) ”= f(j)}l’ensemble des injections de {1, ...., k} dans {e1, ..., en},

2. {(x1, ..., xk) œ Ek, i ”= j =∆ xi ”= xj}l’ensemble des k-uplet d’éléments distincts de E.

Le nombre d’arrangements de k parmi n que l’on peut faire est noté Akn et vaut :

Akn = n(n ≠ 1)....(n ≠ k + 1) = n!

(n ≠ k)! .

Cette formule peut se comprendre à l’aide d’un arbre des choix successifs, puisque le premier élémentest choisi parmi n éléments, le second parmi (n ≠ 1) ... et le dernier parmi (n ≠ k + 1) éléments.

Combinaison Tirage de k objets parmi un ensemble E = {e1, ..., en} de cardinal n, sans classement.Exemple : le tirage du loto, la main d’un jeu de cartes.

Représentation mathématique : L’ensemble des combinaisons de k éléments parmi les n éléments deE = {e1, ..., en} peut se représenter par

1. Pk(E) = {Ê µ E, Card(Ê) = k},l’ensemble des parties à k éléments de E,

2. Si E est ordonné, {(x1, ...., xk) œ Ek, x1 < ... < xk},c’est-à-dire comme l’ensemble des k-uplets ordonnés de E,

3. {(x1, ..., xn) œ {0, 1}n,qn

i=1 xi = k},puisque k des xi valent 1, les autres 0.

Le nombre de combinaisons de k parmi n est

Card(Pk(E)) =3

n

k

4= Ak

n

k! = n!k!(n ≠ k)! .

Ces nombres sont aussi appelés coe�cients du binôme, ils se lisent k parmi n.

Sur un arbre binaire P, F à n branches le nombre!

nk

"correspond au nombre de chemins de la racines

à l’extrémité comportant exactement k branches de type P .


Formules faisant intervenir les coe�cients binomiaux

On suppose que k, n sont des entiers ; x, y des complexes. On rappelle que :3

n

k

4+

3n

k + 1

4=

3n + 1k + 1

4(formule de Pascal)

Cette formule permet de construire le triangle de Pascal. Remarquons que!

nk

"=

!n

n≠k

".

Triangle de Pascal

Exercice 5.2. Les combinaisons interviennent dansles calculs des cardinaux des ensembles suivants :

1. {Ê œ P({5, ..., 10}), Card(Ê) = 3},2. {(x1, ..., x18) œ {0, 1}6,

q18i=1 xi = 5},

3. {(x0, ..., x7) œ {0, ..., 14}, x0 < ... < x7},4. {(x1, ..., x4) œ N4, x1 + ... + x4 = 6}

5. {(x1, ..., x7) œ {0, 1}7,

3ÿ

i=1xi = 2,

7ÿ

i=4xi =

2},

6.;

(x1, .., x4) œ {a, b, c}4,Card{i, xi = a} = 1,Card{i, xi = b} = 2

<

7. {(x0, ...x7) œ {0, ..., 14}, x0 Æ ... Æ x7},

5.4 Sommes finiesDefinition 5.17. Pour des entiers a et b tels que a Æ b, la somme finie ua + ... + ub s’écrit aussiqb

k=a uk =q

{k, aÆkÆb} uk. Par convention une somme de nombres indexés par l’ensemble vide est nulle.

La variable de sommation, ici k, est muette ou liée, elle varie entre la borne inférieure de sommation,a, et la borne supérieure b. Il faut bien distinguer, d’une part, la variable de sommation et les variablesqui en dépendent et, d’autre part, les constantes et les paramètres.

5.4.1 Sommes usuellesSomme d’une constante F Si a Æ b sont des entiers, alors

qbk=a 1 = b ≠ a + 1. Plus généralement

par linéarité,

si µ est une constante,qb

k=a µ = µ(b ≠ a + 1).

Somme géométrique F Par convention, x0 = 1 pour tout nombre x, même nul.

Pour x ”= 1,nÿ

k=0xk = 1 ≠ xn+1

1 ≠ x= xn+1 ≠ 1

x ≠ 1 .

Pour x = 1, on obtient n + 1, comme somme d’une constante.

Plus généralement si a Æ b et si x ”= 1 on aqb

k=a xk = xa 1≠xb≠a+1

1≠x . Le premier terme de la somme xa

est en facteur, on divise par 1 ≠ x et on multiplie par 1 ≠ xp où p est le nombre de termes de la somme.

Exemple 5.1. Calculerqn

k=0 2k32k+1.

Somme de n premiers entiers, des n premiers carrés, des n premiers cubes F On a

nÿ

k=1k = n(n + 1)

2 ,

nÿ

k=1k2 = n(n + 1)(2n + 1)

6 ,

nÿ

k=1k3 =

3n(n + 1)

2

42.

5.5. A PROPOS DES ENSEMBLES INFINIS 45

Formule du binôme de Newton FF

(x + y)n =nÿ

k=0

3n

k

4xkyn≠k.

Cette formule permet de trouver de nombreuses identités.⇤ En prenant x = y = 1 on obtient 2n =

qnk=0

!nk

"

— En prenant x = 1 et y = ≠1, on obtientqn

k=0(≠1)k!

nk

"= 0.

˙ En prenant y = 1 et en dérivant par rapport à x, puis en fixant x = 1 on obtientqn

k=0 k!

nk

"=

n2n≠1.˚ En prenant y = 1,en intégrant / x, puis en fixant x = 1 on obtient

nÿ

k=0

1k + 1

3n

k

4= 1

n + 1(2n+1≠1).

¸ En développant (1 + x)m(1 + x)n = (1 + x)m+n, et en identifiant les coe�cients du même degré,

on obtient :kÿ

j=0

3m

j

43n

k ≠ j

4=

3m + n

k

4(identité de Vandermonde).

˝ En choisissant m = k = n dans la formule précédente, on obtientnÿ

j=0

3n

j

42=

32n

n

4.

5.4.2 OpérationsChasles (découpage horizontal) Valable uniquement si toutes les bornes sont en ordre croissant ! Si a,b et c sont des entiers vérifiant a Æ b Æ b + 1 Æ c, alors

qck=a uk =

qbk=a uk +

qck=b+1 uk.

Exemple 5.2. Calculerq2n

k=0 |n ≠ k|.

Linéarité Somme de sommes et factorisation par les constantes :qb

k=a(⁄uk + µvk) = (⁄qb

k=a uk +µ

qbk=a vk)


k=0 32k(5k ≠ 3k).

Réindexation Change les deux bornes et l’indice de sommation.


k=0(k + 2)3.

Télescopage Si uk = vk ≠ vk+1, alors la sommeqb

k=a uk est une somme dite télescopique et est égaleà va ≠ vb+1.

Exemple 5.5. En décomposant en éléments simples 1k(k+1) calculer

qnk=1

1k(k+1) .

5.4.3 Sommes doublesOn s’interresse ici par exemple à la double somme

qki=1

qlj=0 ai,j , que l’on peut aussi écrire

q(i,j)œI ai,j ,

où I = {(i, j), 0 Æ i Æ k, 0 Æ j Æ l}. Il s’agit bien d’une somme finie. Sur certains exemples, une des astucespour calculer ces sommes, consiste à inverser les sommes en reparamétrant l’ensemble de sommation.

5.5 A propos des ensembles infinis[La présente section est à la limite du programme]

Rappelons que par définition un ensemble non-vide est dit infini s’il n’est pas fini. On a vu que N n’estpas fini. Ce n’est pas le seul ensemble dans ce cas. Un moyen de démontrer qu’un ensemble est infini estd’utiliser le principe énoncé dans la Remarque 5.1 qui peut se traduire par la proposition suivante.


Proposition 5.18.1. Si un ensemble infini s’injecte dans un ensemble F , l’ensemble d’arrivé F est infini.2. De même si un ensemble E se surjecte sur un ensemble infini, l’ensemble de départ E est infini.

Ainsi, Z, Q, R, C sont infinis.

Ensembles dénombrables Cependant, on peut voir que l’infini de N est le plus petit infini qui soit.C’est un infini sympathique, qu’on appelle l’infini dénombrable.

Definition 5.19. Les ensembles qui sont en bijection avec N sont dit dénombrables. On note ›0 leurcardinal.

L’exercice 2.13 montre que Z et N2 sont dénombrables. On s’attend donc à ce que Q le soit aussi.Pour s’assurer qu’un ensemble infini est dénombrable, on utilise une nouvelle version adéquate de laRemarque 5.1

Proposition 5.20.1. Si un ensemble E s’injecte dans un ensemble dénombrable, l’ensemble de départ est fini ou dénom-brable.2. Si un ensemble dénombrable se surjecte sur un ensemble, l’ensemble d’arrivée est fini ou dénombrable.

Ainsi, d’après l’exercice 2.14, Q est dénombrable.

Proposition 5.21. Une union au plus dénombrable d’ensembles dénombrables est dénombrable.Un produit fini d’ensembles dénombrables est dénombrable.

Ensembles non dénombrables NN, R, P(N) ne sont pas dénombrables, comme le montre un procédédiagonal de Cantor. Toutefois ils sont équipotents, et on note 2›0 leur cardinal. La proposition suivantemontre qu’il existe une infinité d’infinis !

Théorème 5.22. (de Cantor) Pour tout ensemble M , il n’existe pas d’injection de P(M) dans M .Ainsi Card(M) < Card(P(M)).

Démonstration. Supposons qu’il existe une injection f : P(M) æ M . On construit alors une surjection gde M dans P(M) de la manière suivante : si x /œ f(P(M)), on définit g(x) = {x} et si x œ f(P(M)), ondéfinit g(x) = f{≠1}({x}).On pose N = {x œ M, x /œ g(x)}. Clairement N est une partie de M , donc N œ P(M). Comme g estsurjective, il existe x0 œ M tel que g(x0) = N . Alors, de deux choses l’une, soit x0 œ N , soit x0 /œ N . Maischaque cas abouti clairement à une contradiction.On a donc montré par l’absurde qu’il n’existe pas d’injection de P(M) dans M .

A propos de la notationq

iœIai On a vu que cette notation a du sens dans le cas où I est fini : si on

ajoute un nombre fini déléments, la somme reste finie, et l’ordre de la sommation n’a pas d’importance.Passer à une somme infini déléments n’est pas un problème aisé.

Dans le cas où l’on cherche à calculer la somme d’un nombre dénombrable de nombres, disons(ai, i œ N), on est amené à définir la notion de série convergente qui correspond à la somme dans l’ordredes ai lorsqu’elle est finie. On utilise la notation

qŒi=1 ai pour indiquer la somme d’une série convergente.

Lorsque l’ordre de la sommation ne change pas le résultat obtenu, on parle de famille sommable et onutilise la notation

qiœNú ai.

Dans le cas où l’on cherche à sommer sur un ensemble non dénombrable, comme un intervalle deR ou bien R tout entier, le signe utilisé devient le signe intégral

s. Il existe plusieurs notions d’intégrales,

l’intégrale de Riemann et celle de Lebesgue par exemple.

5.6. EXERCICES 47

5.6 ExercicesExercice 5.1. ⌥ « Il n’y a que 10 sortes de personnes : ceux qui savent compter en binaire et les autres ».

Écrire 1, 2, 5 et 10 en base 2. Écrire en base 10 les entiers 10012 et 1112.

Exercice 5.2. ⌥ Montrer par récurrence qu’il existe un entier n0 (à préciser) tel que

’n Ø n0, 2n Ø (n + 2)2.

Exercice 5.3. Pour tout n Ø 2, on considère la propriété P (n) : « n points distincts du plan sont toujoursalignés ». Où est l’erreur dans la démonstration par récurrence ci-dessous ?

1. Initialisation. P (2) est vraie car deux points distincts sont toujours alignés.2. Hérédité. Supposons que P (n) est vraie. Montrons alors que P (n + 1) est vraie.

Soit A1, A2, . . . , An, An+1 des points distincts. D’après l’hypothèse de récurrence, A1, A2, . . . , An

sont alignés sur une droite d, et A2, . . . , An, An+1 sont alignés sur une droite dÕ. Les deux droitesd et dÕ ayant n ≠ 1 points communs A2, . . . , An sont confondues. Donc A1, A2, . . . , An, An+1 sontalignés, ce qui montre que P (n + 1) est vraie.

3. Conclusion. La propriété P (n) est vraie pour tout n Ø 2.

Exercice 5.4. W Sur les 1026 élèves d’un lycée, 763 suivent des cours d’anglais, 318 ceux d’allemand, 668ceux d’espagnol. Parmi eux, 470 apprennent au moins l’anglais et l’espagnol, 186 apprennent au moinsl’anglais et l’allemand et 86 apprennent au moins l’allemand et l’espagnol. Enfin, 6 d’entre eux apprennentles trois langues. Combien n’apprennent aucune de ces trois langues ? Combien d’élèves font uniquementde l’anglais et de l’espagnol ?

Exercice 5.5. Soit E un ensemble à n éléments, et A une partie de E à p éléments. Quel est le nombrede parties de E qui contiennent un et un seul élément de A ?

Exercice 5.6. On considère les mains de 5 cartes que l’on peut extraire d’un jeu de 32 cartes.1. Combien y a-t-il de mains di�érentes ?2. Combien y a-t-il de mains comprenant un as ?3. Combien y a-t-il de mains comprenant au moins un valet ?4. Combien y a-t-il de mains comprenant (à la fois) au moins un roi et au moins une dame ?

Exercice 5.7. ⌥ Ecrire les quantités suivantes en utilisant les symboles � ou �.1. 1 ◊ 2 + 2 ◊ 3 + . . . + (n ≠ 1) ◊ n

2. (1 ≠ 12 ) ◊ (1 ≠ 1

3 ) ◊ . . . ◊ (1 ≠ 1n )

3. 2 ◊ 4 ◊ 6 ◊ . . . ◊ 2n

4. 1 ◊ 3 ◊ 5 ◊ . . . ◊ (2n + 1)5. 1 + 1

2 + 14 + 1

8 . . . + 12n

Exercice 5.8. ⌥ Démontrer les identités suivantes.1.

!nk

"=

!n≠2

k

"+ 2

!n≠2k≠1

"+

!n≠2k≠2

", où k et n sont deux entiers naturels tels que 2 Æ k Æ n.

2.!

nk

"= n

k

!n≠1k≠1

", où k et n sont deux entiers naturels tels que 1 Æ k Æ n.

3.!

nk

"!n≠kp≠k

"=

!pk

"!np

", où k, p et n sont trois entiers naturels tels que 0 Æ k Æ p Æ n.

Exercice 5.9. Démontrer la formule de Pascal en utilisant la formule!

nk

"= n!

k!(n≠k)! .

Exercice 5.10. Soit n et m deux entiers naturels tels que m Æ n. Montrer par récurrence que!

nm

"=

kqj=0

!kj

"!n≠km≠j

"pour tout entier naturel k Æ n.

Exercice 5.11. F Soit n un entier naturel.

1. Développer (1 + x)n. En déduire une expression simple denq

k=0

!nk

".


2. Calculer la dérivée de x ‘æ (1 + x)n de deux façons di�érentes : avec l’expression développée etl’expression non-développée de (1 + x)n. En déduire une expression simple de

nqk=0

k!

nk

".

3. Calculers 1

0 (1 + x)ndx de deux façons di�érentes : avec l’expression développée et l’expression

non-développée de (1 + x)n. En déduire une expression simple denq

k=0

1k+1

!nk

".

Exercice 5.12. ⌥ Montrer par récurrence quenq

k=1k2 = 1

6 n(n + 1)(2n + 1) pour tout entier naturel n.

Exercice 5.13. Soit n un entier naturel. On pose S2 =nq

k=0k2 et S =

nqk=0

(k + 1)3 ≠ k3.

1. Développer (k + 1)3 ≠ k3. En déduire une expression de S en fonction de S2 et n

2. Simplifier S par télescopage de ses termes. En déduire une expression de S en fonction de n.3. Déduire des deux questions précédentes une formule exprimant S2 en fonction de n.

Exercice 5.14. F Soit n un entier naturel. On pose S2 =nq

k=0k2 et S3 =

nqk=0

k3.

1. En faisant le changement d’indice i = n ≠ k dans S3, exprimer S3 en fonction de n et S2.2. En utilisant la formule exprimant S2 en fonction de n (donnée dans le cours), exprimer S3 en

fonction de n.

Exercice 5.15. Soit un entier n Ø 2. Simplifier le produitnr

k=2(1 ≠ 1

k ).

Exercice 5.16. W Calculer les sommes suivantes.

1.

nÿ

k=12k ≠ 3k2 2.

n+1ÿ

k=5k2 3.

nÿ

k=1(k + 3)3 4.

nÿ

k=1(n + 1 ≠ k)2 5.

nÿ

k=≠n

|k + 3|

Exercice 5.17. W Calculer les sommes suivantes.

1.

nÿ

i=1

nÿ

j=1ij 2.

nÿ

i=1

iÿ

j=1(i ≠ 1)j 3.

nÿ

i=1

nÿ

j=i

i(j + 1)

Chapitre 6

Groupes

“Les mathématiques ne sont qu’une histoire de groupes” – Henri Poincaré

6.1 GroupesDéfinition

Soit G un ensemble muni d’une loi de composition interne ú, c’est-à-dire une application de G ◊ Gdans G. On dit que (G, ú) est un groupe lorsque les trois conditions suivantes sont réalisées :

(g1) La loi de composition ú est associative : ’x, y, z œ G, (x ú y) ú z = x ú (y ú z) ;(g2) La loi de composition ú possède un élément neutre : ÷e œ G, ’x œ G, x ú e = e ú x = x ;(g3) Tout élément de G possède un symétrique pour ú : ’x œ G, ÷y œ G, x ú y = y ú x = e ;

Un groupe est abélien (on dit aussi commutatif) lorsque sa loi de composition est commutative :’x, y œ G, x ú y = y ú x ; dans ce cas on privilégie souvent la notation additive +, on note alors 0 l’élémentneutre et ≠x le symétrique de x.

Proposition 6.1. F Soit (G, ú) un groupe, alors l’élément neutre est unique et chaque élément possèdeun unique symétrique.

Avant de donner des exemples, quelques remarques d’ordre purement calculatoire sur les groupes. Saufavis contraire, on utilise désormais la notation multiplicative, donc ab désigne le composé des éléments aet b d’un groupe.

Proposition 6.2. F Soit (G, .) un groupe. Alors pour tous éléments a, b et x de G :1. Si ax = bx, alors a = b (simplification à droite).2. Si xa = xb, alors a = b (simplification à gauche).3. Le symétrique de ab est b≠1a≠1.

Donnons quelques exemples de groupes concernant les ensembles de nombres usuels.L’addition usuelle (sur N, Z, Q, R ou C) est associative et a un élément neutre noté 0. Le symétrique

pour l’addition est couramment appelé « opposé » ; dans N il fait défaut : 1 n’a pas d’opposé (dans N),donc (N, +) n’est pas un groupe. Dans Z (puis dans les ensembles usuels bien connus Q,R,C), l’opposéexiste. Ainsi (Z, +) est un groupe abélien pour l’addition.

Pour la multiplication usuelle, 0 n’a jamais d’inverse. En revanche, dans le sous-ensemble formé deséléments non nuls, la multiplication est bien définie, est associative et elle possède un élément neutre 1. Lepoint à problème est l’existence de l’inverse (le symétrique en notation multiplicative). Dans Zú, 2 n’a pasd’inverse ; (Zú, ◊) n’est donc pas un groupe. En revanche, dans (Qú, ◊), (Rú, ◊) ou (Cú, ◊), l’existence del’inverse ne pose pas de problème. Tous ces ensembles sont donc des groupes multiplicatifs.

49

50 CHAPITRE 6. GROUPES

Ordre d’un groupe

L’ordre d’un groupe est simplement son cardinal !

Groupes produits

Soit (G, ı) et (H, �) deux groupes d’éléments neutres respectifs eG et eH . Alors le produit cartésienG◊H munit de la loi de composition interne · définie pour tout (a, b), (aÕ, bÕ) œ G◊H par (a, b)·(aÕ, bÕ) =(a ı aÕ, b�bÕ) est un groupe d’élément neutre (eG, eH). On dit que c’est le groupe produit de G et de H.

6.2 Sous-groupesSoit (G, .) un groupe. On dit qu’un sous-ensemble H de G est un sous-groupe de G lorsque les trois

conditions suivantes sont vérifiées :(sg1) L’ensemble H n’est pas vide.(sg2) Pour tous x, y œ H, le produit x.y est aussi dans H.(sg3) Pour tout x de H , l’inverse x≠1 de x est aussi dans H.

Avant de commenter ce que cela signifie, donnons tout de suite une proposition très simple, et utile enpratique pour vérifier qu’un sous-ensemble d’un groupe est un sous-groupe.

Proposition 6.3. F Soit (G, .) un groupe. Un sous-ensemble H de G est un sous-groupe de G si etseulement si les deux conditions suivantes sont vérifiées :

(sg1’) L’ensemble H contient l’élément neutre.(sg4) Pour tous x, y de H, le produit x.y≠1 est aussi dans H.

Théorème 6.4. F Soit (G, .) un groupe et H un sous-groupe de G. La restriction à H de la loi decomposition sur G fait de (H, .) un groupe.

Proposition 6.5. F Soit (G, .) un groupe, et H un ensemble non vide de sous-groupes de G.L’intersection

‹

HœHH est un sous-groupe de G

Sous-groupe engendré

Soit (G, .) un groupe et S une partie non-vide. Remarquons que G est un sous-groupe de G qui contientS. Ainsi l’ensemble HS des sous-groupes de G contenant S est non vide. Le sous-groupe engendré parS noté ÈSÍ est par définition l’intersection des sous-groupes de G contenant S.

ÈSÍ =‹

HœHS

H où HS est l’ensemble des sous-groupes de G contenant S.

D’après la proposition ci-dessus il s’agit bien d’un sous-groupe. Cette définition fait de ce sous-groupele plus petit sous-groupe contenant S (au sens de l’inclusion).

Lorsqu’il existe un élément a qui engendre un groupe fini G, c’est à dire G = È{a}Í = ÈaÍ, on dit queG est cyclique et que a est un générateur de G.

Ordre d’un élément

Soit (G, .) un groupe d’élément neutre e, et a un élément de G. Si l’ensemble {m œ Nú, am = e} estvide on dit que a est d’ordre infini, sinon on dit que a est d’ordre fini égal à n = min{m œ Nú, am = e}.

La proposition suivante montre que l’ordre de a est l’ordre du sous-groupe È{a}Í engendré par a.

Proposition 6.6. F Soit (G, .) un groupe d’élément neutre e, et a un élément de G d’ordre fini n, alorsÈ{a}Í = {e, a, ...., an≠1}.

Théorème 6.7. (de Lagrange)F Soit (G, .) un groupe fini et H un sous-groupe de G. Alors l’ordre (lenombre d’éléments) de H divise l’ordre (le nombre d’éléments) de G.

6.3. EXEMPLES FONDAMENTAUX DE GROUPES 51

Démonstration. La démonstration repose sur l’introduction de la relation ƒ définie pour tous élémentsx, y de G par :

x ƒ y si et seulement si xy≠1 œ H.

Le plan est le suivant : 1) On vérifie que ƒ est une relation d’équivalence. 2) On vérifie que toutesles classes d’équivalence pour la relation ƒ sont en bijection avec H. 3) On conclut en quelques mots.

Corollaire 6.8. Soit (G, .) un groupe d’ordre fini m et d’élément neutre e. Pour tout a œ G on a : am = e.

6.3 Exemples fondamentaux de groupes6.3.1 Le groupe (Z, +)

D’abord, Z possède une autre opération, la multiplication, qui est une loi de composition interneassociative, commutative, possédant un élément neutre 1, mais seulement deux éléments inversibles 1 et≠1. Ainsi (Z, ◊) n’est pas un groupe. De plus la multiplication est distributive sur l’addition. On ditque (Z, +, ◊) est un anneau, c’est un ensemble dans lequel on peut se poser la question de la résolutiond’équations du type ax ≠ by = c. ou du type ax2 + bx + c = 0 ou encore du type x5 + y5 = z5.

Théorème 6.9. (Division euclidienne) Soit a œ Z et b œ Nú. Il existe un couple unique (q, r) œ Z2

vérifiant a = bq + r avec 0 Æ r < b. On dit que q est le quotient et r le reste de la division euclidienne dea par b.

Le résultat reste vrai avec b œ Zú et 0 Æ r < |b|.

Les sous-groupes de Z

La première conséquence de la division euclidienne dans Z concerne la forme des sous-groupes de Z.

Théorème 6.10. F Soit H une partie de Z, H est un sous-groupe de Z ssi il existe n œ N tel queH = nZ. De plus n est unique.

6.3.2 Les groupes (Z/nZ, +) et ((Z/nZ)ú, ◊)On a déjà remarqué que (Z, +) est un groupe d’élément neutre 0. Z est aussi muni d’une autre loi de

composition interne, ◊ associative, d’élément neutre 1.Fixons n œ Nú, et considérons la relation de congruence modulo n définie sur Z par

’a, b œ Z, a © b mod (n) si et seulement si n divise (b ≠ a).

Lemme 6.11. 1. La relation © mod(n) est une relation d’équivalence sur Z.2. ’a, b, aÕ, bÕ œ Z si a © aÕ mod (n) et b © bÕ mod (n) alors (a + b) © (aÕ + bÕ) mod (n) et ab © aÕbÕ

mod (n).

On définit Z/nZ comme l’ensemble quotient de Z par la relation déquivalence © mod (n). D’aprèsle lemme, les opérations + et ◊ se transportent sur Z/nZ en posant :

’a, b œ Z/nZ, a + b = a + b, a ◊ b = a ◊ b.

Proposition 6.12. 1. Z/nZ = {0, 1, ..., n ≠ 1} ;2. (Z/nZ, +) est un groupe abélien d’élément neutre 0 ;3. la loi de composition interne ◊ sur Z/nZ est associative, commutative, d’élément neutre 1.

Un élément a de Z/nZ est inversible pour la loi ◊ s’il existe b dans Z/nZ tel que a ◊ b = 1.L’ensemble (Z/nZ)ú est défini comme l’ensemble des éléments inversible pour la loi ◊ dans Z/nZ

Proposition 6.13. ((Z/nZ)ú, ◊) est un groupe commutatif.


Attention aux réflexes ! ! !— L’inverse de a n’est certainement pas 1/a qui n’a pas de sens en général ! Ainsi l’inverse de 2 dans

Z/5Z est 3.— La règle de simplification

pour tout a ”= 0, a.b = a.c =∆ b = c,

n’est pas valide en général ! Ainsi dans Z/6Z on a 3.0 = 3.2 et pourtant 0 ”= 2. Pour avoir la règlede simplification, il faut se restreindre à a dans (Z/nZ)ú !

6.3.3 Les groupes de permutationOutre les groupes Z/nZ, les groupes les plus directement utilisables sont sans doute ceux qui in-

terviennent en géométrie. Ceux sont des groupes de transformations respectant telle ou telle propriété ;ainsi les isométries, qui conservent les distances, ou les similitudes, qui conservent les angles. Ces groupesconstituent notre deuxième classe d’exemples.

Tous ces groupes ont le point commun d’avoir pour loi de composition la composition des applicationset d’être formés de bijections.

L’exemple suivant est donc fondamental.

Proposition 6.14. Soit E un ensemble. L’ensemble noté S(E) des bijections de E dans lui-même formeun groupe pour la composition ¶. Son élément neutre est l’application identité IdE.

Cette proposition est une conséquence des résultats établis dans le chapitre 2.Dans le cas où E est l’ensemble fini {1, ..., n}, on note Sn = S(E).L’ensemble Sn des bijections de {1, ..., n}, s’appelle le groupe des permutations sur n éléments. Il

possède n! éléments. Rappelons que Id{1,...,n} et les transpositions tab sont des permutations particulières.Pour n Ø 3, Sn est un exemple de groupe non commutatif. En e�et si on choisit trois éléments distincts

a, b, c on a tab ¶ tbc ”= tbc ¶ tab, puisque tab ¶ tbc(c) = a alors que tbc ¶ tab(c) = b.

6.4 Morphismes de groupesSoient (G, .) et (GÕ, ú) deux groupes. Une application g : G æ GÕ est un morphisme de groupe si

pour tout x, y œ G, g(x.y) = g(x) ú g(y).

Proposition 6.15. F Soit g un morphisme d’un groupe (G, .), d’élément neutre e, vers un groupe (GÕ, ú),d’élément neutre eÕ. Alors g(e) = eÕ et, pour tout élément x de G, g(x≠1) = (g(x))≠1.

On appelle noyau du morphisme g d’un groupe (G, .), d’élément neutre e, vers un groupe (GÕ, ú),d’élément neutre eÕ et on note Ker(g) l’ensemble

Ker(g) = {x œ G, g(x) = eÕ}1

= g{≠1}({eÕ})2

.

Proposition 6.16. F Soient (G, .) et (GÕ, ú) deux groupes. Notons e l’élément neutre de G.Un morphisme g : G æ GÕ est injectif si et seulement si Ker(g) = {e}Proposition 6.17. F Soit g : (G, .) æ (GÕ, ú) un morphisme de groupe d’éléments neutre respectifs e eteÕ. Alors,

1. l’image de g, Im(g) = g(G) est un sous-groupe de GÕ et2. le noyau de g, Ker(g) = g{≠1}({eÕ}) = {x œ G, g(x) = eÕ} est un sous-groupe de G.

Morphisme canonique associé à un élément d’un groupe.Soit (G, ·) un groupe et a un élément de G. L’application „a : Z æ G définie par récurrence par„a(0) = e et pour n Ø 1, „a(n) =an (= a · .... · a (n fois))

„a(≠n) =a≠n (= a≠1 · .... · a≠1 (n fois))est un morphisme du groupe (Z, +) dans le groupe (G, ·).

6.5. EXERCICES 53

Proposition 6.18. Soit G un groupe, a œ G et „a : Z æ G le morphisme canonique associé à a.1. Le sous-groupe engendré par a est l’image de „a , ÈaÍ = Im(„a).2. Si G est d’ordre fini n, alors Im(„a) = {e, a, ...., an≠1} (qui est isomorphe à Z/nZ) et ker(„a) = nZ.

6.5 ExercicesExercice 6.1. ⌥ Parmi les a�rmations suivantes, lesquelles sont vraies, lesquelles sont fausses, et pour-quoi ?

1. La soustraction est une loi de composition interne dans Z.2. 0 est élément neutre de la soustraction dans Z.3. La soustraction dans Z est associative.4. 0 est élément neutre pour l’addition dans N.5. L’addition est associative dans N.

Exercice 6.2. ⌥ Les ensembles suivants, munis de l’addition des réels sont-ils des groupes (oui ou nonet pourquoi) ? 1

1. {a/10n, a œ Z, n œ N}2. {a/10n, a œ Z, n œ Z}3. {a

Ô2, a œ Z},

4. {aÔ

2, a œ N},5. {a

Ô2 + b

Ô3, a, b œ Z},

6. {aÔ

2 + bÔ

3, a œ Z, b œ N}.

Exercice 6.3. ⌥ Les ensembles suivants, munis de la multiplication des réels sont-ils des groupes (oui ounon et pourquoi) ? 2

1. {1, ≠1}, 2. {1, ≠1, 1/2, 2}, 3. {2n, n œ Z}, 4. {a2n, a = ±1, n œ Z},

Exercice 6.4. ⌥ Les ensembles complexes munis de la multiplication sont-ils des groupes ? Pourquoi ? 3

1. (C, ◊),2. ({1, ≠1}, ◊),3. ({i, ≠i}, ◊),4. ({0, 1, ≠1}, ◊),5. ({1, i, ≠1, ≠i}, ◊).

Exercice 6.5. ⌥ Soit E l’ensemble des parties d’un ensemble à deux éléments, par exemple E = P({0, 1})donc

E = {ÿ, {0}, {1}, {0, 1}}.

1. On considère la loi de composition ú sur l’ensemble E définie successivement par(a) la réunion : A ú B = A fi B,(b) l’intersection : A ú B = A fl B,(c) la di�érence symétrique : A ú B = A�B,Ecrire dans chaque cas la table de composition de la loi. Indiquer s’il existe un élément neutre, sila loi est associative, commutative et si l’ensemble muni de la loi est un groupe.

2. Même question en remplaçant E par l’ensemble des parties d’un ensemble quelconque.

Exercice 6.6. ⌥ Soit (G, ú) un groupe. Montrer qu’il existe un unique élément neutre et que pour chaquex œ G il existe un unique symétrique pour la loi ú.

1. oui pour 1,2,5

2. oui pour 1,3,4

3. oui pour 2,5 ; dans 1,4 0 n’a pas d’inverse ; dans 3, il n’y a pas d’élément neutre.


Exercice 6.7. ⌥ Montrer que l’intersection de deux sous-groupes est un sous-groupe, puis qu’une inter-section quelconque de sous-groupes est un sous-groupe.

Exercice 6.8. ⌥ On considère le groupe additif (Z/5Z, +). Pour chaque a œ Z/5Z préciser l’ordre de aet déterminer le groupe engendré par a noté ÈaÍ. Le groupe (Z/5Z, +) est-il cyclique ? Indiquez tous sesgénérateurs.

Mêmes questions pour (Z/6Z, +) et (Z/8Z, +).

Exercice 6.9. F Quels sont les éléments de S3, le groupe des permutations de {1, 2, 3} ? Ecrire la tablede loi de S3. Déterminer les inverses des éléments de S3 ainsi que leur ordre. Le groupe S3 est-il cyclique ?Montrer que S3 est engendré par l’ensemble {(1, 2); (1, 2, 3)}. Mêmes questions sur S4, le groupe despermutations de {1, 2, 3, 4}.

Exercice 6.10. Donner l’inverse de (2, 3) dans le groupe (R, +) ◊ (Rú, ·).Donner la table du groupe (Z/2Z ◊ Z/2Z, +). Est-ce un groupe cyclique ?

Exercice 6.11. F Soit (G, ·) un groupe et H et K deux sous-groupes de G. Montrer que H fi K estun sous-groupe de G si et seulement si H µ K ou K µ H.

Exercice 6.12. Soit (G, +) un groupe abélien et H et K deux sous-groupes de G. Montrer que H +K :={h + k; h œ H, k œ K} est un sous-groupe de G.

Exercice 6.13. Soit (G, ·) un groupe. Soient a, b œ G, exprimer (ab)≠1 en fonction de a≠1 et b≠1.On note e l’élément neutre de G et on suppose ’a œ G, a · a = e. Que peut-on dire sur a≠1 ? En déduireque (G, ·) est commutatif.

Exercice 6.14. Soit G un groupe d’ordre p premier. Montrer que G est cyclique.

Exercice 6.15. F On note (Z/nZ)ú l’ensemble des éléments inversibles de Z/nZ pour la loi ◊. Montrerque ((Z/nZ)ú, ◊) est un groupe. Déterminer (Z/6Z)ú, (Z/7Z)ú et (Z/8Z)ú. Ces groupes sont-ils cycliques ?

Exercice 6.16. On considère le groupe G donné par

1. Déterminer b ı b ı c ı d.2. Quel est l’ordre de G ?3. Quel est l’élément neutre ?4. Déterminer le symétrique de a.5. Déterminer le sous groupe engendré par b, noté < b >.6. Quel est l’ordre de b ?7. Si H est un sous groupe de G, combien peut-il avoir d’éléments ?8. Déterminer < a, b >, le sous groupe engendré par a et b.

6.5. EXERCICES 55

Exercice 6.17. On considère le groupe G donné par

1. Quel est l’ordre de G ?2. Quel est l’élément neutre ?3. Déterminer a ı b ı c ı d.4. Déterminer le symétrique de a.5. Déterminer le sous groupe engendré par d, noté < d >.6. Quel est l’ordre de d ?7. Si H est un sous groupe de G, combien peut-il avoir d’éléments ?8. Déterminer < a, b >, le sous groupe engendré par a et b.

Exercice 6.18. ⌥ On considère le groupe (Cú, ◊) des nombres complexes non nuls muni de la multipli-cation. Les applications suivantes sont elles des automorphismes de (Cú, ◊) ? Si oui préciser le noyau etl’image.

1. L’application qui à z œ Cú associe z2 ;2. L’application qui à z œ Cú associe 2z ;3. L’application qui à z œ Cú associe z/z ;4. L’application qui à z œ Cú associe 1/z.

Exercice 6.19. ⌥ Les applications suivantes sont-elles des morphismes de groupes ? Si oui préciser l’imageet le noyau.

1. L’application qui à x œ R associe e(1+i)x de (R, +) dans (Cú, ◊) ;2. L’application qui à x œ R associe (1 + i)x de (R, +) dans (C, +) ;3. L’application qui à x œ R associe (1 + i)x de (R, +) dans (Cú, ◊) ;4. L’application qui à x œ R associe xeix de (R, +) dans (C, +) ;5. L’application qui à x œ R associe (x + i)eix de (R, +) dans (Cú, ◊) ;


Exercice 6.20. ⌥ Soit (G, .) et (GÕ, ú) deux groupes d’éléments neutres respectifs e et eÕ et soit g : G æ GÕ

une application.1. On suppose que g est un morphisme. Montrer que

(a) g(e) = eÕ,(b) pour tout x dans G, g(x≠1) = g(x)≠1,(c) l’image de g est un sous-groupe de GÕ et son noyau est un sous-groupe de G.

2. Montrer que g est un isomorphisme de groupe si et seulement si ker g = {e}.3. On suppose que g : G æ GÕ est un isomorphisme de groupe. Montrer pour tout a œ G, les ordres

de a et de g(a) sont égaux.

Exercice 6.21. F Montrer que ({≠1, 1}, .) est un groupe isomorphe à (Z/2Z, +) et ({≠1, 1, i, ≠i}, .) estun groupe isomorphe à (Z/4Z, +).

Exercice 6.22. Soit G un groupe d’ordre 4. Montrer que si pour tout a œ G, a · a = e alors G estisomorphe à (Z/2Z ◊ Z/2Z, +). Sinon montrer que G est cyclique et isomorphe à (Z/4Z, +).

Exercice 6.23. Soit (G, ·) un groupe fini de cardinal n. Soit a œ G. Montrer que l’application f : Z æ Gdéfinie par f(k) = ak, pour tout k œ Z est un homomorphisme de groupe qui n’est pas injectif.En déduire qu’il existe k0 œ Nú tel que Ker(f) = k0Z.Montrer que si ak = e alors k0 divise k, et que k0 = min{k œ Nú; ak = e} (on dit que a est d’ordre k0).Montrer que le sous groupe Im(f) de G possède k0 éléments, e, a, . . . , ak0≠1. En déduire que an = e.

Documents

Méthodologie des mathématiques L1 — Université Paris-Est