Math Congruence PDF

Preview

Summary

Cours complet congruence...

Description

COURS SEMESTRE I

M1201 Math discrètes Logique – Arithmétique – Relations binaires 1

CHAPITRE 4

LES RELATIONS

117

I PRODUIT CARTESIEN I1. Produit cartésien de deux ensembles: Soient E et F deux ensembles donnés, le produit cartésien de E et de F (ou produit de E par F) est l’ensemble des couples (x, y) où x est élément de E et y élément de F.

E × F = {(x, y )tels que x ∈ E et y ∈ F}

118

Remarques: x et y sont les composantes du couple (x, y)=(x’, y’)⇔ x=x’ et y=y’ Lorsque E = F le produit s’appelle carré cartésien de E , noté E×E ou E²

119

I2. Généralisation: Le concept de produit cartésien peut être généralisé à un nombre fini d’ensembles. Soient E1 ,E 2 ,...En , E1 × E 2 × ...× En sera l'ensemble suivant: E1 × E2 × ...× En = {( x1 ,x2 ,...,xn ) tels que x1 ∈ E1 ,x2 ∈ E2 ,...,xn ∈ En } Soit E, E n sera l'ensemble suivant: E n = {( x1 ,x2 ,...,xn ) tels que x1 ∈ E,x2 ∈ E ,...,xn ∈ E

}

(x1,x 2 , ,x n ) est appelé un n-uplet 120

Exercices A={x, y, z} ; B={1,2}. Ecrire A×B et B×A puis conclure. A={x, y, z} ; B={1,2}; C={α} Ecrire (A×B)×C et A×(B×C) puis conclure.

121

II RELATIONS II1. Relation et prédicat: Définition 1: Soient E et F deux ensembles et E×F leur produit cartésien. Une relation sur E×F est un prédicat défini sur E×F . ∀x ∈ E, ∀y ∈ F x est en relation avec y par R ⇔ xRy ⇔ R(x, y)

122

Quelques relations incontournables. dans R ;≤ ;≥;=;≠; Dans Z ≡; | ; Dans P(E)

⊂

123

II2. Relation et graphe: Définition 2: Le graphe de la relation R est le sous-ensemble correspondant G de E×F. La relation R est définie à l’aide de son graphe G

G = {( x , y) ∈ E × F t.q x R y} 124

Exemple 1 Soit E et F deux parties de R. E=[a, b]; F=[c, d] Voici une représentation cartésienne de E×F d E×F c

a

Soit GR=E×F, comment définir cette relation à l’aide d’un prédicat? 125

Exemple 2 A={1, 2, 3, 4, 5, 6} B={2, 6, 8, 9} GR ={(1,2),(1,6),(1,8),(1,9),(2,2),(2,6),(2,8), (3,6),(3,9),(4,8),(6,6)} Comment définir cette relation à l’aide d’un prédicat?

126

Exemple 3 Soit E un ensemble donné. On appelle identité de E et on note IE ou 1 E la relation binaire définie sur E par:

∀(x, y) ∈ E 2 , x 1E y ⇔ x = y Comment définir cette relation à l’aide de son graphe, noté ∆ E ?

127

On en conclut le résultat suivant

Soit R une relation définie su r E × F, E et F deu x ensemble s donnés. Soit G R son graph e; ∀ (x, y ) ∈ E × F, x R y ⇔ (x, y ) ∈ G R

128

Relation et matrice booléenne Soit la matrice M suivante :  x11 x12  x1n     x x x  21 22 2n  M =  , xij est un booléen soit xij ∈ {0 ,1}     x x x  pn   p 1 p2

M représente alors une relation sur E × F où E = {e1 ,e2 , ,e p } F = { f1 , f2 , , fn }, de plus : ei Rf j ⇔ xij = 1 129

III PROPRIETES DES RELATIONS R est une relation définie sur E × E ou relation binaire définie sur E 1. R est réflexive 2. R est antiréflexive

∀x ∈ E, x R x

∀x ∈ E, xR x

130

3. R est symétrique

∀(x, y) ∈ E 2 ,xRy  yRx remarque: ⇔ ∀(x, y) ∈ E 2 ,xRy ⇔ yRx 4. R est antisymétrique

∀(x, y) ∈ E 2 ,[xRy ∧ yRx ]  x = y

131

5. R est transitive

∀(x, y,z) ∈ E 3 ,[xRy ∧ yRz ]  xRz

6. R est circulaire

∀(x, y,z) ∈ E 3,[xRy ∧ yRz ]  zRx

132

EXERCICES (travail personnel à rendre suivant les indications données en cours)

