# The only axiom of algebra

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. This post concerns the relation between substitution and evaluation that essentially constitutes the definition of algebra. The Mathematica code for the diagrams is in Subs Eval.nb.

## Substitution and evaluation

This post depends heavily on your understanding of the ideas in the post Presenting binary operations as trees.

### Notation for evaluation

I have been denoting evaluation of an expression represented as a tree like this:

In standard algebra notation this would be written:$(6-4)-1=2-1=1$

This treatment of evaluation is intended to give you an intuition about evaluation that is divorced from the usual one-dimensional (well, nearly) notation of standard algebra. So it is sloppy. It omits fine points that will have to be included in AbAl.

• The evaluation goes from bottom up until it reaches a single value.
• If you reach an expression with an empty box, evaluation stops. Thus $(6-3)-a$ evaluates only to $3-a$.
• $(6-a)-1$ doesn’t evaluate further at all, although you can use properties peculiar to “minus” to change it to $5-a$.
• I used the boxed “1” to show that the value is represented as a trivial tree, not a number. That’s so it can be substituted into another tree.

### Notation for substitution

I will use a configuration like this

to indicate the data needed to substitute the lower tree into the upper one at the variable (blank box). The result of the substitution is the tree

In standard algebra one would say, “Substitute $3\times 4$ for $a$ in the expression $a+5$.” Note that in doing this you have to name the variable.

#### Example

“If you substitute $12$ for $a$ in $a+5$ you get $12+5$”:

results in

#### Example

“If you substitute $3\times 4$ for $a$ in $a+b$ you get $3\times4+b$”:

results in

Like evaluation, this treatment of substitution omits details that will have to be included in AbAl.

• You can also substitute on the right side.
• Substitution in standard algebraic notation often requires sudden syntactic changes because the standard notation is essentially two-dimensional. Example: “If you substitute $3+ 4$ for $a$ in $a\times b$ you get $(3+4)\times b$”.
• The allowed renaming of free variables except when there is a clash causes students much trouble. This has to be illustrated and contrasted with the “binop is tree” treatment which is context-free. Example: The variable $b$ in the expression $(3\times 4)+b$ by itself could be changed to $a$ or $c$, but in the sentence “If you substitute $3+ 4$ for $a$ in $a\times b$ you get $(3+4)\times b$”, the $b$ is bound. It is going to be difficult to decide how much of this needs explaining.

## The axiom

The Axiom for Algebra says that the operations of substitution and evaluation commute: if you apply them in either order, you get the same resulting tree. That says that for the current example, this diagram commutes:

The Only Axiom for Algebra

In standard algebra notation, this becomes:

• Substitute, then evaluate: If $a=3\times 4$, then $a+5=3\times 4+5=12+5$.
• Evaluate, then substitute: If $a=3\times 4$, then $a=12$, so $a+5=12+5$.

Well, how underwhelming. In ordinary algebra notation my so-called Only Axiom amounts to a mere rewording. But that’s the point:

 The Only Axiom of Algebra is what makes algebraic manipulation work.

• In functional notation, the Only Axiom says precisely that $\text{eval}∘\text{subst}=\text{subst}∘(\text{eval},\text{id})$.
• The Only Axiom has a symmetric form: $\text{eval}∘\text{subst}=\text{subst}∘(\text{id},\text{eval})$ for the right branch.
• You may expostulate: “What about associativity and commutativity. They are axioms of algebra.” But they are axioms of particular parts of algebra. That’s why I include examples using operations such as subtraction. The Only Axiom is the (ahem) only one that applies to all algebraic expressions.
• You may further expostulate: Using monads requires the unitary or oneidentity axiom. Here that means that a binary operation $\Delta$ can be applied to one element $a$, and the result is $a$. My post Monads for high school III. shows how it is used for associative operations. The unitary axiom is necessary for representing arbitrary binary operations as a monad, which is a useful way to give a theoretical treatment of algebra. I don’t know if anyone has investigated monads-without-the-unitary-axiom. It sounds icky.
• The Only Axiom applies to things such as single valued functions, which are unary operations, and ternary and higher operations. They also apply to algebraic expressions involving many different operations of different arities. In that sense, my presentation of the Only Axiom only gives a special case.
• In the case of unary operations, evaluation is what we usually call evaluation. If you think about sets the way I do (as a special kind of category), evaluation is the same as composition. See “Rethinking Set Theory”, by Tom Leinster, American Mathematical Monthly, May, 2014.
• Calculus functions such as sine and the exponential are unary operations. But not all of calculus is algebra, because substitution in the differential and integral operators is context-sensitive.

