Cours d'Algèbre I 2023-2024 PDF

# Algèbre I ## Filière: Génie informatique ## Semestre 1 ### Pr. K. Belfakih #### Année Universitaire: 2023-2024 #### Université Ibn Zohr #### Faculté Polydisciplinaire - Taroudant ### Pr. K. Belfakih # Sommaire ## Généralités - Notion de logique - Base de la théorie des ensembles - Relations - Ar...

# Algèbre I ## Filière: Génie informatique ## Semestre 1 ### Pr. K. Belfakih #### Année Universitaire: 2023-2024 #### Université Ibn Zohr #### Faculté Polydisciplinaire - Taroudant ### Pr. K. Belfakih # Sommaire ## Généralités - Notion de logique - Base de la théorie des ensembles - Relations - Arithmétiques de Z - Applications ## Structures algébriques - Groupes, Anneaux - Ideaux, Corps. ## Polynômes et Fractions rationnelles - Notions de base sur les polynômes à une indéterminée - polynôme dérivé, Formule de Taylor - Propriétés arithmétiques des polynômes à coef ds R ou C - Thrm de D'Alembert-Gauss - Fractions rationnelles - Décomposition en éléments simples ds R(X) et ds C(X). # Chapitre I : Généralités ## I. Notion de logique : Proposition ### 1. Proposition #### Définition Une proposition (ou assertion) est un énoncé qui est soit vrai (v), soit faux (f), mais pas les deux en même temps. #### Exemples - "8-2=2" est une proposition qui est fausse. - "NCR est une proposition qui est vraie. - "Bonne journée” n'est pas une proposition. #### Remarques - Les propositions sont souvent notées P, Q, R,... - En effectuant la valeur 1 à la proposition vraie et 0 à la proposition fausse on aboutit à un tableau (ou une table) de vérité. ## I. Notion de logique : Connecteurs ### 2. Connecteurs On peut construire de nouvelles propositions à partir d'une ou plusieurs propositions données. ### 2.1 La négation #### Définition On appelle négation d'une proposition P la proposition notée ¬P, qui est vraie si P est fausse et fausse si P est vraie. | P | ¬P | | ---- | ---- | | 0 | 1 | | 1 | 0 | #### Exemples - La négation de "P : √5 < 5 " est "¬P : √5 > 5" . - La négation de "P : (−2) ∈ N" est "¬P : (−2) ∉ N" . ### 2.2 La conjonction #### Définition La conjonction de deux propositions P et Q est la proposition notée (P et Q) ou (P∧Q) et qui est vraie si P et Q sont toutes les deux vraies, et fausse dans les autres cas. | P | Q | P ∧ Q | |---|---|---| | 0 | 0 | 0 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 | #### Exemples - La proposition" (8 ≤ 10) ∧ (8 > 5)" est vraie. - La proposition" √10 = 5 et 181 = 3" est fausse . ### 2.2 La disjonction #### Définition La disjonction de deux propositions P et Q est la proposition notée (Pou Q) ou (P ∨ Q) et qui est fausse si P et Q sont toutes les deux fausses, et vraie dans les autres cas. | P | Q | P ∨ Q | |---|---|---| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 | #### Exemples - La proposition " 11 est un nombre premier ou 32 = 11" est vraie. - La proposition” (√2∈Z) ∨ (49=7)” est fausse. ### 2.2 L'implication #### Définition L'implication de deux propositions P et Q est la proposition notée (PQ) et qui est fausse si Pest vraie et Q est fausse, et qui est vraie dans les autres cas. | P | Q | P ⇒ Q | |---|---|---| | 0 | 0 | 1 | | 0 | 1 | 1 | | 1 | 0 | 0 | | 1 | 1 | 1 | #### Exemples - La proposition" 21 est impair ⇒ 0 = 1" est fausse. - La proposition" √6 = 3√9 = 3" est vraie. #### Remarque - La proposition Q → Pest la réciproque de P Q. - Les deux propositions P ⇒ Qet Q ⇒ P n'ont pas forcément la même valeur de vérité. ### 2.2 L'équivalence #### Définition L'équivalence de deux propositions Pet Qest la proposition notée (PQ) et qui est vraie si Pet Q ont la même valeur de vérité, et fausse dans le cas contraire. | P | Q | P ⇔ Q | |---|---|---| | 0 | 0 | 1 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 | #### Exemples - La proposition" 50 2 = 25 × 2 25 = 50" est vraie. - La proposition" √6 = 3 ⇔ √9 = 3" est fausse . #### Remarque - À l'aide du tableau de variété on peut montrer que les deux propositions "P ⇔ Q" et "(P ⇒ Q) ^ (Q ⇒ P)" ont la même valeur de vérité, donc elles sont équivalentes. ## I. Notion de logique : Quantificateurs ### 3. Les quantificateurs Une proposition P qui contient une ou plusieurs variables x, y, ... est souvent notée par P(x, y, ...). #### Définition - Les expressions "pour tout" ou "quelque soiť” s'écrivent en abrégé "∀". Il s'agit d'un quantificateur universel. - L'expression "il existe" (resp "il existe un seul") s'écrit en abrégé "∃" (resp∃!). Il s'agit d'un quantificateur universel. #### Exemples - "Pour tout réel x on a x² ≥ 0" s'écrit ” ∀x ∈ R; x² ≥ 0”. Cette proposition est vraie. - "Il existe un entier naturel qui est inférieur strictement à 0" s'écrit " ∃n ∈ N; n < 0”. Cette proposition est fausse. #### Remarque - Une proposition peut contenir plus qu'un quantificateur. - L'ordre des quantificateurs dans une proposition peut changer le sens de cette proposition. - La négation de "∀" est "∃". #### Exemples - "∀X ∈ R,∃n ∈ N; n ≥ x" est vrai, - "∃n ∈ N,∀X ∈ R; n ≥ x” est faux. - "∀x ∈ R, x² + 1 = x" est” ∃x ∈ R; x² + 1 ≠ x". - "∀x ∈ N,∃y ∈ N; x < y" est " ∃x ∈ N, ∀y ∈ N; x > y”. ## 4. Raisonnements logiques ### 4.1.Raisonnement déducatif (direct) #### Principe Pour montrer qu'une proposition Q est vraie il suffit que les deux propositions Pet P ⇒ Q soient vraie. #### Exemple Montrer que pour n ∈ N si n est divisible par 3 alors n² est divisible par 9. On suppose que n est divisible par 3, donc ∃k ∈ N tel que n = 3k ce qui donne n² = 9k2. Ainsi n² est divisible par 9, d'où le résultat. ### 4.2 Raisonnement par contraposée #### Principe Pour montrer qu'une proposition P ⇒Q est vraie on montre que sa contraposée ¬Q ⇒ ¬P est vraie. #### Exemple Montrer que pour n ∈ N, "n² est pair ⇒ n est pair". On montre que "n n'est pas pair → n² n'est pas pair". Puisque "n n'est pas pair ∃k ∈ N tel que n = 2k + 1 donc n² = (2k + 1)² = 2(2k² + 2k) + 1, ce qui signifie que n n'est pas pair, d'où le résultat. ### 4.3 Raisonnement par l'absurde #### Principe Pour montrer qu'une proposition Q est vraie on suppose qu'elle est fausse et on aboutit à une proposition fausse. #### Exemple: Montrer par l'absurde que √2 ∉ Q. ### 4.4 Raisonnement par récurrence #### Principe Soit P(n) une proposition qui dépend de l'entier naturel n et no un entier naturel fixe. Si - P(no) est vraie - ∀n ≥ no P(n) ⇒ P(n+1) Alors l'assertion "\n > no, P(n)" est vraie. # II. Bases de la théorie des ensembles ## non-définition Il n'existe pas de définition précise pour un ensemble, mais on peut dire que c'est une collection d'objets. ## Vocabulaires - Les ensembles ont des éléments qui leur apparteiennent. On note x ∈ E pour signifier l'appartenance d'un objet x à un ensemble E. Ainsi on dit que x appartient à E ou que x est un élément de E. - Pour décrire un ensemble on donne la liste de tous ses éléments (description en extension): E = {−2; 3; 0} ou bien on caractérise ses éléments par une propriété donnée (description en compréention): F = {z ∈ C, |z| = 1}. - L'ensemble qui ne contient aucun objet est appelé l'ensemble vide et il est noté Ø. ## Sous ensemble d'un ensemble Soient A et B deux ensembles. #### Definitions - Inclusion: A est dit inclus dans B si tout les éléments de A appartiennent à Bet on note AC B. Dans ce cas A est appelé sous ensemble de B. - Égalité: A et B sont dits égaux et on écrit A = B si ils ont les mêmes éléments. - Différence La différence de deux ensemble A et B, noté A- B est l'ensemble des éléments de A qui ne sont pas dans B. #### Exemples - N C Z ⊂ Q ⊂ R, - C Ø ⊂ R, - {x ∈ R, x² = 9} = {3; (-3)}. ## Ensemble de parties #### Définition Soit E un ensemble. L'ensemble des parties de E, noté P(E), est l'ensemble des sous ensembles de E. #### Exemples - E = {1,2} alors P(E) = {0; {1}; {2}; {1;2}}. - E = {1,2,3} alors P(E) = {0; {1}; {2}; {3}; {1;2}; {1;3}; {2; 3}; {1; 2; 3}}. ## Opération sur les ensembles Soit A et B deux parties d'un ensemble E. - L'union: L'union de deux ensembles A et B, noté AU B. est l'ensemble des éléments qui appartiennent à Aou B : AU B = {x ∈ Elx ∈ A ou x ∈ B} ou encore x ∈ AU B ⇔ (x ∈ A) ∨ (x ∈ B). - L'intersection de deux ensembles A et B, noté An B, est l'ensemble des éléments qui appartiennent à A et B : An B = {x ∈ Ex ∈ A et x ∈ B} ou encore x ∈ A∩B ⇔ (x ∈ A) ∧ (х є В). - Le complémentaire de A dans E, noté E\A OU CEA OU A, est l'ensemble des éléments qui appartiennent à E mais n'appartiennent pas à A : A = {x ∈ Ex & A} ou encore x ∈à ⇔ (x ∈ E) v (x & B). - La différence de A et B, noté A\B est l'ensemble des éléments de E qui appartiennent à A mais n'appartiennent pas à B: A\B = {x ∈ A\x ¢ B} ou encore x ∈ A\B ⇔ (x ∈ A) v (x ¢ B). - La différence symétrique de A et B, noté A∆B est l'ensemble des éléments de E qui sont soit dans A mais pas dans B, soit dans B mais pas dans A : x ∈ A∆Β ⇔ ((x ∈ A) ∧ (x ∉ B)) v ((х є В) л (х ¢ A)). ## Opérations sur les ensembles - Produit cartésien : Soient A, B deux ensembles. On appelle produit cartésien de A par B, noté A × B l'ensemble des couples (a, b) pris dans cet ordre où a ∈ A et b∈ B. A x B = {(a, b), a ∈ A, b ∈ B}. Dans le cas ou A = B on note A² pour A × A. #### Remarque - Si A, B sont des ensembles finis et si on désigne par Card(A) le nombre des éléments de A et Card(B) le nombre des éléments de B on aura. Card(A × B) = Card(A) × Card(B). #### Exemple: Soit A = {0,2,3,4}, B = {0,1,2,5}, E = {0,1,2,3,4,5, √7}. - ANE, AUE, - ANB, AU B, - CEA (ou encore A), CEB (ou encore B), - A\B, B\A, ΑΔΒ, - AxB, B × A, - Card(AUB), Card(A∩B), - Card(A × B), Card(B x A). #### Propriétés Soit A, B, C des parties d'un ensemble E. - A00=0; AUØ=A; AUA=A; ANA = A; - AUB = BUA; A∩B = BOA (la commutativité); - (A∩B) ก C = An (B∩C) (l'associativité); - (AUB) UC = AU (BÚ C) (l'associativité); - (A∩B) บ C = (AUC) ก (BUC) (la distributivité) - (AUB) ก C = (A∩C) บ (B∩C) (la distributivité); - (AUB) = A ∩ Bº; (A∩B) = Aº U Bº (lois de Morgan). #### Preuve: Montrer que (A ∪ B) ∩ C = (A ∩C) U (B∩C). Pour cela on montre que (AUB) n C c (An C) u (B∩C) et (An C) U (B∩C) c (AUB) ∩ C. - On a x ∈ (AUB) n C ⇒ (x ∈ (A∪ B)) ∧ (х∈ C) ⇒ ((x ∈ A) v (x ∈ B)) л (х є С) ⇒ ((x ∈ A) ∧ (x ∈ C)) v ((x ∈ B) ∧ (х∈ C)) ⇒ (x ∈ An C) v ((x ∈ B∩C)) ⇒ x ∈ (An C) U (B∩C). Donc (AUB) ก CC (A∩C) U (B∩C). De la même manière on montre l'autre inclusion. ## Partition d'un ensemble #### Définition On appelle partition d'un ensemble E toute famille F de parties non vides de E telle que - les élément de F sont deux à deux disjoints, i,e., VA, BEF, A∩B = 0, - Fest un recouvrement de E, i.e, UA∈F = E. #### Exemple Soit E = {0,1,2,3,4,5,6}, alors F₁ = {{0,1,2}; {3}; {4;5;6}} est une partition de E. F2 = {{0, 1}; {2, 3, 4; 5; 6}} est une partition de E. F2 = {{0,1,2}; {2,3}; {4; 5}} n'est pas une partition de E. #### Remarque - L'ensemble qui contient un seul élément a ∈ Е s'appelle un singleton : {a}. ## Applications ### Définition Une application f est définie par un ensemble de départ E, un ensemble d'arrivé F et la donnée, pour tout élément x de E, d'un élément unique de F appelé image de x par f et noté f(x). On dit que l'application f est de E dans F ou encore de E vers Fet on note f: E → F. #### Remarques - Si y = f(x) alors x s'appelle antécédent par f de y. - Une image y peut avoir deux antécédents, mais un antécédent ne peut jamais avoir deux images par une application. - Les deux mots application et fonction sont utilisés en général comme étant synonymes sauf que, pour une fonction un élément de E possède au plus une image de F par f. ### Exemples Soit f, g : R → R deux fonctions définies par f(x) = x² + 1 et g(x) = 1. f est une application alors que g ne l'est pas car 0 n'a pas d'image par g. ### Remarques - Deux applications f et g sont égales si elles ont le même ensemble de départ E, le même ensemble d'arrivée F et ∀x ∈ E, f(x) = g(x). On écrit f = g. - Si ECF alors l'application i : E → F définie par i(x) = x pour tout x ∈ E s'appelle l'injection canonique de E dans F. - Si E = F, l'application IE: E → F définie par IE(x) = x, notée aussi Ide, s'appelle l'application identique de E. ## Restriction, composée - **Restriction** #### Définition Soit f: E → F une application et A C E. L'application fA: A→ F définie par fA(x) = f(x) pour tout x ∈ A est appelée la restriction de f à A. On dit aussi que f est ün prolongement de fa - **Composée** #### Définition Soit f : E → Fet g : F → G deux applications. La composée de g et de f est l'application gof: E → G définie par go f(x) = g(f(x)) pour tout x ∈ E. #### Exemples - Soit f, g : R → R définies par f(x) = x + 3 et g(x) = x² Vx ∈ R. On a go f(x) = (x + 3)² = x² + 6x + 9, fo g(x) = x² + 3. On voit bien que go f ≠ fog. #### Proposition - Soit f : E → Fune application. Alors fole = f et IF 0 f = f. - Soit f: E→ F et g : F → Geth : G → H trois applications. On a (fog)oh=fo(goh) (l'associativité de la composition). ## Image direct, image réciproque - **Image direct** #### Définition Soit f : E → F une application et A C E. On appelle image direct de A par f le sous ensemble de F, noté f(A), qui est donné par f(A) = {y ∈ F/∃x ∈ A tel que f(x) = y} = {f(x) ∈ F/x ∈ A}. - **Image réciproque** #### Définition Soit f : E → F une application et B C F. On appelle image réciproque de B par f le sous ensemble de E, noté f−¹(B), qui est donné par f−¹(B) = {x ∈ E/f(x) ∈ B}. #### Exemples - Soit f : R → R l'application définie par f(x) = x² + 5. Trouver f([-1,2]). Or f([-1,2]) = {f(x), x ∈ [−1,2]} = {x² + 5, x ∈ [−1,2]}. x ∈ [−1,2] → −1 ≤ x ≤ 2 ⇒ (−1 ≤ x ≤ 0) v (0 ≤ x ≤ 2) ⇒ (5 ≤ x² +5 ≤ (−1)² + 5) v (5 ≤ x² + 5 ≤ 2² + 5) ⇒ (5 ≤ x² + 5 ≤ 6) v (5 ≤ x² + 5 ≤ 9) ⇒ (5 ≤ x² + 5 ≤ 9) Donc f([-1,2]) = [5, 9]. - Soit f: R→ R définie par f(x) = |x\. Trouver f-1({-7}) et f-1([2,3]). f−¹({−7}) = {x ∈ R/f(x) = −7} = {x ∈ R/|x| = −7}. D'où f−¹({−7}) = 0. f¯¹([2,3]) = {x ∈ R/f(x) ∈ [2,3]} = {x ∈ R/2 ≤ |x| ≤ 3} = {x ∈ R/(−3 ≤ x ≤ −2) v (2 ≤ x ≤ 3)} = {x ∈ R/(x ∈ [−3, −2]) v (x ∈ [2, 3])} = {x ∈ R/x ∈ [−3, -2] U [2, 3]} Ainsi f−¹([2,3]) = [−3, −2] U [2, 3]. ## Injection, surjection, bijection - **Application injective** #### Définition Soit f: E → F une application. f est dite injective si VX1, X2 ∈ E; f(x1) = f(x2) ⇒ X₁ = X2. f injective VX1, X2 ∈ E, f(x1) = f(X2) ⇒ X₁ = X2 VX1, X2 E E, X1 ≠ X2 ⇒ f(x1) ≠ f(x2) #### Exemples: - Soit f: R → R l'application définie par f(x) = −x+11. f(x1) = f(x2) ⇒ −X1 + 11 = −X2 + 11 ⇒ X₁ = x2. Donc f est injective. - Soit g : R→ R+ l'application définie par g(x) = x². g(x1) = g(x2) ⇒ x} = x2 ⇒ X1 = X2 ou X₁ = −X2. Donc f n'est pas injective. En effet f(2) = f(−2) mais 2 ≠ −2. - **Application surjective** #### Définition Soit f : E → Fune application. f est dite surjective si tout ye Fadmet un antécédent dans E. f surjective ⇔ ∀y ∈ F, ∃x ∈ E; f(x) = y ⇒ f(E) = F. #### Exemples: - Soit f: R→ R l'application définie par f(x) = \x\. L'application f n'est pas surjective car –1 n'a pas d'antécédent. - Soit g: R→ R l'application définie par g(x) = x − 9. L'application g est surjective car pour tout réel y l'équation x-9 = y admet toujours une solution. - **Applicion bijective** #### Définition Soit f : E → F une application. f est dite bijective si elle est injective et surjective, autrement dit sitout élément de E est l'image d'un unique élément de E. f bijective ⇔ ∀y ∈ F,∃!x ∈ E; f(x) = y. #### Exemples: - Soit f: R R l'application définie par f(x) = |x\. f n'est pas une application bijective car elle n'est pas surjective. - Soit g: R→ R l'application définie par g(x) = x + 1. gest bijective car elle est injective et surjective. - **Applicion réciproque** #### Definition Soit f: E F une application bijective. On appelle application réciproque de f l'application notée f-¹ définie par f1:FE et f-¹(y) = x avec f(x) = y. { SXEE [f-1(y) = x f(x) = y yeF #### Example: L'application f: R→R définie par f(x) = 2x + 1 est une application bijective et son application réciproque est f-1 : R → R définie par f-1(x) = ½ ∀x ∈ R. #### Remarques : - f est bijective ⇔ f−¹ est bijective, - (f-1)-1 = f - fo f−1 = Idf; f−1 o f = Ide - (go f)−1 = f-10g-1. #### Proposition - Sif et g sont injectives alors go f est injective. - Sif et g sont surjectives alors go f est surjective. - Sif et g sont bijectives alors go f est bijective. # III. Relations binaires ## Définition Soit E un ensemble. On appelle relation binaire toute assertion entre deux objets, pouvant être vérifiée ou non. Si x est lié à y par la relation R on note xRy et on lit : "x est en relation avec y. ## Exemples - Dans Z on définit la relation de divisibilité notée | par VX, y ∈ Z, xRy ⇔ xly. - Dans R on définit la relation R par Vx, y ∈ R, xRy ⇔ x² = y². ## Le graphe de R #### Définition Soit E un ensemble et R une relation binaire définie sur E. Le graphe de R, noté Gr est la partie de E × E définie par #### Exemples: - Dans l'exemple (1), où R est la relation de divisibilité sur Z, le graphe de la relation R est Gr := {(x, y) ∈ Z x Z; x|y}. On a (2,-4) ∈ Gr mais (5,22) & GR. - Dans l'exemple (2), où R est définie sur R par Vx, y ∈ R, xRy ⇔ x² = y², le graphe de la relation R est GR := {(x, y) ∈ R × R|x² = y²}. On a (1, (-1)) ∈ Gr mais (5,22) & GR. ## Relations binaires : Propriétés #### Propriétés Soit R une relation binaire définie sur un ensemble E. - R est réfléxive ⇔ ∀x ∈ E : (xRx), - Rest symétrique ⇔ ∀x, y ∈ E : (xRy) ⇒ (yRx), - R est antisymétrique ⇔ ∀x,y ∈ E : (xRy)^(yRx) ⇒ x = y, - R est transitive ⇔ ∀x, y, z∈ E: (xRy)^(yRz) ⇒ (xRz). #### Exemples - Dans l'exemple (1) la relation R (de divisibilité dans Z) est : - réflexive: Vx ∈ Z on a xlx, - transitive: ∀x, y, z ∈ Z : (x|y) ^ (y\z) ⇒ x\z, - n'est pas antisymétrique : ∀x, y, ∈ Z : (xy) (y\x) ⇒ x = y, - n'est pas symétrique : Vx, y ∈ Z xly # y\x. - Dans l'exemple (2) où R est définie sur R par Rest: Vx, y ∈ R, xRy ⇔ x² = y², - réflexive: ∀x ∈ R, x2 = x², - transitive: ∀x, y, z ∈ R, (x² = y²) ^ (y² = z²) ⇒ x2 = z², - n'est pas antisymétrique: ∀x, y, ∈ R, (x² = y²) ^ (y² = x²) ⇒ x = y, - est symétrique : ∀x, y ∈ R, x² = y² + y² = x², ## Relations d'équivalence #### Définition On dit qu'une relation binaire R est une relation d'équivalence si elle est réfléxive, symétrique et transitive. Une telle relation peut se noter x = y (modulo R). #### Example • Dans un ensemble non vide E, la relation d'égalité xRyx = y est une relation d'équivalence. En effet - R est réflexive: ∀x ∈ E on a x = x. - R est symétrique: ∀x, y ∈ E. if x = y alors y = x. - Rest transitive : ∀x, y, z ∈ E. if x = y et y = z alors x = z. ## Classes d'équivalence #### Soit R une relation d'équivalence définie sur un ensemble non vide E. #### Pour x ∈ E on appelle classe d'équivalence de x pour R, notée X, le sous ensemble #### Vocabulaires : - **X = {y ∈ E\xRy}.** - **Tout élément y appartenant à une classe X est appelé représentant de X.** - **L'ensemble de toutes les classes d'équivalence de E pour la relation R est appelé ensemble quotient de E pour R et on le note par E/R** #### Remarques - La classe x est aussi noté x, [x] ou encore Cl(x). - Les éléments de E/R (les classes d'équivalence de E pour la relation R) sont des sous ensembles de E. #### Exemples: - Pour la relation d'équivalence de l'égalité sur un ensemble E (xRy ⇔ x = y) on a X = {x}. - Soit f: E F une application. La relation xRy → f(x) = f(y) est une relation d'équivalence (appelée relation d'équivalence associée à f). En effet - R est réflexive : ∀x ∈ E on a f(x) = f(x). - R est symétrique : ∀x, y ∈ E, si f(x) = f(y) alors f(y) = f(x). - Rest transitive: ∀x, y, z ∈ E, si f(x) = f(y) et f(y) = f(z) alors f(x) = f(z). - Pour x ∈ E on a X = {y ∈ E\f(y) = f(x)} = f–1({f(x)}). #### Propriétés - Soit R une relation d'équivalence définit sur un ensemble non vide E. - Vx, y ∈ E, xRy ⇒ x = ӯ, - sixey alors y ∈ X, - si x ∈ ŷ alors X = y, - Les classes d'équivalence forment une partition de E: - les éléments de E/R sont deux à deux disjoints: xyxny= 0, - E/R est un recouvrement de E : UxEE/R = E. ## Relations d'ordre #### Définition Une relation binaire sur un ensemble E est dite relation d'ordre si elle est réfléxive, transitive et anti-symétrique. #### Example • Soit E un ensemble non vide. On définie la relation binaire R sur P(E) par : VA, BCE, ARB ACB. - R est réflexive: pour tout ACE on a ACA, - Rest transitive: pour tout A, B, C CE, si Ac Bet BCC alors A C C, - Rest anti-symétrique : pour tout A, B CE, si Ac Bet BCA alors A = B, - R est une relation d'ordre. #### On a vu dans un exemple précédent que la relation R de divisibilité sur Z n'est pas anti-symétrique donc ce n'est une relation d'ordre dans Z. En revanche R est une relation d'ordre sur N. En effet R est - réflexive: Vx ∈ N on a xix, - transitive: ∀x, y, z∈N: (xy) ^ (yz) ⇒ xiz, - est antisymétrique: ∀x, y, ∈N: (xy) (y\x) ⇒ x = y, ## Relations d'ordre total Une relation d'ordre R sur un ensemble E est dite d'ordre total si deux éléments quelconques sont toujours comparables : x,y ∈ E, (xRy) v (yRx). Si la relation n'est pas d'ordre total elle est dite d'ordre partiel. #### Example Reprenons l'exemple où R est définit sur P(E) par VA, BCE, ARB AC В. Si on prend E = {1,2} alors on a {1} £ {2} et {2} £ {1}, donc la relation R n'est pas d'ordre total, il est d'ordre partiel. # Arithmétique de Z ## Rappels: - L'ensemble des entiers naturels N est donné par N = {0, 1; 2; 3; 4; 5; ...}, et on a N* = N \ {0}. - L'ensemble des entiers relatifs Z est donné par Z = {..... -2;-1;0; 1; 2; ...}, et on a Z* = Z \ {0}. - La relation de divisibilité sur Z n'est pas une relation d'ordre et la relation de divisibilité sur N est une relation d'ordre partiel. ## Divisibilité Soit a, b ∈ Z. On dit que a divise b, et on note alb, s'il existe k ∈ Z tel que b = k x a. On dit aussi que b est divisible par a. ## Divisibilté #### Exemples 2|(-14), (-5)|555 mais 9 ne divise pas (-14789). #### Notation et définition Soit a ∈ Z. On note par D(a) l'ensemble des diviseurs de l'entier a: D(a) = {k ∈ Z, k divise a}. Soit a ∈ Z. On dit que a est premier si |a| ≠ 1 et D(a) = {-1; 1; a