Suppose that $X$ is a nonempty set. Let $A$ denote the set of functions from $X$ to $X$. Let $B$ denote the set of $h \in A$ such that $h$ is bijective. Define a relation $R$ on $A$ by
$$R = \{(f, g) \in A \times A : ∃h \in B \text{ such that }h \circ f = g \circ h\}.$$
Observe that if
$$(f, g) ∈ A × A, h \in B$$
and
$$h \circ f = g \circ h$$
then
$$h^{-1} \circ h \circ f = h^{−1}\circ g \circ h.$$
- Prove that $R$ is an equivalence relation on $A$.
- Prove that if $(f, g) \in R$, then $(f \circ f, g \circ g) \in R$.
- Suppose that $(f, g) \in R$. Suppose that there is some $x \in X$ with $f(x) = x$. Prove that there is some $y \in X$ with $g(y) = y$.
I know what an equivalence relation is, but I have no clue how to prove it effectively. I also have no clue where to start on the other two questions or what the prompt is actually saying. Any help will be greatly appreciated.
I'll use Greek letters for members of $B$.
I'll also drop the use of $\circ$, and concatenate function symbols.
Additionally, I'll use $fRg$ for $(f,g) \in R$.
For (1), you have to prove that $R$ is reflexive, that is $fRf$, for which you can just take $\iota_X$, the identity of $X$, which satisfies $\iota_Xf = f\iota_X$, for all $f \in A$.
Then you must prove it is symmetric, that is, $fRg$ implies $gRf$. Now, if $fRg$ then $\alpha f = g\alpha$, for some $\alpha \in B$. It follows that $\alpha^{-1}\in B$ and $$\alpha^{-1}g = \alpha^{-1}g\alpha\alpha^{-1} = \alpha^{-1}\alpha f\alpha^{-1} = f\alpha^{-1}.$$
Finally, you have to prove that $R$ is transitive, that is, if $fRg$ and $gRh$ then $fRh$.
So suppose that $fRg$ and $gRh$ and for $\alpha, \beta \in B$, we have $\alpha f = g\alpha$ and $\beta g = h \beta$. Check that $\beta\alpha f = h\beta\alpha$.
Thus, $R$ is indeed, an equivalence relation.
(2) is straightforward: if $\alpha f = g\alpha$, then $$\alpha f^2 = (\alpha f) f = (g\alpha) f = g(\alpha f) = g (g\alpha) = g^2\alpha.$$
For (3), if $f(x_0)=x_0$ and $\alpha \in B$ is such that $\alpha f = g\alpha$, then take $y_0 = \alpha(x_0)$, and $$y_0 = \alpha(x_0) = \alpha f(x_0) = g\alpha(x_0) = g(y_0).$$