nLab heap




A heap is an algebraic structure which is basically equivalent to a group when one forgets about which element is the unit. Similar notions are affine space, principal homogeneous space and so on. However, the notion of a heap has a directness and simplicity in the sense that it is formalized as an algebraic structure with only one ternary operation satisfying a short list of axioms. If we start with a group the ternary operation is defined via (a,b,c)ab 1c(a,b,c)\mapsto a b^{-1}c. We can interpret that operation as shifting aa by the (right) translation in the group which translates bb into cc. There is also a dual version, quantum heap.

Heaps in the sense of algebra should not be confused with heaps in the sense of theoretical computer science. There are also a number of synonyms for the term ‘heap’; below we consider ‘torsor’ in this light. In Russian one term for a heap is ‘груда’ (‘gruda’) meaning a heap of soil; this is a pun as it is parallel to the russian word ‘группа’ (‘gruppa’) meaning a group: forgetting the unit element is sort of creating an amorphous version. This term also appears in English as ‘groud’. In universal algebra the standard name is associative Malcev algebra (in various spellings, including Mal’cev, Mal’tsev and Maltsev), other names include herd.


A heap (H,t)(H,t) is a nonempty set HH equipped with a ternary operation t:H×H×HHt : H \times H \times H\to H satisfying the relations

t(b,b,c)=c=t(c,b,b) t(b,b,c) = c = t(c,b,b)
t(a,b,t(c,d,e))=t(t(a,b,c),d,e) t(a,b,t(c,d,e)) = t(t(a,b,c),d,e)

More generally, a ternary operation in some variety of algebras satisfying the first pair of equations is called a Mal'cev operation. A Mal’cev operation is called associative if it also satisfies the latter equation (i.e. it makes its domain into a heap).

A heap is abelian if it additionally satisfies the relation

t(a,b,c)=t(c,b,a) t(a,b,c) = t(c,b,a)

A heap homomorphism, of course, is a function that preserves the ternary operations. This defines a category HeapHeap of heaps.

The hom-sets of the full subcategory AbHeapAbHeap of abelian heaps inherit an abelian heap structure from the pointwise operation in the codomain: given f,g,h:HGf,g,h\colon H \to G, the function at G(f(a),g(a),h(a))a\mapsto t_G(f(a),g(a),h(a)) is again a heap homomorphism.

Automorphism group

As suggested above, if GG is a group and we define t(a,b,c)=ab 1ct(a,b,c) = a b^{-1} c, then GG becomes a heap. This construction defines a functor Prin:GrpHeapPrin:Grp\to Heap. In fact, up to isomorphism, all heaps arise in this way; to every heap is associated a group Aut(H)Aut(H) called its automorphism group, unique up to isomorphism. There are a number of ways to define Aut(H)Aut(H) from HH.

  1. If we choose an arbitrary element eHe\in H, then we can define a multiplication on HH by ab=t(a,e,b)a b = t(a,e,b). It is straightforward to verify that this defines a group structure on HH, whose underlying heap structure is the original one.

  2. We can define Aut(H)Aut(H) to be the set of pairs (a,b)H×H(a,b)\in H\times H, modulo the equivalence relation (a,b)(a,b)(a,b)\sim (a',b') iff t(a,a,b)=bt(a,a',b')=b. (We think of (a,b)(a,b) as representing a 1ba^{-1} b.) We then define multiplication by (c,d)(a,b)=(c,t(d,a,b))(c,d)(a,b) = (c,t(d,a,b)); the inverse of (the equivalence class of) (a,b)(a,b) is (the equivalence class of) (b,a)(b,a) and the identity element is (the equivalence class of) (a,a)(a,a) (for any aa).

  3. We can also define Aut(H)Aut(H) as an actual subgroup of the symmetric group of HH, analogously to Cayley's theorem? (see Wikipedia) for groups. We take the elements of Aut(H)Aut(H) to be set bijections of the form t(,a,b):HHt(-,a,b): H \rightarrow H where a,bHa,b \in H, with composition as the group operation. Note that

    t(,c,d) Aut(H)t(,a,b)=t(t(,c,d),a,b)=t(,c,t(d,a,b)), t(-,c,d) \cdot_{Aut(H)} t(-, a,b) = t(t(-,c,d),a,b) = t(-,c,t(d,a,b)),

    so Aut(H)Aut(H) is closed under this operation. The first axiom of a heap shows that Aut(H)Aut(H) contains the identity t(,x,x)t(-,x,x) for any xx), and the inverse of t(,a,b)t(\cdot,a,b) is t(,b,a)t(\cdot,b,a); thus Aut(H)Aut(H) is a subgroup of the symmetric group of HH.

Note that in both the second and third constructions, the elements of Aut(H)Aut(H) are determined by pairs of elements of HH, modulo some equivalence relation. The following theorem shows that the two equivalence relations are the same.


The following are equivalent

  1. bijections t(,a,b)t(\cdot,a,b) and t(,a,b)t(\cdot,a',b') are the same maps,

  2. t(a,a,b)=bt(a,a',b') = b,

  3. t(b,b,a)=at(b,b',a') = a.


