# Les Relations

- Soient \\( A, B \\) deux ensembles
    - Le **Produit cartésien** noté \\( A \times B \\) est l'ensemble
        - \\( A \times B = \\{ (a,b) | a \in A \land b \in B\\} \\) 
            - Donc \\( A \times B \neq B \times A \\) 
    - Une **Relation Binaire** noté \\( R \\) est un sous-ensemble de
        - \\( A \times B \quad (R \subseteq A \times B)\\) 
        - Soient \\( a \in A \quad b \in B \\) 
            - On dit que a est en **Relation Binaire** ssi \\( (a,b) \in R \\) 
                - noté \\( aRb \\)
            - Quand \\( A = B \quad R \subseteq A \times A \\) on parle de relation sur \\( A \\) 

Par exemple:
1) \\( A = B = \mathbb{R} \quad R = \mathbb{R}^2 \subseteq \mathbb{R}^2 = \mathbb{R} \times \mathbb{R}  \\) 
2) \\( A = \\{2, 3 ,4\\} \quad B = \\{4, 6, 8\\} \quad R = \\{(a,b) \in A \times B | b = 2a\\} \\) 
3) \\( A = B = \\{ \text{ membre d'une famille } \\} \quad R = \\{ (a,b) | a \text{ est le père de }  B \\} \\) 
4) \\( A = B = \mathbb{R} \quad R_{\leq} = \\{ (a,b) \in \mathbb{R}^2 | a \leq b \\} \\) 

## Représentation des relations (finies)

Par exemple, pour:
\\[
    A = B = \\{ 1, 2, 3 \\} \quad R_{<} = \\{ (a,b) | a < b \\} 
\\]

1) Représentation Cartésienne
2) Représentation Patate
3) Représentation Matricielle

## Types de relations

- Soit \\( R \subseteq A \times A \\), On dit uqe R est 
    - **Réfléxive** ssi \\( \forall a \in  A \quad aRa \\) 
        - Que tout les éléments sont en relation avec eux même
    - **transitive** ssi \\( \forall a, b, c \in A \quad (aRb \land bRc) \implies aRc \\) 
        - Une forme de relation d'héritage.(eg: Si a est un ancetre de b et b est un ancetre de c alors a est un ancetre de c)
    - **Symétrique** ssi \\( \forall a,b \in A \quad aRb \implies bRa  \\) 
        - Toutes les relations sont toujours à double sens
    - **Anti-Symétrique** ssi \\( \forall a, b \in A \quad (aRb \land bRa) \implies a=b  \\) 
        - symètrique mais sans double flèches, seulement des flèches vers lui même

**Attention**, anti-symétrique n'est pas la négation de symétrique

## Relation inverse

- Soit \\( R \subseteq A \times B \\) 
    - La **Relation Inverse** notée \\( R^{-1} = \\{ (b, a) \in B \times A | aRb) \\}  \\)

La relation inverse retourne toute les fleches d'un graphe; Les relations sont inversées

On a prouvé que \\( R = R^{-1} \implies R \text{ est symétrique }  \\) 

## Composition de relations

- Soient \\( R_1 \subseteq A \times B \quad R_2 \subseteq B \times C \\) 
    - \\( R_2 \circ R_1 = \\{ (a,b) \in A \times C \mid \exists b \in B \quad  (a,b) \in R_1 \land (b,c) \in R_2 \\}\\) 

Dans ce cas nous devons faire attention à l'ensemble de départ et d'arrivée

- Soit \\( R \subseteq A \times A \\) 
    - \\( R^2 = R \circ R \quad R^n = R \circ ... \circ R \\) 
        - R est Transitive ssi \\( R^2 \subseteq R \iff \forall n \in \mathbb{N}_ 0 R^n \subset R  \\) 

Nous pouvons alors utiliser les matrice et faire un produit matriciel.
On place 1 dans la matrice lorsque les éléments n et m sont en relation et 0 lorsqu'ils ne sont pas en relation
- + équivaut à un ou
- * équiavaut à un et
Ces matrices peuvent nous aider à comprendre mieux ce qu'il se passe
> On a un chemin qui va de 1 à 2 **et** de 2 à 3
> Oui: Donc (1,3) est dans \\( R^2 \\) 

## Les relations d'équivalences

- Soit \\( R \subseteq A \times A \\) 
    - \\( R \\) est une **Relation d'équivalence** ssi
         - R est **Réfléxive**, **Symétrique** et **Transitive**

- Soit \\( R \subseteq A \times A \\) une relation d'équivalence
    - Soit \\( a \in A \\) 
        - La **Classe d'équivalence** de A (Pour R), notée \\( [a]_ R \\) 
            - \\( [a]_ R = \\{ b \in A \mid a R b \\} \\) 
    - **Le quotient de A par R**, noté \\( A/R \\) 
        - \\( A/R = \\{ [a]_ R \mid a \in A \\} \\) 

