6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Arthur Dec 20 '17 at 17:15
  • $\begingroup$ 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. $\endgroup$ – Milo Brandt Dec 20 '17 at 21:55
12
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Thats quite beautiful $\endgroup$ – ASKASK Dec 21 '17 at 4:38
25
$\begingroup$

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

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

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.

$\endgroup$
2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Arthur Dec 20 '17 at 17:19
  • $\begingroup$ @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). $\endgroup$ – Lee Mosher Dec 20 '17 at 18:21
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.