0
$\begingroup$

I am trying to prove the following statement:

Let $f: A \to A$. If $f \circ f$ is a bijection, then $f$ is bijective.

My proof looked like this:

We know that $|A| = |A|$. Since this is the case, there exists a bijection $f: A \to A$ which has us conclude that $f$ is bijective.

Is this sufficient to prove the statement? Or must I separately prove surjectivity and injectivity for $f$ using $f \circ f$?

$\endgroup$
6
  • $\begingroup$ Not exactly a duplicate, but almost: math.stackexchange.com/questions/13135/… $\endgroup$ – Asaf Karagila♦ Mar 27 '20 at 8:24
  • $\begingroup$ I don't think it's a duplicate because $f \circ f$ can be any bijection. Thanks for showing me the similar question though. $\endgroup$ – Kookie Mar 27 '20 at 8:26
  • $\begingroup$ If I thought it was a duplicate, I would have closed the question. It's almost a duplicate, since the argument is quite similar. $\endgroup$ – Asaf Karagila♦ Mar 27 '20 at 8:27
  • $\begingroup$ Oh, right. That would make sense then. :P $\endgroup$ – Kookie Mar 27 '20 at 8:27
  • 1
    $\begingroup$ There exists a bijection $A\to A$, but not necessarly $f$!! $\endgroup$ – Jean-Claude Colette Mar 27 '20 at 8:28
4
$\begingroup$

You are asked to prove a property of a particular function $f$. Saying that there exists a bijection From $A$ onto $A$ proves nothing.

Suppose $f\circ f$ is a bijection. The $f(x)=f(y)$ implies $f(f(x))=f(f(y))$ which implies $x=y$. So $f$ is injective. I will let you show that $f$ is surjective also.

$\endgroup$
4
  • $\begingroup$ Can I prove surjectivity by saying that since $f \circ f$ is surjective, $\forall x \in A, \exists y \in A$ such that $f \circ f(x) = y$, then let $k = f(x) \in A$ and say $\forall k \in A, \exists y \in A$ such that $f(k) = y$ and conclude that $f$ is surjective? $\endgroup$ – Kookie Mar 27 '20 at 8:37
  • $\begingroup$ @Kookie Yoo wrote $\forall x \in A \exists y \in A$ instead of $\forall y \in A \exists x \in A$ $\endgroup$ – Kavi Rama Murthy Mar 27 '20 at 8:40
  • $\begingroup$ It's not a typo. Is it really the other way around? $\endgroup$ – Kookie Mar 27 '20 at 8:42
  • 1
    $\begingroup$ If you say for each $x$ there exists $y$ such that $f(x)=y$ you are only saying that $f$ is a well defined function. To show that it is surjective you have to show that for each $y$ there exists $x$ such that $f(x)=y$. $\endgroup$ – Kavi Rama Murthy Mar 27 '20 at 8:47
2
$\begingroup$

Hint: if $fo g$ is bijection $\implies g$ is one-one and $f$ is onto.

$\endgroup$
1
$\begingroup$

Your proof comes down to using the same letter $f$ for two different things. You are, first of all, given an $f: A \longrightarrow A$. You furthermore write that there exists a bijection $A \longrightarrow A$. You shouldn't call this map $f$, as there's no reason to believe that it's the same as the map you're originally. Indeed, your argument would imply that all maps $A \longrightarrow A$ are bijections, which is nonsense if $|A| \geq 2$.

Back to the proof itself, we do indeed have to show that $f$ is injective and surjective. We certainly have $im(f \circ f) = A$. Furthermore, $im(f \circ f) = f[f[A]]$. Hence, $im(f) \supseteq f[f[A]] = A$, so $f$ is onto. For injectivity, suppose $f(x) = f(y)$. By surjectivity, let $f(a) = x$, $f(b) = y$. Then $f(f(a)) = f(x) = f(y) = f(f(b))$, so $a = b$. Thus, $x = f(a) = f(b) = y$.

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