\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Mes commandes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\multirows}[3]{\multirow{#1}{#2}{$#3$}}%pour rester en mode math \renewcommand{\arraystretch}{1.3}%pour augmenter la taille des case \newcommand{\point}[1]{\marginnote{\small\vspace*{-1em} #1}}%pour indiquer les points ou le temps \newcommand{\dpl}[1]{\displaystyle{#1}}%megamode \newcommand{\A}{\mathscr{A}} \newcommand{\LN}{\mathscr{N}} \newcommand{\LL}{\mathscr{L}} \newcommand{\K}{\mathbb{K}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\M}{\mathcal{M}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathcal{E}} \renewcommand{\P}{\mathcal{P}} \newcommand{\G}{\mathcal{G}} \newcommand{\Kk}{\mathcal{K}} \newcommand{\Cc}{\mathcal{C}} \newcommand{\Zz}{\mathcal{Z}} \newcommand{\Ss}{\mathcal{S}} \newcommand{\B}{\mathbb{B}} \newcommand{\inde}{\bot\!\!\!\bot} \newcommand{\Proba}{\mathbb{P}} \newcommand{\Esp}[1]{\dpl{\mathbb{E}\left(#1\right)}} \newcommand{\Var}[1]{\dpl{\mathbb{V}\left(#1\right)}} \newcommand{\Cov}[1]{\dpl{Cov\left(#1\right)}} \newcommand{\base}{\mathcal{B}} \newcommand{\Som}{\textbf{Som}} \newcommand{\Chain}{\textbf{Chain}} \newcommand{\Ar}{\textbf{Ar}} \newcommand{\Arc}{\textbf{Arc}} \newcommand{\Min}{\text{Min}} \newcommand{\Max}{\text{Max}} \newcommand{\Ker}{\text{Ker}} \renewcommand{\Im}{\text{Im}} \newcommand{\Sup}{\text{Sup}} \newcommand{\Inf}{\text{Inf}} \renewcommand{\det}{\texttt{det}} \newcommand{\GL}{\text{GL}} \newcommand{\crossmark}{\text{\ding{55}}} \renewcommand{\checkmark}{\text{\ding{51}}} \newcommand{\Card}{\sharp} \newcommand{\Surligne}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\SurligneMM}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \renewcommand{\lim}[1]{\underset{#1}{lim}\,} \newcommand{\nonor}[1]{\left|#1\right|} \newcommand{\Un}{1\!\!1} \newcommand{\sepon}{\setlength{\columnseprule}{0.5pt}} \newcommand{\sepoff}{\setlength{\columnseprule}{0pt}} \newcommand{\flux}{Flux} \newcommand{\Cpp}{\texttt{C++\ }} \newcommand{\Python}{\texttt{Python\ }} %\newcommand{\comb}[2]{\begin{pmatrix} #1\\ #2\end{pmatrix}} \newcommand{\comb}[2]{C_{#1}^{#2}} \newcommand{\arrang}[2]{A_{#1}^{#2}} \newcommand{\supp}[1]{Supp\left(#1\right)} \newcommand{\BB}{\mathcal{B}} \newcommand{\arc}[1]{\overset{\rotatebox{90}{)}}{#1}} \newcommand{\modpi}{\equiv_{2\pi}} \renewcommand{\Re}{Re} \renewcommand{\Im}{Im} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\mat}{\mathcal{M}} \newcommand{\und}[1]{{\mathbf{\color{red}\underline{#1}}}} \newcommand{\rdots}{\text{\reflectbox{$\ddots$}}} \newcommand{\Compa}{Compa} \newcommand{\dint}{\dpl{\int}} \newcommand{\intEFF}[2]{\left[\!\left[#1 ; #2\right]\!\right]} \newcommand{\intEFO}[2]{\left[\!\left[#1 ; #2\right[\!\right[} \newcommand{\intEOF}[2]{\left]\!\left]#1 ; #2\right]\!\right]} \newcommand{\intEOO}[2]{\left]\!\left]#1 ; #2\right[\!\right[} \newcommand{\ou}{\vee} \newcommand{\et}{\wedge} \newcommand{\non}{\neg} \newcommand{\implique}{\Rightarrow} \newcommand{\equivalent}{\Leftrightarrow} \newcommand{\Ab}{\overline{A}} \newcommand{\Bb}{\overline{B}} \newcommand{\Cb}{\overline{C}} \newcommand{\Cl}{\texttt{Cl}} \newcommand{\ab}{\overline{a}} \newcommand{\bb}{\overline{b}} \newcommand{\cb}{\overline{c}} \newcommand{\Rel}{\mathcal{R}} \newcommand{\superepsilon}{\varepsilon\!\!\varepsilon} \newcommand{\supere}{e\!\!e} \makeatletter \newenvironment{console}{\noindent\color{white}\begin{lrbox}{\@tempboxa}\begin{minipage}{\columnwidth} \ttfamily \bfseries\vspace*{0.5cm}} {\vspace*{0.5cm}\end{minipage}\end{lrbox}\colorbox{black}{\usebox{\@tempboxa}} } \makeatother \def\ie{\textit{i.e. }} \def\cf{\textit{c.f. }} \def\vide{ { $ {\text{ }} $ } } %Commande pour les vecteurs \newcommand{\grad}{\overrightarrow{Grad}} \newcommand{\Vv}{\overrightarrow{v}} \newcommand{\Vu}{\overrightarrow{u}} \newcommand{\Vw}{\overrightarrow{w}} \newcommand{\Vup}{\overrightarrow{u'}} \newcommand{\Zero}{\overrightarrow{0}} \newcommand{\Vx}{\overrightarrow{x}} \newcommand{\Vy}{\overrightarrow{y}} \newcommand{\Vz}{\overrightarrow{z}} \newcommand{\Vt}{\overrightarrow{t}} \newcommand{\Va}{\overrightarrow{a}} \newcommand{\Vb}{\overrightarrow{b}} \newcommand{\Vc}{\overrightarrow{c}} \newcommand{\Vd}{\overrightarrow{d}} \newcommand{\Ve}[1]{\overrightarrow{e_{#1}}} \newcommand{\Vf}[1]{\overrightarrow{f_{#1}}} \newcommand{\Vn}{\overrightarrow{0}} \newcommand{\Mat}{Mat} \newcommand{\Pass}{Pass} \newcommand{\mkF}{\mathfrak{F}} \renewcommand{\sp}{Sp} \newcommand{\Co}{Co} \newcommand{\vect}[1]{\texttt{Vect}\dpl{\left( #1\right)}} \newcommand{\prodscal}[2]{\dpl{\left\langle #1\left|\vphantom{#1 #2}\right. #2\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \newcommand{\ortho}[1]{{#1}^{\bot}} \newcommand{\oplusbot}{\overset{\bot}{\oplus}} \SelectTips{cm}{12}%Change le bout des flèches dans un xymatrix \newcommand{\pourDES}[8]{ \begin{itemize} \item Pour la ligne : le premier et dernier caractère forment $#1#2$ soit $#4$ en base 10. \item Pour la colonne : les autres caractères du bloc forment $#3$ soit $#5$ en base 10. \item A l'intersection de la ligne $#4+1$ et de la colonne $#5+1$ de $S_{#8}$ se trouve l'entier $#6$ qui, codé sur $4$ bits, est \textbf{\texttt{$#7$}}. \end{itemize} } \)

Relations binaires

Nous avons vu que les ensembles, une fois l'axiomatique correctement posée, offraient un cadre de travail très confortable à beaucoup de calcul : tout est ensemble. La continuité canonique de l'étude est de mettre les ensembles en relation et d'étudier leurs dépendances ou indépendances, tout du moins de se donner des outils de mesure de tels phénomènes. Les relations donnent ce cadre de travail. Nous quitterons très rapidement le chemin tortueux de la généralité pour le confortable sentier de la relation qu'un ensemble peut avoir avec lui-même.

Produit cartésien

Définition

Soient $ X$ et $ Y$ des ensembles de référentiels fixés. On définit le produit cartésien de $ X$ et $ Y$ noté \[X\times Y\] prononcé x croix y, l'ensemble formé des couples $ (x, y)$ où $ x\in X$ et $ y \in Y$ .

L'existence du produit cartésien est garantie par les axiomes de la théorie des ensembles ; notamment l'axiome de la paire. On fera attention aux notations. On note $ \{x, y\}$ l'ensemble à deux éléments $ x$ et $ y$ , tandis que l'on note $ (x, y)$ le couple de $ X\times Y$ ¹. En particulier, nous avions souligné que la notion en extension était assujettie à deux règles :

Ne pas répéter deux fois le même élément. C'est à dire que l'ensemble $ \{x, x\}$ n'existe pas, ou plutôt se simplifie au singleton $ \{x\}$ . Alors que pour un produit cartésien l'élément $ (x, x)\in X\times X$ peut exister.
L'ordre des éléments ne compte pas. C'est à dire que l'ensemble $ \{x, y\}$ est le même ensemble que $ \{y, x\}$ . Alors que le couple $ (x, y)\in X\times Y$ n'est pas, à priori, le même élément que le couple $ (y, x)\in Y\times X$ .

Soient $ X=\{1, 2, 3\}$ et $ Y=\{a, b\}$ alors $ X\times Y =\left\{ \begin{array}{cc} (1,a), &(1,b), \\ (2,a), &(2,b), \\ (3,a), &(3,b) \end{array} \right\} $

Proposition

Soient $ X$ et $ Y$ deux ensembles de cardinalité finie alors \[\Card(X\times Y)=\Card X \times \Card Y\]

Définition

Soit $ X$ un ensemble. On note $ X^2=X\times X$ . De manière générale, pour tout entier $ n\in\N_{{>}0}$ on note $ X^n=X\times X^{n-1}$ où $ X^1=X$ . Les éléments de $ X^n$ sont appelé des $ n$ -uplet.

Si $ X$ est un ensemble alors par construction les éléments de $ X^2$ sont des couples $ (x_1, x_2)\in X\times X$ par construction. Observons les éléments $ X^3$ . Selon la définition précédente, il s'agit de $ X\times X^2$ , c'est à dire des couples de la forme $ (x_1, (x_2, x_3))$ . On peut monter que $ X\times X^2=X^2\times X$ c'est à dire que le couple $ (x_1, (x_2, x_3))$ s'identifie au couple $ ((x_1, x_2), x_3)$ . Cette identification permet la notation $ (x_1, x_2, x_3)$ . C'est pourquoi on parle de triplet ($ 3$ -uplet).

Relation binaire

Nous nous intéressons aux relations entre ensembles de cardinalité finie.

Définition

Soient $ X$ et $ Y$ deux ensembles. Une relation de $ X$ vers $ Y$ (ou $ X$ sur $ Y$ ) est la donnée d'un sous ensemble $ \Rel\subseteq X\times Y$ . On note $ x\Rel y$ pour $ (x, y)\in \Rel$

Soient $ X=\{1, 2, 3\}$ , $ Y=\{a, b\}$ et $ \Rel =\left\{(2, a), (1, b), (2, b), (3, a)\right\}$ . Ainsi $ 2$ est en relation avec $ a$ , noté $ 2\Rel a$ mais $ 2$ n'est pas en relation avec $ b$ . Donnons nous un outil permettant de représenter et de travailler avec les relations. Le premier de ces outils est la représentation matricielle qui est dans la pratique la forme la plus utilisée parce qu'elle se programme facilement (par presque tous les langages de programmation).

Définition

Soit $ \Rel$ une relation de $ X$ vers $ Y$ deux ensembles de cardinalité finies. La matrice booléenne de $ \Rel$ est une matrice avec $ \Card X$ lignes et $ \Card Y$ colonnes définie par la règle \[M_{i, j}=\left\{ \begin{array}{rl} 1&\text{si }x_i\Rel y_j\\ 0&\text{sinon} \end{array} \right.\]

La matrice booléenne de la relation précédente est \[ M=\begin{pmatrix} 0&1\\ 1&1\\ 1&0 \end{pmatrix} \] Il existe une manière plus humaine pour représenter les relations. Il s'agit de la représentation sagittale bipartie. Sagittale = avec des flèches. Bipartie = entre deux paries. On utilise les diagrammes de Venn. On représente les deux ensembles par deux patatoïdes, en marquant les éléments qui les composent. On relie les éléments qui sont relation. Sur l'exemple précédent la représentation sagittale bipartie est

Relation binaire interne

Un cas particulier, et souvent très pratique, est les relations d'un ensemble sur lui-même.

Définition

Un relation $ \Rel$ d'un ensemble $ X$ sur lui-même est appelé une relation binaire interne. On dit simplement que $ \Rel$ est une relation sur $ X$ .

Si par exemple $ X=\{a, b, c\}$ alors \[\Rel=\{(a,b), (b,a), (b, b),(c, a), (c,c)\}\] est une relation sur $ X$ . Pour cette relation $ a\Rel b$ et $ b\Rel a$ mais $ c\Rel a$ sans que $ a$ en soit en relation avec $ c$ . L'ordre des éléments est important. Dans le cas particulier d'une relation binaire interne, il est donc possible qu'un élément soit en relation avec lui-même comme c'est la cas de l'exemple ou $ b\Rel b$ et $ c\Rel c$ . Dans ce cas, les matrices booléennes sont des matrice carrés (autant de ligne que de colonne). Dans cet exemple \[ M=\begin{pmatrix} 0&1&0\\ 1&1&0\\ 1&0&1 \end{pmatrix} \] Approchons-nous de la théorie des graphes. En effet pour représenter les relations binaires internes pour un traitement humain, un peu plus interprétable que les matrices booléennes, on va partir des représentations sagittales biparties. La représentation sagittale bi-partie de l'exemple précédent est

Dans une telle représentation, il n'est pas nécessaire de représenter deux fois l'ensemble $ X$ . Il suffit de le représenter une seule fois et de relier les éléments en relation, le sens de la flèches indiquant le sens de la relation. Finalement une représentation sagittale est simplement \[ \xymatrix{ a\ar@/^1pc/[rr]&&b\ar@/^1pc/[ll]\ar@(rd,ru)[]\\ &c\ar[lu]\ar@(ld, rd)[]&} \]

Propriétés STAR

Certaines relations ont des propriétés assez spéciales (qui permettent de les classer par exemple). Détaillons-en certaines.

Définition

Soit $ \Rel$ une relation binaire sur un ensemble $ X$ .

Symétrique.: On dira qu'une relation est symétrique si \[\forall x, y \in X, \quad (x\Rel y)\Rightarrow(y\Rel x)\]
Transitive.: On dira qu'une relation est transitive si \[\forall x, y, z\in X, \qquad (x\Rel y)\et(y\Rel z)\Rightarrow(x\Rel z)\]
Antisymétrique.: On dira qu'une relation est antisymétrique si \[\forall x, y \in X, \quad (x\Rel y)\et(y\Rel x)\Rightarrow (x=y)\]
Reflexive.: On dira qu'une relation est réflexive si \[\forall x\in X, \qquad x\Rel x\]

Attention à ne pas assimiler l'antisymétricité à la négation de la symétricité. En effet la négation d'être symétrique transforme le quantificateur $ \forall$ en $ \exists$ ce qui n'est pas la caractérisation d'être antisymétrique. Reprenons l'exemple précédent avec la relation dont une représentation sagittale est \[ \xymatrix{ a\ar@/^1pc/[rr]&&b\ar@/^1pc/[ll]\ar@(rd,ru)[]\\ &c\ar[lu]\ar@(ld, rd)[]&} \] Cette relation n'est pas symétrique puisque $ c\Rel a$ mais $ a$ n'est pas en relation avec $ c$ . De même cette relation n'est pas transitive car $ c\Rel a$ et $ a\Rel b$ mais $ c$ n'est pas en relation avec $ b$ . Elle n'est pas non plus antisymétrique puisque $ a\Rel b$ , $ b\Rel a$ et pourtant $ a\neq b$ . Finalement cette relation n'est pas réflexive car $ a$ n'est pas en relation avec $ a$ . En particulier cette relation n'est ni symétrique ni antisymétrique. Prenons l'exemple de la relation dont une représentation sagittale est la suivante : \[ \xymatrix{ &a\ar@/^1pc/[ld]\ar@(lu, ru)[]&&b\ar@/^1pc/[ld]\ar@(lu, ru)[]\\ c\ar@/^1pc/[ru]\ar@(ld, rd)[]&&d\ar@/^1pc/[ru]\ar@(ld, rd)[]& } \] On laisse le soin au lecteur de vérifier que cette realtion est symétrique, réflexive et transitive. Voici un petit outil (informatique) permettant de vérifier certaine de ces propriétés.

Théorème

Soient $ \Rel$ une relation binaire sur une ensemble $ X$ et $ M$ la matrice booléenne de $ \Rel$ (il s'agit donc d'une matrice carré).

$ \bullet$: La relation $ \Rel$ est réflexive si et seulement si \[\forall i, \qquad M_{i, i}=1\] Autrement : il n'y a que des $ 1$ sur la diagonale principale de $ M$ .
$ \bullet$: La relation $ \Rel$ est symétrique si et seulement si \[\forall i, j, \qquad M_{i, j}=M_{j, i}\] Autrement : la matrice est symétrique par rapport la la diagonale principale.
$ \bullet$: La relation $ \Rel$ est antisymétrique si et seulement si \[\forall i\neq j, \qquad, M_{i, j}\times M{j ,i}=0\] où le produit peut être assimiler à celui de $ \Z$ (mais est en fait celui de l'algèbre booléenne standard). Autrement dit : aucun $ 1$ n'est symétriquement opposé, par rapport à la diagonale principale, à un $ 1$ .

Démonstration

$ \bullet$: Dire que $ x_i\Rel x_i$ est strictement équivalent à dire $ M_{i, i}=1$ .
$ \bullet$: La proposition $ x_i\Rel x_j$ est soit vraie soit faux. Si elle est vraie elle implique, si la relation est réflexive, que $ x_j\Rel x_i$ . Donc $ M_{i, j}=1$ et $ M_{j, i}=1$ soit $ M_{i, j}=M_{j, i}$ . Si $ x_i\Rel x_j$ est faux alors $ M_{i, j}=0$ . Dans ce cas peut importe que $ x_j\Rel x_i$ ou non, la proposition de symétricité sera vérifiée. Mais si $ x_j\Rel x_i$ est vraie alors, puisque qu'il y a le quantificateur $ \forall$ , il faut, par le raisonnement précédent (en inversant $ i$ et $ j$ ) que $ x_i\Rel x_j$ ce que nous avons supposer faux. Donc nécessairement $ x_j\Rel x_i$ est faux, c'est à dire $ M_{i, j}=0=M_{j, i}$ .
$ \bullet$: On raisonne comme précédemment en raisonnant avec des $ 0$ et $ 1$ dans la matrice. Si $ M_{i, j}=0$ ou $ M_{j, i}=0$ alors $ x_i\Rel x_j\et x_j\Rel x_i$ est faux et donc l'implication est vraie. Dans ce cas $ M_{i, j}\times M_{j, i}=0$ .

Lorsque l'on combine certaine de ces propriétés on caractérise (classe) les relations.

Définition

Soit $ \R$ une relation sur un ensemble $ X$ .

$ \bullet$: Si $ \Rel$ est réflexive, symétrique et transitive alors on dira que c'est une relation d'équivalence.
$ \bullet$: Si $ \Rel$ est réflexive, antisymétrique et transitive alors on dira que c'est une relation d'ordre.

Par exemple sur $ \N$ la relation $ =$ est une relation d'équvalence. De même la relation $ \leqslant$ est une relation d'ordre.

¹En bref, il faut faire attention aux symboles utilisées : accolade pour des ensembles, parenthèses pour des couples