tite fractale

Théorie des ensembles et relations

1. Introduction

On travaille dans un ensemble $E$. Dans les schémas, il sera symbolisé par le grand rectangle.

La notion d’appartenance à un sous-ensemble de $E$, disons $A$, ne se définit pas. On écrit $x \in A$ ou $x \notin A$.

Un ensemble peut être décrit :

L’ensemble qui ne contient aucun élément est noté $\emptyset$.

2. Liens avec la logique

2.1. Négation

Si $A$ est un sous-ensemble de $E$, $A$ peut être noté :

$$ A = \left\{ x \in E, x \in A \right\}$$

Si $P$ est la proposition «$x \in A$», alors $\overline P$ est «$x \notin A$». $\overline A$ est donc :

$$ \overline A = \left\{ x \in E, x \notin A \right\}$$

diagramme ss-ensemble diagramme complémentaire

Rappels :

$P$ $\overline P$
0 1
1 0

Remarque : $ \overline {\overline A} = A$.

2.2. Union et intersection

Si $A$ et $B$ sont deux sous-ensembles de $E$, on note :

$$ A \cap B = \left\{ x \in E, x \in A \wedge x \in B \right\} $$ $$ A \cup B = \left\{ x \in E, x \in A \vee x \in B \right\} $$

$\cap$ se lit « inter », et $\cup$ se lit « union ».

diagramme intersection diagramme union

Le résultat de ces opérations est un nouvel ensemble.

Rappels :

$P$ $Q$ $P \wedge Q$
0 0 0
0 1 0
1 0 0
1 1 1

 

$P$ $Q$ $P \vee Q$
0 0 0
0 1 1
1 0 1
1 1 1

Remarques :

2.3. Égalité et inclusion

Si $A$ et $B$ sont deux sous-ensembles de $E$, on note :

Le résultat de ces opérations est un booléen.

Schéma

Rappels :

$P$ $Q$ $P \Leftrightarrow Q$
0 0 1
0 1 0
1 0 0
1 1 1

 

$P$ $Q$ $P \Rightarrow Q$
0 0 1
0 1 1
1 0 0
1 1 1

2.4. Quelques calculs de base

$A$ est un sous-ensemble de $E$. Faire une figure.

Simplifier les expressions suivantes et réfléchir aux éléments neutres ou absorbant de l’intersection et de l’union.

2.5. Cardinal

Le nombre d’éléments d’un ensemble s’appelle le cardinal de cet ensemble.

Exemples :

2.6. Subtilités de notation

2.6.1. Entre l’appartenance et l’inclusion

$$ \begin{aligned} \text{élément} &\in \text{ensemble} \\\\ \text{ensemble} &\subset \text{ensemble} \end{aligned}$$

Exemple :

En géométrie, les éléments sont en général des points. Si $M$ est un point, $D$ une droite et $P$ un plan, on peut écrire :

2.6.2. Complication avec les ensembles d’ensembles

On note $\mathscr P (E)$ l’ensemble des parties de $E$, c’est-à-dire l’ensemble composé de tous les sous-ensembles de $E$. On a :

$$ A \in \mathscr P (E) \Leftrightarrow A \subset E $$

Exemple : Trouvez tous les sous-ensembles de $\left\{ 1; 2; 3\right\}$.

$\emptyset$, {1}, {2}, {3}, {1;2}, {1;3}, {2;3}, {1;2;3}
On a donc $\mathscr P (\left\{1;2;3\right\}) = \left\{$\emptyset$,\{1\},\{2\},\{3\},\{1;2\},\{1;3\},\{2;3\},\{1;2;3\}\right\}$.

Pour tout ensemble $E$, on a (notez l’utilisation de $\in$) :

Un ensemble à $n$ éléments a $2^n$ parties.

3. Produit cartésien

3.1. Définition

Le produit cartésien de deux ensembles $E$ et $F$ est l’ensemble de tous les couples $(x,y)$ (dans cet ordre) tels que $x \in E$ et $y \in F$.

On note :

$$E×F = \left\{ (x,y), x \in E \wedge y \in F \right\}$$

On prononce : « E croix F ».

Notation : Si $E=F$, on note $E×E=E^2$.

3.2. Exemples

3.3. Produit cartésien de plusieurs ensembles

On peut définir le produit cartésien de $n$ ensembles. Ses éléments sont des $n$-uplets, ou tuples.

