# If $f^n$ is the identity map then prove that $f$ is bijection

Let $f:A\rightarrow A$ and $f^n=1_A$ where $f^n=\underbrace{f\circ f\circ\cdots\circ f}_\text{n times}$. Prove that $f$ is bijection.

I found some type of proof and it's a contradiction proof but don't quite understand the surjectivity.

If f is not injection then there exist $x_1,x_2\in A$ such that $f(x_1)=f(x_2)$ and $x_1\neq x_2$. Then $f^{n-1}(f(x_1))=f^{n-1}(f(x_2)) \iff f^n(x_1)=f^n(x_2)$. But then $x_1=x_2$ therefore a contradiction.

If f is not surjection then there exist $y\in A$ such that for every $x\in A$ $f(x) \neq y$. This somehow implies that $f(f^{n-1}(z))\neq y$ for every $z\in X$.

There are some steps skipped in the surjectivity proof and honestly not sure how we get contradiction here or how we even got that $f(x) \neq y \implies f(f^{n-1}(z))\neq y$. Any help is appreciated.

Also is the injectivity proof reasonable?

• No need for any contradiction. Just strip the contradiction assumptions from the beginning and the "therefore a contradiction" from the end of the proof, and it's just as good, if not better. – Arthur Dec 20 '17 at 17:15
• As to your surjectivity proof, if there are no $x$ such that $f(x)=y$, then certainly, in particular, letting $x=f^{n-1}(z)$ has $f(f^{n-1}(z))\neq y$. This works (let $z=y$ - then you have $y\neq y$, which is a problem), but as the answers point out, isn't the best way to do it. – Milo Brandt Dec 20 '17 at 21:55

## 8 Answers

I would avoid a proof by contradiction here. In that case, your proof of injectivity becomes:

"Suppose $f(x_1)=f(x_2)$. Then $x_1=f^{n-1}(f(x_1))=f^{n-1}(f(x_2))=x_2$."

For surjectivity: $f^n=\mathrm{id}_A$, so $f(f^{n-1}(y))=y$, meaning $f(x)=y$ where $x=f^{n-1}(y)$.

• Thats quite beautiful – ASKASK Dec 21 '17 at 4:38

Note that $f^{n-1}$ is the inverse of $f$. It follows that $f$ is a bijection.

• Slam dunked. Just group parens around the $f \circ f \circ \cdots \circ f$ stuff. Composition is associative. – The_Sympathizer Dec 21 '17 at 2:19

Recall:

Theorem. Let $F \colon A \to B$ and $G \colon B \to C$.

1. If $G \circ F$ is injective, then $F$ is injective.
2. If $G \circ F$ is surjective, then $G$ is surjective.

Use that theorem for $f \colon A \to A$.

• Since $\operatorname{id}_A = f^n = f^{n-1} \circ \color{red}f$ is injective, $f$ is injective.
• Since $\operatorname{id}_A = f^n = \color{red}f \circ f^{n-1}$ is surjective, $f$ is surjective.

Therefore, $f$ is bijective.

Your injection proof is fine.

In your surjection proof, here's a hint for continuing, starting from the equation $f(x) \ne y$: what can you conclude by applying $f$ over and over again to both sides of that equation?

There is no need for contradiction at surjectivity. Since $$f^n(y) = y$$ for each $y$ then however we chose $y$ then $x= f^{n-1}(y)$ will map to $y$: $$f(x)= f(f^{n-1}(y))=f^n(y) = y$$

Injectivity looks good, for surjectivity, suppose there exists $a\in A$ so that $f(x)\neq a$ $\forall x\in A$. We know that $f^n(a)=(a)$, which means that $f^{n-1}(a)=b\in A$ is an element so that $f(b)=a$ which is a contraddiction.

• As mentioned in several of the answers and in my comment above, this looks better without the contradiction part. Just "For any $a\in A$, let $b = f^{n-1}(a)$. We get $f(b) = a$." is enough. – Arthur Dec 20 '17 at 17:19
• @Arthur: There may be no need for a proof by contradiction. And the best proof may look better without it. But it may help the OP to point out that his start of a proof can indeed be completed (as this answer and my answer both indicate). – Lee Mosher Dec 20 '17 at 18:21

How about this:

Surjective:

Let $y \in A$.

Need to show that there exists a $x \in A$ with

$f(x)=y.$

Consider $f^{n-1}(y)$, since $y \in A$, $f^{n-1}(y) \in A$.

For this

$x:= f^{n-1}(y)$ we have $f(x) =y$.

To prove that $f$ is surjective, we need to show that for every $y\in{A}$ there exists $x\in{A}$ such that $f(x)=y$. Assume this is not true, i.e. there exists $y\in{A}$ with no $x\in{A}$ that satisfies $f(x)=y$. Then $f(x)\ne{y}$ for every $x\in{A}$.

Since this applies for all $x\in{A}$, this must apply to $x=f^{n-1}(y)$ as well, i.e. $$f(f^{n-1}(y))\ne{y}$$ but $f(f^{n-1}(y))=f^n(y)=y$ so we have a contradiction.