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.

• $+:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ is a binary operation.
• $+:\mathbb{R}\times\mathbb{R}\to\mathbb{R}$ is another binary operation.

Mathematicians commonly refer to these particular binops as “addition on the integers” and “addition on the reals”.

Remark

You 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 middle-aged Wave and type theory, in the version of homo­topy type theory, is a brand new baby Wave. Both Waves have changed and will change our under­standing of math in deep ways.

Trees

An 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.

Remark

The Wikipedia treatment of trees is scat­tered 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 represen­ta­tions of the expressions “$3+5$”, “$3\times5$”, and “$3-5$”.

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 points

I regard an expression as an abstract math object that can have many repre­sentations. For example “$3+5$” and the left tree in 3trees are two different represen­ta­tions 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

• If you evaluate $3+5$ you get $8$.
• If you evaluate $3\times 5$ you get $15$.
• If you evaluate $3-5$ you get $-2$.

I will show evaluation on trees like this:

Evaluation with trace

A 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.

Variables

In 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.

• You can’t evaluate an expression until you substitute numbers for the letters, which produces an instance of expression. (“Instance” is the preferable name for this, but I often refer to such a thing as an “example”.)
• If a variable is repeated you have to substitute the same value for each occurrence. So $a\Delta b$ is a different expression from $a\Delta a$: $2+3$ is an instance of $a+b$ but it is not an instance of $a+a$. But $a\Delta a$ and $b\Delta b$ are the same expression: any instance of one is an instance of the other.
• Substitute $a\Delta b$ for $a$ in $a\Delta b$ and you get $(a\Delta b)\Delta b$. You may have committed variable clash. You might have meant $(a\Delta b)\Delta c$. (Somebody please tell me a good link that describes variable clash.)
• Later, you will deal with multiplication tables for algebraic structures. There the elements are denoted by letters of the alphabet. They can’t be substituted for.

Empty boxes

A 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 $-$.
I have seen that notation in texts explaining variables, but I don’t know a reference. I expect to use this notation with trees in AbAl.

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.

Substitution

Given 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 $(a-b)-c)$ and $a-(b-c)$ respectively. Note that this tree

would be represented in algebra as $(a-b)-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 general

By 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.

References

• Abstracting algebra. An outline of the proposed book.
• Presenting binary operations.

Other references

• Abstraction in abstractmath.org.
• Algebra is a difficult foreign language. G&G post.
• Monads for high school III. G&G post.
• Monads in Wikipedia
• Symbolic language of math in abstractmath.org.
• Visible Algebra I.G&G post.
• Visible algebra I supplement. G&G post.
• Visible Algebra II. G&G post.