3.4. Cardinal du produit cartésien

Le cardinal du produit cartésien de deux ensembles est le produit des cardinaux de ces ensembles.

$$\mathbf{card}(E×F) = \mathbf{card}(E) × \mathbf{card}(F)$$

Cette formule se généralise au produit cartésien de plusieurs ensembles.

Attention : le sens des mots « produit » peuvent être différents (produit d’ensembles, produit de nombres). Idem pour les symboles « × ».

4. Relations binaires

4.1. Définition

Une relation binaire $\mathscr R$ d’un ensemble $E$ vers un ensemble $F$ est la donnée de :

Pour $x \in E$ et $y \in F$, $x \mathscr R y$ signifie $(x,y) \in G$.

Cette année, nous aurons toujours $E=F$, c’est-à-dire :

Une relation binaire $\mathscr R$ sur un ensemble $E$ est la donnée de :

Pour $x \in E$ et $y \in F$, $x \mathscr R y$ signifie $(x,y) \in G$.

C’est donc très similaire aux graphes.

4.2. Sur l’exemple

Prenons $E = \left\{ a,b,c,d,e \right\}$ et $\mathscr R$ la relation : « … aime le prénom de … ».

4.2.1. Avec un tableau

a b c d e
b,c a a,d,e b,c,d

4.2.2. Avec un diagramme sagittal

Dans le cas ou $F = E$, ne dessiner qu'un seul ensemble.

4.2.3. Avec une matrice

4.2.4. Avec le graphe de la relation

Rappel :

$$ \begin{aligned} E×E = \left\{ \right. & (a,a), (a,b), ... , (a,e), \\\\ & (b,a), (b,b), ... , (b,e), \\\\ & ... \\\\ & (e,a), (e,b), ... , (e,e) \left. \right\} \end{aligned}$$

$$ \begin{aligned} G = \left\{ \right. & (a,b), (a,c), \\\\ & (b,a), \\\\ & (d,a), (d,d), (d,e), \\\\ & (e,b), (e,c), (e,d) \left. \right\} \end{aligned}$$

Que l’on peut bien sûr écrire sur une seule ligne.

4.3. Autres exemples

Représentez chacun des exemples suivants avec :

Les exemples classiques :

  1. Égalité dans $E$ :
    $x \mathscr R y \Leftrightarrow x=y$
  2. Inégalité large dans $\mathbb R$ :
    $x \mathscr R y \Leftrightarrow x \ge y$
  3. Inégalité stricte dans $\mathbb R$ :
    $x \mathscr R y \Leftrightarrow x < y$
  4. Divisibilité dans $\mathbb N ^*$ :
    $x \mathscr R y \Leftrightarrow x ~\text{divise}~ y$
  5. Congruence dans $\mathbb N ^*$ :
    $x \mathscr R y \Leftrightarrow x \equiv y [n]$
  6. Si $P$ est un plan géométrique et $E = \mathscr P (P)$ (ensembles de $P$),
    $A \mathscr R B \Leftrightarrow A \subset B$

4.4. Propriétés des relations binaires

4.4.1. Réflexivité

$\mathscr R$ est dite réflexive si $\forall x \in E, x \mathscr R x$.

Autrement dit, si tout élément est en relation avec lui-même.

Parmi les exemples précédents, seule $<$ ne l’est pas.

4.4.2. Symétrie

$\mathscr R$ est dite symétrique si $\forall (x,y) \in E^2, x \mathscr R y \Rightarrow y \mathscr R x$.

Autrement dit, si un premier élément est en relation avec un second, alors le second est aussi en relation avec le premier.

Parmi les exemples précédents, seules $=$ et $\equiv$ le sont.

4.4.3. Antisymétrie

$\mathscr R$ est dite antisymétrique si $\forall (x,y) \in E^2, \left( x \mathscr R y \right) \wedge \left( y \mathscr R x \right) \Rightarrow x = y$.

Autrement dit, si deux éléments sont en relation dans les deux sens, alors c’était en fait le même élément.

Parmi les exemples précédents, $<$ et $\equiv$ ne le sont pas.

En effet, cela n’a pas vraiment de sens pour $<$ et on peut trouver des contre-exemples pour $\equiv$.

$1 \equiv 8 [7]$ et $8 \equiv 1 [7]$, mais $1 \neq 8$.