## References

### Preceding posts in this series

##### Remarks concerning these posts
• Each of the posts in this series discusses how I will present a small part of AbAl.
• The wording of some parts of the posts may look like a first draft, and such wording may indeed appear in the text.
• In many places I will talk about how I should present the topic, since I am not certain about it.

Send to Kindle

# 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 presen­ta­tion 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 “$3-5$”,

### Fine points

The definition of a binop as a function has termi­no­logical 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.

• $+:\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

 The two basic operations on algebraic expressions are 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:

2trees

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.

Send to Kindle

# Presenting binary operations

This is the first of a set of notes I am writing to help me develop my thoughts about how particular topics in my book Abstracting algebra should be organized. This article describes my plan for the book in some detail. The present post has some thoughts about presenting binary operations.

## Before binary operations are introduced

Traditionally, an abstract algebra book assumes that the student is familiar with high school algebra and will then proceed with an observation that such operations as $+$ and $\times$ can be thought of as functions of two variables that take a number to another number. So the first abstract idea is typically the concept of binary operation, although in another post I will consider whether that really should be the first abstract concept.

The Abstracting Algebra book will have a chapter that presents concrete examples of algebraic operations and expressions on numbers as in elementary school and as in high school algebra. This section of the post outlines what should be presented there. Each subsection needs to be expanded with lots of examples.

### In elementary school

In elementary school you see expressions such as

• $3+4$
• $3\times 4$
• $3-4$

The student invariably thinks of these expressions as commands to calculate the value given by the expression.

They will also see expressions such as
$\begin{array}[b]{r} 23\\ 355\\ + 96\\ \hline \end{array}$
which they will take as a command to calculate the sum of the whole list:
$\begin{array}[b]{r} 23\\ 355\\ + 96\\ \hline 474 \end{array}$

That uses the fact that addition is associative, and the format suggests using the standard school algorithm for adding up lists. You don’t usually see the same format with more than two numbers for multiplication, even though it is associative as well. In some elementary schools in recent years students are learning other ways of doing arithmetic and in particular are encouraged to figure out short cuts for problems that allow them. But the context is always “do it”, not “this represents a number”.

### Algebra

In algebra you start using letters for numbers. In algebra, “$a\times b$” and “$a+b$” are expressions in the symbolic language of math, which means they are like noun phrases in English such as “My friend” and “The car I bought last week and immediately totaled” in that both are used semantically as names of objects. English and the symbolic language are both languages, but the symbolic language is not a natural language, nor is it a formal language.

#### Example

In beginning algebra, we say “$3+5=8$”, which is a (true) statement.

The expressions “$3+5$” and “$8$”

• are not the same expression
• but in the standard semantics of algebra they have the same meaning
• and therefore the equation communicates information that neither “$3+5$” nor “$8$” communicate.

Another example is “$3+5=6+2$”.

Facts like this example need to be communicated explicitly before binary operations are introduced formally. The students in a college abstract algebra class probably know the meaning of an equation operationally (subconsciously) but they have never seen it made explicit. See Algebra is a difficult foreign language.

#### Note

The equation “$3+5=6+2$” is an expression just as much as “$3+5$” and “$6+2$” are. It denotes an object of type “equation”, which is a mathematical object in the same way as numbers are. Most mathematicians do not talk this way, but they should.

## Binary operations

### Early examples

Consciousness-expanding examples should appear early and often after binary operations are introduced.

#### Common operations

• The GCD is a binary operation on the natural numbers. This disturbs some students because it is not written in infix form. It is associative. The GCD can be defined conceptually, but for computation purposes needs (Euclid’s) algorithm. This gives you an early example of conceptual definitions and algorithms.
• The maximum function is another example of this sort. This is a good place to point out that a binary operation with the “same” definition cen be defined on different sets. The max function on the natural numbers does not have quite the same conceptual definition as the max on the integers.

