For a function Y : X→X , if Y is injective, then Y∘Y∘Y is injective.

Question

For a function Y : X→X , if Y is injective, then Y∘Y∘Y is injective.

My attempt: Using contrapositive, if Y is not injective. then Y ∘ Y is not injective, the there exist x, x' ∈ X with x ≠ x' but y(x) = y(x'). Then applying function y again both sides yields: y(y(x)) = y(y(x')). similarly for Y ∘ Y ∘ Y that is y(y(y(x))) = y(y(y(x'))). Thus, there exist x, x' ∈ X with x ≠ x' with (Y ∘ Y ∘ Y)(x) = (Y ∘ Y ∘ Y)(x'), is not injective.

Can someone correct me if I am wrong? or maybe is there a better approach to prove Y∘Y∘Y is injective?

Answer 1

You can also prove it directly. For simplicity let $Y^k$ be $Y$ nested $k$ times. We'll use the fact that function composition is associative. Suppose $Y^3(x)=Y^3(y)$ for $x,y\in X$. We can also write this as $Y(Y^2(x))=Y(Y^2(y))$. By injectivity of $Y$, it follows that $Y^2(x)=Y^2(y)$. In other words, $Y(Y(x))=Y(Y(y))$. Again by injectivity $Y$, this implies $Y(x)=Y(y)$. Once again by injectivity, this implies $x=y$.

We've thus shown that if $Y^3(x)=Y^3(y)$, then $x=y$. This is the definition of $Y^3$ being injective.

Answer 2

The issue I seewith your proof is that we haven't really established any form of contradiction.

You can do it more directly by simply proving that composition of injective functions is injective. Which is done here

Answer 3

By definition $\; f:X\to X\;$ means that $\;\forall a\in X\;( f(a)\in X)$

Now, $\;f: X\to X\;$ is injective iff $\;\forall a\in X\;\forall b \in X \;\Big( f(a)=f(b) \to a=b\Big)\;$.

So first show that: $\;\forall n\in\Bbb Z^+\;\forall a\in X\;\forall b\in X\; \Big(f\mathop{\circ}^{n} (a)=f\mathop{\circ}^n (b) \to f\mathop{\circ}^{n-1}(a)=f\mathop{\circ}^{n-1}(b)\Big)$

Then by hypological syllogism (the chain rule), show that: $\;\forall n\in\Bbb Z^+\;\forall a\in X\;\forall b\in X\; \Big(f\mathop{\circ}^{n} (a)=f\mathop{\circ}^n (b) \to a=b\Big)$

---

$f\mathop{\circ}^n$ is the $n$-degree self-composition of $f$. Ie: $f\mathop{\circ}^3 (x) = f\circ f\circ f(x)$ and so forth.