Magma, Semigroups, and Monoids, and Groups

Properties of binary operators over sets: Magma, Semigroups, and Monoids, and Groups

Magma

A magma is a set with a closed binary operator. That’s it.

Example

• let our set be all positive integers

• our binary operator be x ^ y

• Note that we don’t allow negative numbers because if y is negative, we get a fraction.

Clearly, the output will be in the space of integers.

Interestingly, this example is not commutative or associative. You can convince yourself of this by picking values for a, b, and c in the python code below.

assert a ** (b ** c) != (a ** b) ** c
assert a ** b != b ** a

But we don’t care. A magma is the one of the least restrictive kinds of algebraic structures. All that matters is that the binary operator is closed. Everything else is fair game.

Semigroup

A semigroup is a magma where the binary operator must be associative. In other words, a semigroup is a set with a binary operator that is closed and associative.

• Associative means (A * B) * C = A * (B * C)

Example

• Let our (infinite) set be the set of all possible non-empty strings from the traditional alphabet a,b,…,y,z. For example, “az”, “programmer”, “zero”, “asdfghjk”, “foo”, and “bar” are all in this set.

• Let our binary operator be the concatenation of strings. This is closed, because it produces another string in the set.

• Work out that concatenating “foo”, “bar”, “baz” in that order is associative

To demonstrate that concatenating "foo," "bar," and "baz" in that order is associative, we need to show that for any strings x, y, and z, the following equation holds:

(x + y) + z = x + (y + z)

In this case, the binary operator is string concatenation, which is known to be associative. Let's work through the proof:

1. Associativity of String Concatenation: String concatenation is an associative operation by definition. That is, for any strings a, b, and c:

   (a + b) + c = a + (b + c)

2. Specific Case with "foo," "bar," and "baz": We have:

   ("foo" + "bar") + "baz" = "foobar" + "baz" = "foobarbaz"

   "foo" + ("bar" + "baz") = "foo" + "barbaz" = "foobarbaz"

As you can see, both sides of the equation result in the same string "foobarbaz."

Exercise: Give an example of a magma and a semigroup. The magma must not be a semigroup. Don’t use the examples above.

1. Magma (Not a Semigroup):

   • Consider the set of integers ℤ (positive and negative whole numbers) as our set.

   • Define a binary operation * as follows: a * b = |a - b| (the absolute difference between a and b).

   Let's see why this is a magma but not a semigroup:

   • Magma Property: For any pair of integers a and b, the result of |a - b| is always a non-negative integer, which is still an integer. Therefore, the operation is closed within the set ℤ, satisfying the magma property.

   • However, it's not a semigroup because it doesn't satisfy the associativity property. Associativity requires that for all elements a, b, and c in the set, (a * b) * c = a * (b * c). In this case, consider a = 3, b = 2, and c = 1:

     • Left side: (3 * 2) * 1 = |3 - 2| * 1 = 1 * 1 = 1

     • Right side: 3 * (2 * 1) = 3 * |2 - 1| = 3 * 1 = 3

   Since 1 is not equal to 3, the associativity property is violated, making it a magma but not a semigroup.

2. Semigroup Example:

   • Consider the set of non-negative integers ℤ+ (positive whole numbers) as our set.

   • Define a binary operation ⋅ (multiplication) on this set.

   This forms a semigroup because multiplication is both closed (the product of two positive integers is still a positive integer) and associative (multiplication is associative for integers). Therefore, it satisfies the properties of a semigroup.

Monoid

Monoid extends Semigroup with the requirement that it has an "empty" (identity).

• For example, addition over positive integers without zero is a semigroup, but if you include zero, it becomes a monoid.

• An identity element means you do a binary operator with the identity element and another element a, you get a. In the example of addition 8 + 0 = 8, where 0 is the identity element.

• If your binary operator was multiplication, then the identity element would be 1, since multiplying by 1 gives the same number back.

Union and Intersection of Sets

• are binary operators

• both of these operators are associative

If we define our domain to be the set of all sets of integers, then the binary operators union and intersection are closed because their result is a set of integers.

Set union has an identity element in this domain: the empty set. Take the union of a set with the empty set and you get the original set, i.e. A ∪ {} = A.

Hence, the set of all sets of integers over union is a monoid.

Group

A group is a monoid where each element has an inverse.

Or to be explicit, it is a set with three properties

1. a closed and associative binary operator (a semigroup)

2. an identity element (a monoid)

3. every element has an inverse. That is, there exists an inverse element of the set such that the binary operator of an element and its inverse produces the identity element.