## 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 the concepts of bijection, surjection, and injection are equivalent.

*Remark: *As always denote by .

**The Problem**

**Theorem: **Let . Then, is an injection if and only if it’s a surjection.

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

**Proof: **Suppose that is injective and let be arbitrary. Consider . Clearly then for some distinct . Otherwise

is an injection, but this is impossible by the Pigeonhole Principle. Thus, there exists some with such that . But, since is an injection this implies that , and continuing on this way we arrive at . Thus, . It follows from the arbitrariness of that is surjective.

Conversely, suppose that is surjective. Then, define

This is clearly an injection since implies that and in particular . But, by the last part of our proof this implies that is a surjection. So, let be distinct. Then, there exists (obviously distinct) such that and . Thus,

from where it follows that is an injection.

**Corollary:** A function is bijective if and only if it’s either surjective or injective.

**Corollary: **A mapping from to with 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.

[…] 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 |

[…] 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 |

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

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

[…] 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 |

[…] 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 |

[…] 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 |

[…] 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 |

[…] 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 |