Heap (mathematics)

In abstract algebra, a semiheap is an algebraic structure consisting of a non-empty set H with a ternary operation denoted ${\displaystyle [x,y,z]\in H}$ that satisfies a modified associativity property:

${\displaystyle \forall \ a,b,c,d,e\in H\ \ \ \ [[a,b,c],d,e]=[a,[d,c,b],e]=[a,b,[c,d,e]].}$[1]

A biunitary element h of a semiheap satisfies [h,h,k] = k = [k,h,h] for every k in H.[1]^:75,6

A heap is a semiheap in which every element is biunitary.[1]^:80

The term heap is derived from груда, Russian for "heap", "pile", or "stack". Anton Sushkevich used the term in his Theory of Generalized Groups (1937) which influenced Viktor Wagner, promulgator of semiheaps, heaps, and generalized heaps.[1]^:11 Груда contrasts with группа (group) which was taken into Russian by transliteration. Indeed, a heap has been called a groud in English text.[2])

Examples

Two element heap

Turn ${\displaystyle H=\{a,b\}}$ into the cyclic group ${\displaystyle C_{2}}$, by defining ${\displaystyle a}$ the identity element, and ${\displaystyle bb=a}$. Then it produces the following heap:

${\displaystyle [a,a,a]=a,\,[a,a,b]=b,\,[b,a,a]=b,\,[b,a,b]=a,}$

${\displaystyle [a,b,a]=b,\,[a,b,b]=a,\,[b,b,a]=a,\,[b,b,b]=b.}$

Defining ${\displaystyle b}$ as the identity element and ${\displaystyle aa=b}$ would have given the same heap.

Heap of integers

If ${\displaystyle x,y,z}$ are integers, we can set ${\displaystyle [x,y,z]=x-y+z}$ to produce a heap. We can then choose any integer ${\displaystyle k}$ to be the identity of a new group on the set of integers, with the operation ${\displaystyle *}$

${\displaystyle x*y=x+y-k}$

and inverse

${\displaystyle x^{-1}=2k-x}$.

Heap of a groupoid with two objects

One may generalize the notion of the heap of a group to the case of a groupoid which has two objects A and B when viewed as a category. The elements of the heap may be identified with the morphisms from A to B, such that three morphisms x, y, z define a heap operation according to:

${\displaystyle [x,y,z]=xy^{-1}z.}$

This reduces to the heap of a group if a particular morphism between the two objects is chosen as the identity. This intuitively relates the description of isomorphisms between two objects as a heap and the description of isomorphisms between multiple objects as a groupoid.

Heterogeneous relations

Let A and B be different sets and ${\displaystyle {\mathcal {B}}(A,B)}$ the collection of heterogeneous relations between them. For ${\displaystyle p,\ q,\ r\in {\mathcal {B}}(A,B)}$ define the ternary operator ${\displaystyle [p,\ q,\ r]\ =\ pq^{T}r}$ where q^T is the converse relation of q. The result of this composition is also in ${\displaystyle {\mathcal {B}}(A,B)}$ so a mathematical structure has been formed by the ternary operation.[3] Viktor Wagner was motivated to form this heap by his study of transition maps in an atlas which are partial functions.[4] Thus a heap is more than a tweak of a group: it is a general concept including a group as a trivial case.

Theorems

Theorem: A semiheap with a biunitary element e may be considered an involuted semigroup with operation give by ab = [a, e, b] and involution by a^–1 = [e, a, e].[1]^:76

Theorem: Every semiheap may be embedded in an involuted semigroup.[1]^:78

As in the study of semigroups, the structure of semiheaps is described in terms of ideals with an "i-simple semiheap" being one with no proper ideals. Mustafaeva translated the Green's relations of semigroup theory to semiheaps and defined a ρ class to be those elements generating the same principle two-sided ideal. He then proved that no i-simple semiheap can have more than two ρ classes.[5]

He also described regularity classes of a semiheap S:

