Let be a set and let denote the free semigroup on . Find the orders of elements in . Does have a kernel?
To answer this question the Right Way, we really need to have a more rigorous definition for . To accomplish this, we will introduce ‘lists’. The next several paragraphs borrow heavily from the book “Set Theory” by Monk and from the paper “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire” by Meijer, Fokkinga, and Paterson (primarily from the latter, with a bit of influence from the former). Both of those publications are very good.
This post was originally written for an experimental blog I started writing a while ago but quickly abandoned, so the style is a bit different.
One of the most basic “data structures” we use is the list; that is, a finite sequence of elements from some set. In this post we will give a precise definition for lists and prove some basic facts about them. The definition of list that we will use might seem strange, but it lends itself well to recursive proofs and to implementation in software. This will allow us to implement our proofs in a computer program, reasonably confident that the program does as we expect.
Definition: Let be a set. We define a function on recursively as follows: and . Then we define the set of lists in to be the set .
Note that for all sets , . We will call this the empty list and denote it by . By definition, every element of is either or of the form for some and .
Theorem (Basic facts about ):
- for all nonzero if and only if .
- If is nonempty and , then there exists a unique such that . We call this unique the length of and denote it .
- If with , then for some and with .
- () Since in particular , we have . () Suppose to the contrary, and choose minimal such that is empty. Then is empty, so that is empty, a contradiction.
- Let be the set of all lists which are not contained in a unique . Suppose is not empty. Note that each is contained in a smallest , say . Now let be the unique least element among the , and let be in . Then we have for some . If , then we have since . On the other hand, we have for some , and . This is a contradiction because no element of is the empty set. Suppose now that ; then we have and . Now , where . This is a contradiction since was chosen to be minimal.
- This follows from the definition of .
Note that by definition, every list has finite length. Elements of are ordered pairs which may be nested on the right; for instance, , , and are lists. To cut down on the number of parentheses we have to write, we will frequently use bracket notation as a shorthand. For instance, means and means .
One of the more useful things we can do with a list is deconstruct it. Functions that do this in a certain well-behaved way are called catamorphisms, and they have a nice uniqueness property.
Theorem (List catamorphisms): Let and be sets with nonempty, let , and let be a function. Then there exists a unique function such that and . We will denote this function by , and call functions of this kind list catamorphisms.
(Existence) Define a function recursively as follows: and . Certainly then is a function from to . Moreover, we have , and if , then . (Uniqueness) Suppose is a function such that and . We prove that by induction on the length. Certainly . Now suppose that for all lists of length we have , and let have length . Then . Thus is unique.
A catamorphism takes a binary operator and an element of , and returns a function which takes lists over and deconstructs them into a single element of using the operator. More literally, a catamorphism takes a list an replaces all commas with the operator and replaces the empty list with the fixed element . This may seem strange at first, but as we will see, several useful functions which take lists as input can be written as a catamorphism or a chain of catamorphisms composed together. One advantage of this is that certain functional transformation rules can be used to rewrite a given function to be “more efficient”, whatever that means. Two basic rules are called the Fusion law and the Split law; roughtly speaking, the Fusion law says when the composition of a function and a catamorphism is a catamorphism, and the Split law says that catamorphisms interact with direct products in a nice way.
- (Fusion law) Let , , and be nonempty sets, let and , and let and . Finally, let be a function. Then if and only if and for all and such that , .
- (Split law) Let , , and be nonempty sets, let and , and let and . Define by , and let and denote the coordinate projections. Then and .
- () Note that . Moreover, if and , then . () Note that and that . By the uniqueness of catamorphisms, .
- We proceed by induction on the length of the input . If , then . Suppose now that the result holds for all lists of length , and suppose has length . Then .
The fusion and split laws for catamorphisms will be useful both for proving theorems about functions defined in terms of catamorphisms (as we will see) and for developing efficient programs for performing explicit computations.
Definition: (List Concatenation) Let be a nonempty set. We define a binary operator recursively as follows: and . This oeprator is called concatenation.
Lemma: is associative. Proof: Let be a triple of lists in . We proceed by induction on the length of . For the base case, we have . For the inductive step, suppose is associative on all triples where has length , and that has length . Now . So is associative.
Lemma: for all lists . Proof: by definition. To see the second equality, we use induction on the length of . Certainly . If the result holds for , then as desired.
So if is nonempty, the set with the operator is a semigroup, and in fact is a monoid with identity element . We define the free monoid on to be .
Lemma: . Proof: By induction on the length of . Certainly . If the result holds for , then .
Lemma: has no zero divisors. Proof: If , then comparing lengths, .
Since has no zero divisors, the set is a subsemigroup. We call the free semigroup on .
We are finally in a position to answer the original problem: what are the orders of elements in ? Since every element of has positive length, and since length is additive over products, the powers of any element have monotonically increasing length. That is, the subsemigroup generated by is infinite. So every element of has infinite order.
Next we can consider the kernel of . Note that for any word of length , every element of the two sided ideal has length at least . As a consequence, for any element of length , we can construct an ideal in which every element has length at least – and so the ideal does not include . In particular, the intersection of all the ideals in is empty. So this semigroup has no kernel.