Recall that the notation means that f is a function
whose domain (set of inputs) is X and whose outputs lie in the set Y.
Note that there may be elements of Y which are *not* outputs
of f.

* Definition.* Let be a function
from a set X to a set Y.

1. f is * injective* (or *
one-to-one*) if implies for all .

2. f is * surjective* (or *
onto*) if for all , there is an such that .

3. f is * bijective* (or a *
one-to-one correspondence*) if it is both injective and
surjective.

Informally, a function is * injective* if
different inputs always produce different outputs. A function is * surjective* if everything in the target set is an
output of the function.

* Example.* (* Injective and
surjective functions*) Show that the function given by is not injective or
surjective.

f is *not* injective, because

Nor is f surjective. There is no , for instance, such that .

Note, however, that if is defined by , then g is surjective. ( denotes the set of real numbers greater than or equal to 0.) I just shrunk the target set so that it coincides with the set of outputs of .

* Example.* (* Injective and
surjective functions*) Show that the function given by is injective
but not surjective.

f is injective: If two outputs are the same, say

That is, the inputs must have been the same.

*This is one way to show that a function f is injective:*
Assume that , and prove that .

However, f is not surjective: There is no such that , i.e. such that , because is always positive.

You may know that there is a graphical test for injectivity for functions . A function is injective if and only if every horizontal line intersects the graph at most once. You can see that this is true for the graph of .

* Example.* (* Injective and
surjective functions*) Define by

Show that f is not injective, but that f is surjective.

f is not injective, since and : Different inputs can produce the same output.

f is surjective: You can see from the graph that every y-value is an output of the function. To prove this algebraically, I have to show that every is an output of f.

If , .

If , then , so .

*To prove a function is surjective, take an arbitrary output y and
find an input that produces it.* As in this example, your input
may be specified in terms of y, since that is given.

While you can show that a function is bijective by showing that it's
injective and surjective, there's a method which is usually easier:
Simply produce an * inverse function*.

* Definition.* Let be a function
from a set X to a set Y. An * inverse* for f is a
function such that:

1. For all , .

2. For all , .

The next result is extremely useful. It asserts that being bijective is the same as having an inverse.

* Lemma.* Let be a function
from a set X to a set Y. f is bijective if and only if f has an
inverse .

* Proof.* ( ) Suppose that
f is bijective. I'll construct the inverse function .

Take . Since f is surjective, there is an element such that . Moreover, x is unique: If and , then . But f is injective, so .

Define

I have defined a function . I must show that it is the inverse of f.

Let . By definition of , to compute I must find an element such that . But this is easy --- just take . Thus, .

Going the other way, let . By definition of , to compute I must find an element such that . Then , so

Therefore, really is the inverse of f.

( ) Suppose f has an inverse . I must show f is bijective.

To show that f is surjective, take . Then , so I've found an element of X --- namely --- which f maps to y. Therefore, f is surjective.

To show that f is injective, suppose and . Then

Therefore, f is injective.

Since f is injective and surjective, it's bijective.

*This result says that if you want to show a function is
bijective, all you have to do is to produce an inverse.* In many
cases, it's easy to produce an inverse, because an inverse is the
function which "undoes" the effect of f.

* Example.* (* Proving that a
function is bijective*) Define by . Show that f is bijective.

The opposite of cubing is taking the cube root, so I'll guess that the inverse is . Check it:

Thus, g is the inverse of f. By the lemma, f is bijective.

* Definition.* Let A be a set. A * permutation* of (or *on*) A is a bijection
.

* Proposition.* The set of permutations of a set A is a group under function
composition.

* Proof.* First, the composition of bijections is
a bijection: The inverse of is . Thus, function composition is a binary
operation on the set of bijections from A to A.

Function composition is always associative. The identity map is a permutation of A, and serves as an identity under function composition. Since bijective maps have inverses which are bijections, if is a bijection, so is . Therefore, is a group.

is called the * symmetric group*
on A. If S has n elements, you may as well take (since it doesn't matter what you
*call* the elements). The corresponding symmetric group is
denoted , the * symmetric group on n
letters*.

I'll use to denote the * identity
permutation* that sends every element to itself.

One way to write a permutation is to show where each element goes. For example, suppose

I'll refer to this as * permutation notation*.
This means that

Thus, the identity permutation in is

* Example.* (* Computing a
product of permutations*) Suppose

Compute the product .

The product means " first, then ".

Here's how to compute it:

So

Some people prefer to multiply permutations left-to-right: For them,
means " first, then ". You should probably choose one method and use
it all the time, to avoid confusing yourself. The right-to-left
approach I used above is consistent with the fact that permutations
are *functions*: In function notation, means , i.e. "g first, then
f".

* Example.* (* Finding the
inverse of a permutation*) Find the inverse of the permutation

I can find by simply reading "upside-down".

For example, , so . In this way, I get

Permutation notation is fine for computations, but is cumbersome for
writing permutations. We can represent permutations more concisely
using * cycle notation*. The idea is like
factoring an integer into a product of primes; in this case, the
elementary pieces are called * cycles*.

* Definition.* A * cycle* is
a permutation which maps a finite subset by

This cycle will be denoted .

The cycle has *
length* n. For example, the cycle has length 3.

Note that a cycle of length n has order n as an element of . For example,

A cycle of length 2 is called a * transposition*.
A transposition is a permutation that swaps two elements and leaves
everything else fixed. For example, is the
transposition that swaps 3 and 6.

* Example.* (* Examples of
cycles*) (a) Write the cycle in
permutation notation.

(b) Write the permutation as a cycle.

(a) The cycle in

(b)

