| Algebraic structures |
|---|
Inabstract algebra, amagma,binar,[1] or, rarely,groupoid is a basic kind ofalgebraic structure. Specifically, a magma consists of aset equipped with a singlebinary operation that must beclosed by definition. No other properties are imposed.
The termgroupoid was introduced in 1927 byHeinrich Brandt describing hisBrandt groupoid. The term was then appropriated by B. A. Hausmann andØystein Ore (1937)[2] in the sense (of a set with a binary operation) used in this article. In a couple of reviews of subsequent papers inZentralblatt, Brandt strongly disagreed with this overloading of terminology. The Brandt groupoid is agroupoid in the sense used in category theory, but not in the sense used by Hausmann and Ore. Nevertheless, influential books in semigroup theory, includingClifford andPreston (1961) andHowie (1995) use groupoid in the sense of Hausmann and Ore. Hollings (2014) writes that the termgroupoid is "perhaps most often used in modern mathematics" in the sense given to it in category theory.[3]
According to Bergman and Hausknecht (1996): "There is no generally accepted word for a set with a not necessarily associative binary operation. The wordgroupoid is used by many universal algebraists, but workers in category theory and related areas object strongly to this usage because they use the same word to mean 'category in which all morphisms are invertible'. The termmagma was used bySerre [Lie Algebras and Lie Groups, 1965]."[4] It also appears inBourbaki'sÉléments de mathématique, Algèbre, chapitres 1 à 3, 1970.[5]
A magma is asetM matched with anoperation • that sends any twoelementsa,b ∈M to another element,a •b ∈M. The symbol • is a general placeholder for a properly defined operation. To qualify as a magma, the set and operation(M, •) must satisfy the following requirement (known as themagma orclosure property):
And in mathematical notation:
If • is instead apartial operation, then(M, •) is called apartial magma[6] or, more often, apartial groupoid.[6][7]
Amorphism of magmas is a functionf :M →N that maps magma(M, •) to magma(N, ∗) that preserves the binary operation:
For example, withM equal to thepositive real numbers and • as thegeometric mean,N equal to the real number line, and ∗ as thearithmetic mean, alogarithmf is a morphism of the magma (M, •) to (N, ∗).
Note that these commutative magmas are not associative; nor do they have anidentity element. This morphism of magmas has been used ineconomics since 1863 whenW. Stanley Jevons calculated the rate ofinflation in 39 commodities in England in hisA Serious Fall in the Value of Gold Ascertained, page 7.
The magma operation may be applied repeatedly, and in the general, non-associative case, the order matters, which is notated with parentheses. Also, the operation • is often omitted and notated by juxtaposition:
A shorthand is often used to reduce the number of parentheses, in which the innermost operations and pairs of parentheses are omitted, being replaced just with juxtaposition:xy •z ≡ (x •y) •z. For example, the above is abbreviated to the following expression, still containing parentheses:
A way to avoid completely the use of parentheses isprefix notation, in which the same expression would be written••a•bcd. Another way, familiar to programmers, ispostfix notation (reverse Polish notation), in which the same expression would be writtenabc••d•, in which the order of execution is simply left-to-right (nocurrying).
The set of all possiblestrings consisting of symbols denoting elements of the magma, and sets of balanced parentheses is called theDyck language. The total number of different ways of writingn applications of the magma operator is given by theCatalan numberCn. Thus, for example,C2 = 2, which is just the statement that(ab)c anda(bc) are the only two ways of pairing three elements of a magma with two operations. Less trivially,C3 = 5:((ab)c)d,(a(bc))d,(ab)(cd),a((bc)d), anda(b(cd)).
There arenn2 magmas withn elements, so there are 1, 1, 16, 19683,4294967296, ... (sequenceA002489 in theOEIS) magmas with 0, 1, 2, 3, 4, ... elements. The corresponding numbers of non-isomorphic magmas are 1, 1, 10, 3330,178981952, ... (sequenceA001329 in theOEIS) and the numbers of simultaneously non-isomorphic and non-antiisomorphic magmas are 1, 1, 7, 1734,89521056, ... (sequenceA001424 in theOEIS).[8]
Afree magmaMX on a setX is the "most general possible" magma generated byX (i.e., there are no relations or axioms imposed on the generators; seefree object). The binary operation onMX is formed by wrapping each of the two operands in parentheses and juxtaposing them in the same order. For example:
MX can be described as the set of non-associative words onX with parentheses retained.[9]
It can also be viewed, in terms familiar incomputer science, as the magma of fullbinary trees with leaves labelled by elements ofX. The operation is that of joining trees at the root.
A free magma has theuniversal property such that iff :X →N is a function fromX to any magmaN, then there is a unique extension off to a morphism of magmasf′
Magmas are not often studied as such; instead there are several different kinds of magma, depending on what axioms the operation is required to satisfy. Commonly studied types of magma include:
Note that each of divisibility and invertibility imply thecancellation property.
| Total | Associative | Identity | Divisible | Commutative | |
|---|---|---|---|---|---|
| Partial magma | Unneeded | Unneeded | Unneeded | Unneeded | Unneeded |
| Semigroupoid | Unneeded | Required | Unneeded | Unneeded | Unneeded |
| Small category | Unneeded | Required | Required | Unneeded | Unneeded |
| Groupoid | Unneeded | Required | Required | Required | Unneeded |
| Commutativegroupoid | Unneeded | Required | Required | Required | Required |
| Magma | Required | Unneeded | Unneeded | Unneeded | Unneeded |
| Commutativemagma | Required | Unneeded | Unneeded | Unneeded | Required |
| Quasigroup | Required | Unneeded | Unneeded | Required | Unneeded |
| Commutativequasigroup | Required | Unneeded | Unneeded | Required | Required |
| Unital magma | Required | Unneeded | Required | Unneeded | Unneeded |
| Commutativeunital magma | Required | Unneeded | Required | Unneeded | Required |
| Loop | Required | Unneeded | Required | Required | Unneeded |
| Commutativeloop | Required | Unneeded | Required | Required | Required |
| Semigroup | Required | Required | Unneeded | Unneeded | Unneeded |
| Commutativesemigroup | Required | Required | Unneeded | Unneeded | Required |
| Associativequasigroup | Required | Required | Unneeded | Required | Unneeded |
| Commutative-and-associativequasigroup | Required | Required | Unneeded | Required | Required |
| Monoid | Required | Required | Required | Unneeded | Unneeded |
| Commutative monoid | Required | Required | Required | Unneeded | Required |
| Group | Required | Required | Required | Required | Unneeded |
| Abelian group | Required | Required | Required | Required | Required |
A magma(S, •), withx,y,u,z ∈S, is called
| Idempotence | Commutative property | Associative property | Cancellation property | OEIS sequence (labeled) | OEIS sequence (isomorphism classes) |
|---|---|---|---|---|---|
| Unneeded | Unneeded | Unneeded | Unneeded | A002489 | A001329 |
| Required | Unneeded | Unneeded | Unneeded | A090588 | A030247 |
| Unneeded | Required | Unneeded | Unneeded | A023813 | A001425 |
| Unneeded | Unneeded | Required | Unneeded | A023814 | A001423 |
| Unneeded | Unneeded | Unneeded | Required | A002860 add a(0)=1 | A057991 |
| Required | Required | Unneeded | Unneeded | A076113 | A030257 |
| Required | Unneeded | Required | Unneeded | ||
| Required | Unneeded | Unneeded | Required | ||
| Unneeded | Required | Required | Unneeded | A023815 | A001426 |
| Unneeded | Required | Unneeded | Required | A057992 | |
| Unneeded | Unneeded | Required | Required | A034383 add a(0)=1 | A000001 with a(0)=1 instead of 0 |
| Required | Required | Required | Unneeded | ||
| Required | Required | Unneeded | Required | a(n)=1 for n=0 and all odd n, a(n)=0 for all even n≥2 | |
| Required | Unneeded | Required | Required | a(0)=a(1)=1, a(n)=0 for all n≥2 | a(0)=a(1)=1, a(n)=0 for all n≥2 |
| Unneeded | Required | Required | Required | A034382 add a(0)=1 | A000688 add a(0)=1 |
| Required | Required | Required | Required | a(0)=a(1)=1, a(n)=0 for all n≥2 | a(0)=a(1)=1, a(n)=0 for all n≥2 |
The category of magmas, denotedMag, is thecategory whose objects are magmas and whosemorphisms aremagma homomorphisms. The categoryMag hasdirect products, and there is aninclusion functor:Set → Med ↪ Mag as trivial magmas, withoperations given byprojectionx T y =y .
An important property is that aninjectiveendomorphism can be extended to anautomorphism of a magmaextension, just thecolimit of the (constant sequence of the)endomorphism.
Because thesingleton({*}, *) is theterminal object ofMag, and becauseMag isalgebraic,Mag is pointed andcomplete.[12]