1. La relation divise sur Z est réflexive. 2. Soit la relation S1 définie sur Z par : ∀ (x,y ) ∈ Z 2 , xS1 y ⇔ x − y est pair Montrer que S1 est symétrique. 3. Soit la relation S2 définie sur Z par : Soit la re lation binaire S définie sur Z par: ∀( x,y) ∈ Z 2 , xS 2 y ⇔ x + y est pair Montrer que S2 est transitive. 133

III RELATIONS D’ EQUIVALENCE III.1 Définition et exemples: Définition 1: Une relation R définie sur E est une relation d’équivalence sur E si R est à la fois réflexive, symétrique et transitive.

134

Définition 2: R est une relation d’équivalence définie sur E, et x∈E. On appelle classe d’équivalence de x (modulo R) et on note x l’ensemble suivant:

x = {y ∈ E tq x R y}

135

Définition 3: L’ensemble des classes d’équivalence modulo R est appelé ensemble quotient de E par R et est noté Remarque:

E E

R

R

= {c ∈ P(E) tq ∃ x ∈ E tq x = c}

E

R

⊂ P(E) ⇔ E

R

∈ P(P(E)) 136

III.2 Congruence modulo n Soit n un entier naturel différent de 0, on définit la congruence modulo n par :

n ∈ N * , x ≡ y( n ) ⇔ ∃k ∈ Z / x − y = kn x ≡ y( n ) se lit « x est congru à y modulo n » Théorème : La congruence modulo n est une relation d’équivalence. Démonstration (en cours)

137

IV RELATIONS D’ORDRE SUR E IV.1 Définition, exemples: Définition: Soit R une relation binaire définie sur E. On dit que R est une relation d’ordre sur E si R est réflexive, antisymétrique, transitive.

138

Notation: Une relation d’ordre sera notée par un signe spécifique soit par: «  » On pourra lire: « x  y » « x est dominé par y »

139

Exemples Sur N, Z, Q, R les relations classiques, ≤, ≥ sont des relations d ’ordre . Les relations < et > ne sont pas des relations d ’ordre car elles ne sont pas réflexives.

140

EXERCICE (travail personnel à rendre suivant les indications données en cours)

Soit E un ensemble donné et soit P(E) et soit la relation définie sur P(E) par:

∀(A, B) ∈ (P(E)) 2 , A R B ⇔ A ⊂ B l’inclusion est une relation d ’ordre sur E.

141

EXERCICE (travail personnel à rendre suivant les indications données en cours)

Considérons la relation « divise » sur N

∀(a, b) ∈ N 2 , a b ⇔ (∃k ∈ N tq b = ka ) Cette relation est une relation d ’ordre sur N.

142

IV2. Ordre total, ordre partiel Définition: Une relation d ’ordre,  sur un ensemble E est appelée ordre total si pour tous éléments x et y de E, x et y sont comparables.

∀( x, y ) ∈ E 2 , x  y ∨ y  x Les relations précédemment évoquées ≤ ou ≥ sont des ordres totaux.

143

Définition: Une relation, d ’ordre  sur un ensemble E qui n ’est pas une relation d ’ordre total est une relation d ’ordre partiel . En prenant la négation de la proposition précédente:

∃(x, y ) ∈ E 2 tq x  y ∧ y  x x et y sont alors 2 éléments non comparables.

144

Exemple 1. Considérons la structure ordonnée (P(E), ⊂) où E est un ensemble non vide et possède au moins 2 éléments. Alors

∃({e1 },{e2 })∈ P(E)2 tq

{e1 }⊄ {e2 }∧ {e2 }⊄ {e1 }

145

IV3. Eléments remarquables d ’une partie d ’un ensemble ordonné. IV3.1 Majorants, minorants d ’une partie X de ( E ,  ) Définition: ( E , ) est une structure ordonnée, X est une partie de E, a un élément de E est un majorant de X si

∀x ∈ X, x  a

146

Définition :

(E ,  )

est une structure ordonnée, X est une partie de E b un élément de E est un minorant de X si

∀x ∈ X, b  x

147

Exemple 1 Soient

E = {e 1 , e 2 , e 3 } et A = {e 1 , e 2 } P(A) = {φ , {e 1 }, {e 2 }, A} On munit P(E) de la relation ⊂ . (P(E), ⊂ ) est un ensemble ordonné.

φ est un minorant de P(A). A est un majorant de P(A). E est un majorant de P(A)

148

Diagramme de Hasse Le diagramme de Hasse de ( E,  ) est une représentation graphique qui contient toutes les informations concernant la relation d’ordre ∀ (x, y) ∈ E2 , représentée: x  y si partant du sommet x on peut atteindre le sommet y en montant le long des arêtes

.

149

Diagramme de Hasse : (P(E), ⊂) E = {e1, e2, e3} E {e1,e2} {e1}

