Cours Algèbre Chapitre 1 PDF

Université Mohammed V - Agdal Faculté des Sciences Département de Mathématiques et Informatique Avenue Ibn Batouta, B.P. 1014 Rabat, Maroc.:: Module Mathématiques I : Algèbre ::. Filière : Sciences de Matière Physique (SMP)...

Université Mohammed V - Agdal Faculté des Sciences Département de Mathématiques et Informatique Avenue Ibn Batouta, B.P. 1014 Rabat, Maroc.:: Module Mathématiques I : Algèbre ::. Filière : Sciences de Matière Physique (SMP) et Sciences de Matière Chimie(SMC) Chapitre I: Opérations logiques élementaires. Ensembles. Quantificateurs. Relations binaires et Applications Par Prof: Jilali Mikram Groupe d’Analyse Numérique et Optimisation http://www.fsr.ac.ma/ANO/ Email : [email protected] Année : 2005-2006 1 TABLE DES MATIERES 1 Opérations logiques élementaires. Ensembles. Quantifica- teurs. Relations binaires et Applications 3 1.1 Qu’est-ce qu’une expression mathématique ?.......... 3 1.2 Négation d’une proposition : non P.............. 3 1.3 Disjonction de deux propositions : P ou Q........... 4 1.4 Equivalence de deux propositions : P ⇔ Q.......... 5 1.5 Conjonction de deux propositions :P et Q............ 5 1.6 Implication logique de deux propositions :P ⇒ Q....... 6 2 Quelques formes de raisonnements 7 2.1 Raisonnement à partir de la contraposée............ 7 2.2 Raisonnement par l’absurde................... 8 3 Notions sur les ensembles 8 3.1 Définition d’un ensemble.................... 8 3.2 Définition d’un sous-ensemble et de l’ensemble vide...... 9 3.3 Intersection et union d’ensembles................ 10 3.4 Complémentaire d’une partie d’un ensemble.......... 10 3.5 Cardinal d’un ensemble..................... 11 3.6 Produit cartésien d’ensembles.................. 12 4 Quantificateurs 13 4.1 Proposition dépendant d’une variable : P (x)......... 13 4.2 Quantificateur universel : ∀................... 13 4.3 Quantificateur existentiel : ∃.................. 14 4.4 Quantificateurs multiples.................... 14 5 Relation binaires 15 5.1 Relation d’équivalence...................... 16 5.2 Classes d’équivalence....................... 16 5.3 Relations d’ordre......................... 17 5.4 Eléments particuliers d’un ensemble ordonné.......... 18 6 Quelques mots sur les applications 19 6.1 Composition des applications.................. 21 6.2 Définition de l’application réciproque.............. 22 6.3 Composition des applications réciproques............ 23 2 1 Opérations logiques élementaires. Ensem- bles. Quantificateurs. Relations binaires et Applications 1.1 Qu’est-ce qu’une expression mathématique ? Il s’agit de se familiariser à l’expression mathématique du raisonnement et à quelques règles de raisonnement logique constamment utilisées en mathématiques et ailleurs. Ces règles permettent, à partir de propositions sur (ou propriétés, ou relations entre) des objets mathématiques (nombres, figures géométriques, fonctions,... ), connues ou posées comme vraies , de déduire d’autres propositions ou propriétés vraies. Ici, le mot ‘proposition’ désigne tout énoncé sur les objets considérés auquel on √ peut attribuer une valeur de vérité. Par exemple : – (P1 ) 2 est un nombre rationnel, – (P2 ) par deux points il passe une droite et une seule, – (P3 ) une fonction dérivable est continue. Quant à la vérité en question, il s’agit d’une valeur logique qui est l’un des deux mots vraie ou fausse (principe du tiers exclu). Ainsi (P1 ) est fausse et (P3 ) est vraie. Un certain nombre de propositions sont considérées comme vérités premières, qui ne se déduisent pas d’autres propositions vraies. Certaines d’entre elles traduisent en langage mathématique les propriétés les plus évidentes des ob- jets concrets auxquels on pense. On les appelle des axiomes. Par exemple, (P2 ) est un des axiomes de la géométrie euclidienne. Les autres propositions vraies le sont par déduction des axiomes ou d’autres propositions dont la vérité est déjà démontrée. Les axiomes sont en petit nombre et possèdent une cohérence interne, en ce sens qu’on ne peut déduire d’eux aucune proposition à la fois vraie et fausse. 1.2 Négation d’une proposition : non P Définition 1.1 Si P est une proposition, sa négation, notée non(P ) est une proposition qui est fausse si P est vraie et qui est vraie si P est fausse. Il résulte de cette définition que non(nonP ) et P ont la même valeur logique, c’est à dire sont vraies simultanément ou fausses simultanément. Par exemple: – P : Tous les dimanches je vais au restaurant, 3  non(P ) : Il existe au moins un dimanche où je ne vais pas au restaurant – P : Je vais au restaurant au moins un dimanche de décembre, non(P ) : Je ne vais jamais au restaurant le dimanche en décembre. Remarque I.1.1. non(P ) se note aussi :P. 1.3 Disjonction de deux propositions : P ou Q Définition 1.2 Si P et Q sont deux propositions, la disjonction, notée P ou Q, est une proposition qui est vraie si au moins l’une des deux propositions est vraie et qui est fausse si les deux propositions sont fausses. On introduit maintenant la notion de table de vérité : Définition 1.3 Soient P et Q deux propositions, R une proposition dépendant de P et Q (dans cet ordre). On associe à R le tableau suivant : V F V F où les cases blanches seront remplies par la lettre V chaque fois que R est vraie et la lettre F si elle est fausse, selon les valeurs logiques V ou F ) de P et Q respectivement indiquées sur la 1ere colonne et la 1ere ligne. Ce tableau s’appelle la table de vérité de R. Par exemple si R = (P ou Q), sa table de vérité s’écrit : V F V V V F V F Par exemple, si on considère les deux propositions : – P: Tous les lundis je vais au cinéma, – Q: Le 15 de chaque mois je vais au cinéma, La proposition ( P ou Q ) est vraie si elle s’applique à quelqu’un qui va au cinéma tous les lundis ou à quelqu’un qui va au cinéma le 15 de chaque mois (il peut évidemment faire les deux). Elle est fausse dans tous les autres cas. En particulier elle est fausse s’il s’agit de quelqu’un qui ne va au cinéma que les lundis 15. Attention, le ‘fromage ou dessert’ du restaurant n’est pas un ‘ou mathématique’ car il est exclusif. 4  Si dans une démonstration on veut utiliser l’hypothèse P ou Q est vraie, alors deux cas sont possibles : – soit P est vraie et on utilise ce résultat dans la démonstration, – soit P est fausse, alors Q est vraie et l’on utilise ces deux résultats dans la démonstration. Pour montrer que P ou Q est vraie, il faut démontrer que l’on est dans l’un des deux cas suivants : – soit P est vraie et donc P ou Q est vraie, – soit P est fausse et ceci peut être utilisé pour montrer que Q est vraie. Remarque 1.1 P ou Q se note aussi P ∨ Q 1.4 Equivalence de deux propositions : P ⇔ Q Définition 1.4 Deux propositions P et Q sont équivalentes si elles ont la même valeur logique. On note P ⇔ Q Lorsque P et Q sont équivalentes, on dit aussi que P (resp Q ) est une condition nécessaire et suffisante de Q (resp P ), ou que P (resp. Q ) est vraie si et seulement si Q (resp. P ) est vraie. Dans ce cas, les deux propositions sont vraies ou fausses simultanément. Par exemple : {non ( non P )} ⇔ P {P ou Q} ⇔ {Q ou P } {2x = 4} ⇔ {x = 2} La disjonction est associative dans le sens où {P ou ( Q ou R )} ⇔ {(P ou Q) ou R} Si P est toujours fausse, alors (P ou Q) est équivalente à Q. 1.5 Conjonction de deux propositions :P et Q. Définition 1.5 Si P et Q sont deux propositions, la conjonction, notée(P et Q), est la proposition qui est vraie si les deux propositions sont vraies et qui est fausse si au moins l’une des deux propositions est fausse. 5 Il résulte de cette définition que les propositions (P et Q) et (Q et P ) ) sont équivalentes. Par exemple, soient les deux propositions : –P : Tous les lundis je vais au cinéma, –Q: Le 15 de chaque mois je vais au cinéma, La proposition (P et Q) est vraie si elle s’applique à quelqu’un qui va au cinéma tous les lundis et le 15 de chaque mois. Elle est fausse dans tous les autres cas. Attention, (P et Q) ne correspond pas à : Tous les lundis 15 je vais au cinéma. La conjonction est associative dans le sens où ((P et Q) et R) est équivalente à(P et (Q et R)). Si P est toujours vraie, alors (P et Q) est équivalente à Q. Remarque I.1.3. (P et Q) se note aussi P ∧ Q. 1.6 Implication logique de deux propositions :P ⇒ Q Définition 1.6 Soient P et Q deux propositions, on appelle l’implication logique (de Q par P ) la proposition, notée P ⇒ Q, qui est vraie si – soit P est fausse, – soit P est vraie et Q est vraie. Elle est fausse dans le seul cas où P est vraie et Q est fausse. Attention P ⇒ Q n’est pas équivalente à Q ⇒ P.L’implication se dit, en langage courant,0 P implique Q0 et signifie queQ est vraie dès que P l’est. D’ailleurs pour prouver que cette implication est vraie, on n’a qu’une seule chose à faire : démontrer que si P est vraie, alors Q aussi l’est. Mais il faut faire attention car elle ne donne aucun renseignement sur Q si P est fausse, comme on le voit dans l’exemple suivant : Soient 3 nombres réels x, y, z. On a l’implication (bien connue) suivante : (x = y) ⇒ (xz = yz) On voit sur cet exemple que quand la proposition (P ) est fausse (x 6= y) la conclusion (Q) peut être vraie (si z = 0) ou fausse (si z 6= 0). Dans la pratique, par abus de langage, quand la notation (P ⇒ Q) est utilisée, on entend que cette implication est vraie : on dira ‘démontrer P ⇒ Q plutôt que ‘démontrer que (P ⇒ Q) est vraie. Proposition 1.1 (P ⇒ Q) est équivalente à ((non P ) ou Q). Démonstration: On a vu que ((non P ) ou Q) est vraie si (non P ) est vraie (donc P fausse) ou si (non P ) est fausse (P vraie) et Q est vraie. Ceci correspond bien à (P ⇒ Q) 6  Au lieu de dire que P implique Q on dit aussi que P est une condition suffisante de Q (pour que Q soit vraie, il suffit que P le soit), ou que Q est une condition nécessaire de P ( si P est vraie, nécessairement Q l’est). Corollaire 1.1 non (P ⇒ Q) est équivalente à (P et (non Q)). Attention ! La négation d’une implication n’est pas une implication. Enfin, l’implication est transitive, soit ((P1 ⇒ P2 )et(P2 ⇒ P3 )) ⇒ (P1 ⇒ P3 ) Proposition 1.2 (P ⇒ Q) ⇔ (nonQ) ⇒ nonP ) La démonstration est à faire en exercice. Proposition 1.3 (P ⇔ Q) est équivalent à P ⇒ Q et Q ⇒ P. L’équivalence est transitive, soit: ((P1 ⇔ P2 ) et (P2 ⇔ P3 )) ⇒ (P1 ⇔ P3 ) 2 Quelques formes de raisonnements Un raisonnement est une manière d’arriver à une conclusion en partant d’une (ou de plusieurs) hypothèse(s), et en utilisant les règles de déduction d’une proposition à partir d’une autre. Vous connaissez déjà le raisonnement par équivalence qui consiste à partir d’une proposition vraie (l’hypothèse par exemple) et à construire par équivalence d’autres propositions (qui sont donc vraies), dont la dernière est la conclusion. Vous connaissez le raisonnement par récurrence. Voici deux autres formes de raisonnement qui découlent des règles de logique précédentes. 2.1 Raisonnement à partir de la contraposée La proposition 1.2 donne une autre manière de démontrer que P ⇒ Q. En effet il est équivalent de montrer que (nonQ)) ⇒ (nonP ), c’est-à-dire que si la proposition Q est fausse alors la proposition P est fausse, ce qui est parfois plus simple. C’est ce que l’on appelle un raisonnement par contraposée. Un premier exemple emprunté à Racine est : ‘Si Titus est jaloux, il est amoureux’. En effet, s’il n’est pas amoureux, il n’a aucune raison d’être jaloux ! 7  Un deuxième exemple mathématique : Si n est un entier impair alors le chiffre des unités de n est impair. On va montrer la contraposée, à savoir : (le chiffre des unités de n est pair) ⇒ n est pair. En effet, si le chiffre des unités de n est pair, on peut écrire n = 10q + 2p soit n = 2(5q + p) c’est-à-dire n est pair. Attention La proposition (P ⇒ Q) ⇔ (nonP ⇒ nonQ) est fausse!. Elle peut conduire à de nombreuses erreurs, par exemple la suivante : étant donné que ‘tout homme est mortel’, cet énoncé pourrait servir à prouver que ‘toute vache est immortelle’. 2.2 Raisonnement par l’absurde Le principe du raisonnement par l’absurde est le suivant : pour démontrer qu’une proposition R est vraie, on suppose le contraire (c’est-à-dire R fausse), et on essaye d’arriver à un résultat faux (absurde). Par exemple, pour mon- trer qu’il n’existe pas de plus petit réel strictement positif, on va supposer qu’il en existe un, noté a (donc 0 < a est tel qu’il n’existe aucun réel x tel que0 < x < a). Or le réel a2 est tel que 0 < a2 < a , ce qui contredit l’hypothèse. On peut appliquer ce principe par exemple à la proposition (P ⇒ Q), notée R. On a vu précedement que (P ⇒ Q) s’écrit (Qou(nonP )) et que non(Qou(nonP )) est équivalente à ((nonQ)etP ). On peut donc mon- trer l’implication (P ⇒ Q) en montrant que ((nonQ)etP ) est fausse. Plus précisément on suppose que P est vraie et Q est fausse et l’on démontre que cela aboutit à un résultat faux. Par exemple, pour montrer que, n étant un entier, (n impair) ⇒ (le chiffre des unités de n est impair), on va supposer à la fois que n est impair et que le chiffre de ses unités est pair, ce qui donne : 2m + 1 = 10q + 2p,donc 1 = 2(5q + p − m) ce qui est impossible puisque 1 ne peut pas être le produit de deux entiers dont l’un est 2. 3 Notions sur les ensembles 3.1 Définition d’un ensemble Un ensemble E est considéré comme une collection d’objets (mathématiques) appelés éléments. x ∈ E signifie x est un élément de E, x 6∈ E signifie x n’est pas un élément de E. Un ensemble E est donc défini si, pour chaque objet x considéré, une et une seule des deux éventualités x ∈ E et x 6∈ E est vraie. En pratique, on définit un ensemble, soit en exhibant tous ses éléments, soit en donnant un critère permettant de vérifier la vérité de (x ∈ E) ou de (x 6∈ E). 8  Par exemple l’ensemble des nombres réels positifs ou nuls s’écrit IR+ = {x ∈ IR; x ≥ 0}. Dans la suite, nous supposerons connus les ensembles suivants : l’ensemble IN des entiers naturels, l’ensemble Z des entiers relatifs, l’ensemble Q des nombres rationnels, l’ensemble IR des nombres réels, l’ensemble C des nombres complexes. l’ensemble IR∗ des nombres réels non nuls, l’ensemble IR+ des nombres réels positifs ou nuls, l’ensemble IR− des nombres réels négatifs ou nuls. Remarque 3.1 Le chapitre 2 de ce cours, sera toutefois consacré à un rappel et à certains développements des propriétés fondamentales de IR et de C. 3.2 Définition d’un sous-ensemble et de l’ensemble vide Soit E un ensemble, une partie ou sous-ensemble de E est un ensemble A vérifiant la propriété suivante pour tout x : (x ∈ A) ⇒ (x ∈ E) On dit aussi que A est inclus dans E, et on note A ⊂ E, par exemple IR+ ⊂ IR. Pour montrer l’égalité de deux ensembles on procède par double inclusion, c’est-à-dire (A = B) ⇔ (A ⊂ B)et(B ⊂ A) ou par équivalence, c’est-à-dire (x ∈ A) ⇔ (x ∈ B) qui est la traduction de la double inclusion. L’ensemble vide, noté ∅ est un ensemble qui ne contient aucun élément, c’est-à-dire qui est tel que la propriété (x ∈ ∅) est fausse quel que soit x. Donc ∅ ⊂ E pour tout ensemble E. En effet (x ∈ ∅) étant toujours fausse l’implication (x ∈ ∅) ⇒ (x ∈ E) est vraie. 9 3.3 Intersection et union d’ensembles Si A et B sont deux parties de E, on appelle intersection de Aet B, notée A ∩ B l’ensemble des éléments communs à A et B, et l’on a : (x ∈ A ∩ B) ⇒ (x ∈ A)et(x ∈ B) Par exemple, soit E = IN , A l’ensemble des entiers multiples de 3, B l’ensemble des entiers multiples de 5, alors A ∩ B est l’ensemble des entiers multiples de 15. De manière générale, si A est l’ensemble des entiers multiples de n et B l’ensemble des entiers multiples de m,alors A ∩ B est l’ensemble des entiers multiples du plus petit multiple commun de n etm. (à propos vous souvenez-vous du calcul de ce plus petit multiple commun ?). On appelle union de A et B, notée A ∪ B l’ensemble des éléments appar- tenant à A ou à B, et l’on a : (x ∈ A ∪ B) ⇒ ((x ∈ A)ou(x ∈ B)). Ainsi, soit E = IN , A l’ensemble des entiers multiples de 3, B l’ensemble des entiers multiples de 5, alors A ∪ Best l’ensemble des entiers qui sont multiples de 3 ou de 5. Soit E un ensemble quelconque, pour toutes parties A; B et C de l’ensemble E, on a les égalités ensemblistes suivantes : A ∩ (B ∩ C) = (A ∩ B) ∩ C, A ∪ (B ∪ C) = (A ∪ B) ∪ C A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). que l’on peut démontrer par équivalence. 3.4 Complémentaire d’une partie d’un ensemble Soit E un ensemble, pour toute partie A de E, l’ensemble des éléments de E qui n’appartiennent pas à A s’appelle le complémentaire de A dans E et se note CE A ou E \ A. Lorsque, du fait du contexte, il n’y a pas d’ambiguité sur l’ensemble E, on se contente souvent de noter CA, le complémentaire de A dans E. Par exemple: soit E = IN et soit A l’ensemble des entiers pairs, alors CA est l’ensemble des entiers impairs, 10  soit E = IR et soit A = {0}, alors CA = IR∗ soit E = IR et soit B = {2} alors CB = IR \ {2} soit E = IR et soit A = IR+ , alors CA = IR∗−. Pour toutes parties A et B d’un ensemble E, on a les propriétés suivantes A ⊂ B ⇒ CB ⊂ CA, C(CA) = A, C(A ∩ B) = CA ∪ CB, C(A ∪ B) = CA ∩ CB. Notons bien que le complémentaire d’une intersection est l’union des complémentaires et de même le complémentaire d’une union est l’intersection des complémentaires. Notons aussi que lorsque l’on définit un ensemble E comme l’ensemble des éléments vérifiant une propriété P, soit E = {x, P (x)} le complémentaire de E est l’ensemble des éléments vérifiant nonP. De même, si A et B sont définis à l’aide des propriétés P et Q, alors A ∩ B est défini par (P et Q) et A ∪ B par (P ou Q). Attention : la notation CE A suppose que Aest inclus dans E, on a donc CE (CE A) = A, alors que la notation B \A définie par x ∈ B \A ⇒ x ∈ B, x 6∈ A ne suppose pas que A est inclus dans B, on a alors B \ (B \ A) = A ∩ B. Par exemple: E = IR, A = [1, 3], B = [2, 5], B \ A =]3, 5], B \ (B \ A) = [2 , 3] = A ∩ B, on montrerait de même que A \ (A \ B) = [2 , 3]. 3.5 Cardinal d’un ensemble On dit qu’un ensemble E est fini s’il a un nombre fini d’éléments. Le nombre de ses éléments est appelé cardinal de E et se note card(E). Par exemple, si E = {1, 2, 3}, alors card(E)=3. On note P (E) l’ensemble des parties de E. Proposition 3.1 Le nombre des parties d’un ensemble fini de cardinal n est égal à 2n. Démonstration- Il suffit de dénombrer le nombre des parties de E = {a1 ,...., an } : 11  partie vide ∅ parties ne contenant qu’un élément, il y en a n {a1 },.....,{an } parties formées de deux éléments, il y en a C2n de la forme {ai , aj } avec i 6= j,... parties formées de p éléments obtenues en prenant toutes les combi- naisons de p éléments parmi n, il y en a Cpn... E lui-même (E ⊂ E) Le nombre d’éléments est donc C0n + C1n +...Cpn +....Cnn = (1 + 1)n = 2n Cette dernière relation est une application de la formule du binôme de New- ton. 3.6 Produit cartésien d’ensembles Si E et F sont deux ensembles, le produit cartésien de E par F , noté E × F , est constitué des couples (x, y), où x décrit E et où y décrit F. Les couples (x, y) et (x0 , y0 ) sont égaux si et seulement si x = x0 et y = y0. Si E est un ensemble, le produit cartésien E × E se note E 2. Par exemple, le produit cartésien IR2 est formé des couples de nombres réels ; ceux-ci permettent de déterminer un point du plan par ses coordonnées, lorsqu’on s’est donné un repère (appelé aussi repère cartésien) c’est-à-dire la donnée − → →− d’une origine O et de deux vecteurs non colinéaires ( i , j ). Plus généralement, pour tout entier n supérieur ou égal à 2, le produit cartésien de E par lui même n fois se note E n. Les éléments de E n sont les n-uples (x1 , x2 ,....xn ) où les éléments x1 , x2 ,....xn appartiennent à E. Les n- uples (x1 , x2 ,....xn ) et (y1 , y2 ,....yn ) sont égaux si et seulement si on a xi = yi , pour tout i tel que 1 ≤ i ≤ n. Attention ! lorsque E 6= F , E × F est différent de F × E. 12 4 Quantificateurs 4.1 Proposition dépendant d’une variable : P (x) Si P est une proposition dont l’énoncé dépend de la valeur d’une variable x on peut la noter P (x) et considérer les cas particuliers P (a) où a est une valeur particulière de x. Par exemple, soit dans IR la proposition suivante P (x) : x2 − 1 < 0. Alors P (2) est fausse et P (0) est vraie, et plus généralement P (x) est vraie pour toutes les valeurs de x appartenant à ] − 1, +1[. Soit E un ensemble, P une propriété dépendant d’une variable x de E, on est souvent amené à considérer l’ensemble des éléments a de E tels que P (a) soit vraie (on dit aussi, les a qui vérifient la propriété P ). On le note AP = {x ∈ E, P (x)} 4.2 Quantificateur universel : ∀ Pour exprimer qu’une propriété P (x) est vraie pour tous les éléments x d’un ensemble de E, on écrit : ∀x ∈ E, P (x) (La virgule dans cette phrase’ peut être remplacée par un autre signe séparateur, couramment le point-virgule ( ;) ou le trait vertical (|)). Si on reprend la no- tation AP définie précédemment, on a alors : (∀x ∈ E, P (x)) ⇔ AP = E Exemples ∀x ∈ IR; x2 ≥ 0 ∀x ∈ [2, +∞[, x2 − 4 ≥ 0 E ⊂ F s’écrit : ∀x ∈ E; x ∈ F Proposition 4.1 On a l’équivalence suivante : (∀x ∈ E, (P (x) et Q(x))) ⇔ ((∀a ∈ E, P (a)) et (∀b ∈ E, Q(b))) Démonstration - En effet P (x) et Q(x) sont vraies pour tout élément de E est bien équivalent à P (x) est vraie pour tout élément de E et Q(x) est vraie pour tout élément de E. On peut également démontrer cette proposition avec les ensembles, en effet : AP ∩ AQ = E ⇔ AP = E et AQ = E 13 4.3 Quantificateur existentiel : ∃ Pour exprimer qu’une propriété P (x) est vérifiée pour au moins un élément x d’un ensemble E, on écrit : ∃x ∈ E, P (x) qui se traduit par : ’il existe x appartenant à E tel que P (x) est vraie’. S’il existe un unique élément x de E tel que P (x) est vraie, on écrira ∃!x ∈ E, P (x) Par exemple ∃x ∈ IR, x2 = 1, mais ∃!x ∈ IR; x2 = 1 est fausse. Par contre, vous pouvez écrire ∃!x ∈ IR+ , x2 = 1 La propriété (∃x ∈ E, P (x)) se traduit par AP 6= ∅. Proposition 4.2. On a l’équivalence suivante : ∃x ∈ E; ((P (x) ou Q(x)) ⇔ (∃a ∈ E; P (a)) ou (∃b ∈ E, Q(b)) Cette proposition peut être démontrée en exercice par double implication. 4.4 Quantificateurs multiples Il s’agit simplement de successions de ∀ et ∃. Mais il faut faire très attention à l’ordre dans lequel on les écrit. Par contre on a le résultat évident suivant: Proposition 4.3 Deux quantificateurs de même nature qui se suivent peu- vent être échangés Par exemple ∀x ∈ IR, ∀y ∈ IR; x2 + y 2 ≥ 0 ⇔ ∀y ∈ IR, ∀x ∈ IR; x2 + y 2 ≥ 0 De même ∃x ∈ IR; ∃y ∈ IR, x + y = 0 ⇔ ∃y ∈ IR; ∃x ∈ IR, x + y = 0 Proposition 4.4 On a les équivalences suivantes : non(∀x ∈ E, P (x)) ⇔ (∃a ∈ E, nonP (a)) non(∃a ∈ E, Q(a)) ⇔ (∀x ∈ E; nonQ(x)) 14  Démonstration: La négation de la proposition : (P est vérifiée pour tout élément de E ) est: ( il existe au moins un élément de E pour lequel la proposition P est fausse ). Ce qui s’exprime mathématiquement par : non(∀x ∈ E, P (x)) ⇔ (∃a ∈ E; nonP (a)) On peut démontrer cette proposition avec les ensembles : non(AP = E) ⇔ (∃a ∈ E, a 6∈ AP ) ⇔ (∃a ∈ E, nonP (a)) La deuxième proposition n’est que la négation de cette première proposition, si l’on appelle Q la proposition (nonP ). Par exemple, la négation de ∀x ∈ IR, x > 0 est ∃a ∈ IR, a ≤ 0. Proposition 4.5 Soient E et F deux ensembles et P une proposition dépendant de deux indéterminées et à chaque couple d’éléments (a, b) du produit cartésien E × F , on associe P (a, b). Alors on a: non(∀a ∈ E, ∃b ∈ F, P (a, b)) ⇔ (∃a ∈ E, ∀b ∈ F, nonP (a, b)) Démonstration :C’est une application directe de la proposition précédente. Attention ! L’implication inverse de celle de la proposition ci-dessus est fausse. Attention ! ∃x, ∀y n’a pas le même sens que ∀y, ∃x. 5 Relation binaires Définition 5.1. On appelle relation binaire dans E une partie de E × E. Plus précisément, soit R ⊂ E × E , on dit que x et y sont liés par la relation R si (x, y) ∈ R. On écrit souvent xRy pour indiquer que x et y sont liés par la relation R. Par exemple E = IN et R = {(x, y) ∈ IN × IN |x ≤ y} définit une partie de IN × IN et la relation associée est la relation ’inférieur ou égal’. Autre exemple, E = Z × Z ∗ et R = {(p, q), (p0 , q 0 )) ∈ E × E|pq 0 = p0 q} définit un exemple de relation qui va être appelée relation d’équivalence. 15 5.1 Relation d’équivalence Définition 5.2 On appelle relation d’équivalence une relation qui vérifie les trois propriétés suivantes : elle est réflexive : xRx elle est symétrique : xRy ⇒ yRx elle est transitive : xRy et yRz ⇒ xRz. Si R est une relation d’équivalence, on écrit souvent x ≡ y, ou x ∼ y, au lieu de xRy. Dans un ensemble quelconque, la relation ’x est égal à y’ est une relation d’équivalence. À partir d’une relation d’équivalence on peut définir des classes d’équivalence. La relation d’équivalence est d’ailleurs une généralisation de la relation d’égalité. Elle est présente partout en mathématiques. Elle permet, lorsque l’on étudie certains objets mathématiques, de n’en conserver que les propriétés perti- nentes pour le problème considéré. 5.2 Classes d’équivalence Définition 5.3 étant donnée une relation d’équivalence R, on appelle classe d’équivalence de l’élément a ∈ E la partie a ∈ E définie par : a = {x ∈ E|xRa} Tous les éléments de a sont donc équivalents entre eux. On appelle ensemble quotient de E par R, que l’on note E/R, l’ensemble constitué des classes d’équivalences des éléments de E. L’ensemble des classes d’équivalences constitue une partition de E, c’est- à-dire une famille de sous-ensembles de E deux à deux disjoints et dont la réunion est égale à E. En effet tout élément a ∈ E appartient à la classe a. Par ailleurs s’il existe x ∈ a ∩ b alors on a xRa et xRb et donc, d’après la transitivité, aRb ce qui implique a = b. Donc a 6= b ⇒ a ∩ b = ∅ ce qui correspond bien à une partition. Soit E = Z × Z ∗ et R = {(p, q), (p0 , q 0 )) ∈ E × E|pq 0 = p0 q}, alors la classe d’équivalence de (p, q) avec q 6= 0 est l’ensemble des (p0 , q 0 ), q 0 6= 0, tels que p 0 q = pq0. On peut alors construire un ensemble, noté Q , comme l’ensemble quotient de Z × Z ∗ par la relation d’équivalence précédente. Un élément de Q, qui est appelé nombre rationnel, est donc la classe d’équivalence d’un couple (p, q), q 6= 0 et on le note, par abus de langage, pq. 16 5.3 Relations d’ordre Définition 5.4 Soit E un ensemble on appelle relation d’ordre , une relation binaire qui vérifie les 3 propriétés suivantes : R est réflexive : xRx R est antisymétrique : si xRy et yRx alors x = y R est transitive : xRy et yRz ⇒ xRz. On dit qu’on a un ordre partiel sur E, et que E est partiellement ordonné par R. On notera ≤ les relations d’ordre partiel, par analogie avec la relation ” est plus petit ou egal ” qui définit une relation d’ordre sur IN. Définition 5.5 Soit E un ensemble et R une relation d’ordre sur E. On dit que x et y sont comparables si l’une des affirmations : xRy ou yRx est vraie Définition 5.6 Etant donné un ensemble E et une relation d’ordre R sur E, on dit que R est un ordre total sur E si, et seulement si, deux éléments quelconques de E sont comparables. Un ensemble muni d’une relation d’ordre total est dit totalement ordonné Définition 5.7 Etant donné un ensemble E et une relation d’ordre R sur E, on dit que R est un bon ordre sur E si, et seulement si, toute partie non vide de E possède un plus petit élément. Si R est un bon ordre sur E, on dit que E est un ensemble bien ordonné par R. Remarque 5.1 Un ensemble bien ordonné est totalement ordonné. En effet si x et y sont des éléments de E , alors {x, y} est une partie de E,elle possède donc un plus petit élément; et donc soit x ≤ y soit y ≤ x. Mais un ensemble totalement ordonné n’est pas forcément bien ordonné!! C ’est ainsi que Z et IR sont totalement ordonnés par la relation d’ordre classique ≤ sans être bien ordonnés : {x ∈ Z|x ≤ −1} et ]0, 1] ne possédent pas de plus petit élément. Définition 5.8 Etant donné un ensemble E muni d’une relation d’ordre R, on dit que E est un treillis si, et seulement si, toute partie finie non vide de E admet une borne supérieure et une borne inférieure. 17 5.4 Eléments particuliers d’un ensemble ordonné Etant donné un ensemble E muni d’une relation d’ordre ≤ et une partie A de E : On appelle maximum (ou plus grand élément) de A et on note M ax(A) tout élément x ∈ A vérifiant : (∀y ∈ E)(y ∈ A ⇒ y ≤ x) S’il existe, le maximum de A est unique. On appelle minimum ( ou plus petit élément) de A et on note M in(A) tout élément x ∈ A vérifiant : (∀y ∈ E)(y ∈ A ⇒ x ≤ y) S’il existe, le minimum de A est unique. On appelle majorant de A tout élément x ∈ E vérifiant: (∀y ∈ E)(y ∈ A ⇒ y ≤ x) Si un tel élément existe, A est dite majorée par x. Le maximum est un majorant qui appartient à A. On appelle minorant de A tout élément x ∈ E vérifiant: (∀y ∈ E)(y ∈ A ⇒ x ≤ y) Si un tel élément existe, A est dite minorée par x. Le minimum est un minorant qui appartient à A. On appelle borne supérieure de A et on note Sup(A) tout élément x ∈ E vérifiant : – x est un majorant de A – si a est un majorant de A : x ≤ a Si elle existe, la borne supérieure de A est unique : c’est le minimum de l’ensemble des majorants. Si la borne supérieure appartient à A, c’est un maximum. On appelle borne inférieure de A et on note Inf (A) tout élémentx ∈ E vérifiant : 18  – x est un minorant de A – si a est un minorant de A : a ≤ x Si elle existe, la borne inférieure de A est unique : c’est le maximum de l’ensemble des minorants. Si la borne inférieure appartient à A, c’est un minimum. On appelle élément maximal de A tout élément x ∈ A vérifiant : (∀y ∈ E)(y ∈ A et x ≤ y ⇒ x = y) Le maximum est un élément maximal. On appelle élément minimal de A tout élément x ∈ A vérifiant : (∀y ∈ E)(y ∈ A et y ≤ x ⇒ x = y) Le minimum est un élément minimal. 6 Quelques mots sur les applications Une application d’un ensemble E (dit ’ensemble de départ’) dans un ensemble F (dit ’ensemble d’arrivée’) est une correspondance qui associe à tout élément de E un et un seul élément de F. On note cette application : f : E → F ou f : x 7→ y = f (x) où : l’ élément y = f (x) de F est l’image de x par f et x est l’antécédent de y. Le graphe de f est la partie G de E × F constituée des éléments de la forme (x, f (x)), où x ∈ E. Une fonction de E dans F est une application de D dans F , où D ⊂ E est appelé domaine de définition (D = domf ) de la fonction f. Pour tout ensemble E, l’application de E dans E qui à tout élément x associe x, se note idE et s’appelle l’application identique ou identité de E. Deux applications f1 et f2 sont égales si elles ont même ensemble de départ E, même ensemble d’arrivée F et si ∀x ∈ E, f1 (x) = f2 (x). Définition 6.1 On appelle image d’une application f : E → F l’ensemble : Imf = {y ∈ F, ∃x ∈ E : y = f (x)} ce qui se traduit par : Imf est l’ensemble des éléments y de F tels qu’il existe au moins un élément x de E vérifiant y = f (x). 19  Par exemple, la fonction f : IR → IR, f : x → x2 est définie pour tout réel, c’est donc une application de IR dans IR. Montrons par double inclusion que Imf = IR+. En effet, l’élément f (x) = x2 est toujours √ positif √ d’où Imf ⊂ IR+ , de plus si a ∈ IR+ on peut écrire a = f ( a)(= ( a)2 ), ce qui montre que IR+ ⊂ Imf. Définition 6.2 Soient E et F deux ensembles et f : E → F une application. On dit que : l’application f est injective si : ∀x ∈ E, ∀x0 ∈ E (f (x) = f (x0 )) ⇒ (x = x0 ) l’application f est surjective si : ∀y ∈ F ∃x ∈ E tel que y = f (x), ( soit Imf = F ) l’application f est bijective, si : ∀y ∈ F ; ∃!x ∈ E tel que y = f (x) Par exemple,l’application x → sin x est surjective si on la considère comme application de IR dans [−1, +1]. Elle n’est pas injective puisque, par exem- ple, sin0 = sin2π. Elle est bijective si on la considère comme application de [ −π 2 , +π 2 ] sur [−1, +1]. Vous montrerez en exercice les résultats suivants : f n’est pas injective si vous pouvez exhiber deux éléments distincts de E qui ont la même image, f est injective si et seulement si : ∀x ∈ E; ∀x0 ∈ E; (x 6= x0 ) ⇒ (f (x) 6= f (x0 )) Proposition 6.1 Soient E et F deux ensembles et f : E → F une ap- plication. L’application f est bijective si et seulement si f est injective et surjective. Démonstration - Nous allons raisonner par double implication. Supposons que l’application est bijective, c’est-à-dire que, quel que soit y ∈ F , il existe un unique x ∈ E tel que y = f (x). Elle est donc surjective par définition. Montrons qu’elle est injective. 20  Soient deux éléments x et x0 de E tels que f (x) = f (x0 ). Posons y = f (x) alors on a aussi y = f (x0 ) et comme, par définition de la bijectivité, il n’y a qu’un seul antécedent à y, on a x = x0. On a donc (f (x) = f (x0 )) ⇒ (x = x0 ) et f est injective. Réciproquement, supposons que f est injective et surjective. Puisque f est surjective, ∀y ∈ F, ∃x ∈ E tel que y = f (x). Il reste à démontrer que cet antécédent x est unique. Supposons qu’il existe un deuxième antécédent x0 vérifiant donc y = f (x0 ), alors l’injectivité (f (x) = f (x0 )) ⇒ (x = x0 ), ce qui montre bien que l’antécédent est unique. 6.1 Composition des applications Définition 6.3 Soient E, F , G des ensembles et f : E → F , g : F → G des applications. La composée de f et g, notée g ◦ f (ce qui se lit ’g rond f ’) est l’application de E dans G définie par (g ◦ f )(x) = g(f (x)) pour tout x ∈ E. Soit f : E → F , alors on a f ◦ idE = f. En effet, idE : E → E donc la composition f ◦ idE : E → F est valide et ∀x ∈ E; f ◦ idE (x) = f (idE (x)) = f (x). On montre de la même manière que idF ◦ f = f Proposition 6.2 Soient E, F , G des ensembles et f : E → F , g : F → G , h : G → H des applications, alors on a: h ◦ (g ◦ f ) = (h ◦ g) ◦ f (associativité de la composition) et cette application est notée h ◦ g ◦ f : E → H. Démonstration - Par définition de la composition, on a h ◦ (g ◦ f ) : E → H et (h ◦ g) ◦ f : E → H, et, pour tout x de E : h ◦ (g ◦ f )(x) = h((g ◦ f )(x)) = h(g(f (x))) (h ◦ g) ◦ f (x) = (h ◦ g)(f (x)) = h(g(f (x))) d’où l’égalité des deux applications. Notons bien que la notation h ◦ g ◦ f n’a de sens que parce que l’on vient de démontrer que l’on obtient la même application en composant g ◦ f , puis en formant h ◦ (g ◦ f ) qu’en composant h ◦ g, pour former enfin (h ◦ g) ◦ f. Attention à la notation g◦f. Pour former (g◦f )(x), on applique d’abord f à x, puis g à f (x). La composée est notée g◦f , parce que (g◦f )(x) = g(f (x)). 21 6.2 Définition de l’application réciproque Définition 6.4 Soit f une application de E dans F , on dit que g, application de F dans E, est une application réciproque de f si on a f ◦ g = idF et g ◦ f = idE (1) C’est à dire ∀y ∈ F, (f ◦ g)(y) = y, et ∀x ∈ E, (g ◦ f )(x) = x. Proposition 6.3 Si f admet une application réciproque g , alors cette ap- plication réciproque est unique. Lorsque l’application réciproque de f existe on la note f −1. Démonstration : Pour montrer l’unicité de g, on suppose qu’il existe deux applications g1 et g2 qui vérifient (1). Alors on a g2 = g2 ◦ idF = g2 ◦ (f ◦ g1 ) = (g2 ◦ f ) ◦ g1 = idE ◦ g1 = g1 Proposition 6.4 Soit f est une application de E dans F 1. Si f est une application bijective, alors f admet une application réciproque f −1. De plus l’application f −1 est bijective de F dans E. 2. Si f admet une application réciproque, alors f est bijective Démonstration: 1. On suppose que f est bijective de E dans F. La démonstration se déroule en 2 étapes : tout d’abord l’existence de f −1 , puis le caractère bijectif de f −1. (a) Comme f est bijective, ∀y ∈ F, ∃!x ∈ E, y = f (x). Puisque x est unique on peut définir une application g : F → E par g(y) = x. Alors pour tout y de F , on a f (g(y)) = f (x) = y, par définition de g, d’où f ◦ g = idF. D’autre part, à x ∈ E on associe y = f (x) et donc g(y) = x(unicité de l’antécédent), ce qui donne x = g(f (x)), soit g ◦ f = idE. Donc g est l’application réciproque de f. (b) Soit x ∈ E, alors x = g(f (x)) et donc il existe y = f (x) élément de F tel que x = g(y), d’où g est surjective. Supposons que g(y) = g(y 0 ), alors f (g(y)) = f (g(y 0 )) soit y = y 0. L’application g est donc injective. 22  2. On suppose que f admet une application réciproque, on va montrer que f est bijective de E sur F. f (x) = f (x0 ) ⇒ f −1 (f (x)) = f −1 (f (x0 )) ⇒ x = x0 , donc f est injective. Soit y quelconque appartenant à F , alors y = f (f −1 (y)), donc y admet un antécédent dans E : c’est f −1 (y). f est surjective sur F Exemple : la fonction f : IR+ → IR+ , f : x → x2 , est une application bijective (elle ne le serait pas si l’on prenait IR comme ensemble √ de départ) −1 + + −1 et l’application inverse est f : IR → IR , f : x → x n’est autre que la fonction racine carrée ! Vous montrerez en exercice un résultat qui semble évident : (f −1 )−1 = f. 6.3 Composition des applications réciproques Proposition 6.5 Soient E, F , G des ensembles et f : E → F , g : F → G des applications bijectives. Alors l’application g ◦ f : E → G est bijective et (g ◦ f )−1 = f −1 ◦ g −1. Démonstration - Soit z ∈ G, alors ∃!y ∈ F , z = g(y) (g bijective), puis ∃!x ∈ E; y = f (x) (f bijective) et donc ∃!x ∈ E, z = g(f (x)) = (g ◦ f )(x), ce qui montre que g ◦ f est bijective. Elle admet donc une fonction réciproque (g ◦ f )−1 : G → E, unique solution de (g ◦ f )−1 ◦ (g ◦ f ) = idE et (g ◦ f ) ◦ (g ◦ f )−1 = idG : On peut montrer aisément que f −1 ◦ g −1 vérifie ces deux équations, de sorte que l’on a bien : (g ◦ f )−1 = f −1 ◦ g −1. 23