#### Extensional definitions

In order to emphasize the arbitrariness of definitions, some random operations on a small finite sets should be given by a multiplication table, on sets of numbers and sets represented by letters of the alphabet. This will elicit the common reaction, “What operation is it?” Hidden behind this question is the fact that you are giving an extensional definition instead of a formula — an algorithm or a combination of familiar operations.

#### Properties

The associative and commutative properties should be introduced early just for consciousness-raising. Subtraction is not associative or commutative. Rock paper scissors is commutative but not associative. Groups of symmetries are associative but not commutative.

### Binary operation as function

The first definition of binary operation should be as a function. For example, “$+$” is a function that takes pairs of numbers to numbers. In other words, $+:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ is a function.

We then abstract from that example and others like it from specific operations to arbitrary functions $\Delta:S\times S\to S$ for arbitrary sets $S$.

This is abstraction twice.

• First we replace the example operations by an arbitrary operation. such as multiplication, subtraction, GCD and MAX on $\mathbb{Z}$, or something complicated such as $(x,y)\mapsto 3(xy-1)^2(x^2+xy^3)^3$.
• Then we replace sets of numbers by arbitrary sets. An example would be the random multiplication on the set $\{1,2,5\}$ given by the table
$\begin{array}{c|ccc} \Delta& 1&2&5\\ \hline 1&2&2&1\\ 2&5&2&1\\ 5&2&1&5 \end{array}$
This defines a function $\Delta:\{1,2,5\}\times\{1,2,5\}\to\{1,2,5\}$ for which for example $\Delta(2,1)=5$, or $2\Delta 1=5$. This example uses numbers as elements of the set and is good for eliciting the “What operation is it?” question.
• I will use examples where the elements are letters of the alphabet, as well. That sort of example makes the students think the letters are variables they can substitute for, another confusion to be banished by the wise professor who know the right thing to say to make it clear. (Don’t ask me; I taught algebra for 35 years and I still don’t know the right thing to say.)

It is important to define prefix notation and infix notation right away and to use both of them in examples.

### Other representations of binary operations.

The main way of representing binary operations in Abstracting Algebra will be as trees, which I will cover in later posts. Those posts will be much more interesting than this one.

#### Binary operations in high school and college algebra

• Some binops are represented in infix notation: “$a+b$”, “$a-b$”, and “$a\times b$”.
• “$a\times b$” is usually written “$ab$” for letters and with the “$\times$” symbol for numbers.
• Some binops have idiosyncratic representation: “$a^b$”, “${a}\choose{b}$”.
• A lot of binops such as GCD and MAX are given as functions of two variables (prefix notation) and their status as binary operations usually goes unmentioned. (That is not necessarily wrong.)
• The symbol “$(a,b)$” is used to denote the GCD (a binop) and is also used to denote a point in the plane or an open interval, both of which are not strictly binops. They are binary operations in a multisorted algebra (a concept I expect to introduce later in the book.)
• Some apparent binops are in infix notation but have flaws: In “$a/b$”, the second entry can’t be $0$, and the expression when $a$ and $b$ are integers is often treated as having good forms ($3/4$) and bad forms ($6/8$).

#### Trees

The chaotic nature of algebraic notation I just described is a stumbling block, but not the primary reason high school algebra is a stumbling block for many students. The big reason it is hard is that the notation requires students to create and hold complicated abstract structures in their head.

##### Example

This example is a teaser for future posts on using trees to represent binary operations. The tree below shows much more of the structure of a calculation of the area of a rectangle surmounted by a semicircle than the expression

$A=wh+\frac{1}{2}\left(\pi(\frac{1}{2}w)^2\right)$
does.

The tree explicitly embodies the thought process that leads to the formula:

• You need to add the area of the rectangle and the area of the semicircle.
• The area of the rectangle is width times height.
• The area of the semicircle is $\frac{1}{2}(\pi r^2)$.
• In this case, $r=\frac{1}{2}w$.

