Semigroup: one associative operation, and nothing else promised¶

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

One line: A semigroup is a set with one operation that can be chained without brackets, and that is all; integers under max, positive integers under +, and strings under concatenation are semigroups, and subtraction is the standard non-example.

Laws required¶

associative, of the four on the parent page.

What it is, and the examples¶

A semigroup is a set with a binary operation that is associative: (a · b) · c = a · (b · c), so a chain a · b · c · d has one value whatever the brackets. No identity is promised and no inverses. The name says "half a group": the law that lets you write a chain, without the laws that let you solve an equation in it.

Three examples, checked in the program: the integers under max, where the chain max(a, b, c) is the largest of the three and there is no identity among the integers (every n has a larger one, so nothing is "below" all); the positive integers under +, associative with no identity, since 0 is not positive; and nonempty strings under concatenation, which is associative and not commutative, since "ab" is not "ba". The non-example is subtraction: (8 − 5) − 2 = 1 but 8 − (5 − 2) = 5, so ℤ under − is not a semigroup and a chain of subtractions must be bracketed.

Why the word matters: a semigroup is exactly the structure where a fold over a list is well defined without an order of evaluation, which is why map-reduce frameworks ask the combining function to be associative and nothing else, and why "monoid" is asked for only when an empty list must have a value.

What the program prints¶

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

LAWS REQUIRED: associative
   integers under max
     associative: True
     identity:    True   it is -3
     inverses:    False   none for -2, -1, 0
     commutative: True
   positive integers 1..6 under +
     associative: True
     identity:    False   none in the sample
     inverses:    False
     commutative: True
   nonempty strings under concatenation (sample)
     associative: True
     identity:    False   none in the sample
     inverses:    False
     commutative: False   fails at 'a', 'b'
   integers under − (the non-example)
     associative: False   fails at -3, -3, -3
     identity:    False   none in the sample
     inverses:    False
     commutative: False   fails at -3, -2
   max and + on positives are semigroups without identity; strings are a semigroup
   that is not commutative; subtraction is not a semigroup at all.

Po polsku, w skrócie¶

Półgrupa to zbiór z jednym działaniem łącznym: (a · b) · c = a · (b · c), więc łańcuch a · b · c ma jedną wartość bez nawiasów. Nic więcej nie jest obiecane: ani element neutralny, ani odwrotności. Przykłady: liczby całkowite z max, dodatnie liczby całkowite z +, napisy ze sklejaniem; odejmowanie nie jest łączne, więc ℤ z − półgrupą nie jest. Półgrupa to dokładnie to, czego potrzebuje fold po liście bez ustalonej kolejności.

Auf Deutsch: Stichwörter¶

Halbgruppe: eine assoziative Verknüpfung und sonst nichts versprochen.

Stichwörter: Halbgruppe, Assoziativgesetz, Verkettung, Maximum.