* Example.* (* The inverse of a
cycle*) Find the inverse of .

To find the inverse of a cycle, just run the cycle backwards. Thus,

* Example.* (* Solving a
permutation equation*) Solve for x:

and . So the equation is

Hence,

* Example.* (* A permutation
which is not a cycle*) Show that the following permutation is not
a cycle.

In fact,

Note that the cycles and are * disjoint* --- no element is moved by both of them.
In fact, *an arbitrary permutation may be written as a product of
disjoint cycles*. Every permutation may also be written as a
product of transpositions.

The last example is a particular case of the following theorem.

* Theorem.* Every permutation on a finite set can
be written as a product of disjoint cycles.

* Proof.* Induct on the number of elements in the
set.

First, prove the result for a set with 1 element. This is easy --- there is only one permutation (the identity), and it is the cycle .

Next, assume that the result is known for sets with fewer than n elements and try to prove the result for a set with n elements. Suppose, then, that a permutation on a set with less than n elements can be written as a product of disjoint cycles. I have to show that a permutation on a set with n elements --- that is, an element --- can be written as a product of disjoint cycles.

Since is a finite group, has finite order. Let m be the order of . Consider the set

If , is the cycle

Otherwise, , so .

Now restricted to is a permutation on , so by the inductive assumption it can be written as a product of disjoint cycles. Then

Thus, has been expressed as a product of disjoint cycles. This completes the induction step, and establishes the result for all n.

The proof actually contains an algorithm for decomposing a permutation into a product of disjoint cycles. Start with an element and follow its "orbit" under the permutation until the orbit closes up. If you've exhausted all the elements, you're done. Otherwise, pick an element which wasn't in the orbit of the first element and follow the new element's orbit. Keep going.

* Example.* (* Writing a
permutation as a product of cycles*) Write the following
permutation as a product of disjoint cycles:

Here's a picture which shows how I got : 1 goes to 6, which goes to 5, which goes to 4, which goes back to 1.

After finishing a cycle, I start with the next element that hasn't been "used" so far. I keep going until all the elements have been accounted for.

If you have a permutation like in which an element doesn't move --- in this case, 2 --- you don't need to write " ". 2 is simply omitted from the cycle list, since an element which isn't listed doesn't move.

As a general rule, I'll express results of permutation computations as products of disjoint cycles. Note that, for instance, , so a given cycle can be written in different ways. You can pick one way by specifying that the first element be the smallest element in the cycle. Moreover, disjoint cycles can be listed in different orders, as the next result shows.

* Lemma.* Disjoint cycles commute.

* Proof.* Roughly speaking, if two cycles move
different sets of elements, then their effects are independent and it
doesn't matter in which order they're applied.

Suppose and are disjoint cycles:

Thus, .

Then

* Definition.* A *
transposition* is a permutation which interchanges two elements
and leaves everything else fixed. (That is, a transposition is a
cycle of length 2.)

* Proposition.* Every permutation is a product of
transpositions.

* Proof.* It suffices to show that every cycle is
a product of transpositions, since every permutation is a product of
cycles. Just observe that

To do the same for an arbitrary cycle , just add a's to the equation above.

* Remark.* While the decomposition of a
permutation into disjoint cycles is unique up to order and
representation of the cycles (i.e. ),
a permutation may be written as a product of transpositions in
infinitely many ways. You can always tack on trivial terms of the
form .

* Example.* (* Writing a
permutation as a product of transpositions*) Express as a product of transpositions in two different ways.

The decomposition of a permutation into a product of transpositions
is * not* unique.

* Lemma.* A permutation cannot be written as a
product of both an odd and an even number of transpositions.

* Proof.* Suppose

Assume m is even and n is odd, and all the 's and 's are transpositions.

Since ,

Note that the identity permutation has been written as a product of an odd ( ) number of transpositions. If this is impossible, I have a contradiction.

It therefore suffices to show that the identity permutation *cannot* be written as a product of an odd
number of transpositions. I'll give a proof by contradiction.

Suppose m is odd and

Here is a clever idea. Consider a polynomial in n variables. A permutation transforms f into another polynomial by "permuting the variables":

For example, suppose . Suppose . Then

Now consider the polynomial

For example, if ,

Obviously, the identity permutation takes f to itself.

On the other hand, a transposition for takes the factor to . In other words, a factor of -1 is introduced for each transposition. Since contains an odd number of transpositions, it will send f to .

This is a contradiction: If and are the same permutation, they should have the same effect on f. Therefore, the identity cannot be written as a product of an odd number of transpositions. Hence, a permutation cannot be written as a product of both an even and an odd number of transpositions.

Since the lemma shows that you can't write a given permutation as a product of both an even and an odd number of transpositions, the following definition makes sense.

* Definition.* A permutation is *
even* if it can be written as a product of an even number of
transpositions; a permutation is * odd* if it can
be written as a product of an odd number of transpositions.

* Remark.* Consider the decomposition

This shows that a cycle of length n is an even permutation if n is odd, and is an odd permutation if n is even. For example, the cycle is even, since it has length 3 and 3 is odd.

* Definition.* The * alternating
group* on n letters is the subgroup of consisting of the even permutations.

I should check that really is a subgroup. First, is even, so . Next, if and are even, then is even (decompose into transpositions, and write the product backwards). Therefore, is even (by concatenating decompositions of and into products of transpositions). Hence, .

If , there are an equal number of even and odd
permutations. Therefore, . In fact,
is a * normal* subgroup of .

* Example.* List the elements of , the alternating group on 3 letters.

Here is the multiplication table for :

The alternating group on 3 letters is the "rotation subgroup":

Copyright 2022 by Bruce Ikenaga