Summry
Bibliothèque de cours

Éléments de la Théorie des Ensembles

5 générations
Résumé

Éléments de la Théorie des Ensembles

A. Produit Cartésien de 2 Ensembles

Le produit cartésien E×FE \times F est l'ensemble des couples (a;b)(a ; b) où a∈Ea \in E et b∈Fb \in F. E×F={(a,b)∣a∈E et b∈F}E \times F = \{(a, b) \mid a \in E \text{ et } b \in F\} Exemple : E={1;2},F={1;2;3}E = \{1 ; 2\}, F = \{1 ; 2 ; 3\}. E×F={(1,1);(1,2);(1,3);(2,1);(2,2);(2,3)}E \times F = \{(1,1);(1,2);(1,3);(2,1);(2,2);(2,3)\}. Notez que E×F≠F×EE \times F \neq F \times E (non commutatif). La cardinalité est Card(E×F)=Card(E)×Card(F)\text{Card}(E \times F) = \text{Card}(E) \times \text{Card}(F).

B. Relation Binaire

Une relation binaire R\mathcal{R} de EE vers FF est définie par le triplet (E,F,G)(E, F, G), où GG est une partie du produit cartésien E×FE \times F (le graphe). La notation xRyx \mathcal{R} y signifie (x,y)∈G(x, y) \in G. Si E=FE=F, c'est une relation sur EE.

C. Propriétés d'une Relation Binaire (cas E=FE = F)

Soit R\mathcal{R} une relation binaire sur EE :

  • Réflexive : ∀x∈E, xRx\forall x \in E,\ x \mathcal{R} x
  • Symétrique : ∀(x,y)∈E2, xRy⇒yRx\forall (x, y) \in E^2,\ x \mathcal{R} y \Rightarrow y \mathcal{R} x
  • Transitive : ∀(x,y,z)∈E3, (xRy)∧(yRz)⇒xRz\forall (x, y, z) \in E^3,\ (x \mathcal{R} y) \wedge (y \mathcal{R} z) \Rightarrow x \mathcal{R} z
  • Antisymétrique : ∀(x,y)∈E2, (xRy)∧(yRx)⇒x=y\forall (x, y) \in E^2,\ (x \mathcal{R} y) \wedge (y \mathcal{R} x) \Rightarrow x = y

D. Exemples et Diagrammes Sagittaux

Exemple 1 : E={1;2;3;4}E = \{1 ; 2 ; 3 ; 4\}, G={(1,1);(1,2);(2,1);(3,3);(3,4);(4,3);(2,2);(4,4)}G = \{(1,1) ; (1,2) ; (2,1) ; (3,3) ; (3,4) ; (4,3) ; (2,2) ; (4,4)\}. Puisque {(1,1);(2,2);(3,3);(4,4)}⊂G\{(1,1);(2,2);(3,3);(4,4)\} \subset G, R\mathcal{R} est réflexive. Puisque (1,2),(2,1)(1,2), (2,1) et (3,4),(4,3)(3,4), (4,3) sont présents, R\mathcal{R} est symétrique. R\mathcal{R} est également transitive (vérification requise par l'énoncé).

Exemple 2 : Sur E={0;1;4;7;8;11}E = \{0 ; 1 ; 4 ; 7 ; 8 ; 11\}, xRy  ⟺  x+yx \mathcal{R} y \iff x + y est pair. (Ceci regroupe les pairs entre eux et les impairs entre eux.)

E. Relations d'Équivalence et d'Ordre

Une relation binaire R\mathcal{R} sur EE est une relation d'équivalence si elle est réflexive, symétrique et transitive. Une relation d'ordre est réflexive, transitive et antisymétrique. La classe d'équivalence d'un élément est l'ensemble des éléments qui lui sont liés par la relation d'équivalence.

F. Exemple : Relation d'Équivalence sur Z\mathbb{Z}

Sur Z2\mathbb{Z}^2, la relation R\mathcal{R} est définie par xRy  ⟺  x2≡y2(mod5)x \mathcal{R} y \iff x^2 \equiv y^2 \pmod{5}. Cette relation est réflexive (x2≡x2x^2 \equiv x^2), symétrique (si a≡ba \equiv b alors b≡ab \equiv a), et transitive (si x2≡y2x^2 \equiv y^2 et y2≡z2y^2 \equiv z^2, alors x2≡z2x^2 \equiv z^2). R\mathcal{R} est donc une relation d'équivalence.

Les valeurs possibles de n2(mod5)n^2 \pmod{5} pour n∈Zn \in \mathbb{Z} sont {0,1,4}\{0, 1, 4\}. Si n∈{0,5,10,… }n \in \{0, 5, 10, \dots\}, n2≡0n^2 \equiv 0. Si n∈{1,4,6,9,… }n \in \{1, 4, 6, 9, \dots\}, n2≡1n^2 \equiv 1. Si n∈{2,3,7,8,… }n \in \{2, 3, 7, 8, \dots\}, n2≡4n^2 \equiv 4. Les 3 classes d'équivalence correspondent aux restes : {0}\{0\}, {1}\{1\}, {4}\{4\}.