Christophe Bertault — Mathématiques en MPSI RELATIONS BINAIRES Dans tout ce cha
Christophe Bertault — Mathématiques en MPSI RELATIONS BINAIRES Dans tout ce chapitre, E est un ensemble quelconque. 1 RELATIONS BINAIRES SUR UN ENSEMBLE • Les relations sont partout — et dans le monde mathématique, et dans la vraie vie. Nous passons notre temps à comparer des objets, à les mettre en rapport les uns avec les autres selon tel ou tel aspect. Les phrases suivantes, pourtant diverses, sont toutes l’affirmation d’un lien entre deux objets : « Minou et Matou ont la même couleur de poils », « 3 ⩽5 », « Machin est amoureux de Bidule », « 4 divise 12 », « Pierre est plus âgé que Paul », « 1+i et 1 −i ont le même module », etc. • De quelle manière pourrions-nous définir proprement la notion de relation en mathématiques ? Quel OBJET la relation < est-elle sur l’ensemble ⟦1,4⟧? Ce qui est sûr, c’est qu’elle est régie par les relations suivantes : 1 < 2, 1 < 3, 1 < 4, 2 < 3, 2 < 4 et 3 < 4. Formellement, nous pouvons DÉFINIR la relation < comme l’ensemble : ¦ (1,2),(1,3),(1,4),(2,3),(2,4),(3,4) © des couples (x, y) ∈⟦1,4⟧2 pour lesquels : x < y, car connaître cet ensemble, c’est exactement connaître la rela- tion <. Dans ce cas, la relation ⩽sur ⟦1,4⟧est l’ensemble : ¦ (1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4) © . Ces remarques préliminaires conduisent à la définition suivante : Définition (Relation binaire sur un ensemble) On appelle relation binaire sur E toute partie de E × E. Si R est une telle relation, la proposition : (x, y) ∈R sera notée de préférence : x R y pour tous x, y ∈E, et lue : « x est en relation avec y par R ». $ Attention ! Parce que le couple (x, y) n’est pas le couple (y, x), la relation : x R y peut être vraie sans que la relation : y R x le soit. Vous savez sans doute qu’on peut être amoureux sans être aimé en retour. Exemple Vous connaissez depuis toujours certaines relations binaires : — la relation d’égalité = sur E, — les relations ⩽et < sur R, — la relation d’inclusion ⊂sur P (E), — la relation ⩽sur RR, définie pour toutes fonctions f, g ∈RR par : f ⩽g ⇐⇒ ∀x ∈R, f (x) ⩽g(x), — la relation de divisibilité | sur Z, définie pour tous m, n ∈Z par : m|n ⇐⇒ ∃k ∈Z, n = km, — pour tout α ∈R, la relation ≡[α] de congruence modulo α sur R, définie pour tous x, y ∈R par : x ≡y [α] ⇐⇒ ∃k ∈Z, x = y + kα. Définition (Propriétés des relations binaires) Soit R une relation binaire sur E. • On dit que R est réflexive si : ∀x ∈E, x R x. • On dit que R est transitive si : ∀x, y,z ∈E, x R y et y R z =⇒ x R z. • On dit que R est symétrique si : ∀x, y ∈E, x R y =⇒ y R x. • On dit que R est antisymétrique si : ∀x, y ∈E, x R y et y R x =⇒ x = y. Exemple • La relation d’égalité = sur E est réflexive, transitive, symétrique et antisymétrique. • Les relations ⩽sur R et RR sont réflexives, transitives et antisymétriques. Elles ne sont pas symétriques car par exemple : 1 ⩽2 mais : 2 1, et de même : (x 7−→1) ⩽(x 7−→2) mais : (x 7−→2) (x 7−→1). • La relation < sur R est transitive et antisymétrique, mais elle n’est ni réflexive, ni symétrique. 1 Christophe Bertault — Mathématiques en MPSI • La relation | de divisibilité sur Z est réflexive et transitive, mais elle n’est pas antisymétrique car par exemple : −2|2 et 2| −2 alors que : −2 ̸= 2. • La relation d’inclusion ⊂sur P (E) est réflexive, transitive et antisymétrique. • La relation « avoir le même signe » sur R∗est réflexive, transitive et symétrique. Définition (Éléments comparables, relation binaire totale/partielle) Soit R une relation binaire sur E. • Deux éléments x ∈E et y ∈E sont dits comparables (par R) si : x R y ou y R x — éventuellement les deux. • On dit que la relation R est totale si deux éléments quelconques de E sont toujours comparables par R, i.e. si : ∀x, y ∈E, x R y ou y R x. Une relation non totale est dite partielle. $ Attention ! Toute relation binaire n’est pas totale ! Quand vous voulez montrer que x R y pour certains x, y ∈E, ne raisonnez pas par l’absurde en supposant que y R x, il est possible qu’aucune de ces deux relations ne soit vraie. Exemple • La relation ⩽sur R est totale. En particulier, tous les réels sont comparables à 0 — positifs ou négatifs — et c’est pourquoi, par exemple, on a eu le droit de définir la fonction valeur absolue |x| sur R en distinguant deux cas : x ⩾0 et x < 0. • La relation ⩽sur RR est partielle car, par exemple, sin et cos ne sont pas comparables : sin cos et cos sin. • La relation de divisibilité | sur Z est partielle car 2 et 3 ne sont comparables, on n’a ni : 2 ̸ | 3, ni : 3 ̸ | 2. • La relation d’inclusion ⊂sur P (E) est partielle dès que E contient au moins deux éléments. En effet, pour tous a et b éléments DISTINCTS de E : a ̸⊂ b et b ̸⊂ a . 2 RELATIONS D’ÉQUIVALENCE Définition (Relation d’équivalence) On appelle relation d’équivalence sur E toute relation binaire sur E qui est à la fois réflexive, transitive et symétrique. Les relations d’équivalence sont généralement notées ∼ou ≃ou ≈ou ≡... Exemple La relation d’égalité = sur E et la relation « avoir le même signe » sur R∗sont des relations d’équivalence. Exemple Pour tout α ∈R, la relation ≡[α] de congruence modulo α sur R est une relation d’équivalence. De manière analogue, pour tout n ∈N, la relation ≡[n] de congruence modulo n sur Z est une relation d’équivalence. Démonstration Soit α ∈R. • Réflexivité : Pour tout a ∈R : a = a + 0 × α avec : 0 ∈Z, donc : a ≡a [α]. • Transitivité : Soient a, b, c ∈R. On suppose que : a ≡b [α] et b ≡c [α], i.e. : a = b + kα et b = c + lα pour certains k, l ∈Z. Alors : a = b + kα = (c + lα)+ kα = c + (k + l)α avec : k + l ∈Z, donc : a ≡c [α]. • Symétrie : Soient a, b ∈R. On suppose que : a ≡b [α], i.e. : a = b + kα pour un certain k ∈Z. Alors : b = a + (−k)α avec : −k ∈Z, donc : b ≡a [α]. 2 Christophe Bertault — Mathématiques en MPSI Théorème (Classes d’équivalence d’une relation d’équivalence, ensemble quotient) Soit ∼une relation d’équiva- lence sur E. • Pour tout x ∈E, l’ensemble y ∈E | x ∼y est appelé la classe d’équivalence de x (pour ∼). Les classes d’équivalences pour ∼forment une partition de E. Cela revient à dire qu’elle sont non vides, que leur réunion est E tout entier, et qu’elles sont deux à deux égales ou disjointes. • L’ensemble des classes d’équivalences de E pour ∼est appelé l’ensemble quotient de E par ∼et souvent noté E ∼. La notion d’ensemble quotient est hors programme mais il n’est pas inutile de l’avoir quelque part en tête. Vous noterez bien que le quotient E ∼est un ENSEMBLE D’ENSEMBLES, en l’occurrence un ensemble de parties de E. E Une classe d’équivalence Une classe d’équivalence Une classe d’équivalence Ce que ce théorème raconte, c’est que la relation d’équivalence ∼peut être représentée comme une carte au sens géographique. Chaque classe d’équiva- lence est comme un pays à l’intérieur de E dont les éléments sont caractérisés par une certaine nationalité. Le monde E se trouve ainsi partitionné en pays. On peut dire les choses autrement. Toute relation d’équivalence peut être exprimée en français sous la forme « Avoir le même (...) » : « avoir le même signe », « avoir le même reste de division euclidienne par n », etc. Démonstration Pour tout x ∈E, notons cl(x) la classe d’équivalence de x pour ∼. • Pour tout x ∈E : x ∼x par réflexivité, donc : x ∈cl(x), donc en particulier cl(x) est non vide. • Clairement : E = [ x∈E cl(x), car pour tout x ∈E : x ∈cl(x). • Soient x, y ∈E. Pour montrer que cl(x) et cl(y) sont égales ou disjointes, supposons-les NON disjointes et montrons qu’elles sont alors égales. Nous pouvons nous donner un élément z commun à cl(x) uploads/s1/ cours-relations-binaires 1 .pdf
Documents similaires
-
33
-
0
-
0
Licence et utilisation
Gratuit pour un usage personnel Attribution requise- Détails
- Publié le Jan 03, 2023
- Catégorie Administration
- Langue French
- Taille du fichier 0.0862MB