1

For a finite set $A$, $f : A \to A$ is a bijection if there is an inverse function $g : A \to A$ such that $$\forall x \in A\quad g(f(x)) = x$$

Proof. If $f(x) = f(x')$, then $x = g(f(x)) = g(f(x')) = x'$. Therefore, $f$ is one-to-one.

Since $f$ is one-to-one, there must be $\vert A\vert$ elements in the range of $f$. This implies that $f$ is also one-to-one

I am confused on what $f : A \to A$ is supposed to mean. I understand that $f : A \to B$ means that $\forall x$ in the domain $A$ maps to the co-domain $B$, but how does $A$ map to itself in $f : A \to A$? Also, how do we arrive at $f(x) = f(x')$ from our antecedent? To me, the statement, $f(x) = f(x')$, looks like it is not one-to-one.

Thomas Prévost
  • 579
Jumping Juniper
  • 31
  • Onto means that when $x\ne x'$, we have $f(x)\ne f(x')$. The converse is $f(x)=f(x')$ then $x=x'$. – Kenta S Feb 17 '21 at 13:06
  • @KentaS What's you said was the very definition of injectivity, though for maps on finite dimensional spaces injectivity and subjectivity are the same thing. – Sam Wong Feb 17 '21 at 13:24
  • Oh sorry does "onto" mean surjective? I thought it was the other way. My bad. – Kenta S Feb 17 '21 at 13:32

1 Answers1

1

$f:A\to A$ means that $f$ maps every element of $A$ to $A$. If $f$ is onto, then $f$ is actually a rearrangement of elements of $A$ (because the dimension of $A$ is finite). But $f$ doesn't have to be onto, for example, $f\equiv 0$ is also a map from $A$ to $A$. And of course, $f$ now is not a rearrangement.

The proof actually shows that the map $f$ is injective. And for maps on finite dimensional spaces, injectivity is equivalent to surjectivity. See here.

Sam Wong
  • 2,277