Event-token graph, how do you obtain this first step?

Question

In https://writings.stephenwolfram.com/2022/03/the-physicalization-of-metamathematics-and-its-implications-for-the-foundations-of-mathematics/#mathematics-and-physics-have-the-same-foundations, chapter 15 there is the following event-token graph

If I understand correctly, this graph basically says that you apply rule $a\_\circ b\_ \longleftrightarrow a\_$ to itself, and obtain a number of rules. While I understand how you might get a number of the rules which are represented, I fail to derive $a\_\longleftrightarrow (a\_\circ b\_ )\circ c\_$.

Why is sometimes $c\_$ introduced, while $a\_$ is not substituted anything?

What is here the reasoning or procedure to make sure to obtain the whole set of derived rules?

Answer 1

Variables such as $a\_$, $b\_$, and $c\_$ don't have an independent meaning outside the expression; they are just placeholders. The expression "$a\_ \circ b\_ \leftrightarrow a\_$" is exactly equivalent to, say, "$c\_ \circ d\_ \leftrightarrow c\_$". They are both a long way of expressing:

The composition of two objects by the $\circ$ operation is equivalent, under the $\leftrightarrow$ relationship, to just the first of the two objects by itself.

Now suppose we want to take $a\_ \leftrightarrow a\_ \circ b\_$ and apply this rule to itself, replacing the second occurrence of $a\_$ in the expression. It would be incorrect (not fully general!) to write $a\_ \leftrightarrow (a\_ \circ b\_) \circ b\_$.

Instead, we want to express the idea that the second $a\_$ can be replaced by any $\circ$-composition of $a\_$ with another object - whether or not that object already appears in the expression! So we take $a\_ \leftrightarrow a\_ \circ b\_$ and replace the second occurrence of $a\_$ by $a\_ \circ c\_$, where $c\_$ is used to represent a third variable not necessarily equal to any of the previous ones.

This gives us $a\_ \leftrightarrow (a\_ \circ c\_) \circ b\_$. This is the same as $a\_ \leftrightarrow (a\_ \circ b\_) \circ c\_$, the expression you're confused by. In principle, either version is equally good...

...but to make life simpler, we would prefer to keep a "canonical" version of each possible expression we can derive, to make it easy to tell when we have the same expression. One way to get a canonical version of an expression is "out of all expressions equivalent to this one, take the first lexicographically". This means that in the canonical verion, the first variable that appears in our expression is called $a\_$, the second is called $b\_$, the third is called $c\_$, and so on.