Binary operations as trees
This is one of a series of posts I am writing to help me develop my thoughts about how particular topics in my book Abstracting Algebra (“AbAl“) should be organized. In some parts, I present various options that I have not decided between.
This post concerns the presentation of binary operations as trees. The Mathematica code for the diagrams is in Substitution in algebra.nb
Binary operations as functions
A binary operation or binop $\Delta$ is a function of two variables whose value at $(a,b)$ is traditionally denoted by $a\Delta b$. Most commonly, the function is restricted to having inputs and outputs in the same set. In other words, a binary operation is a function $\Delta:S\times S\to S$ defined on some set $S$. $S$ is the underlying set of the operation. For now, this will be the definition, although binops may be generalized to multiple sets later in the book.
In AbAl:
 Binops will be defined as functions in the way just described.
 Algebraic expressions will be represented
as trees, which exhibit more clearly the structure of the expressions that is encoded in algebraic notation.  They will also be represented using the usual infix expressions such as “$3\times 5$” and “$35$”,
Fine points
The definition of a binop as a function has terminological consequences. The correct point of view concerning a function is that it determines its domain and its codomain. In particular:
A binary operation determines its underlying set. Thus if we talk about an arbitrary binop $\Delta$, we don’t have to give a name to its underlying set. We can just say “the underlying set of $\Delta$” or “$U(\Delta)$”. Examples“$+$” is not one binary operation.
Mathematicians commonly refer to these particular binops as “addition on the integers” and “addition on the reals”. RemarkYou almost never see this attitude in textbooks on algebra. It is required by both category theory and type theory, two Waves flooding into math. Category theory is a middleaged Wave and type theory, in the version of homotopy type theory, is a brand new baby Wave. Both Waves have changed and will change our understanding of math in deep ways. TreesAn arbitrary binop $\Delta$ can be represented as a binary tree in this way: generic binop This tree represents the expression that in standard algebraic notation is “$a\Delta b$”. In more detail, the tree is an ordered rooted binary tree. The “ordered” part means that the leaves (nodes with no descendants) are in a specific left to right order. In AbAl, I will define trees in some detail, with lots of pictures. The root shows the operation and the two leaves show elements of the underlying set. I follow the custom in computing science to put the root at the top. Metaphors should not dictate your life by being taken literally. RemarkThe Wikipedia treatment of trees is scattered over many articles and they almost always describe things mostly in words, not pictures. Describing math objects in words when you could use pictures is against my religion. Describing is not the same as defining, which usually requires words. Some concrete examples:3trees
These are representations of the expressions “$3+5$”, “$3\times5$”, and “$35$”. Just as “$5+3$” is a different expression from “$3+5$”, the left tree in 3trees above is a different expression from this one: switch They have the same value, but they are distinct as expressions — otherwise, how could you state the commutative law? Fine pointsI regard an expression as an abstract math object that can have many representations. For example “$3+5$” and the left tree in 3trees are two different representations of the same (abstract) expression. This deviates from the usual idea that “expression” refers to a typographical construction. In previous posts, when the operation is not commutative, I have sometimes labeled the legs like this: I have thought about using this notation consistently in AbAl, but I suspect it would be awkward in places. Evaluation and substitution
They and the Only Axiom of Algebra, which I will discuss in a later post, are all that is needed to express the true nature of algebra. Evaluation
I will show evaluation on trees like this:
Evaluation with traceA more elaborate version, valuation with trace, would look like this. This allows you to keep track of where the valuations come from. You could also keep track of the operation used at each node. An interactive illustration of this is in the post Visible algebra I supplement. That illustration requires CDF Player to be installed on your computer. You can get it free from the Mathematica website. VariablesIn the tree above, the $a$ and $b$ are variables, just as they are in the equivalent expression $a\Delta b$. Algebra beginners have a hard time understanding variables.
Empty boxesA straightforward way to denote variables would be to use empty boxes: The idea is that a number (element of the underlying set) can be inserted in each box. If $3$ (left) and $5$ (right) are placed in the boxes, evaluation would place the value of $3\Delta5$ in the root. Each empty box represents a separate variable. Empty boxes could also be used in the standard algebraic notation: $\Delta$ or $+$ or $$. To achieve the effect of one variable in two different places, as in we can cause it to repeat, as below, where “$\text{id}$” denotes the identity function on the underlying set: To evaluate at a number (member of the underlying set) you insert a number into the only empty box which evaluates to which of course evaluates to $3\Delta3$. This way of treating repeated variables exhibits the nature of repeated variables explicitly and naturally, putting the values automatically in the correct places. This process, like everything in this section, comes from monad theory. It also reminds me of linear logic in that it shows that if you want to use a value more than once you have to copy it. SubstitutionGiven two binary trees you could attach the root of the first one to one of the leaves of the second one, in two different ways, to get these trees:
which in standard algebra notation would be written $(ab)c)$ and $a(bc)$ respectively. Note that this tree would be represented in algebra as $(ab)b$. In general, substituting a tree for an input (variable or empty box) consists of replacing the empty box by the whole tree, identifying the root of the new tree with the empty box. In graph theorem, “substitution” may be called “grafting”, which is a good metaphor. You can evaluate the left tree in 2trees at particular numbers to evaluate it in two stages: Of course, evaluating the right one at the same values would give you a different answer, since subtraction is not associative. Here is another example: Binary trees in generalBy repeated substitution, you can create general binary trees built up of individual trees of this form: In AbAl I will give examples of such things and their counterparts in algebraic notation. This will include binary trees involving more than one binop, as well. I showed an example in the previous post, which example I repeat here: It represents the precise unsimplified expression \[A=wh+\frac{1}{2}\left(\pi(\frac{1}{2}w)^2\right)\] Some of the operations in that tree are associative and commutative, which is why the expression can be simplified. The collection of all (finite) binary trees built out of a single binop with no assumption that it satisfies laws (associative, commutative and so on) is the free algebra on that binary operation. It is the mother of all binary operations, so it plays the same role for an arbitrary binop that the set of lists plays for associative operations, as described in Monads for High School III: Algebras. All this will be covered in later chapters of AbAl. ReferencesPreceding posts in this series
Other references

This work is licensed under a Creative Commons AttributionShareAlike 2.5 License.