A small semigroup vocabulary

When you work on a group of related problems, you find your self using the same procedures over and over. That is when you can start to name the procedures and build a specialized vocabulary. For example, the Greens relation worksheet has several related problems. Here are a few semigroup words you can use to work on those problems

gensem(n) returns a list of the functions from A = {1..n} to A. As we saw, this list gets big fast so don't bother trying to use gensem for n > 6 unless you have lots of spare time on your hands.

> gensem := proc(n)
local sem,i,step,newsem,j;
step := proc(lst,n)
local i,loclst;
loclst := NULL:
for i from 1 to n do loclst := loclst,[op(lst),i] od:
loclst end;
sem := [seq([i],i=1..n)];
for i from 2 to n do newsem := [ seq(step(sem[j],n),j=1..nops(sem))];
sem := newsem od:
sem end:

> F[3]:=gensem(3);

The elements of are ordered in a 'dictionary' order f < g means for some i between 1 and n, f(i) < g(i), and for all j < i, f(j) = g(j). ithelt(n,i) returns the ith element of in this order. This allows us to work with the elements of without actually creating the list of elements

> ithelt := proc(n,i)
local q,q1,lst,r,j;
q := i-1;
lst := NULL:
for j from 1 to n do
r := irem(q,n,'q1');
q := q1;
lst := r+1,lst
od;
[lst]; end:

> ithelt(10,29383);

Range(f) returns the set of values of the function f. That just means replace the square brackets in f with curley brackets. Maple removes all duplicates.

> Range := proc(f) {op(f)} end:

> Range(ithelt(10,29383));

rclass is a brute force word to list the R-class of a function f in Notice it uses Range and ithelt in its definition.

> rclass := proc(f)
local s, i,n, e;
s:= NULL;n:= nops(f):
for i from 1 to n^n do
e := ithelt(n,i):
if Range(f) = Range(e) then s := s,e fi od:
[s] end:

> rclass([1,2,2]);

dclass is an other brute force word to list the elements which are D-related to f. It uses Range and ithelt in its definition too.

> dclass := proc(f)
local s, i,n,m, e;
s:= NULL;n:= nops(f):
m := nops(Range(f));
for i from 1 to n^n do
e := ithelt(n,i):
if nops( Range(e))=m then s := s,e fi od:
[s] end:

> dclass([1,2,2]);

These two words rclass and dclass will allow you to fill in the first 6 rows of the r and d triangles mentioned in the Greens relation worksheet.