Relations binaires

On peut maintenant voir de manière formelle la notion de relation déjà abordée de manière naïve.

Notion de couple

On doit tout d'abord définir la notion de couple. L'idée est qu'à partir de deux éléments $a$ et $b$, on construit un couple que l'on va noter $(a,b)$. Un couple est une paire ordonnée c'est à dire que l'ordre a une importance, on a $(a,b)\ne (b,a)$.

On doit définir cette notion à partir de la théorie des ensembles c'est à dire comme d'habitude qu'on doit n'avoir que des ensembles donc un couple sera un ensemble. Malheureusement, on ne peut pas définir simplement le couple en écrivant $(a,b)=\{a,b\}$ car nous avons vu (axiome d'extensionnalité) que $\{a,b\}=\{b,a\}$ ce qui contredit $(a,b)\ne (b,a)$.

Pour pouvoir résoudre cette difficulté, on définit le couple comme ceci:

Avec cette définition on a bien $(a,b)\ne (b,a)$ car $\left\{\right\{a\},\{a,b\left\}\right\}\ne \left\{\right\{b\},\{b,a\left\}\right\}$.

Produit cartésien

En utilisant la notion de couple, on définit la notion de produit cartésien. Si on a deux ensembles $A$ et $B$, leur produit cartésien est l'ensemble noté $A\times B$, et dont les éléments sont des couples avec le premier élément dans $A$ et le deuxième dans $B$.

Par exemple, si $A=\{1,2\}$ et $B=\{0,2,4\}$, alors:

On peut maintenant définir cette notion de manière formelle. On a deux ensembles $A$ et $B$. On va essayer de définir cet ensemble en compréhension. La propriété qu'on va utiliser pour que $(a,b)\in A\times B$ est tout simplement $a\in A\wedge b\in B$. Reste à définir le sur-ensemble de $A\times B$ et c'est plus compliqué.

Soit $a\in A$ et $b\in B$. On a bien $(a,b)\in A\times B$. On a aussi que $\{a,b\}\subset A\cup B$ donc que $\{a,b\}\in P(A\cup B)$. De même on a que $\left\{a\right\}\subset A\cup B$ donc que $\left\{a\right\}\in P(A\cup B)$ (rappel: $P(X)$ est l'ensemble des parties de $X$).

On sait donc que $\{a,b\}\in P(A\cup B)$ et que $\left\{a\right\}\in P(A\cup B)$. On conclut alors que $\left\{\right\{a\},\{a,b\left\}\right\}\in P(P(A\cup B))$. On peut alors écrire:

De plus on écrit souvent $A^2$ au lieu de $A\times A$ ou $A^3$au lieu de $A\times A\times A$,...

Relations binaires

Définition

On a déjà vu cette notion de manière naïve, il est temps d'en donner une définition formelle dans le cadre de la théorie des ensembles. On va dire (sans surprise encore une fois) qu'une relation binaire est un ensemble.

On sait déjà qu'une relation binaire met en relation deux ensembles. On va donc considérer une relation comme un ensemble de couples. Par exemple si la relation est notée $R$, et si $a$ et $b$ sont en relation, alors on a $(a,b)\in R$.

Supposons donc qu'on ait deux ensembles $A$ et $B$. On a une relation $R$ entre ces deux ensembles. Il s'agit d'un ensemble de couple $(a,b)$ avec $a\in A$ et $b\in B$, donc un sous-ensemble de $A\times B$.

On peut alors considérer que tout sous-ensemble de $A\times B$ est une relation binaire. L'ensemble des relations binaires entre $A$ et $B$ sera noté $A\rightleftharpoons B$. On a évidemment:

Domaine et ensemble image

On définit aussi le domaine d'une relation binaire. Une relation binaire entre $A$ et $B$ associe à des éléments de $A$ des éléments de $B$, mais certains éléments de $A$ ne sont associés à aucun élément de $B$. On va donc définir un ensemble (le domaine) qui est l'ensemble des éléments de $A$ qui sont en relation avec au moins un élément de $B$. Si la relation est $R$, on note le domaine: $Dom(R)$.

On peut facilement définir le domaine en compréhension:

De même, il existe des éléments de $B$ qui ne sont associés à aucun élément de $A$. On définit alors l'ensemble image qui est l'ensemble des éléments de $B$ qui sont en relation avec au moins un élément de $A$, ensemble que l'on note $Im(R)$.

Inverse

On a une relation $R$ entre $A$ et $B$. On peut définir l'inverse de $R$, que l'on note $R^{-1}$, qui est la même relation en échangeant les ensembles $A$ et $B$, c'est à dire que si le couple $(a,b)$ appartient à $R$ alors $(b,a)$ appartient à $R^{-1}$. On a donc:

Composée

Si on a une relation $R$ de $A$ vers $B$ et une relation $R\prime$ de $B$ vers $C$, alors on peut définir la composée de $R$ et $R\prime$ que l'on note $R\circ R\prime$ qui est une relation de $A$ vers $C$. Si par exemple on a un élément $a\in A$ en relation par $R$ avec un élément $b\in B$ et que cet élément est en relation par $R\prime$ avec un élément $c\in C$, alors $a$ et $c$ sont en relation par $R\circ R\prime$.

On définit cet ensemble en compréhension: