The laws of an operation¶

Level: 101 · for anyone who has seen a + b = b + a written down as a rule

One line: Every book's list of rules is the same four laws — commutative, associative, identity, inverses — applied to its own set and its own operation; names like group and monoid only say which of the four hold, and the news in any new list is the law that is missing.

The same list, again¶

Serge Lang's Basic Mathematics opens its section on rules for addition with two boxed laws for the integers: a + b = b + a, and (a + b) + c = a + (b + c). Sheldon Axler's Linear Algebra Done Right defines a vector space (definition 1.20) with u + v = v + u, and (u + v) + w = u + (v + w). Two chapters later it lists associativity, an identity and distributive properties once more, this time for products of linear maps.

So it is true that every book repeats itself. The reason is that the list is short. An operation takes two members of a set and returns a member of the same set, and there are only four things that are usually worth asking about it:

Law	Says	For the integers under +
commutative	a · b = b · a	3 + 5 = 5 + 3
associative	(a · b) · c = a · (b · c)	(1 + 2) + 3 = 1 + (2 + 3)
identity	there is an e with a · e = e · a = a for every a	e = 0
inverses	every a has a b with a · b = b · a = e	the inverse of 3 is −3

The dot stands for whichever operation the book is about. Every time a book introduces a new set with a new operation, it has to say which of these four hold, and so it prints the list again. The program below writes the four checks once and runs them on ten different sets.

What the program prints¶

Verified output of laws_of_an_operation.py — regenerated by tools/run_examples.py, never hand-typed.

1. FOUR LAWS, ONE OPERATION
   commutative   a.b = b.a
   associative   (a.b).c = a.(b.c)
   identity      there is an e with a.e = e.a = a for every a
   inverses      every a has a b with a.b = b.a = e
   Every book's list of 'rules' is these four, for its own set and its own '.'.

2. TEN SETS, ONE CHECK
   set, operation                comm  assoc  ident   inv   the name for that combination
   integers, +                    yes    yes    yes   yes   commutative group
   vectors in R^2, +              yes    yes    yes   yes   commutative group
   integers, x                    yes    yes    yes    -    commutative monoid
   fractions except 0, x          yes    yes    yes   yes   commutative group
   fourth roots of unity, x       yes    yes    yes   yes   commutative group
   integers, -                     -      -      -     -    no name: not even associative
   integers, max                  yes    yes     -     -    commutative semigroup
   strings, concatenation          -     yes    yes    -    monoid
   invertible 2x2 matrices, x      -     yes    yes   yes   group
   floats, +                      yes     -     yes   yes   no name: not even associative
   The integers under + and the vectors under + fill the same row: the
   school book and the linear-algebra book are listing the same four laws.

3. THE MISSING LAW IS THE NEWS: A WITNESS FOR EVERY '-'
   integers, x
     no inverses:      nothing x 2 gives 1
   integers, -
     not commutative:  1 - 2 = -1
                       2 - 1 = 1
     not associative:  (1 - 1) - 1 = -1
                       1 - (1 - 1) = 1
     no identity:      1 - 0 = 1,  but 0 - 1 = -1
     no inverses:      with no identity there is nothing to get back to
   integers, max
     no identity:      see section 4
     no inverses:      with no identity there is nothing to get back to
   strings, concatenation
     not commutative:  'ab' + 'c' = 'abc'
                       'c' + 'ab' = 'cab'
     no inverses:      nothing + 'ab' gives ''
   invertible 2x2 matrices, x
     not commutative:  [[0, -1], [1, 0]] x [[1, 1], [0, 1]] = [[0, -1], [1, 1]]
                       [[1, 1], [0, 1]] x [[0, -1], [1, 0]] = [[1, -1], [1, 0]]
   floats, +
     not associative:  (0.1 + 0.2) + 0.3 = 0.6000000000000001
                       0.1 + (0.2 + 0.3) = 0.6

4. A SAMPLE CAN REFUTE A LAW, NOT PROVE ONE
   integers, max, on the samples [1, 2, 3, 0, -1, -2, -3]:
     members that act as an identity on every sample: [-3]
     but max(-3, -4) = -3, not -4
   An identity for max would have to be at most every integer, and no
   integer is. The smallest sample passed only because nothing smaller
   was tried. That is why every 'yes' above is a theorem about the
   whole set, and every '-' is a witness you can check by hand.

5. TWO OPERATIONS, AND THE LAW THAT LINKS THEM
   distributive  a x (b + c) = a x b + a x c,  and  (a + b) x c = a x c + b x c
   set            + comm. group  x assoc, ident  distrib  x comm  x inverses   name
   integers                 yes             yes      yes     yes           -   commutative ring
   fractions                yes             yes      yes     yes         yes   field
   2x2 matrices             yes             yes      yes       -           -   ring
   floats                     -               -        -                       none: not a ring
   The witnesses:
     integers: nothing x 2 gives 1
     2x2 matrices: [[0, -1], [1, 0]] x [[1, 0], [0, 0]] = [[0, 0], [1, 0]]
                   [[1, 0], [0, 0]] x [[0, -1], [1, 0]] = [[0, -1], [0, 0]]
     2x2 matrices: nothing x [[1, 0], [0, 0]] gives [[1, 0], [0, 1]]
     floats: + is not associative (section 3)
     floats: (0.1 x 0.1) x 0.3 = 0.0030000000000000005
             0.1 x (0.1 x 0.3) = 0.003
     floats: 0.1 x (0.1 + 0.3) = 0.04000000000000001
             0.1 x 0.1 + 0.1 x 0.3 = 0.04
   A field is two rows of section 2, a commutative group under + and
   another under x once 0 is set aside, joined by distributivity. That
   is the whole list of field axioms, and the F in 'a vector space over F'.

