Notes

Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations


Algebraic systems [and operator systems]

Operator systems can be viewed as algebraic systems of the kind studied in universal algebra (see page 1150). With a single two-argument operator (such as ·) what one has is in general known as a groupoid (though this term means something different in topology and category theory); with two such operators a ringoid. Given a particular algebraic system, it is sometimes possible—as we saw on page 773—to reduce the number of operators it involves. But the number of systems that have traditionally been studied in mathematics and that are known to require only one 2-argument operator are fairly limited. In addition to basic logic, semigroups and groups, there are essentially only the rather obscure examples of semilattices, with axioms {a · (b · c) == (a · b) · c, a · b == b · a, a · a == a}, central groupoids, with axioms {(b · a) · (a · c) == b}, and squags (quasigroup representations of Steiner triple systems), with axioms {a · b == b · a, a · a == a, a · (a · b) == b} or equivalently {a · ((b · (b · (((c · c) · d) · c))) · a) == d}. (Ordinary quasigroups are defined by {a · c == b, d · a == b} with c, d unique for given a, b—so that their table is a Latin square; their axioms can be set up with 3 operators as {a ∖\ (a · b) == b, a · b / b == a, a · (a ∖\ b) == b, (a / b) · b == a}.)

Pages 773 and 774 indicate that most axiom systems in mathematics involve operators with at most 2 arguments (there are exceptions in geometry). (Constants such as 1 or \[EmptySet] can be viewed as 0-argument operators.) One can nevertheless generalize say to polyadic groups, with 3-argument composition and analogs of associativity such as

(a · b · c) · d · e == a · (b · c · d) · e == a · b · (c · d · e)

Another example is the cellular automaton axiom system of page 794; see also page 886. (A perhaps important generalization is to have expressions that are arbitrary networks rather than just trees.)


From Stephen Wolfram: A New Kind of Science [citation]