Any mathematician will extract the same abstract structure from the formula$A=wh+\frac{1}{2}\left(\pi(\frac{1}{2}w)^2\right)$ This is difficult for students beginning algebra.

Send to Kindle

# Monads for high school I

### Notes for viewing

The interactive examples in this post require installing Wolfram CDF player, which is free and works on most desktop computers using Firefox, Safari and Internet Explorer, but not Chrome. The source code is the Mathematica Notebook associative.nb, which is available for free use under a Creative Commons Attribution-ShareAlike 2.5 License. The notebook can be read by CDF Player if you cannot make the embedded versions in this post work.

I've been working on first drafts (topic posts) of several sections of my proposed book Abstracting algebra (AbAl), concentrating on the ideas leading up to monads.  This is going slowly because I want the book to be full of illustrations and interactive demos.  I am writing the demos in Mathematica simultaneously with writing the text, and designing demos is very s l o w work. It occurred to me that I should write an outline of the path leading up to monads, using some of the demos I have already produced. This is the first of probably two posts about the thread.

• AbAl is intended to give people with a solid high school math background a mental picture of or way of thinking about the various levels of abstraction of high school algebra.
• This outline is not a "Topic post" as described in the AbAl page. In particular, it is not aimed at high school students! It is a guided tour of my current thoughts about a particular thread through the book.
• The AbAl page has a brief outline of the topics to be covered in the whole book.  Perhaps it should also have a list of threads like this post.

## Associativity

AbAl will have sections introducing functions and binary operations using pictures and demos (not outlined in this thread).  The section on binary operations will introduce infix, prefix and postfix notation but will use trees (illustrated below) as the main display method.  Then it will introduce associativity, using demos such as this one:

Using this computingscienceish tree notation makes it much easier to visualize what is happening (see Visible Algebra II), compared to, for example, $(ab)(cd)=a(b(cd))=a((bc)d)=((ab)c)d=(a(bc))d$  In this equation, the abstract structure is hidden.  You have to visualize doing the operation starting with the innermost parentheses and moving out.  With the trees you can see the computation going up the tree.

I will give examples of associative functions that are not commutative using $2\times2$ matrices and endofunctions on finite sets such as the one below, which gives all the functions from a two element set to itself.

• Note that each function is shown by a diagram, not by an arbitrary name such as "id" or "sw", which would add a burden to the memory for an example that occurs in one place in the book. (See structural notation in the Handbook.)
• The section on composition of functions will also look in some depth at permutations of a three-element set, anticipating a section on groups.

By introducing a mechanism for transforming trees of associative binary operations, you can demonstrate (as in the demo below) that any associative binary operation is defined on any list of two or more elements of its domain.

For example, applying addition to three numbers $a$, $b$ and $c$ is uniquely defined. This sort of demo gives an understanding of why you get that unique definition but it is not a proof, which requires formal induction. AbAl is not concerned with showing the reader how to prove math statements.

In this section I will also introduce the oneidentity concept: the value of an associative binary operation on a an element $a$ is $a$.  Thus applying addition or multiplication to $a$ gives $a$.  (The reason for this is that you want an associative binary operation to be a unique quotient of the free associative binary operation.  That will come up after we talk about some examples of monads.)

The oneidentity property also implies that for an associative binary operation with identity element, applying the operation to the empty set gives the identity element.  Now we can say:

An associative binary operation with identity element is uniquely defined on any finite list of elements of its domain.

Thus, in prefix notation,$+(2,3)=5$, $+(2,3,5)=10$, $+(2)=2$ and $+()=0$.  Similarly $\times(2)=2$ and $\times()=1$.

This fact suggests that the natural definition of addition, multiplication, and other associative binary operations is as functions from lists of elements of the domain to elements of the domain.   This fits with our early intuition of addition from grade school, not to mention from Excel:  Addition is something you do to lists.  That feeling (for me) is not so strong for multiplication; for many common business applications you generally multiply two things like price and number sold. That's because multiplication is usually for things of different data types, but you usually add things of the same data type (not apples and oranges?).