D’un autre côté, $\ge$ l’est car si $x \ge y$ et $y \ge x$, alors $x=y$.
Démontrez que $\subset$ l’est aussi.

4.4.4. Transitivité

$\mathscr R$ est dite transitive si $\forall (x,y,z) \in E^3, \left( x \mathscr R y \right) \wedge \left( y \mathscr R z \right) \Rightarrow x \mathscr R z$.

Autrement dit, si un premier élément est en relation avec un deuxième, et si ce deuxième est en relation avec un troisième, alors le premier est aussi en relation avec le troisième.

Parmi les exemples précédents, toutes le sont.

4.4.5. Point méthode

Pour montrer qu’une relation est…

4.5. Relations d’équivalence, relations d’ordre

$\mathscr R$ est une relation d’équivalence si elle est :

C’est le cas de $=$ et de $\equiv$.

$\mathscr R$ est une relation d’ordre si elle est :

Elles le sont toutes sauf $<$ et $\equiv$.

4.6. Ordre total, ordre partiel

Si $\mathscr R$ est une relation d’ordre, on dit que l’ordre est total si $$\forall (x,y) \in \mathbb E ^2, \left( x \mathscr R y \right) \vee \left( y \mathscr R x \right)$$

Exemple : dans la cour de récréation, quand deux enfants comparent leur taille, ils s’attendent à ce que l’un des deux soit le plus grand.

Méthode : Pour nier le caractère total d’une relation d’ordre, il faut nier un « quelque soit… et… ». On cherche donc un contre-exemple : « il existe… ou… ».

Quart d’heure philosophique : on ne peut pas toujours classer les êtres humains !

5. Fonctions et applications

Soit deux ensembles $E$ et $F$.

$E$ sera souvent appelé « ensemble de départ » et $F$ « ensemble d’arrivée ».

5.1. Définitions

Une fonction de $E$ dans $F$ est la donnée d’un ensemble $\Gamma$ de couples $(x,y)$ inclus dans $E×F$ tel que pour chaque $x$ de $E$ il n’y a pas plus d’un couple $(x,y)$.

Une application est une fonction pour laquelle chaque $x$ de $E$ a exactement un couple $(x,y)$.

Dans les deux cas, si la fonction ou l’application est notée $f$ et si $(x,y)$ est dans $\Gamma$, on peut noter $f(x)=y$, et on dira « l’image de $x$ est $y$ » (noter l’article défini).

De plus, si $y$ est un élément de $F$, on appelle un antécédent de $y$ tout $x$ de $E$ tel que $f(x) = y$.

Exemple

Prenons $E = \left\{ a,b,c,d,e \right\}$,  $F = \left\{ f,g,h,i \right\}$ et $\Gamma = \left\{ (a,g);(b,f);(c,g);(d,i);(e,g) \right\}$.

(Schéma à faire)

5.2. Ensemble image et ensemble image réciproque

Si $A \subset E$ ($A$ est un sous-ensemble de $E$), on appelle image de $A$ l’ensemble noté $f(A)$ défini par :

$$f(A) = \left\{ y \in F, \exists x \in A, f(x)=y \right\}$$

Si $B \subset F$ ($B$ est un sous-ensemble de $F$), on appelle image réciproque de $B$ l’ensemble noté $f^{-1}(B)$ défini par :

$$f^{-1}(B) = \left\{ x \in E, \exists y \in B, f(x)=y \right\}$$

Sur l’exemple

Remarque

$f^{-1}(\left\{ y \right\})$ est l’ensemble des antécédents de $y$.

Dans l’exemple, on a $f^{-1}(\left\{ h \right\}) = \emptyset$.

6. Injection, surjection et bijection

6.1. Injectivité

$f$ est une application injective si :

Autrement dit,

On remarque ce ces deux propositions sont contraposées.

6.2. Surjectivité

$f$ est une application surjective si tout élément de $F$ a au moins un antécédent.

Autrement dit,

$\forall y \in F, \exists x \in E ~\text{tel que}~ f(x) = y$

6.3. Bijectivité

$f$ est une application bijective si elle est à la fois injective et surjective, c’est-à-dire si tout élément de $F$ a exactement un antécédent.

7. Composition

À suivre…




Christophe Gragnic, avec quelques inspirations dans le Sigma, le 08/03/2017, 16h11'28".






Page générée le 08/03/2017, 16h11'32" (source).
historique global

 TogetherJS