Fiche de révision

Relations d’équivalence et relations d’ordre

1. Relations

Une relation entre deux ensembles E et F est un sous-ensemble de E × F.

On note : x R y

Propriétés

2. Relation d’équivalence

Une relation est une relation d’équivalence si elle est :

Classe d’équivalence

La classe d’équivalence de x est :

Cx = { y ∈ E | xRy }

Exemple (modulo n)

x ≡ y (mod n) ⇔ n | (x − y)

3. Relation d’ordre

Une relation est une relation d’ordre si elle est :

Ordre total et ordre partiel

4. Bornes et éléments remarquables

Majorant : ∀x ∈ F, x ≤ M

Minorant : ∀x ∈ F, m ≤ x

Borne supérieure : plus petit des majorants

Borne inférieure : plus grand des minorants

5. Treillis

Un treillis est un ensemble ordonné où tout couple {a,b} admet :

7. Schémas et tableaux (méthodes indispensables)

7.1 Diagramme sagittal

But : représenter une relation entre deux ensembles différents.

Méthode :

  1. Écrire l’ensemble E à gauche
  2. Écrire l’ensemble F à droite
  3. Tracer une flèche x → y si xRy
E        F
1  ----> a
2  ----> a
2  ----> b
3

7.2 Graphe orienté

But : relation sur un seul ensemble.

  1. Chaque élément est un point
  2. Flèche de x vers y si xRy
  3. Boucle si xRx
1 ↺ → 2 → 3

7.3 Diagramme de Hasse (relation d’ordre)

Étapes obligatoires :

  1. Tracer le graphe orienté
  2. Supprimer les boucles (réflexivité)
  3. Supprimer les flèches transitives
  4. Mettre les plus petits en bas
  5. Supprimer les flèches (traits simples)
    6
   / \
  2   3
   \ /
    1

7.4 Matrice (tableau) de relation

But : représenter une relation sous forme de tableau.

  1. Éléments en lignes et colonnes
  2. 1 si xRy, 0 sinon
R123
1110
2001
3000

Lecture rapide :

7.5 Tableau des classes d’équivalence

  1. Choisir un élément
  2. Écrire tous ses équivalents
  3. Recommencer jusqu’à couvrir E
ClasseÉléments
C₀..., -3, 0, 3, 6, ...
C₁..., -2, 1, 4, 7, ...
C₂..., -1, 2, 5, 8, ...
```