That raises the question: Does every function taking lists to elements come from an associative binary operation?  I will give an example that says no.  But the next thing is to introduce joining lists (concatenation), where we discover that joining lists is an associative binary operation.  So it is really an operation on lists of lists.  This will turn out to give us a systematic way to define all associative binary operations by one mechanism, because it is an example of a monad.  That is for the second installment of this outline.

Send to Kindle

# Visible algebra II

### MathJax.Hub.Config({ jax: ["input/TeX","output/NativeMML"], extensions: ["tex2jax.js"], tex2jax: { inlineMath: [ ['$','$'] ], processEscapes: true } }); The interactive examples in this post require installing Wolfram CDF player, which is free and works on most desktop computers using Firefox, Safari and Internet Explorer, but not Chrome. The source code is the Mathematica Notebook Wolfram website. The code for the demos is in the Mathematica notebook algebra2.nb, which is available for free use under a Creative Commons Attribution-ShareAlike 2.5 License. The notebook can be read by CDF Player if you cannot make the embedded versions in this post work.

I have written about visible algebra in previous posts (see References). My ideas about the interface are constantly changing. Some new ideas are described here.

In the first place I want to make it clear that what I am showing in these posts is a simulation of a possible visual algebra system.  I have not constructed any part of the system; these posts only show something about what the interface will look like.  My practice in the last few years is to throw out ideas, not construct completed documents or programs.  (I am not saying how long I will continue to do this.)  All these posts, Mathematica programs and abstractmath.org are available to reuse under a Creative Commons license.

## Commutative and associative operations

Times and Plus are commutative and associative operations.  They are usually defined as binary operations.  A binary operation $*$ is said to be commutative if for all $x$ and $y$ in the underlying set of the operation, $x*y=y*x$, and it is associative if for all $x$,$y$ and $z$ in the underlying set of the operation, $(x*y)*z=x*(y*z)$.

It is far better to define a commutative and associative operation $*$ on some underlying set $S$ as an operation on any multiset of elements of $S$.  A multiset is like a set, in particular elements can be rearranged in any way, but it is not like a set in that elements can be repeated and a different number of repetitions of an element makes a different multiset.  So for any particular multiset, the number of repetitions of each element is fixed.  Thus $\{a,a,b,b,c\} = \{c,b,a,b,a\}$ but $\{a,a,b,b,c\}\neq\{c,b,a,b,c\}$. This means that the function (operation) Plus, for example, is defined on any multiset of numbers, and $\mathbf{Plus}\{a,a,b,b,c\}=\mathbf{Plus} \{c,b,a,b,a\}$ but $\mathbf{Plus}\{a,a,b,b,c\}$ might not be equal to $\mathbf{Plus} \{c,b,a,b,c\}$.

This way of defining (any) associative and commutative operation comes from the theory of monads.  An operation defined on all the multisets drawn from a particular set is necessarily commutative and associative if it satisfies some basic monad identities, the main one being it commutes with union of multisets (which is defined in the way you would expect, and if this irritates you, read the Wikipedia article on multisets.). You don't have to impose any conditions specifically referring to commutativity or associativity.  I expect to write further about monads in a later post.

The input process for a visible algebra system should allow the full strength of this fact. You can attach as many inputs as you want to Times or Plus and you can move them around.  For example, you can click on any input and move it to a different place in the following demo.

Other input notations might be suitable for different purposes.  The example below shows how the inputs can be placed randomly in two dimensions (but preserving multiplicity).  I experimented with making it show the variables slowly moving around inside the circle the way the fish do in that screensaver (which mesmerizes small children, by the way — never mind what it does to me), but I haven't yet made it work.

A visible algebra system might well allow directly input tables to be added up (or multiplied), like the one below. Spreadsheets have such an operation In particular, the spreadsheet operation does not insist that you apply it only as a binary operation to columns with two entries.  By far the most natural way to define addition of numbers is as an operation on multisets of numbers.

## Other operations

Operations that are associative but not commutative, such as matrix multiplication, can be defined the monad way as operations on finite lists (or tuples or vectors) of numbers.  The operation is automatically associative if you require it to preserve concatenation of lists and some other monad requirements.

