Abstract Nonsense

Crushing one theorem at a time

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



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.


November 2, 2010 - Posted by | Set Theory | , , , ,


  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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: