{"id":829,"date":"2018-12-12T04:46:20","date_gmt":"2018-12-12T04:46:20","guid":{"rendered":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/?p=829"},"modified":"2021-10-02T18:42:59","modified_gmt":"2021-10-02T17:42:59","slug":"united-monoids","status":"publish","type":"post","link":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/united-monoids\/","title":{"rendered":"United Monoids"},"content":{"rendered":"

In this blog post we will explore the consequences of postulating\u00a00\u00a0=\u00a01<\/span> in an algebraic structure with two binary operations\u00a0(S,\u00a0+,\u00a00)<\/span> and (S,\u00a0\u22c5,\u00a01)<\/span>. Such united monoids<\/em>\u00a0have a few interesting properties, which are not immediately obvious. For example, we will see that the axiom\u00a00\u00a0=\u00a01<\/span>\u00a0is equivalent to a seemingly less extravagant axiom ab\u00a0=\u00a0ab\u00a0+\u00a0a<\/span>, which will send us tumbling down the rabbit hole of algebraic graphs<\/a> and topology<\/a>.<\/p>\n

<\/p>\n

We start with a brief introduction to monoids, rings and lattices. Feel free to jump straight to the section “What if 0\u00a0=\u00a01?”<\/a>, where the fun starts.<\/p>\n

Monoids<\/h4>\n

A monoid<\/a>\u00a0(S,\u00a0\u2218,\u00a0e)<\/span>\u00a0is a way to express a basic form of composition in mathematics: any two elements a<\/span> and b<\/span> of the set S<\/span>\u00a0can be composed into a new element a\u00a0\u2218\u00a0b<\/span> of the same set S<\/span>, and furthermore there is a special element\u00a0e\u00a0\u2208\u00a0S<\/span>, which is the identity\u00a0element<\/em> of the composition, as expressed by the following identity axioms<\/em>:<\/p>\n

a \u2218 e = a
\ne \u2218 a = a<\/span><\/p>\n

In words, composing the identity\u00a0element with another element does not change the latter. The identity element is sometimes also called unit.<\/em><\/p>\n

As two familiar everyday examples, consider addition and multiplication over integer numbers<\/a>: (\u2124,\u00a0+,\u00a00)<\/span> and (\u2124,\u00a0\u22c5,\u00a01)<\/span>. Given any two integers, these operations produce another integer, e.g.\u00a02\u00a0+\u00a03\u00a0=\u00a05<\/span> and 2\u00a0\u22c5\u00a03\u00a0=\u00a06<\/span>, never leaving the underlying set of integers \u2124<\/span>; they also respect the identity axioms, i.e. both\u00a0a\u00a0+\u00a00 = 0\u00a0+\u00a0a\u00a0=\u00a0a<\/span> and a\u00a0\u22c5\u00a01 = 1\u00a0\u22c5\u00a0a\u00a0=\u00a0a<\/span>\u00a0hold for all integers\u00a0a<\/span>. Note: from now on we will often omit the multiplication operator and write simply ab<\/span> instead of a\u00a0\u22c5\u00a0b<\/span>, which is a usual convention.<\/p>\n

Another important monoid axiom is associativity:<\/em><\/p>\n

a \u2218 (b \u2218 c) = (a \u2218 b) \u2218 c<\/span><\/p>\n

It tells us that the order in which we group composition operations does not matter. This makes monoids convenient to work with and allows us to omit unnecessary parentheses. Addition and multiplication are associative: a\u00a0+\u00a0(b\u00a0+\u00a0c) = (a\u00a0+\u00a0b)\u00a0+\u00a0c<\/span> and a(bc)\u00a0=\u00a0(ab)c<\/span>.<\/p>\n

Monoids are interesting to study, because they appear everywhere in mathematics, programming and engineering. Another example comes from Boolean algebra<\/a>: the logical disjunction (OR) monoid\u00a0({0,1},\u00a0\u2228,\u00a00)<\/span> and the logical conjunction (AND) monoid\u00a0({0,1},\u00a0\u2227,\u00a01)<\/span>. Compared to numbers, in Boolean algebra the meanings of composition and identity elements are very different (e.g. number zero<\/em> vs logical false<\/em>), yet we can abstract from these differences, which allows us to reuse general results about monoids across various specific instances.<\/p>\n

In this blog post we will also come across commutative<\/em> and idempotent<\/em> monoids. In commutative monoids, the order of composition does not matter:<\/p>\n

a \u2218 b = b \u2218 a<\/span><\/p>\n

All four examples above (+,\u00a0\u22c5,\u00a0\u2228,\u00a0\u2227)<\/span> are commutative monoids. String concatenation<\/a> (S,\u00a0++,\u00a0“”)<\/span> is an example of a non-commutative monoid: indeed, “a”\u00a0++\u00a0“b”\u00a0=\u00a0“ab”<\/span> and\u00a0“b”\u00a0++\u00a0“a”\u00a0=\u00a0“ba”<\/span>\u00a0are different strings.<\/p>\n

Finally, in an idempotent monoid, composing an element with itself does not change it:<\/p>\n

a \u2218 a = a<\/span><\/p>\n

The disjunction \u2228\u00a0<\/span>and conjunction \u2227\u00a0<\/span>monoids are idempotent, whereas the addition +<\/span>, multiplication \u22c5\u00a0<\/span>and concatenation ++<\/span> monoids are not.<\/p>\n

A monoid which is both commutative and idempotent is a bounded semilattice<\/a>; both\u00a0disjunction\u00a0<\/span>and conjunction are bounded semilattices.<\/p>\n

Rings and lattices<\/h4>\n

As you might have noticed, monoids often come in pairs: addition and multiplication (+,\u00a0\u22c5)<\/span>, disjunction and conjunction (\u2228,\u00a0\u2227)<\/span>, set union and intersection (\u22c3,\u00a0\u22c2)<\/span>, parallel and sequential composition (||,\u00a0;<\/i>)\u00a0etc.<\/span><\/span>\u00a0I’m sure you can list a few more examples of such pairs. Two common ways in which such monoid pairs can be formed are called rings<\/em> and lattices<\/em>.<\/p>\n

A ring<\/a>, or more generally a semiring<\/a>, (S,\u00a0+,\u00a00,\u00a0\u22c5,\u00a01) comprises an\u00a0additive<\/em> monoid (S,\u00a0+,\u00a00)<\/span> and a multiplicative<\/em> monoid (S,\u00a0\u22c5,\u00a01)<\/span>, such that: they both operate on the same set S<\/span>, the additive monoid is commutative, and the multiplicative monoid\u00a0distributes<\/em> over the additive one:<\/span><\/span><\/p>\n

a(b + c) = ab + ac
\n(a + b)c = ac + bc<\/span><\/p>\n

Distributivity is very convenient and allows us to open parentheses, and (if applied in reverse) to factor out a common term of two expressions. Furthermore, ring-like algebraic structures require that\u00a00<\/span>\u00a0annihilates<\/em> all elements under multiplication:<\/p>\n

a\u00a0\u22c5 0 = 0
\n0\u00a0\u22c5 a = 0<\/span><\/p>\n

The most basic and widely known ring is that of integer numbers with addition and multiplication: we use this pair of monoids every day, with no fuss about the underlying theory. Various lesser known\u00a0tropical<\/a>\u00a0and star semirings<\/a>\u00a0are a great tool in optimisation on graphs\u00a0— read this cool functional pearl<\/a>\u00a0by\u00a0Stephen Dolan if you want to learn more.<\/p>\n

A bounded lattice<\/a> (S,\u00a0\u2228,\u00a00,\u00a0\u2227,\u00a01)\u00a0also comprises two monoids, which are called join<\/em>\u00a0(S,\u00a0\u2228,\u00a00)<\/span> and meet<\/em>\u00a0(S,\u00a0\u2227,\u00a01).<\/span>\u00a0They operate on the same set S<\/span>, are required to be commutative and idempotent, and satisfy the following absorption<\/em> axioms:<\/span><\/span><\/p>\n

a\u00a0\u2227\u00a0(a \u2228 b) = a
\na \u2228\u00a0(a \u2227 b) = a
\n<\/span><\/p>\n

Like rings, lattices show up very frequently in different application areas. Most basic examples include Boolean algebra\u00a0({0,1},\u00a0\u2228,\u00a00,\u00a0\u2227,\u00a01),\u00a0the power set<\/a> (2S<\/sup>,\u00a0\u22c3,\u00a0\u00d8,\u00a0\u22c2,\u00a0S), as well as integer numbers with negative and positive infinities and the operations max<\/span>\u00a0and min<\/span>:\u00a0(\u2124\u00b1\u221e<\/sup>,\u00a0max,\u00a0-\u221e,\u00a0min,\u00a0+\u221e)<\/span>. All of these lattices are distributive,<\/em> i.e.\u00a0\u2227<\/span> distributes over\u00a0\u2228<\/span> and vice versa.<\/span><\/span><\/span><\/span><\/p>\n

What if 0 = 1?<\/h4>\n

Now that the scene has been set and all characters introduced, let’s see what happens when the identity elements of the two monoids in a pair (S,\u00a0+,\u00a00)<\/span> and (S,\u00a0\u22c5,\u00a01)\u00a0<\/span>coincide, i.e. when 0\u00a0=\u00a01<\/span>.<\/p>\n

In a ring (S,\u00a0+,\u00a00,\u00a0\u22c5,\u00a01)<\/span>, this leads to devastating consequences. Not only 1<\/span> becomes equal to 0<\/span>, but all other elements of the ring become equal to 0<\/span> too, as demonstrated below:<\/p>\n\n\n\n\n\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0a\u00a0\u00a0\u00a0 <\/span><\/td>\n=<\/span><\/td>\na \u22c5 1<\/span><\/td>\n(identity of \u22c5<\/span>)<\/td>\n<\/tr>\n
<\/td>\n=<\/span><\/td>\na \u22c5 0<\/span><\/td>\n(we postulate 0 = 1<\/span>)<\/td>\n<\/tr>\n
<\/td>\n=<\/span><\/td>\n0<\/span><\/td>\n(annihilating 0<\/span>)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

The ring is annihilated<\/em> into a single point 0<\/span>.<\/p>\n

In a bounded lattice (S,\u00a0\u2228,\u00a00,\u00a0\u2227,\u00a01)<\/span>, postulating\u00a00\u00a0=\u00a01<\/span> leads to the same catastrophe, albeit in a different manner:<\/p>\n\n\n\n\n\n\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0a\u00a0\u00a0\u00a0<\/span><\/td>\n=<\/span><\/td>\n1 \u2227 a<\/span><\/td>\n(identity of \u2227<\/span>)<\/td>\n<\/tr>\n
<\/td>\n=<\/span><\/td>\n1 \u2227 (0 \u2228 a)<\/span><\/td>\n(identity of \u2228<\/span>)<\/td>\n<\/tr>\n
<\/td>\n=<\/span><\/td>\n0 \u2227 (0 \u2228 a)<\/span><\/td>\n(we postulate 0 = 1<\/span>)<\/td>\n<\/tr>\n
<\/td>\n=<\/span><\/td>\n0<\/span><\/td>\n(absorption axiom)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

The lattice is absorbed<\/em> into a single point 0<\/span>.<\/p>\n

Postulating the axiom\u00a00\u00a0=\u00a01<\/span> has so far led to nothing but disappointment. Let’s find another way of pairing monoids, which does not involve the axioms of annihilation and absorption.<\/p>\n

United monoids<\/h4>\n

Consider two monoids\u00a0(S,\u00a0+,\u00a00)<\/span> and (S,\u00a0\u22c5,\u00a01)<\/span>, which operate on the same set S<\/span>, such that +<\/span> is commutative and\u00a0\u22c5<\/span> distributes over +<\/span>. We call these monoids united<\/strong><\/span> if\u00a00\u00a0=\u00a01<\/span>. To avoid confusion with rings and lattices, we will use e<\/span> to denote the identity element of both monoids:<\/p>\n

a + e = ae = ea = a<\/span><\/p>\n

We will call this the united identity axiom<\/em>. We’ll also refer to e<\/span> as empty<\/em>, the operation +<\/span> as overlay,<\/em> and the operation\u00a0\u22c5<\/span> as connect.<\/em><\/p>\n

What can we tell about united monoids? First of all, it is easy to prove that the monoid\u00a0(S,\u00a0+,\u00a0e)<\/span> is idempotent:<\/p>\n\n\n\n\n\n\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0a + a\u00a0\u00a0\u00a0<\/span><\/td>\n=<\/span><\/td>\nae + ae<\/span><\/td>\n(united identity)<\/td>\n<\/tr>\n
<\/td>\n=<\/span><\/td>\na(e + e)<\/span><\/td>\n(distributivity)<\/td>\n<\/tr>\n
<\/td>\n=<\/span><\/td>\nae<\/span><\/td>\n(united identity)<\/td>\n<\/tr>\n
<\/td>\n=<\/span><\/td>\na<\/span><\/td>\n(united identity)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Recall that this means that\u00a0(S,\u00a0+,\u00a0e)<\/span> is a bounded semilattice.<\/p>\n

The next consequence of the united identity axiom is a bit more unusual:<\/p>\n

ab = ab + a<\/span>
\nab = ab + b
\nab = ab + a + b<\/span><\/p>\n

We will refer to the above properties as\u00a0containment laws:<\/em> intuitively, when you connect\u00a0a<\/span> and b<\/span>, the constituent parts are contained in the result ab<\/span>. Let us prove containment:<\/p>\n\n\n\n\n\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ab + a\u00a0\u00a0\u00a0<\/span><\/td>\n=<\/span><\/td>\nab + ae<\/span><\/td>\n(united identity)<\/td>\n<\/tr>\n
<\/td>\n=<\/span><\/td>\na(b + e)<\/span><\/td>\n(distributivity)<\/td>\n<\/tr>\n
<\/td>\n=<\/span><\/td>\nab<\/span><\/td>\n(united identity)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

The two other laws are proved analogously (in fact, they are equivalent to each other).<\/p>\n

Surprisingly, the containment law\u00a0ab\u00a0=\u00a0ab\u00a0+\u00a0a<\/span> is equivalent to the united identity law\u00a00\u00a0=\u00a01<\/span>, i.e. the latter can be proved from the former:<\/p>\n\n\n\n\n\n\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a00\u00a0 \u00a0<\/span><\/td>\n=<\/span><\/td>\n1 \u22c5 0<\/span><\/td>\n(1<\/span> is identity of \u22c5<\/span>)<\/td>\n<\/tr>\n
<\/td>\n=<\/span><\/td>\n1 \u22c5 0 + 1<\/span><\/td>\n(containment)<\/td>\n<\/tr>\n
<\/td>\n=<\/span><\/td>\n0 + 1<\/span><\/td>\n(1<\/span> is identity of \u22c5<\/span>)<\/td>\n<\/tr>\n
<\/td>\n=<\/span><\/td>\n1<\/span><\/td>\n(0<\/span> is identity of +<\/span>)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

This means that united monoids can equivalently be defined as follows:<\/p>\n