---
title: "folo - Cours 3 : Relation et fonctions"
tags: folo, cours, MiMos
---
{%hackmd theme-dark %}

$$
\newcommand{\vt}[3]{
\begin{pmatrix}
{#1} \\
{#2} \\
{#3}
\end{pmatrix}
}
\newcommand{\limto}[1]{\xrightarrow[#1]{}}
$$

# FoLo - Cours 3 : Relation et fonctions

[`video`](url_video)
[`cours`](url_cours)
[`slides`](url_slides)

---

[TOC]

---

## Introduction
On veut définir des relations entre les objets.

Formellement, une relation binaire est un sous-ensemble $R \subseteq E \times E$.

On note les relations d'équivalence:

$$
\sim_R
$$

On va formaliser ces relations avec un prédicat sur 2 variables de tel sorte que $x\sim_Ry$ est vraie si et seulement si $(x,y) \in R$. ($x$ est relié d'une certaine manier à $y$).

Notons que $x \sim_R y$ n'implique pas $y \sim_R x$. Il y a un ordre dans les relations.

Cependant, si cela marche, on considère la définition suivante :

> ### Définition
>
> $$
> \begin{align}
> \forall x \in E, (x \sim_R x) &\iff R \text{ reflexive}\\
> (\forall x, y \in E, (x \sim_R y) \iff (y \sim_R x)) &\iff R \text{ symétrique}\\
> (\forall x, y, z \in E, (x \sim_R y) \land (y \sim_R z) \implies (x \sim_R z)) &\iff R \text{ transitive}
> \end{align}
> $$

Le comportement de la relation d'égalité dans un ensemble $E$.
$\forall x,y,z \in E$ :

- **Réfléxive** : $x = x$.
- **Symétrique** : $x = y$ si et seulement si $y = x$.
- **Transitive** : $x = y$ et $y = z$ alors $x = z$.

### Exemple 1

Soit $p \in \mathbb{N}$

$$
x \equiv y[p] \iff x \mod p = y \mod p
$$

or

$$
z \equiv x \land z \not\equiv y
$$

or

$$
z \equiv x \equiv y \text{ absurde }
$$

### Exemple 2

$$
x \not\equiv y \implies [x] \cap [y] = \emptyset
$$

$\exists z \in [x] \cap [y]$ :

$$
(z \equiv x \implies x \equiv z) \land (z \equiv y) \implies x \equiv y
$$

### Exemple 3

$x \in [x]$

$$
\exists! [y], x \in [y]
$$

**Existance**

La proposition existe par la 1ère ligne

**Unicité**

si $x \in [u] \land x \in [v]$

alors $x \equiv u$ et $x \equiv v$

donc $u \equiv v$

par exemple 1, $[u] \equiv [y]$

## Relation d'équivalence

Une relation binaire $R$ est dite **relation équivalente** si elle est **réflexive, symétrique et transitive**.

On utilise souvent la notation :

$$
\equiv_R
$$

On veut regrouper les éléments qui sont sémentiquement semblables.
Soit $x \in E$, on définie la classe d'équivalence de $x$ en fonction de $\equiv_R$ comme l'ensemble $[x]_R$ tel que :

$$
y \in [x]_R \iff x \equiv_R y
$$

On peut aussi noter :

$$
[x]_R = \{y \in E \text{ | } x \equiv_R y\}
$$

Propriétés sur une classe d'equivalence avec $\forall x,y \in E$ :
- Si $x \equiv_R y$ alors $[x]_R = [y]_R$.
- Si $x \not\equiv_R y$ alors $[x]_R \cap [y]_R = \emptyset$.
- $x \in [x]_R$ toujours.

Tout les éléments $x$ d'un ensemble $E$ appartiennent a une classe d'équivalence en accord avec la relation $\equiv_R$.

Partition d'un ensemble :
Un ensemble $\mathcal P$ est dit partition de $E$ s'il vérifie les propriétés suivantes :
- $\forall X \in \mathcal P, X\subseteq E \text{ et } X \not\equiv \emptyset$.
- $\forall X,Y \in \mathcal P, X \cap Y = \emptyset$.
- $\forall x \in E, \exists! X \in \mathcal P, x \in X$.

L'ensemble de classes d'equivalence $E \setminus \equiv_R$ de $E$ tel que à $\equiv_R$ forme une partition de $E$. Ceci est appelé l'espace quotient de $E$ par rapport à $\equiv_R$.

Un nombre fini de classe d'équivalence peut représenter un espace infini de $E$.

Prendre un représentant $y \in [x]_R$ par classe d'équivalence comme un représentant canonique.

Calculer une seule classe d'équivalence équivaut à calculer pour toutes les classes d'équivalence.

Exemples :

On veut prouver que : $[x]_R$

$$
x \equiv_R y \iff [x]_R = [y]_R
$$

## Fonctions

Deux ensembles $E$ et $F$, une fonction partielle est un sous-ensemble $f \subseteq E \times E \text{ (aussi en écrivant } f : E)$