Good Math, Bad Math

We start by defining a new property for monoids - a kind of equivalence relation called a monoid congruence. A Monoid congruence defines equivalence classes within the set of values in a monoid. The monoid congruence relation is generally written as "~", and it's a relation between two values in a monoid: ~⊆M×M. A monoid congruence has all of the usual properties of an equivalence relation: it's symmetric, reflexive, and transitive. It also respects the monoid operator: if a, b, c, and d are all members of a monoid M, a~c, and b~d, then aºb~cºd.

If we have a monoid congruence relation "~", then we can obviously use it to create a collection of equivalence classes, called congruence classes. If a is a member of monoid (M,º), then we can define the congruence class [a]={m∈M | x~a } - that is, the set of objects in M that are "~" with a.

We can then define a new operation on the congruence classes: if a and b are members of a monoid (M,º), then we can define an operation "*" by [a]*[b]=[aºb]. If you look at the set of congruence classes of M given by "~", and the "*", what do you get? Another monoid, which we call a quotient monoid. The quotient monoid created by a particular congruence relation "~" is written M/~.

Now, we take a new step, and this is where it starts to get really interesting. Remember how I described the relationship between monoids and computing devices? We're going to start taking advantage of that. If we take a monoid, and use concatenation as the notation for the monoid operator, then we can describe products as strings: "abc" is (aºb)ºc.

In automata theory, we talk about formal languages, which are specific sets of strings of symbols. A formal language is usually described by some system of rules, which describe how the strings in the language are generated. For a very simple example, we can use a regular expression, like "a⁺b^*" to represent the language consisting of any number of "a"s, possibly followed by any number of "b"s. We can talk about more complicated languages, by using grammars. For example, the classic first language that can't be described by simple regular expressions is the following:

	X → (X)
	X → X X
	X → ε

This language consists of sequences of open and close parens where the number of opens and closes is balanced: strings like "()", "(())", "((()(()(()))))", and so on.

If we think of a monoid as a meta-computing machine, then we can talk about the kinds of languages that can be accepted by a particular monoid - that is, if we're working with a machine built from the monoid, what kinds of languages can that machine accept? It turns out that we can define that set using monoid quotients!

We can start by defining a syntactic quotient, using contatenation to denote the monoid operator. If M is a monoid, and S is a subset of M, then we can define left and right syntactic quotients of S:

• If m∈M, then the right syntactic quotient of S by m, written S/m = { a∈M | am ∈ S }.
• If n∈M, then the left syntactic quotient of S by n, written n\S = { b∈M | mb∈S }.

We can then use the syntactic quotients to define congruence relations, exactly as we did above. We get two congruence relations, the right syntactic equivalence, ~s, which is the congruence relation induced by the right syntactic quotient, and the left syntactic equivalence s~, which is the congruence relation implied by the left syntactic quotient. And finally, we can define a total syntactic congruence (also called a double-sided congruence), written ~_s using both:

a ~_s b ⇔ (∀x,y∈M: xay∈S ⇔ xby∈S

So, here's where the connection to computable languages comes in. The syntactic quotient, following the procedure above, defines a new monoid - the syntactic monoid of S, which we call M(S). The syntactic monoid of S is a monoid which accepts the set S. We call a language - consisting of the strings of symbols that concatenated together by M's monoid operator result in values in S. So we've finally really gotten to the point where we can really see how a monoid represents a computing device. In computation theory, we can describe every computing device in terms of languages. We can likewise describe computable languages in terms of monoids.

In particular, we can define what it means for a language to be recognizable by a monoid, M. Take a language, L⊆M. If the set of quotients {L/m|m∈M} is finite, then L is recognizable by M.

There's more to it than this - transition monoids are particularly interesting. But that's enough for this post. We'll save it for later.