Relation (mathématiques)/Exercices/Relation d'équivalence

Exercice 1-1

Soit $f:A\to A$ une injection. On définit sur $A$ la relation ${\mathcal {R}}$ par (pour tous $x,y\in A$) :

$x{\mathcal {R}}y\Longleftrightarrow \exists n\in \mathbb {N} \quad y=f^{n}(x){\text{ ou }}x=f^{n}(y)$.

(Pour la notation $f^{n}$, voir Puissances itérées d'une fonction.)

1°   Montrer que (pour tous $x,y\in A$)

$x{\mathcal {R}}y\Longleftrightarrow \exists p,q\in \mathbb {N} \quad f^{p}(x)=f^{q}(y)$.

2°   Montrer que ${\mathcal {R}}$ est une relation d'équivalence sur $A$.

3°  Soit $C$ une classe d'équivalence pour ${\mathcal {R}}$.

a)  Montrer que $f(C)=C\cap \operatorname {Im} (f)$.

b)  Montrer que si $a\in C\setminus f(C)$ alors $C=\{f^{n}(a)\mid n\in \mathbb {N} \}$ et $C\setminus f(C)=\{a\}$.

4°  Montrer que toute partie $X\subset A$ telle que $f(X)=X$ est une réunion de classes d'équivalences.

5°  Soit $f:\mathbb {Z} \to \mathbb {Z}$ définie par : $f(n)={\begin{cases}n+2&{\text{si }}&n<0\\n+4&{\text{si }}&n\geq 0.\end{cases}}$

a)  Montrer que $f$ est injective.

b)  Déterminer $\operatorname {Im} (f)$.

c)  Décrire les classes d'équivalence de la relation ${\mathcal {R}}$ associée à $f$.

Solution

1°   Si $y=f^{n}(x){\text{ ou }}x=f^{n}(y)$ alors $f^{p}(x)=f^{q}(y)$, pour $(p,q)=(n,0){\text{ ou }}(0,n)$.

Réciproquement, si $f^{p}(x)=f^{q}(y)$ avec $p,q\in \mathbb {N}$ :

• si $q\leq p$, alors $f^{p-q}(x)=y$ (par injectivité de $f^{q}$) ;
• de même, si $q\leq p$ alors $f^{q-p}(y)=x$.

Dans les deux cas, $x{\mathcal {R}}y$.

2°   La réflexivité et la symétrie de ${\mathcal {R}}$ étant immédiates (par définition de $f^{0}$ et de ${\mathcal {R}}$), démontrons la transitivité, grâce à la question précédente. Supposons donc $x{\mathcal {R}}y$ et $y{\mathcal {R}}z$. Il existe alors $p,q,r,s\in \mathbb {N}$ tels que $f^{p}(x)=f^{q}(y)$ et $f^{r}(y)=f^{s}(z)$, d'où $f^{p+r}(x)=f^{q+r}(y)=f^{q+s}(z)$ et donc $x{\mathcal {R}}z$.

3°  a)  Pour tout $x\in A$, puisque $f(x){\mathcal {R}}x$, on a $x\in C\Leftrightarrow f(x)\in C\Leftrightarrow f(x)\in C\cap \operatorname {Im} (f)$.

b)   Si $a\in C\setminus f(C)$ alors (par définition de ${\mathcal {R}}$ et puisque $a\notin \operatorname {Im} (f)$) $\forall x\in A\quad x\in C\Leftrightarrow x{\mathcal {R}}a\Leftrightarrow \exists n\in \mathbb {N} \quad x=f^{n}(a)$, donc $a$ est l'unique élément de $C\setminus \operatorname {Im} (f)=C\setminus f(C)$.

4°  Soit $X$ une telle partie, montrons que $X=\cup _{x\in X}{\overline {x}}$, où ${\overline {x}}$ désigne la classe d'équivalence de $x$. Autrement dit : pour tout $x\in X$, montrons que ${\overline {x}}\subset X$, c'est-à-dire que $y{\mathcal {R}}x\Rightarrow y\in X$. Si $y=f^{n}(x)$ (pour un certain $n\in \mathbb {N}$), on a bien sûr $y\in f^{n}(X)=X$. Mais si $x=f^{n}(y)$, on a aussi $y\in \left(f^{n}\right)^{-1}(X)=X$ (car $f^{-1}(X)$ est égal à $f^{-1}(f(X))$ par hypothèse, c'est-à-dire — par injectivité de $f$ — à $X$).

5°  a)  $f$ envoie injectivement $\mathbb {Z} \setminus \mathbb {N}$ sur $A=\{\dots ,-2,-1,0,1\}$ et $\mathbb {N}$ sur $B=\{4,5,6,\dots \}$. Comme $A$ et $B$ sont disjoints, $f$ est injective.

b)  $\operatorname {Im} (f)=A\cup B=\mathbb {Z} \setminus \{2,3\}$.

c)  Il y a quatre classes : ${\overline {2}}=2+4\mathbb {N}$, ${\overline {3}}=3+4\mathbb {N}$, ${\overline {0}}=4\mathbb {N} \cup -2\mathbb {N}$ et ${\overline {1}}=1+{\overline {0}}$.