(ii) follows from (i) and t(a,a,b)=bt(a,a,b) = b.

(iii) follows from (ii) by applying t(,b,a)t(\cdot,b',a') on the right. Similarly (ii) follows from (iii).

(i) follows from (ii) by the calculation:

t(x,a,b)=t(t(x,a,a),a,b)=t(x,a,t(a,a,b))=t(x,a,b). t(x,a',b') = t(t(x,a,a),a',b')= t(x,a,t(a,a',b')) = t(x,a,b).

The composition laws are also easily seen to agree, so the second two constructions of Aut(H)Aut(H) are canonically isomorphic. To compare them to the first construction, observe that for a fixed eHe\in H, any equivalence class contains a unique pair of the form (e,a)(e,a). (If (b,c)(b,c) is in the equivalence class, then aa is determined by a=t(e,b,c)a = t(e,b,c).) This sets up a bijection between the first two constructions, which we can easily show is an isomorphism.

The second two constructions are clearly functorial, so we have a functor Aut:HeapGrpAut:Heap\to Grp. Note that we have Aut(Prin(G))GAut(Prin(G))\cong G for any group GG, and Prin(Aut(H))HPrin(Aut(H))\cong H for any heap HH, but while the first isomorphism is natural, the second is not. In particular, the categories HeapHeap and GrpGrp are not equivalent.

Heaps and torsors

Note that Aut(H)Aut(H) comes equipped with a canonical action on HH (this is most clear from the third definition). This action is transitive (by t(a,a,b)=bt(a,a,b) = b) and free (if t(a,b,c)=at(a,b,c) = a then by the previous statement t(x,b,c)=xt(x,b,c) = x for each xx, and in particular t(b,b,c)=bt(b,b,c) = b and also t(b,b,c)=ct(b,b,c) = c). Therefore, HH is an Aut(H)Aut(H)-torsor (over a point). Conversely, a torsor HH over any group GG can be made into a heap, by defining t(a,b,c)=gct(a,b,c) = g\cdot c, where gGg\in G is the unique group element such that gb=ag\cdot b = a.

In fact, the category HeapHeap is equivalent to the following category TorsTors: its objects are pairs (G,H)(G,H) consisting of a group GG and a GG-torsor HH, and its morphisms are pairs (ϕ,f):(G,H)(G,H)(\phi,f):(G,H)\to (G',H') consisting of a group homomorphism ϕ:GG\phi:G\to G' and a ϕ\phi-equivariant map f:HHf:H\to H'.

The empty heap

If we wish HeapHeap to be an algebraic category, then we must remove the clause that the underlying set of a heap must be nonempty (see also at pseudo-torsor). Then the empty set becomes a heap in a unique way.

However, in this case, the various theorems relating heaps to groups above all break down. For this reason, one usually requires a heap to be inhabited.

On the other hand, we could generalize the notion of group to allow for an empty group. This even remains a purely algebraic notion: we can define a group as an inhabited invertible semigroup (S,,() 1)(S,\cdot,(-)^{-1}) or an inhabited associative quasigroup. Then any invertible semigroup or associative quasigroup is a possibly-empty-heap, and every possibly-empty-heap arises in this way from its automorphism invertible semigroup or automorphism associative quasigroup (defined by either method (2) or (3)); the category of possibly-empty-heaps is equivalent to the category of invertible semigroups equipped with torsors over the point, and the category of associative quasigroups equipped with torsors over the point; etc.

This is even constructive; the theorems can be proved uniformly, rather than by treating the empty and inhabited cases separately. (This rather trivial method is obvious to a classical mathematician, but it's not constructively valid, since a invertible semigroup/associative quasigroup/heap as defined here can't be constructively proved empty or inhabited; it can only be proved empty iff not inhabited. Indeed, taking any group GG and any truth value PP, the invertible subsemigroup or associative subquasigroup {xG|P}\{x \in G \;|\; P\} is empty or inhabited iff PP is false or true.)

References and remarks

А. К. Сушкевич, Теория обобщенных групп, Государственное научно-техническое издательство Украины, 1937.

  • G.M. Bergman, A.O. Hausknecht, Cogroups and co-rings in categories of associative rings, Ch.IV, paragraph 22, p.95ff – Providence, R.I. : AMS 1996.

  • Z. Škoda, Quantum heaps, cops and heapy categories, Mathematical Communications 12, No. 1, pp. 1–9 (2007); arXiv:math.QA/0701749

  • Thomas Booker, Ross Street, Torsors, herds and flocks, J. Algebra 330 (2011) 346–374 pdf arXiv:0912.4551

  • Peter T. Johnstone, The ‘closed subgroup theorem’ for localic herds and pregroupoids, Journal of Pure and Applied Algebra 70 (1991) 97-106. doi90010-y).

  • wikipedia:heap

  • John Baez on Heaps and torsors

There is an oidification (horizontal categorification) of a heap, sometimes called a heapoid.

Last revised on September 13, 2022 at 10:45:19. See the history of this page for a list of all contributions to it.