Some binary operations are neither commutative nor associative.  Two such operations on numbers are Subtract and Power.  Such operations are truly binary operations; there is no obvious way to apply them to other structures.  They are only binary because the two inputs have different roles.  This suggests that the inputs be given names, as in the examples below.

Later, I will write more about simplifying trees, solving the max area problem for rectangles surmounted by semicircles, and other things concerning this system of doing algebra.

Send to Kindle

# Semantics of algebra I

## MathJax.Hub.Config({ jax: ["input/TeX","output/NativeMML"], extensions: ["tex2jax.js"], tex2jax: { inlineMath: [ ['$','$'] ], processEscapes: true } });

Note: This post uses MathJax. If you see mathematical formulas with dollar signs around them, or badly formatted formulas, try refreshing the screen. Sometimes you have to do it two or three times.

In the post Algebra is a difficult foreign language  I listed some of the difficulties of the syntax of the symbolic language of math (which includes high school algebra and precalculus).  The semantics causes difficulties as well.  Again I will list some examples without any attempt at completeness.

## The status of the symbolic language as a language

There is a sharp distinction between the symbolic language of math and mathematical English, which I have written about in The languages of math and in the Handbook of mathematical discourse. Other authors do not make this sharp distinction (see the list of references at the end of this post). The symbolic language occurs embedded in mathematical English and the embedding has its own semantics which may cause great difficulty for students.

The symbolic language of math can be described as a natural formal language. Pieces of it were invented by mathematicians and others over the course of the last several hundred years. Individual pieces (notation such as "$3x+1=2y$") can be given a strictly formal syntax, but the whole system is ambiguous, inconsistent, and context-sensitive.  When you get to the research level, it has many dialects: Research mathematicians in one field may not be able to read research articles in a very different field.

## Examples

I think the examples below will make these claims plausible.  This should be the subject of deep research.

### Superscripts and functions

• A superscript, as in $5^2$ or $x^3$, has a pretty standard meaning denoting a power, at least until you get to higher level stuff such as tensors.
• A function can be denoted by a letter, symbol, or string, and the notation $f(x)$ refers to the value of the function at input $x$.

For functions defined on numbers, it is common in precalculus and higher to write $f^2(x)$ to denoted $(f(x))^2=f(x)\,f(x)$.  Since the value of certain multiletter functions are commonly written without the parentheses (for example, $\sin\,x$), one writes $\sin^2x$ to mean $(\sin\,x)^2$.

The notation $f^n$ is also widely used to mean the $n$th iterate of $f$ (if it exists), so $f^3(x)=f(f(f(x)))$ and so on.  This leads naturally to writing $f^{-1}(x)$ for the inverse function of $f$; this is common notation whether the function $f$ is bijective or not (in which case $f^{-1}$ is set-valued).  Thus $\sin^{-1}x$ means $\arcsin\,x$.

It is notorious that words in mathematical English have different meanings in different texts.  This is an example in the symbolic language (and not just at the research level) of a systematic construction that can give expressions that have ambiguous meanings.

This phenomenon is an example of why I say the symbolic language of math is a natural formal language: I have described a natural extension of notation used with multiplication of values that has been extended to being used for the binary operation of composition.  And that leads to students thinking that $\sin^{-1}x$ means $\frac{1}{\sin\,x}$.

History can overtake notation, too: Mathematicians probably took to writing $\sin\,x$ instead of $\sin(x)$ because it saves writing.  That was not very misleading in the old days when mathematical variables were always single symbols.  But students see multiletter variable names all the time these days (in programming languages, Excel and elsewhere), so of course some of them think $\sin\,x$ means $\sin$ times $x$. People who do this are not idiots.

### Juxtaposition

Juxtaposition of two symbols means many different things.

• If $m$ and $n$ are numbers, $mn$ denotes the product of the two numbers.
• Multiplication is commutative, so $mn$ and $nm$ denote the same number, but they correspond to different calculations.
• If $M$ and $N$ are matrices, $MN$ denotes the matrix product of the two matrices.
• This is a binary operation but it is not the same operation denoted by juxtaposition of numbers. (In fact it involves both addition and multiplication of numbers.)
• Now $MN$ may not be the same matrix as $NM$.
• If $A$ and $B$ are points in a geometric drawing, $AB$ denotes the line segment from $A$ to $B$.
• This is a function of two variables denoting points whose value is a line segment.
• It is not what is usually called a binary operation, although as an opinionated category theorist I would call it a multisorted binary operation.
• It is commutative, but it doesn't make sense to ask if it is associative.