{e 1,e3 } {e2 }

{e2 ,e3} {e 3}

∅ 150

EXERCICE (travail personnel à rendre suivant les indications données en cours)

Soit

( R, ≤ ) et B = {1 n , n ∈ N *} 0 est un minorant de B. 1 est un majorant de B. en effet ∀ x ∈ B 0 ≤ x ≤ 1

151

IV3.2 Plus grand élément, plus petit élément d ’un ensemble (ou d ’une partie) ordonné(e). Soit E un ensemble ordonné par  et soit X une partie de E.

Définition : M ∈ E, M est le plus grand élément de X si : M ∈ X ∧ ∀ x ∈X, x  M En d’autres termes: M est un élément de X et M est un majorant de X.

152

Exemples: On reprend les exemples précédents. A-t-on un plus grand élément?

Remarque et notation : Par définition du plus grand élément, lorsqu’il existe celui-ci est unique et se note max(X) (maximum) Preuve: par l’absurde, soient M1 et M2 etc… 153

Définition : Soit E un ensemble ordonné par  et soit X une partie de E. m ∈ E, m est le plus petit élément de X si : m ∈X ∧ ∀ x ∈X, m  x En d’autres termes: m est un élément de X et m est un minorant de X.

154

Remarque et notation: Par définition du plus petit élément, lorsqu’il existe celui-ci est unique et se note min(X) (minimum) Preuve: par l’absurde, soient m1 et m2 etc…

155

Exercices: 1. (R, ≤ ) X1 = [a, b]; X2 = ]a, b[ 2. (N, ≤ ) X = N 3. (R, ≤ ) X = {(-1)k, k ∈Z } 4. Soit ( X , ) où X = {2,4,6,8,10,28,50} Déterminer min(X), max(X),s’ils existent

156

IV3.3 Borne supérieure d’une partie majorée. Borne inférieure d’une partie minorée. Définitions et notations : Soit E un ensemble ordonné par  et soit X une partie de E. 1. Major(X) = a ∈ E tq ∀x ∈ X, x  a

{

}

Major(X) est l’ensemble des majorants de X. De plus X est une partie majorée de E si Major(X) ≠ ∅

157

2. Minor(X) =

{b ∈ E tq ∀x ∈ X, b  x}

Minor(X) est l’ensemble des minorants de X. De plus X est une partie minorée de E si Minor(X) ≠ ∅

158

Définitions : 1. Soit X une partie majorée de (E,  ). Considérons l’ensemble des majorants de X. Si Major(X) admet un plus petit élément alors il s’appelle la borne supérieure de X et il est unique. Notation: SupE(X) = min(Major(X))

SupE (X) est le plus petit des majorants de X.

159

2. Soit X une partie minorée de (E,  ). Considérons l’ensemble des minorants de X. Si Minor(X) admet un plus grand élément alors il s’appelle la borne inférieure de X et il est unique. Notation: InfE(X) = max(Minor(X))

InfE(X) est le plus grand des minorants de X.

160

Proposition 1: Soit X une partie de (E,  ).Les propositions suivantes sont équivalentes: 1. X admet un plus grand élément. 2. X admet une borne supérieure et SupE (X) ∈X

Preuve:

161

Proposition 2: Soit X une partie de (E,  ).Les propositions suivantes sont équivalentes: 1. X admet un plus petit élément. 2. X admet une borne inférieure et InfE(X) ∈ X

Preuve:

162

Exemples 1 et 2 1. Dans (R,≤ ) infR([a,b]); infR(]a,b[) sup R([a,b]); sup R(]a,b[) 2. Dans (P(E), ⊂ ) Que peut-on dire de supP(E) ({X, Y}) ? infP(E)({X, Y}) ? Où X et Y sont éléments de P(E).

163

EXERCICE (travail personnel à rendre suivant les indications données en cours)

1. Dans (R,≤) Soit X ={1/n + (-1)n, n ∈N*} sup R(X) et infR(X)

164

Diagramme de Hasse de ( E,  ) 11

6

7

3

4

5

1

2 0

écrire le graphe de cette relation. 165

•Y-a-t-il un plus petit élément dans E? •Y-a-t-il un plus grand élément dans E? •Soit X = {1,2 ,4 ,5 ,7} , déterminer s’ils existent min(X),max(X) Major(X),Minor(X) infE(X),sup E(X)

166

Exercice: • Enumérer les éléments de D*70. • Faire le diagramme de Hasse de ( D*70, | ) . • Quel est le minimum de ( D*70 , | ) ? • Quel est le maximum de ( D*70, | ) ? • Soit X={5,7,35} Déterminer s’ils existent Min(X), max(X) Major(X), Minor(X) puis infE(X), supE (X) 167...