Cours du 15 au 19 septembre

1 files changed, 120 insertions, 0 deletions

diff --git a/semestre 3/mathématiques discrètes/1- Ensembles, relations, fonctions.md b/semestre 3/mathématiques discrètes/1- Ensembles, relations, fonctions.md
index b0066aa..8d7ceec 100644
--- a/semestre 3/mathématiques discrètes/1- Ensembles, relations, fonctions.md
+++ b/semestre 3/mathématiques discrètes/1- Ensembles, relations, fonctions.md
@@ -125,3 +125,123 @@ Une partition de $E$ est une famille $(A_i)_{i\in I}$ de parties de $E$ telle qu
 - $E=\bigcup_{i\in I} A_i$
 
 > [!warning] Une partition de $E$ n'est pas unique dans le cas générale !
+## Relation
+**Définition**
+Relation binaire $R$ d'un ensemble $E$ vers $F$ est un sous-ensemble de $E\times F$, i.e.
+$$ R\subseteq E\times F $$
+On peut la noter $(x,y)\in R$, $x R y$, $R(x,y)$.
+Lorsque $E=F$, on dit que $R$ est une relation binaire sur $E$.
+
+Exemple :
+- $\mathrm{Id}_E$ est la relation identité de $E$ est une relation binaire sur $E$ telle que $\{(e,e)|e\in E\}$
+- $\mathrm{Id}_{\mathbb{N}} = \{(n,n)|n\in\mathbb{N}\}$
+- $\leqslant$ sur $\mathbb{N}$ est aussi une relation binaire : $\{(n_1,n_2)\in\mathbb{N}^2|n_1\leqslant n_2\}$
+- $<$ sur $\mathbb{N}$ est aussi une relation binaire (elle est incluse dans $\leqslant$)
+
+> [!NOTE] Opérations sur les relations
+> Comme une relation est un ensemble, on peut appliquer les opérations ensemblistes dessus 🎉
+
+**Définition**
+Relation $n$-aire est un sous-ensemble du produit cartésien $E_1\times\ldots\times E_n$
+
+**Définition**
+Une relation unaire est un sous-ensemble d'un ensemble $E$.
+
+Définir par compréhension permet d'énoncer la propriété caractéristique de l'ensemble
+|> on peut avoir une même relation pour des propriétés caractéristiques différentes
+Définir par extension permet de lister les éléments
+
+**Définition**
+La relation inverse $R^{-1}$ d'une relation $R\subseteq E\times F$ est la relation de $F$ vers $E$ contenant tous les couples $(x,y)$ tels que $(y,x)\in R$, i.e.
+$$ R^{-1} = \{(x,y)\in F\times E|(y,x)\in R\} $$
+
+**Définition**
+Un produit de relation est quand on applique plusieurs relations à la suite.
+
+Le produit de $R_1\subseteq E\times F$ et de $R_2\subseteq F\times G$ est définie par :
+$$ R_1R_2 = \left\{(x,y)\in E\times G\quad|\quad\exists z, (x,z)\in R_1\quad\land\quad(z,y)\in R_2\right\} $$ -> revoir le cours pour cette expression, ça me semble chelou
+On la note $R_1\circ R_2$ ou $R_1\cdot R_2$.
+```mermaid
+flowchart LR
+	A -- R1⋅R2 ---C
+	A-- R1 ---B
+	B-- R2 ---C
+```
+
+Par exemple, on peut définir $<$ comme $S\cdot\leqslant$ où $S$ est la relation successeur (i.e. $S=\{(x,y)|x+1=y\}$)
+
+> [!warning] Commutativité
+> Le produit de relation n'est pas commutatif
+
+> [!warning] $R\cdot R^{-1}\neq\mathrm{Id}_E$
+> De même dans l'autre sens
+
+**Propriétés**
+$\varnothing$ est un élément est absorbant des relations : $R\cdot\varnothing = \varnothing\cdot R = R$
+Le produit est associatif : $R_1\cdot(R_2\cdot R_3) = (R_1\cdot R_2)\cdot R_3$
+$\mathrm{Id}$ est l'élément neutre : $R\cdot\mathrm{Id}_F = \mathrm{Id}_ER=R$ (si $R$ est dans $E\times F$)
+|> ⚠ faire bien attention à la modification de l'identité en fonction qu'on soit à droite ou à gauche
+
+**Notations**
+Si $R$ est une relation sur $E$, on note :
+$$ R^n = \underbrace{R\ldots R}_n = \left\{\begin{matrix}
+	\mathrm{Id}_E&\text{si}&n=0\\
+	R\cdot R^{n-1}&\text{sinon}
+\end{matrix}\right. $$
+
+***Revoir les diapos 23 à 29***
+
+**Définition**
+Une relation est dite d'équivalence si, et seulement si, elle est :
+- réflexive
+- symétrique
+- transitive
+
+Une relation est dite d'ordre si, et seulement si, elle est :
+- réflexive
+- anti-symétrique
+- transitive
+
+Par exemple :
+- $\equiv$ (congruence) est une relation d'équivalence
+- $\leqslant$ est une relation d'ordre
+- $<$ n'est pas une relation d'ordre car elle n'est pas anti-symétrique !
+
+**Définition**
+Soit $R$ une relation d'équivalence sur $E$.
+La classe d'équivalence d'un élément $e\in E$ pour $R$ est noté $[e]_R$ et :
+$$ [e]_R = \{e'\in E|(e,e')\in R\} $$
+Remarque : $e\in[e]_R$ car $R$ est réflexive
+
+**Définition**
+On note $E_{/R}$  l'ensemble des quotients de $E$ par $R$
+***J'AI PAS EU LE TEMPS DE NOTER (diapo 31)***
+## Fonctions
+**Définition**
+Une relation de $E$ vers $F$ est dite déterministe (ou fonctionnelle) si, et seulement si, tout élément de $E$ est en relation avec au plus un élément de $F$, i.e.
+$$ \forall e\in E,\quad\forall(e_1,e_2)\in F^2,\quad(e,e_1)\in R\quad\land\quad(e,e_2)\in R \implies e_1=e_2 $$
+
+Exemples :
+- $S$ est fonctionnelle
+- $S^{-1}$ l'est aussi
+- $\leqslant$ ne l'est pas par contre
+
+**Proposition**
+Une relation déterministe est une fonction $f$.
+
+Si $f$ n'est pas définie pour tout l'ensemble de départ, on dit qu'elle est partielle.
+
+Preuves :
+- relation déterministe ne donne qu'une unique image
+
+**Définition**
+Une relation $R$ de $E$ vers $F$ est dite totale à gauche si, et seulement si, chaque élément de $E$ est en relation avec au moins un élément de $F$ :
+$$ \forall e_1\in E,\quad\exists e_2\in F,\quad (e_1,e_2)\in R $$
+
+**Définition**
+Une application est une relation déterministe et totale à gauche, on la note :
+$$ f : E\to F $$
+i.e. tout élément de $E$ possède une (unique) image.
+On dit parfois qu'elle est une fonction totale.
+
+***Voir diapo 36 à 45 car j'ai pas le temps de noter***
\ No newline at end of file