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.

 

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 - Posted by | Set Theory | , , , ,

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


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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: