Introduction aux mathématiques/Relations binaires

Ici $E$ désigne un ensemble.

Généralités

Voir aussi : Relation (mathématiques)/Définition.

Définition, exemples

Exemples :

1. Pour $E=\mathbb{N}$, posons $ℛ=\{(0,1),(3,7),(3,4),(1,1)\}$. On a $0ℛ1$, $3ℛ7$, $3ℛ4$ mais pas $3ℛ5$.
2. L'égalité ($=$) sur $E$ provient de $\mathrm{\Delta }=\{(x,x),x\in E\}$. Ici on préfèrera $x=y$ à $x\mathrm{\Delta }y$.
3. L'inclusion sur $𝒫(E)$ : $ℛ=\{(X,Y)\in 𝒫(E{)}^2/X\subset Y\}$.
4. L'ordre sur $ℝ$ : $ℛ=\{(x,y)\in {ℝ}^2/x\le y\}$.

Qualités d'une relation binaire

Soit $ℛ$ une relation binaire sur E. $ℛ$ est dite :

• réflexive ssi $\mathrm{\forall }x\in E,xℛx$ (les exemples 2, 3, et 4 ci-dessus illustrent cette propriété) ;
• transitive ssi $\mathrm{\forall }x,y,z\in E,(xℛz\text{et}zℛy)\Rightarrow xℛy$ (exemples 1, 2, 3, et 4) ;
• symétrique ssi $\mathrm{\forall }x,y\in E,xℛy\Rightarrow yℛx$ (exemples 2 et 3 si E est vide) ;
• antisymétrique ssi $\mathrm{\forall }x,y\in E,xℛy\text{et}yℛx\Rightarrow x=y$ (exemples 1, 2, 3, et 4).
• complète ssi $\mathrm{\forall }x,y\in E,xℛy\text{ou}yℛx$

Relations d'équivalence

Exercice

Étant donnée une partition de $E$, définir une relation d'équivalence canoniquement associée à la partition. Quelles en sont les classes d'équivalence ?

Relations d'ordre

Voir aussi : Relation (mathématiques)/Relation d'ordre.

Éléments remarquables d'un ensemble ordonné $(E,\le )$ :

Exercice

Soit $\le$ un ordre sur $E$. On définit $\ge$, par $\mathrm{\forall }x,y\in E,x\ge y\iff y\le x$. Montrer que c’est un ordre. Quels en sont les éléments remarquables ?

Liens avec les applications

On s'intéresse ici à la compatibilité des applications avec les relations d'équivalence ou d'ordre.

Avec l'équivalence

Modèle:Wikipédia Soit $f:E\to F$ une application et $\sim$ une relation d'équivalence sur $E$. On dit que $f$ est compatible avec $\sim$ si $\mathrm{\forall }x,y\in E(x\sim y\Rightarrow f(x)=f(y))$. Alors, l'application $f$ passe au quotient, c'est-à-dire qu'on peut définir une nouvelle application $\tilde{f}:E/\sim \to F,\bar{x}\mapsto f(x)$.

Exercices :

1. Étant donnée une application $f:E\to F$, la rendre canoniquement surjective. On note encore $f$ la surjection obtenue.
2. On considère la relation binaire sur $E$ définie par $\mathrm{\forall }x,x^{\prime }\in E(x\sim x^{\prime }\iff f(x)=f(x^{\prime }))$. Montrer qu’il s'agit d'une relation d'équivalence. Que dire de l’application obtenue en passant au quotient ?

Avec l’ordre

Exemple : $𝒫(E)\to 𝒫(E),A\mapsto A^c$ est décroissante pour l'inclusion.

Exercices :

1. Soit $\mathrm{\Phi }:𝒫(E)\to 𝒫(E)$ croissante pour l'inclusion. Montrer que $\mathrm{\Phi }$ admet un point fixe, c'est-à-dire une partie $A\subset E$ telle que $\mathrm{\Phi }(A)=A$.
2. Soit $f:E\to F$ et $g:F\to E$ deux injections. Montrer le théorème de Cantor-Bernstein : « Il existe une bijection de $E$ sur $F$. »

Modèle:Wikipédia Modèle:Wikipédia Indications :

1. Considérer $𝒜:=\{A\subset E\mid \mathrm{\Phi }(A)\subset A\}$ et $A_0:=\bigcap _{A\in 𝒜}A$.
2. Faire un dessin et appliquer 1/, ou aller voir sur Wikipédia…