The multiway graphs in the previous section are in a sense fundamentally metamathematical. Their “raw material” is mathematical statements. But what they represent are the results of operations—like substitution—that are defined at a kind of meta level, that “talks about mathematics” but isn’t itself immediately “representable as mathematics”. But to help understand this relationship it’s useful to look at simple cases where it’s possible to make at least some kind of correspondence with familiar mathematical concepts.
Consider for example the axiom
that we can think of as representing commutativity of the binary operator ∘. Now consider using substitution to “apply this axiom”, say starting from the expression (a∘b)∘(c∘d). The result is the (finite) multiway graph:
Conflating the pairs of edges going in opposite directions, the resulting graphs starting from any expression involving s ∘’s (and s+1 distinct variables) are:
And these are just the Boolean hypercubes, each with 2s nodes.
If instead of commutativity we consider the associativity axiom
then we get a simple “ring” multiway graph:
With both associativity and commutativity we get:
What is the mathematical significance of this object? We can think of our axioms as being the general axioms for a commutative semigroup. And if we build a multiway graph—say starting with (a∘b)∘b—we’ll find out what expressions are equivalent to (a∘b)∘b in any commutative semigroup—or, in other words, we’ll get a collection of theorems that are “true for any commutative semigroup”:
But what if we want to deal with a “specific semigroup” rather than a generic one? We can think of our symbols a and b as generators of the semigroup, and then we can add relations, as in:
And the result of this will be that we get more equivalences between expressions:
The multiway graph here is still finite, however, giving a finite number of equivalences. But let’s say instead that we add the relations:
Then if we start from a we get a multiway graph that begins like
but just keeps growing forever (here shown after 6 steps):
And what this then means is that there are an infinite number of equivalences between expressions. We can think of our basic symbols a and b as being generators of our semigroup. Then our expressions correspond to “words” in the semigroup formed from these generators. The fact that the multiway graph is infinite then tells us that there are an infinite number of equivalences between words.
But when we think about the semigroup mathematically we’re typically not so interested in specific words as in the overall “distinct elements” in the semigroup, or in other words, in those “clusters of words” that don’t have equivalences between them. And to find these we can imagine starting with all possible expressions, then building up multiway graphs from them. Many of the graphs grown from different expressions will join up. But what we want to know in the end is how many disconnected graph components are ultimately formed. And each of these will correspond to an element of the semigroup.
As a simple example, let’s start from all words of length 2:
The multiway graphs formed from each of these after 1 step are:
But these graphs in effect “overlap”, leaving three disconnected components:
After 2 steps the corresponding result has two components:
And if we start with longer (or shorter) words, and run for more steps, we’ll keep finding the same result: that there are just two disconnected “droplets” that “condense out” of the “gas” of all possible initial words:
And what this means is that our semigroup ultimately has just two distinct elements—each of which can be represented by any of the different (“equivalent”) words in each “droplet”. (In this particular case the droplets just contain respectively all words with an odd or even number of b’s.)
In the mathematical analysis of semigroups (as well as groups), it’s common ask what happens if one forms products of elements. In our setting what this means is in effect that one wants to “combine droplets using ∘”. The simplest words in our two droplets are respectively a and b. And we can use these as “representatives of the droplets”. Then we can see how multiplication by a and by b transforms words from each droplet:
With only finite words the multiplications will sometimes not “have an immediate target” (so they are not indicated here). But in the limit of an infinite number of multiway steps, every multiplication will “have a target” and we’ll be able to summarize the effect of multiplication in our semigroup by the graph:
More familiar as mathematical objects than semigroups are groups. And while their axioms are slightly more complicated, the basic setup we’ve discussed for semigroups also applies to groups. And indeed the graph we’ve just generated for our semigroup is very much like a standard Cayley graph that we might generate for a group—in which the nodes are elements of the group and the edges define how one gets from one element to another by multiplying by a generator. (One technical detail is that in Cayley graphs identity-element self-loops are normally dropped.)
Consider the group D2 (the “Klein four-group”). In our notation the axioms for this group can be written:
Given these axioms we do the same construction as for the semigroup above. And what we find is that now four “droplets” emerge, corresponding to the four elements of D2
and the pattern of connections between them in the limit yields exactly the Cayley graph for D2:
We can view what’s happening here as a first example of something we’ll return to at length later: the idea of “parsing out” recognizable mathematical concepts (here things like elements of groups) from lower-level “purely metamathematical” structures.