The semigroup of selfmaps on a finite set.

Definitions. Let A and B be nonempty sets. The Cartesian product of A with B is the set A x B of all ordered pairs [a,b] where a A and b B. A function from A to B is a subset f of A x B such that for each a A, there exactly one ordered pair in f with a as the first term. The symbol f: A -> B is written to mean f is a function from A to B. If [a,b] f, one says that b is the value of the function f at a and writes . If f: A -> B, then A is called the domain of f and B is the range of f. The set {f(a) | a in A} is called the image of A under f and is written f(A). The function f is one-to-one if it satisfies the condition f(x)=f(y) implies x = y. If f : A -> B and g: B -> C, then gf: A -> C is the function defined by gf (x) = g (f (x)). gf is called the composition of g with f. If A = B, then f: A -> B is called a selfmap of A

Examples. Let A = B = {1,2,3}. Two functions from A to A are and . The composition of fg and gf are different: They have different values at 1, fg(1) = f(g(1)) = f(2) = 1, and gf(1) = g(f(1)) = g(1) = 2.

Lemma. If f and g are functions with the same domain A and for each x in A, f(x) = g(x), then f = g.

Proof. f = { (x,f(x)) | x A} = {(x,g(x)) | x A} = g. qed.

Theorem. The set of all functions from a set A to A is a semigroup under the operation of composition.

Proof: We need to show that the operation of composition is associative. So let f, g, and h be functions A->A. Then f(gh)(x) = f(gh(x)) = f(g(h(x)) = fg(h(x) = (fg)h (x) for each x X. So by the lemma, (fg)h = f(gh). qed.

Problem. How many elements in ?

Start on Solution. We worked this out in class for A = {1,2,3} and got 27. Work it out in general, A = {1, 2, ..., n}.

Definition. If A is a finite set and f: A -> A is 1-1, then f is called a permutation of A. At the other extreme, f is called a constant function if f(A) has only one element. Let and denote the permutations and constant selfmaps of A respectively.

Problem. If A = {1,2, ..., n}, how many elements in ? ? Justify.

Problem. Is a semigroup under composition? What about ? Justify.

Using Maple to work with functions on a finite set.

Notation. It is very convenient use an abbreviated notation for a function f: A -> A by by just listing its sequence of values. So if f = {(1,3), (2,1), (3,1)} and g= {(1,2), (2,2), (3,1)} , then as lists of values f = [3,1,1] and g = [2,2,1]. . Maple can handle these as lists

> f := [3,1,1]; g:= [2,2,1];

Lets generate the set of all selfmaps on {1,2,3}. (We will make a list, rather than a set because Maple orders the elements of a differently than I like.)

> F := NULL:
for i from 1 to 3 do for j from 1 to 3 do for k from 1 to 3 do
F := F,[i,j,k] od od od:
F := [F];

Note all the functions which satisfy f(1)=1 come first, then all functions such that f(1)=2, and last all functions with f(1) = 3.

Problem. List all the functions in F with exactly two values. How many are there?

Problem. If A = {1,2, ..., n}, describe a method of listing all functions in with exactly two values. How many such functions are there?

Hint on getting started. Depending on how much experience you have had counting things, you might be able to just figure this out without experiment. Otherwise, work it for n = 3 first. Then n = 4. etc. until you see the pattern. Then use mathematical induction to prove that the formula always works. Use maple profusely to generate data to look for the pattern.

The composition operation

The composition operation can be conveniently defined in Maple by an 'ampersand' operation (see neutral operators in Maple help).

> `&c` := proc(f,g)
local i;
[seq(f[g[i]],i=1..nops(f))] end;

> [1,2,2] &c [1,2,2];

Definition. A function f: A -> A is called idempotent if f(f) = f. That is, f(f(x)) = f(x) for each x in A.

Problem. List all the idempotent functions in , where A = {1,2,3}. How many are there?

Solution: One solution is to just go though the list F and list all the ones for which f &c f = f.

> for f in F do if f &c f = f then print(f) fi od ;

So we see that there are 10 idempotent selfmaps on a 3 element set: 1 permutation, 3 constants, and 6 idempotents with exactly 2 values.

Problem. If A = {1,2, ..., n}, describe a method of listing all idempotent functions in . How many such functions are there?