${\displaystyle D(m,n)\ =\ \{a:\exists x\in S\ \ a\ =\ a^{n}xa^{m}\}}$ where n and m have the same parity and the ternary operation of the semiheap applies at the left of a string from S.

He proves that S can have at most 5 regularity classes. Mustafaev calls an ideal B "isolated" when ${\displaystyle a^{n}\in B\implies a\in B.}$ He then proves that when S = D(2,2), then every ideal is isolated and conversely.[6]

Studying the semiheap Z(A, B) of heterogeneous relations between sets A and B, in 1974 K. A. Zareckii followed Mustafaev's lead to describe ideal equivalence, regularity classes, and ideal factors of a semiheap.[7]

Generalizations and related concepts

• A pseudoheap or pseudogroud satisfies the partial para-associative condition[4]

${\displaystyle [[a,b,c],d,e]=[a,b,[c,d,e]].}$

• A Malcev operation satisfies the identity law but not necessarily the para-associative law,[8] that is, a ternary operation ${\displaystyle f}$ on a set ${\displaystyle X}$ satisfying the identity ${\displaystyle f(x,x,y)=f(y,x,x)=y}$.
• A semiheap or semigroud is required to satisfy only the para-associative law but need not obey the identity law.[9]

An example of a semigroud that is not in general a groud is given by M a ring of matrices of fixed size with

${\displaystyle [x,y,z]=x\cdot y^{\mathrm {T} }\cdot z}$

where • denotes matrix multiplication and T denotes matrix transpose.[9]

• An idempotent semiheap is a semiheap where ${\displaystyle [a,a,a]=a}$ for all a.
• A generalised heap or generalised groud is an idempotent semiheap where

${\displaystyle [a,a,[b,b,x]]=[b,b,[a,a,x]]}$ and ${\displaystyle [[x,a,a],b,b]=[[x,b,b],a,a]}$ for all a and b.

A semigroud is a generalised groud if the relation → defined by

${\displaystyle a\rightarrow b\Leftrightarrow [a,b,a]=a}$

is reflexive (idempotence) and anti-symmetric. In a generalised groud, → is an order relation.[10]

Notes

1. C.D. Hollings & M.V. Lawson (2017) Wagner's Theory of Generalised Heaps, Springer books ISBN 978-3-319-63620-7 MR3729305
2. Schein (1979) pp.101–102: footnote (o)
3. Christopher Hollings (2014) Mathematics across the Iron Curtain: a history of the algebraic theory of semigroups, pages 264,5, History of Mathematics 41, American Mathematical Society ISBN 978-1-4704-1493-1
4. Vagner (1968)
5. L. G. Mustafaev (1966) "Ideal equivalences of semiheaps" MR0202892
6. L. G. Mustafaev (1965) "Regularity classes of semiheaps" MR0209386
7. K. A. Zareckii (1974) "Semiheaps of binary relations" MR0364526
8. Borceux, Francis; Bourn, Dominique (2004). Mal'cev, Protomodular, Homological and Semi-Abelian Categories. Springer Science & Business Media. ISBN 978-1-4020-1961-6.
9. Moldavs'ka, Z. Ja. "Linear semiheaps". Dopovidi Ahad. Nauk Ukrain. RSR Ser. A. 1971: 888–890, 957. MR 0297918.
10. Schein (1979) p.104

References

• Anton Sushkevich (1929) "On a generalization of the associative law", Transactions of the American Mathematical Society 31(1): 204–14 doi:10.1090/S0002-9947-1929-1501476-0 MR1501476
• Schein, Boris (1979). "Inverse semigroups and generalised grouds". In A.F. Lavrik (ed.). Twelve papers in logic and algebra. Amer. Math. Soc. Transl. 113. American Mathematical Society. pp. 89–182. ISBN 0-8218-3063-5.
• Vagner, V. V. (1968). "On the algebraic theory of coordinate atlases, II". Trudy Sem. Vektor. Tenzor. Anal. (in Russian). 14: 229–281. MR 0253970.

External links

• Mal'cev variety in nLab