Introduction aux mathématiques/Exercices/Relations binaires

Exercice 3-1

Soit $E$ un ensemble de cardinal $n$. Combien existe-t-il sur $E$ de relations binaires :

1. quelconques ? 2. réflexives ? 3. symétriques ?

Solution

1. $\operatorname {card} ({\mathcal {P}}(E\times E))=2^{n^{2}}$.
2. $\operatorname {card} ({\mathcal {P}}(E\times E\setminus \Delta _{E}))=2^{n(n-1)}$.
3. $2^{n(n-1)/2+n}=2^{n(n+1)/2}$.

 

Exercice 3-2

Il y a une erreur dans le raisonnement suivant :

Soit $E$ un ensemble et ${\mathcal {R}}$ une relation sur $E$, symétrique et transitive. Alors, ${\mathcal {R}}$ est réflexive.

En effet, si $x{\mathcal {R}}y$ alors $y{\mathcal {R}}x$ et, par transitivité, $x{\mathcal {R}}y$ et $y{\mathcal {R}}x$ impliquent que $x{\mathcal {R}}x$ (et $y{\mathcal {R}}y$).

Quelle est l'erreur commise ?

Solution

L'erreur est, pour démontrer que $x{\mathcal {R}}x$, de supposer qu'il existe un $y\in E$ tel que $x{\mathcal {R}}y$. Par exemple la relation de graphe vide est symétrique et transitive mais antiréflexive.