Par example, 
- \\( A = \\{ 0, 1, 2, 3, 4, 5\\}  \\) 
    - \\( R = \\{ (a,b) \in A^2 \mid a \equiv_3 b \\}\\) est une relation d'équivalence
        - \\( [0]_ R = \\{ b \in A \mid 0 \equiv_3 b \\} = \\{ 0, 3 \\} = [3] _R \\) 

- Soit \\( R \subseteq A^2 \\) une relation d'équivalence
    - Soient \\( a, b \in A \\). Les affirmations suivantes sont équivalence
        1) \\( a R b \\) 
        2) \\( [a]_ R = [b]_ R \\) 
        3) \\( [a]_ R \cap [b]_ R \neq \emptyset \\) 

- Soit \\( A \\) un ensemble.
    - P **une Partition** de A
        - \\( \mathcal{P} = \\{ A_ i \mid A_ i \subseteq A \\} \\) tq
            1) \\(\cup_ {A_i \in \mathcal{P}} A_ i = A \\) 
            2) \\( \forall A_ i, A_ j \in \mathcal{P} \quad A_ i \neq A_ j \implies A_ i \cap A_ j = \emptyset\\) 

On a donc que \\( A/R \\) est une partition de A

## Les relations d'ordre

- Soit \\( A \\) un ensemble, \\( R \subseteq A \times A \\) 
    - On dit que \\( R \\) est **une relation d'ordre** sur \\( A \\) ssi \\( R \\) est:
        1) Réfléxive
        2) Transitive
        3) Anti-Symétrique
    - On dit alors que \\( (A, R) \\) est un ensemble ordonné

Exemple: \\( (a, =), (\mathbb{N} \leq), (\mathbb{R} \leq ), (\mathbb{R}, \geq ), (\mathbb{N}_ 0, \vert ), (2^X, \subseteq)\\) 

- Soit \\( (A, R) \\)  un ensemble ordonné, Soit \\( a, b \in A \\)
    - On dit que a et b sont **Comparables** (par rapport à R) ssi
        - \\( a R b \lor b R a \\) 
    - Sinon ils sont **Incomparable**

- Soit \\( (A, R) \\) un ensemble ordonné.
    - On dit que l'ensemble est **Totalement ordonné** ssi
        - Il ne contient pas de paire d'incomparable pour R
        - \\( \forall a,b \in A \quad aRb \lor bRa\\) 
    
### Diagramme de Hasse

Il est évidement toujours possible de faire un graphe associé à la relation mais une forme de graphe particulièrement addaptée aux Relations Ordonnées
sont les **Diagramme de Hasse**.

![Diagramme de Hasse](https://upload.wikimedia.org/wikipedia/commons/2/2e/Inclusion_ordering.svg "Diagramme de Hasse")
Représentation de \\( 2^{\\{ x,y \\} } \\) 

- Soit \\( (A, \preccurlyeq) \\). Soient \\( a, b \in A \\) 
    - on dit que b est un successeur immédiat de a ssi
        - \\( a \prec b \land \neg(\exists c \quad a \prec c \prec) \\) 

Exemple:
- \\( \mathbb{N} , \leq \\) 2 est succésseur immédiat de 1  
    - \\( 1 < 2 \land \neg(\exists c \quad 1 < c < 2) \\) 

- Soit \\( (A, \preccurlyeq) \\) 
    - On dit que a est **maximum** ssi
        - \\( \forall b \in A \quad b \preccurlyeq a \\) 
    - On dit que a est **maximal** ssi
        - \\( \neg(\exists b \in A \quad a \prec b)\\) 
    - un maximum implique qu'il soit maximal mais pas l'inverse.  
    - Il n'éxiste pas toujours un maximum ni un maximal

- Soit \\( (A, \preccurlyeq) \\) un ensemble ordonné.
    - Soit \\( X \subseteq A \quad a \in A \\) 
        - On dit que a est **une borne supérieure** de x ssi
            - \\( \forall x \in X \quad x \preccurlyeq a \\) 
                - Une borne supérieur peut:
                    1) Ne pas exister
                    2) être infini
                    3) comprendre des élements dans et hors de l'ens
        - On dit que a est **supéremum** de X ssi
            - a est le minimum des bornes supérieure de X
    - On dit que cet ensemble est un **Treilli** ssi
        - toute les paire d'éléments de A, \\( \\{ a, b \\} \subseteq A \\) possédent un infinum et un supremum
    - C'est un ensemble **Bien-Ordonné** ssi
        - \\( \forall X \subseteq A \quad  X \neq \emptyset \quad X \text{ posède un minimum } \\) 
        - Ca nous permet par exemple de faire des preuves par inductions

- Soit \\( (A, R) \\) un ensemble ordonné
    - Soit \\( \preccurlyeq \subseteq A^2 \\) un ordre Total sur A.
        - On dit que \\( \preccurlyeq \\) est **compatible** avec \\( R \\) ssi
            - \\( \forall a, b \in A \quad aRb \implies a \preccurlyeq b \\) 

Par exemple: Un tri topologique.
A la manière de la construction d'une maison, On peut y aller dans un ordre qui est "compatible".