The names are only combinations¶

Section 2 names each row, and the names are nothing more than which boxes are ticked:

Laws that hold	Name	Row in section 2
associative	semigroup	integers under max
associative, identity	monoid	strings under concatenation
associative, identity, inverses	group	invertible 2 × 2 matrices under ×
any of those, plus commutative	commutative semigroup, monoid or group	integers under +

Each name has a page of its own, with the definition, examples and non-examples, and a program that checks the laws on finite samples.

A commutative group is also called an abelian group, after Niels Henrik Abel. An operation with no laws at all still has a name, a magma, and subtraction is one. The names matter because a theorem proved for every group is proved at once for every row that says group, which is the subject of the next lesson.

The first two rows are the point of this page. The integers under + and the vectors of ℝ² under + have exactly the same verdicts. Lang's list and Axler's list are the same list, applied to different sets.

The missing law is the news¶

Section 3 prints a witness for every dash: actual members of the set, and the actual answers that break the law. You can check each one by hand, and each one says something the full list could not:

Integers under ×: no inverses. Nothing times 2 gives 1, not among the integers. This is the reason fractions exist, and the row "fractions except 0, ×" has all four laws.
Integers under −: nothing at all. Subtraction is not commutative, not associative, and 0 is an identity on one side only, since 1 − 0 = 1 but 0 − 1 = −1. This is why algebra books rewrite a − b as a + (−b). Addition has all four laws, so the rewriting lets subtraction borrow them. Division is handled the same way: a ÷ b = a × b⁻¹.
Strings under concatenation: order matters, and nothing can be undone. 'ab' + 'c' is 'abc', and 'c' + 'ab' is 'cab'. No string appended to 'ab' gives the empty string back, because appending never shortens anything.
Invertible matrices under ×: order matters. The quarter turn [[0, −1], [1, 0]] times the shear [[1, 1], [0, 1]] is not the shear times the quarter turn. That is the one piece of news in Axler's list for products of linear maps: it gives associativity, identity and distributivity, and leaves out commutativity.
Floats under +: not associative. (0.1 + 0.2) + 0.3 and 0.1 + (0.2 + 0.3) differ in the last digit. Machine numbers explains why: each grouping rounds at a different step.

The row "fourth roots of unity, ×" is a group with only four members, 1, i, −1 and −i, written as pairs. Multiplying any two of them gives another of the four, and each has an inverse among them. Roots of unity finds the twelfth roots, which form a group of twelve in the same way.

A sample can refute a law, not prove one¶

A program can only try finitely many members, and section 4 shows what that costs. Among the samples −3 … 3, the member −3 acts as an identity for max: max(a, −3) = a for every sample a. It is not an identity for the integers, because max(−3, −4) = −3. An identity for max would have to be at most every integer, and no integer is.

So the two kinds of cell are not equally strong. Every dash comes with a witness, and one witness settles it. Every "yes" is a theorem about the whole set, proved in the book that defines it: the program only shows that none of its samples contradicts the theorem.

Two operations, and the law that links them¶

Numbers have two operations, and one more law ties them together:

a × (b + c) = a × b + a × c, and (a + b) × c = a × c + b × c

This is the distributive law, and section 5 adds it:

A ring is a commutative group under +, together with a × that is associative and has an identity, with distributivity linking the two. The integers are a commutative ring.
A field is a commutative ring in which every member except 0 has an inverse under ×. The fractions are a field, and so are the real numbers. Multiplication as pairs checks that the complex numbers are a field too.

A field, then, is two rows of section 2 joined by distributivity: a commutative group under +, and another commutative group under × once 0 is set aside. That is the whole list of field axioms, often printed as nine or eleven separate lines. It is also the F in Axler's definition, "a vector space over F".

The 2 × 2 matrices are a ring and not a field, for two separate reasons, and section 5 has a witness for each. Their product is not commutative. And [[1, 0], [0, 0]] is not zero but has no inverse: it flattens the whole plane onto a line, and no matrix can undo that. It is also a zero divisor, since [[1, 0], [0, 0]] × [[0, 0], [0, 1]] is the zero matrix, which is the failure multiplication can be undone is about. Floats are not even a ring: addition is not associative, multiplication is not either, and distributivity fails too.

How to read the next list¶

When a book prints the rules again, you do not have to read them again. Ask three questions:

Which set?
Which operation?
Which law is missing?

The third is the only news. For Lang's integers under +, nothing is missing, so the section confirms what you know. For linear maps under composition, commutativity is missing, and every surprise in the rest of that chapter comes from it.

Run it yourself¶

From the root of your clone of this repository:

python3 06_Algebraic_Structures/laws_of_an_operation/examples/laws_of_an_operation.py

Auf Deutsch: Stichwörter¶

Jede Liste von Rechenregeln ist dieselbe Speisekarte aus vier Gesetzen; Halbgruppe, Monoid, Gruppe und abelsche Gruppe sind die Auswahl daraus.

Stichwörter: Verknüpfung, Assoziativgesetz, neutrales Element, inverses Element, Kommutativgesetz, Halbgruppe, Monoid, Gruppe, abelsche Gruppe, Verknüpfungstafel.