Monoid: associative, with an identity element¶

Level: 101 · one row of the table on the laws of an operation, on its own page

One line: A monoid is a semigroup with a do-nothing element: ℕ under × with 1, ℕ under gcd with 0, strings under concatenation with the empty string, sets under ∪ with ∅; it is the structure in which an empty chain has a value.

Laws required¶

associative, identity, of the four on the parent page.

What it is, and the examples¶

A monoid is a set with an associative operation and an identity, an element e with e · x = x = x · e for every x. Simovici and Djeraba's Definition 1.141 writes it as an algebra of type (0, 2): one zero-ary operation, the constant e, and one binary operation. The identity is unique, since if e and e′ both are identities then e = e · e′ = e′.

The examples in the program: ℕ under × with identity 1; ℕ under gcd with identity 0, since gcd(0, n) = n, the example Simovici and Djeraba give and prove associative; strings under concatenation with the empty string, the monoid every programming language has; the subsets of a set under ∪ with ∅ and under ∩ with U, which are the identity laws of set algebra; and ℕ under + with 0. The non-example is the positive integers under +, a semigroup that is not a monoid because 0 is missing.

What the identity buys is a value for the empty chain: the sum of no numbers is 0, the product of no numbers is 1, the concatenation of no strings is "", the union of no sets is ∅. That is why sum([]) is 0, why math.prod([]) is 1, and why a fold needs an initial value exactly when the list may be empty.

What the program prints¶

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

LAWS REQUIRED: associative, identity
   ℕ under ×
     associative: True
     identity:    True   it is 1
     inverses:    False   none for 0, 2, 3
     commutative: True
   ℕ under gcd
     associative: True
     identity:    True   it is 0
     inverses:    False   none for 1, 2, 3
     commutative: True
   strings under concatenation (sample)
     associative: True
     identity:    True   it is ''
     inverses:    False   none for 'a', 'b', 'ab'
     commutative: False   fails at 'a', 'b'
   subsets of {1, 2} under ∪
     associative: True
     identity:    True   it is ∅
     inverses:    False   none for {1}, {2}, {1, 2}
     commutative: True
   positive integers 1..6 under + (the non-example)
     associative: True
     identity:    False   none in the sample
     inverses:    False
     commutative: True
   each monoid has exactly one identity, and it is the value of an empty chain:
   sum([]) = 0, math.prod([]) = 1, ''.join([]) = ''

Po polsku, w skrócie¶

Monoid to półgrupa z elementem neutralnym e, takim że e · x = x = x · e. Przykłady: ℕ z mnożeniem i 1, ℕ z gcd i 0 (bo gcd(0, n) = n), napisy ze sklejaniem i pustym napisem, podzbiory z ∪ i ∅. Element neutralny daje wartość pustemu łańcuchowi: suma niczego to 0, iloczyn niczego to 1, sum([]) to 0. Dodatnie liczby całkowite z + to półgrupa, ale nie monoid, bo brakuje 0.

Auf Deutsch: Stichwörter¶

Monoid: assoziativ, mit neutralem Element, aber nicht jedes Element hat ein Inverses.

Stichwörter: Monoid, neutrales Element, Zeichenketten unter Verkettung, natürliche Zahlen unter Addition.