Binary operations

If \({ A }\) is a set then a function from \({ A ^ 2 }\) to \({ A }\) is called a binary operation. Examples include

Functions are left total, so we can’t define subtraction or division as binary operations on the natural numbers. We can define subtraction as a binary operation on a larger set, like the set of integers, rationals or reals. We can’t define division as a binary operation on any of these sets, at least if we want the relation \({ ( x / y ) · y = x }\) to hold for all \({ x }\) and \({ y }\), because of the problems with division by zero.

The notation used for binary operations varies. Most of the operations above are usually written with an infix notation, like \({ x · y }\), \({ A ∪ B }\), or \({ f ∘ g }\). Maximum and minimum are usually written with functional notation, like \({ \max ( x , y ) }\). Arguably this should be \({ \max ( ( x , y ) ) }\) with one set of parentheses identifying function arguments and the other identifying an ordered pair, since this is a function on ordered pairs, but in reality no one uses that notation. The infix notation \({ x ∧ y }\) for maximum and \({ x ∨ y }\) for minimum is sometimes used. This is consistent with the notation for Boolean operators provided you accept that falsehood is greater than truth. Notation for concatenation is not completely standardised. Functional notation is used by some authors. Others use an infix notation, often with no actual symbol in between, like \({ v w }\) for the list consisting of the items of \({ v }\) followed by those of \({ w }\). I’ll use a mix of notations, but will mostly prefer functional notation when described properties of general binary operations and whatever notation is most commonly used for specific binary operators when they appear as examples.

A binary operation \({ f }\) on a set \({ A }\) is called associative if \[ f ( x , f ( y , z ) ) = f ( f ( x , y ) , z ) \] for all \({ x }\), \({ y }\) and \({ z }\) in \({ A }\). It is called commutative if \[ f ( x , y ) = f ( y , x ) \] for all \({ x }\) and \({ y }\) in \({ A }\).

We can apply the associativity property multiple times to show that, for example \[ f ( w , f ( x , f ( y , z ) ) ) = f ( f ( w , x ) , f ( y , z ) ) = f ( f ( f ( w , x ) , y ) , z ) . \] This is usually easier to follow with an infix notation. For example, the previous calculation applied to the union operator for sets is \[ A ∪ ( B ∪ ( C ∪ D ) ) = ( A ∪ B ) ∪ ( C ∪ D ) = ( ( A ∪ B ) ∪ C ) ∪ D . \]

The parentheses tell you in what order the union operator is to be applied but the equation essentially tells you that the order doesn’t matter. Or at least it tells you that the order doesn’t affect the final result. In a computational problem the order may have a very noticeable affect on the time or resources required. Matrix multiplication, for example, is associative, in the sense that if \({ L }\), \({ M }\) and \({ N }\) are matrices such that the \({ M }\) has as many rows as \({ L }\) has columns and as many columns as \({ N }\) has rows then \[ ( L M ) N = L ( M N ) . \] Without those conditions on the numbers of rows and columns the products are not defined. Suppose \({ L }\) is has \({ m }\) rows and \({ n }\) columns while \({ N }\) has \({ p }\) rows and \({ q }\) columns. The number of multiplications needed to compute \({ L M }\) is \({ m n p }\) and the number of further multiplications needed to compute \({ ( L M ) N }\) is \({ m p q }\), so the left hand side requires \({ m p ( n + q ) }\) multiplications. Similarly, number of multiplications needed to compute \({ M N }\) is \({ n p q }\) and the number of further multiplications needed to compute \({ L ( M N ) }\) is \({ m n q }\) so the total number for the right hand side is \({ ( m + p ) n q }\). These numbers might be very different. In the case of a square matrix followed by a column vector, thought of as a matrix with a single column, and then a row vector, thought of as a matrix with a single row, we would have \({ m = n = q }\) and \({ p = 1 }\) so the left hand side needs \({ 2 m ^ 2 }\) operations while the right hand side needs \({ m ^ 3 + m ^ 2 }\) operations. Quite a bit of computational linear algebra is devoted to figuring out the most efficient ways to apply associativity.

Of the examples above, \({ ⊃ }\) and \({ ∖ }\) are neither associative nor commutative. \({ ∘ }\) and concatenation are associative but not commutative. The remaining ones are all associative and commutative. It’s certainly possible to construct examples of operations which are commutative but not associative, but naturally occurring examples are somewhat rare. One is the nand operator, \({ ⊼ }\), from Boolean algebra, which we briefly considered in the context of the Nicod formal system.