This phenomenon is called overloaded notation.

• In order to understand the meaning of the juxtaposition of symbols, you have to know the type of the variables.
• The surrounding text may tell you specifically the variables denote matrices or whatever. So this is an instance of context-sensitive semantics.
• Students tend to expect that they know what any formula means in isolation from the text.  It may make them very sad to discover that this doesn't work — once they believe it, which can take quite a while.
• In many cases the problem is alleviated by the use of convention.
• Matrices are usually denoted by capital letters, numbers by lower case letters.
• But points in geometry are usually denoted by capital letters too.  So you have to know that referring to a geometric diagram is significant to understanding the notation. This is an indirect form of context-sensitivity.  Did any teacher every point this out to students?  Does it appear anywhere in print?

The earlier example of $\sin^{-1}x$ is a case which is not context-sensitive.  Knowing the types of the variables won't help.  Of course, if the author explains which meaning is meant, that explanation is within the context of the book!  That is not a lot of help for grasshoppers like me that look back and forth at different parts of a math book instead of reading it straight through..

### Equations

Consider the expressions

1. $x^2-5x+4=0$
2. $x^2+y^2=1$
3. $x^2+2x+1=(x+1)^2$

They are assertions that two expressions have the same value. A strictly logical view of an equation containing variables is that it puts a constraint on the variables.  It is true of some numbers (or pairs of numbers) and false of others.  That is the defining property of an equation. Equation 1 requires that $x=1$ or $x=4$.  Equation 2 imposes a constraint which is satisfied by uncountably many pairs of real numbers, and is also not true of uncountably many pairs. But equation 3 puts no constraint on the variable.  It is true of every number $x$.

A strictly logical view of symbolic notation does math a disservice.  Here, the notion that an equation is by definition a symbolic statement that has a truth set and a falsity set may be correct but it is not the important thing about any particular equation. When we read and do math we have many different metaphors and images about a concept.  The definition of a kind of object is often in terms of things that may not be the most important things to know about it.  (One of the most important fact about groups is that it is an abstraction of symmetries, which the axioms don't mention at all.)

Equation 1. is something that would make most people set out to discover the truth set.  Equation 2. calls out for drawing its graph.  Equation 3. being an identity means that is useful in algebraic reasoning.  The images they call up are different and what you do with them is different.  The images and metaphors that cluster around a concept are an important part of the semantics of the symbolic language.

I expect to post separately about the semantics of variables and about the semantics of symbolic language embedded in mathematical English.

Send to Kindle

# Operation as metaphor in math

Operation: Is it just a name or is there a metaphor behind it?

A function of the form ${f:S\times S\rightarrow S}$ may be called a binary operation on ${S}$. The main point to notice is that it takes pairs of elements of ${S}$ to the same set ${S}$.

A binary operation is a special case of n-ary operation for any natural number ${n}$, which is a function of the form ${f:S^n\rightarrow S}$. A ${1}$-ary (unary) operation on ${S}$ is a function from a set to itself (such as the map that takes an element of a group to its inverse), and a ${0}$-ary (nullary) operation on ${S}$ is a constant.

It is useful at times to consider multisorted algebra, where a binary operation can be a function ${f:S_1\times S_2\rightarrow S_3}$ where the ${S_i}$ are possibly different sets. Then a unary operation is simply a function.

Calling a function a multisorted unary operation suggest a different way of thinking about it, but as far as I can tell the difference is only that the author is thinking of algebraic operations as examples. This does not seem to be a different metaphor the way “function as map” and “function as transformation” are different metaphors. Am I missing something?

In the 1960’s some mathematicians (not algebraists) were taken aback by the idea that addition of real numbers (for example) is a function. I observed this personally. I don’t think any mathematician would react this way today.

Send to Kindle