# Abstract Nonsense

## Function Theorem

Point of post: In this post we prove a fundamental theorem in the study of finite permutation groups. Namely, that for a function $f:\{1,\cdots,n\}\to\{1,\cdots,n\}$ the concepts of bijection, surjection, and injection are equivalent.

Remark: As always denote $\{1,\cdots,n\}$ by $[n]$.

The Problem

Theorem: Let $f:[n]\to[n]$. Then, $f$ is an injection if and only if it’s a surjection.

This is intuitively clear. If $f$ is an injection then $f(1),\cdots,f(n)$ are $n$-distinct elements of $[n]$, but since $[n]$ has only $n$-elements it makes sense that $\{f(1),\cdots,f(n)\}$ “takes up all the room” in $[n]$. Also, if $f$ is not injective then $f(1),\cdots,f(n)$ can have at most $n-1$ distinct elements and so can’t “take up all of ” $[n]$. That said, no theorem can go without formal proof.

Proof: Suppose that $f$ is injective and let $m\in[n]$ be arbitrary. Consider $f(m),f^2(m),\cdots,f^{n+1}(m)$. Clearly then $f^{k}(m)=f^{\ell}(m)$ for some distinct $\ell,k\in\{1,\cdots,n\}$. Otherwise

$g:[n+1]\to [n]:k\mapsto f^{k}(m)$

is an injection, but this is impossible by the Pigeonhole Principle. Thus, there exists some $\ell,k\in[n]$ with $\ell such that $f^{\ell}(m)=f^{k}(m)$. But, since $f$ is an injection this implies that $f^{\ell-1}(m)=f^{k-1}(m)$, and continuing on this way we arrive at $f^{\ell-k}(m)=m$. Thus, $f\left(f^{\ell-k-1}(m)\right)=m$. It follows from the arbitrariness of $m$ that $f$ is surjective.

Conversely, suppose that $f$ is surjective. Then, define

$\overset{\leftarrow}{f}:[n]\to[n]:m\mapsto \min f^{-1}(\{m\})$

This is clearly an injection since $m_1\ne m_2$ implies that $f^{-1}(\{m_1\})\ne f^{-1}(\{m_2\})$ and in particular $\min f^{-1}(\{m_1\})\ne \min f^{-1}(\{m_2\})$. But, by the last part of our proof this implies that $\overset{\leftarrow}{f}$ is a surjection. So, let $m_1,m_2\in[n]$ be distinct. Then, there exists (obviously distinct) $k_1,k_2\in[n]$ such that $\overset{\leftarrow}{f}(k_1)=m_1$ and $\overset{\leftarrow}{f}(k_2)=m_2$. Thus,

$f(m_1)=f\left(\overset{\leftarrow}{f}(k_1)\right)=f\left(\min f^{-1}(k_1)\right)=k_1\ne k_2=f\left(\min f^{-1}(k_2)\right)=f(m_2)$

from where it follows that $f$ is an injection. $\blacksquare$

Corollary: A function $f:[n]\to[n]$ is bijective if and only if it’s either surjective or injective.

Corollary: A mapping from $A$ to $B$ with $|A|=|B|<\infty$ is bijective if and only if it’s either injective or surjective.

References:

For more information on the abstract notion of functions and specifically functions between finite sets see

1. Munkres, James R. Topology. Upper Saddle River, NJ: Prentice Hall, 2000. Pri

2.  Stoll, Robert Roth. Set Theory and Logic. New York: Dover Publications, 1979. Print.

Advertisements

November 2, 2010 -

## 8 Comments »

1. […] number of injections . But, consider fixing and considering the number of injections . Then, by previous discussion we know that the number of such injections is the same as the number of such bijections. Thus, the […]

Pingback by Permutations (Pt. I) « Abstract Nonsense | November 6, 2010 | Reply

2. […] precisely one in it and zeros elsewhere). Since to prove that is a bijection it suffices, by this post, to prove it’s an injection. To do this suppose suppose that . Then, every entry of these […]

Pingback by Permutations (Pt. II Permutation Matrices) « Abstract Nonsense | November 6, 2010 | Reply

3. […] this spirit of this post we can recall that if […]

Pingback by Permutations (Pt. III Orbits and Cycles) « Abstract Nonsense | November 6, 2010 | Reply

4. […] recall though that is an injection if and only if it’s a bijection so that and thus . Thus, it follows that may be rewritten as […]

Pingback by Characterization of Alternating Multilinear Forms, and the Determinant « Abstract Nonsense | November 15, 2010 | Reply

5. […] is the inversion map . Since and consequently is finite and is a bijection, it follows from first principles that being ambivalent is equivalent to . Now, for notational convenience for we denote by and […]

Pingback by Representation Theory: The Connection Between the Square Root Function and the Number of Self-Conjugate Irreps (Cont.) « Abstract Nonsense | March 25, 2011 | Reply

6. […] second part of our theorem is an injection. But, by a previous theorem we have that and thus by a simple set theoretic fact we may conclude that is also a surjection from where the conclusion […]

Pingback by Representation Theory: The Irreps of the Product of Finitely Many Finite Groups « Abstract Nonsense | April 11, 2011 | Reply

7. […] the map . By the above remark we know that is injective, and since is finite we may appeal to a common set-theoretic fact to conclude that is surjective. Thus, there exists such that and since is commutative we know […]

Pingback by Integral Domains « Abstract Nonsense | June 15, 2011 | Reply

8. […] Proof: Define by for . We begin by showing that this is a well-defined mapping (in the sense that for each . To see that is an automorphism we first note that so that is a homomorphism, it’s an injection since implies and since is invertible this implies , and it’s surjective since for any we have that (note, we already knew it was surjective since is an injection from a finite set to itself, from where the rest follows from basic set theory). […]

Pingback by The Unit and Automorphism Group of Z/nZ (pt. II) « Abstract Nonsense | September 10, 2011 | Reply