Context and lattice orbifolds have been discussed by M. Zickwolff [1,2], B. Ganter and D. Borchmann[3,4]. Preordering the folding automorphisms by set inclusion of their orbits gives rise to further development. The minimal elements of this preorder have a prime group order and any group element can be dissolved into the product of group elements whose group order is a prime power. This contribution describes a way to compress an orbifold annotation to sets of such minimal automorphisms. This way a hierarchical annotation is described together with an interpretation of the annotation. Based on this annotation an example is given that illustrates the construction of an automaton for certain pattern matching problems in music processing.
Introduction
Lattice orbifolds have been described by Monika Zickwolff [
In the work of Zickwolff, Ganter and Borchmann together with the theory also a method of data compression by means of the stabilisers in the automorphism group has been provided. This abridged annotation contains the automorphisms that violate a certain kind of symmetry which can be described by the stabilisers of the equivalence classes. Thus, it provides an insight how the lattice violates the symmetry reflected by the folding group.
The latter approach starts from a global view at the orbifold and cuts out redundant information treating all nodes in the Hasse diagram equally. Properties like direction are not used for this kind of annotation.
The work presented here, starts from a local view (a pair of neighbours) and uses both direction and transitivity of the relation to minimise the annotation. In this way it spares the necessity to save the stabilisers increasing the information provided by the edge annotation in comparison with the classical abridged annotation.
After some theoretical section an example is given that provides further insight into applications of the theory provided in this article. 2
Preliminaries If not stated otherwise algebraic structures are be denoted by double stroke letters, the base set of an algebraic structure A by the same letter A in normal font. Aut A is its automorphism group and 1 := {(1)}, ·, (1) the trivial group. For any permutation group G on a set A we denote the set of its orbits by A \\ G := {xG | x ∈ A}. Obviously, for any group element g ∈ G and any orbit U ∈ A \\ G also its adjoint gU g−1 is an orbit. Throughout this paper we refer to the set of volatile points of an automorphism g ∈ Aut A as Var g := {x ∈ M | xg 6= x} and to its set of fixed points using the notation Fix g := {x ∈ M | xg = x}. Obviously, for any element g ∈ Aut A the equation A = Fix g ∪ Var g holds. We say that a permutation g ∈ G acts semiregular on a set M ⊆ A, iff M \ Var g ∈ {∅, M } is true. Note that Var g is not restricted to be a subset of M .
If (M, ≤) is an ordered set and N ⊆ M then the corresponding order ideal is defined by the set ↓≤ N := {1 ∈ M | ∃y ∈ N : x ≤ y} and we write ↓≤ x for ↓≤{x} if the context is clear. The neighbourhood relation is denoted by the symbol ≺.
As defined in [
[ xG<zG<yG λ(xG, zG) · λ(zG, yG) = [
Gx · g · Gy.
g∈λ(x,y) g6∈λ(xG,zG)·λ(zGG,yG) xG<zG<y This consists of a transversal T of M \\ G and an abridged annotaton function λabr : T × T → P G, where λabr(x, y) is a set of double coset representatives, i. e. it is a minimal set such that Gx · λabr(x, y) · Gy = λ(x, y).
It is well known that orbits of automorphisms of a finite ordered set are
always antichains in this set.
1 For other settings see [
Minimal Acting Automorphisms Let A be an algebraic structure. The orbits of the cyclic subgroups of Aut A can be used to preorder the automorphism group. If we refer to some group G or its base set G without further notice it is always meant to be G ≤ Aut A. Lemma 1. Let Aut A the automorphism group of a finite algebraic structure A. Then the binary relation ⊑ ⊆ Aut A × Aut A defined by
g ⊑ h :⇔ ∀U ∈ (A \\ hgi)∃U ′ ∈ (A \\ hhi) : U ⊆ U ′ is a preorder.
Proof. This follows directly from the definition: Reflexivity is obivious as the equation A \\ hgi = A \\ hgi holds. Given three automorphisms f, g, h ∈ Aut A such that for each orbit U ∈ (A \\ hf i) there exists an orbit U ′ ∈ (A \\ hgi) with U ⊆ U ′. If the same condition is true for the pair (g, h) we can find an orbit U ′′ ∈ (A \\ hhi) such that U ⊆ U ′ ⊆ U ′′. Thus transitivity holds, too. ⊓⊔ As in any cyclic subgroup the implication hgni ⊆ hgi ⇒ xhgni ⊆ xhgi holds, we can fix the following corollary: Corollary 1. For any group element g ∈ Aut A and any natural number we get: gn ⊑ g In particular, this means that g ∈ Aut A and n ∈ N imply Var gn ⊆ Var g.
On the other hand, the so defined relation ⊑ is usually no order relation as for any g ∈ Aut A we have A \\hgi = A \\hg−1i, but in general the equation g = g−1 does not hold.
If A is finite, then the preordered set (Aut A, ⊑) has minimal elements. Definition 1. Let A be a finite algebraic structure. The minimal elements of the preordered set (Aut A, ⊑) are called automorphisms with minimal action. Corollary 2. Let g be minimal in (G, ⊑), then the cyclic group hgi acts semiregular on Var g.
Proof. Suppose hgi does not act semiregular on Var g. Then there exist elements ∃x, y ∈ Var g and a positive integer n ∈ N \ {0} such that xgn = x, ygn 6= y. This implies xhgni = {x} 6= xhgi. Thus, xhgni 6∈ A \\ hgi. Consequently, gn ⊑ g and g 6⊑ gn. Thus, g is not minimal. ⊓⊔ Corollary 3. Let g ∈ G be minimal in (G, ⊑). Then for any element h ∈ G : huh−1 is minimal, too.
Proof. Suppose the existence of an element v ∈ G such that the set of its orbits A \\hvi is a refinement of A \\hgug−1i. Then, A \\hg−1vgi = (A \\hvi)g is a refinement of A \\hui, as A = Ag−1 . This means that u is not minimal. ⊓⊔ The set containing the minimal nontrivial automorphisms of (G, ⊑) will be denoted by Min(G, ⊑), in particular we define
(1) ∈ Min(G, ⊑) iff Min(G, ⊑) \ {(1)} = ∅ and G 6= ∅.
Corollary 4. The subgroup hMin(G, ⊑)i is a normal subgroup in G.
Hall’s theorem [
P := g ∈ G |hgi| is a prime power is a generating set of G.
For the construction of the Sylow groups, we can use the following lemma: Lemma 2. Let g ∈ Aut A an automorphism of finite order n ∈ N \ {0} and g1, g2 ∈ hgi with |hg1i| = m1 and |hg2i| = m2. Then hggcd(n/m1,n/m2)i ≤ hg1, g2i. Proof. As cyclic groups are Abelian, there exist integers a, b ∈ Z such that gcd( mn1 , mn2 ) = a mn1 + b mn2 . Since g1 ∈ hgn/m1 i and g2 ∈ hgn/m2 i, w. l. o.g. we can assume g1 = gn/m1 and g2 = gn/m2 . Thus, we get ggcd(n/m1,n/m2) = g1ag2b. ⊓⊔ Consequently, the generating set of Corollary 5 contains all minimal elements Min(G, ⊑).
Lemma 3. Let G ≤ Aut A be a finite automorphism group. Then the elements of Min(G, ⊑) have prime order.
Proof. Let |hgi| = pn where p is prime. Then gpn−1 = p. As hgi is cyclic, its order is the least common multiple of the sizes of its orbits. Thus, it has at least one orbit of size pn, while the orbits in hgn−1i have either one or p elements. Corollary 1 tells us, that the minimal Elements of (G, ⊑) are those of prime orders. ⊓⊔ 4
Automorphisms of ordered sets Let G ≤ Aut A and U1, U2 ≤ G such that U1 · U2 = G. Considering the implied action of G on P A, a straight forward calculation shows for all X ⊆ P A that X ∈ (A \\ U1) \\ U2 iff S X ∈ A \\ G.
Let us consider some additional properties of automorphisms of finite lattices. Definition 2. Let (M, ≤) be an ordered set, G ≤ Aut(M, ≤), and x ∈ M . The set
G↓≤ x := {g ∈ G | Var g ∩ ↓≤ x = ∅} (1) is called downwards stabiliser of x in G.
Obviously the downwards stabiliser of a maximal element in a complete lattice is 1. In fact G↓≤ x is a subgroup of the stabiliser Gx of x.
Corollary 6. Let V = (V, ≤) be a finite lattice ordered set. And let x ∈ V while y, z ∈ V are upper neighbours of x. Furthermore, if there exist two automorphisms g, h ∈ G↓≤ x with the property zg = y = zh, then the equation (↓≤ y)h−1g = ↓≤ y holds.
Proof. We know that yh−1g = y. So for any a ∈ ↓≤ y we know ah−1g ≤ y as g and h are automorphisms. ⊓⊔ Thus, if two elements are in the same orbit their downwards stabilisers are related by conjugation. This proves the following lemma: Lemma 4. Let V = (V, ≤) a finite lattice ordered set, G ≤ Aut V, and let x, y, z ∈ V while y and z are upper neighbours of x. Any automorphism g with zg = y is an automorphism mapping V \ ↓≤ z to V \ ↓≤ y, while the equation G↓≤ y = g−1G↓≤ zg holds.
Proof. Let g ∈ G↓≤ x with zg = y and let h ∈ G↓≤ z. Then for any a ∈ V \↓≤ z and any b ∈ V \↓≤ y we get ag ∈ V \↓≤ y and bg−1 ∈ V \↓≤ z as g is an automorphism. As V \ ↓≤ y and V \ ↓≤ z are isomorphic by g, for any automorphism h ∈ G↓≤ z the mapping f := g−1hg is an automorphism on V \ ↓≤ y and even f ∈ G↓≤ y, as it is constant for any c ∈ ↓≤ y. Finally, we get gf g−1 = h. Thus, G↓≤ z is a conjugate of G↓≤ y. The other direction of the implication is obvious. ⊓⊔ As an immediate conclusion, we get that the downwards stabiliser of an element is contained in the union of the downwards stabilisers of its upper neighbours: Corollary 7. Let V = (V, ≤) a finite lattice ordered set, G ≤ Aut V, and let x ∈ V and N = {y ∈ V | x ≺ y} the set of upper neighbours of x. Let further T a transversal of N \\ G and S ⊆ G such that T S = N . Then S ·St∈T G↓≤ t ⊆ G↓≤ x. In other words: At any point in the lattice we can restrict ourselves to a local view. These considerations can be easily extended to finite ordered sets. 5
Orbifolds In this section we define an orbifold representation using minimisations according to the preorder discussed in Section 3. Definition 3. Let λ : T × T → P G be a mapping that assigns to each pair of elements from a finite set T to a subset of another set G. A contiguous chain of λ from x ∈ T to y ∈ T is defined as a subset C ⊆ T such that the relation ρ := {(z, z′) ∈ T × T | λ(z, z′) 6= ∅} forms the neighbourhood relation of a linear order with minimal element x and maximal element y. The set of all such contiguous chains of λ between two elements x and y will be denoted by CT,λ(x, y).
Further let the relation ≺′ ⊆ T × T be defined by x ≺′ y :⇔ ∃g ∈ G : x ≺ yg. Using the non-commutative complex product Q in largest-left order, the operator Λλ : T × T → P G is defined by Λ(x, x) = 1, and for x 6= y by Λλ(x, y) := *
|C| [ Y λ(zi−1, zi) i=2
C ∈ CT,λ(x, y), zi−1 ≺ zi,+ {z1, z2, . . . , z|C|} = C ∩ Gx,y.
(2) Theorem 7 will provide us with another kind of annotation of an orbifold: Definition 4. Let V = (V, ≤) be a finite lattice ordered set, G ≤ Aut V, T a transversal of V \\ G, and the relation ≺′ defined as above.
A mapping λhier : T × T → P G is called hierarchical annotation (of V , T and G), if it fulfils the following conditions for all x, y ∈ T : 1. λhier(x, y) ⊆ G↓≤ x, 2. λhier(x, y) = ∅ if ∀y′ ∈ yG : x 6≺′ y′, and 3. x ≺′ y implies yλhier(x,y) = yG↓≤ x 4. yλhier(x,y)Λλhier (0,x) = yGx .
Corollary 8. Let V = (V, ≤) be a finite lattice ordered set, G ≤ Aut V, and λ
a hierarchical annotation. Then the equation Sx,y∈T λ(x, y) ≤ G holds.
Example 1. Figure 1 shows a simple example of a lattice and its orbifold
annotated with three different annotations. Besides the hierarchical annotation the
annotations from Borchmann, Ganter and Zickwolff [
Proof. For any x, y ∈ T and any z ∈ V with x ≺ y, x ≺ z, if z ∈ yG↓≤ x we fix an arbitrary gx,y,z ∈ G λ1(x, y) := {gx,y,z | z ∈ yG↓↓≤≤ xx }s.uIcfhzth∈aty zx =\yyGg↓x≤,yx,z .anInd Gthat case we define G ↓≤ x = ∅ then the orbits of y are predefined by all automorphisms that act below x thus, we define λ1(x, y) := 1.
In any case where z ∈ yGx \ yG↓≤ x , there exists an automorphism hx,y,z ∈ Gx such that z ∈ yλ1(x,y)hx,y,z . Then there exist two elements xˆz, yˆz ∈ ↓≤′ x such E E
G 7 4 8
E G E G 5 2
G G 7 4 8
E E E E 5 2
E E 7 4 1 (a) Original order
1 (b) Hierarchical annotation.
1 (c) Full annotation.
1 (d) Abridged annotation. that xˆz ≺′ yˆz and there is an automorphism hx,y,z ∈ G↓≤ xˆz \ Gyˆz and another automorphism hˆx,y,z ∈ Λ(xˆ, x). Using this we define a second preliminary x,y,z | z ∈ yG \ yG↓≤ x }. annotation λ2(xˆz, yˆz, x, y) := {hx,y,z hˆ−1
For all other combinations of elements xˆ, yˆ, x, y we set λ1(x, y) := ∅ and λ2(xˆ, yˆ, x, y) := ∅. Finally we define: λhier(x, y) := λ1(x, y) ∪
λ2(x, y, x˜, y˜, z˜).
[ x˜,y˜∈T,z˜∈y˜Gx
Obviously such a function exists and fulfils the conditions of Definition 4. ⊓⊔ Now, as we know how to describe the automorphism group G ≤ Aut V by means of automorphisms acting locally, we will use automorphisms that are minimal under certain restrictions. The corresponding operator is defined as follows: Definition 5. Let V = (V, ≤) be a finite lattice ordered set, and G ≤ Aut V an automorphism group of V, while U ⊆ G is one of its subsets. For any x, y, z ∈ V the elements of the set
Minx,y7→z U := Min⊑{g ∈ U | xg = x, yg = z} are called minimal annotating automorphisms (fixing x and mapping y to z). The elements of the set Minx,y7→z U ∩ G↓≤ x 1 Min↓ x,y7→z U := ∅
Minx,y7→z U ∩ G↓≤ x 6= ∅ Minx,y7→z U ∩ G↓≤ x = ∅ and Minx,y7→z U 6= ∅ else (3) (4) are called upper minimal automorphisms. For applications it would be interesting to have an annotation that consists only of minimal acting automorphisms. Unfortunately, that is not generally possible. Nevertheless when Irred∨≤ : V → P V maps each element to the set of supremum irreducible elements less or equal to it, we can proof the following lemma: Lemma 6. For any finite lattice ordered set V = (V, ≤), any automorphism group G ≤ Aut(V, ≤), and any transversal T ⊆ V of V \\ G there exists a hierarchical annotation that consists of upper minimal automorphisms, if for all elements x, y ∈ T with x ≺ y and z ∈ Irred∨≤ y \ Irred∨≤ x the following condition holds: (Irred∨≤ y \ Irred∨≤ x)G = zG (5) Proof. It is a well-known fact, that for each automorphism g ∈ G and every element x ∈ V the equation xg = W (Irred∨≤ x)g .
Let x ≺′ y a pair of neighbours in (T, ≤′) and x ≺ z a pair of neighbours in (V, ≤) such that z ∈ yG. Then we can modify the proof of Lemma 5 with the following refinements: 1. If y ∈ Irred∨≤ y then choose for any z ∈ yG↓≤ x a minimal automorphism gx,y,z ∈ Minx,y7→z G and define λ1 as in Lemma 5. 2. For y ∈ Irred∨≤ y and z 6∈ yG↓≤ x there exist an automorphism g ∈ Gx \ G↓≤ x and an automorphism h ∈ λ1(x, y) such that z = yhg where g 6= (1). In that case the action of hgi on z depends on the action on ↓≤ x. As (↓≤ x)hgi ⊆ ↓≤ x and the action of hgi on ↓≤ x is defined by the irreducibles also the action on z depends on the irreducibles below it (everything else we have already collected in λ1(x, y). Let 0 = xˆ0 ≺′ xˆ1 ≺′ . . . ≺′ xˆl = x be a maximal chain from 0 to x of elements of V . Then there exists a chain x0 ≺ x1 ≺ . . . ≺ xl such that xi ∈ xˆiG. For each pair (xi, xi+1) we define I(xi, xi+1) := Irred∨≤ xi+1 \ Irred∨≤ xi. Let g0 = (1). Given xˆigi = xi chose a minimal automorphism mi from λ(xˆi, xˆi+1) that maps xˆi to xig+gi−11 . This is always possible as |I(xi, xi+1)G ∩ T | = 1. Then define gi+1 := migi. Finally we get an automorphism gl that acts on ↓≤ x, implying glg−1 ∈ G↓≤ x. 3. If y 6∈ Irred∨≤ y there exist a unique irreducible yˆ ∈ T and an element xˆ ∈ T such that yˆ ∈ (Irred∨≤ y \ Irred∨≤ x)G, xˆ ≺′ yˆ and xˆ < x hold. Obviously yˆ 6≤ x. In that case we define λ1(x, y) := λ1(xˆ, yˆ).
Induction over the height (the size of the longest chain) leads to the desired annotation. Obviously we don’t need to define any λ2 to something different than the empty set. Thus we can define λ := λ1 which fulfils the conditions of Definition 4 and provides a labelling using upper minimal automorphism. ⊓⊔ Definition 6. Let V = (V, ≤) a finite lattice and G ≤ Aut V a group of automorphisms. Let further T ⊆ V a transversal of the orbit partition V \\ G and λ : T ×T → P G a minimal acting annotation. Let further ≤′ defined by x ≤′ y iff there exists an automorphism g ∈ G such that x ≤ yg. Then the triplet (T, ≤′, λ) is called minimal acting orbifold of V by G. Theorem 1 (Unfolding). Let V = (V, ≤) a finite lattice and G ≤ Aut V a group of automorphisms and (T, ≤′, λ) a hierarchical (minimal acting) orbifold of V by G. Let further for C : T × T → P T the mapping that assigns a pair x ≤′ y to the set of all contiguous chains of λ from x to y, and to the empty set otherwise (i. e. if x 6≤′ y).
Then the ordered set (L, 2) with the relation 2 ⊆ L × L defined by L := [{xΛ(0,x) | x ∈ T },
and x 2 y :⇔ ∃z, zˆ ∈ T, g ∈ Λ(0, zˆ) : zg = x, zˆg = y, z ≤′ zˆ (6) (7) equals (V, ≤).
Proof. We prove this theorem by induction. As any finite lattice is also a complete lattice the orbit of the minimal element 0 of (V, ≤) is a singleton. That implies that 0 ∈ T .
Let us start with the set L0 := {0} containing the infimum of the lattice and the relation 20:= {(0, 0)}.
Let y ∈ V and suppose that for any x < y we have already proved that ↓2 x = ↓≤ x ⊆ V . Thus, for each x ∈ {x′ ∈ V | x′ ≺ y} there exists an automorphism gx ∈ G such that xgx ∈ T . W. l. o. g. gx ∈ Λ(0, xgx ) (otherwise there exists g′ ∈ Λ(0, xgx ) with xg′ = ygx ). As T is a transversal of V , there is also an automorphism gy ∈ G such that ygy ∈ T . From x ≤ y we know xgx ≤′ ygy and thus, if gy ∈ λ(xgx , ygy ) · Λ(0, xgx ) then also x 2 y.
Note that for any z the equation Λ(0, z) = Szˆ≺′z λ(zˆ, z)Λ(0, zˆ) holds. If there exists an automorphism h ∈ λ(xgx , ygy ) such that ygx = (ygy )h then the condition h · gx−1 ∈ h · Λ(0, xgx ) ⊆ λ(xgx , ygy ) · Λ(0, xgx ) holds. Thus, y ∈ L and x 2 y. If there is no such element in λ(xgx , ygy ), then by Definition 4 we can find an automorphism h ∈ λ(x, y) · Λ(0, x) which maps ygy to ygx . Thus, y ∈ L and x 2 y hold in this case, too. As we had chosen x arbitrarily below y we have proved ↓≤ y ⊆ ↓2 y.
Since L is constructed by automorphisms of V which map certain elements
of V to other elements of V , we know L ⊆ V . Suppose that for any two elements
x, y ∈ L the inequality x 2 y holds. Then we know that in equation (7) the
condition λ(z, zˆ) · Λ(0, z) ⊆ λfull(z, zˆ) holds if λfull is the full annotation as
discussed in [
As we have proved the condition ↓2 y = ↓≤ y ⊆ V , induction proves the equation (L, 2) = (V, ≤) for y = 1 ∈ T . ⊓⊔ 6
An Example with Musical Background
In many parts of computational music theory pitches and notes are represented
by integers. This has been proved to be useful especially in technical applications.
As there are well-documented mathematical models available (see e. g., [
Let H ⊆ Zo a harmony. Then for some chromatic interval i ∈ Zo the mapping ti : P Zo → P Zo : H 7→ {p + i | p ∈ H} is called a transposition. The harmonic form F (H) of some harmony H is defined as the mapping F : P Zo → P(P Zo) : H 7→ {ti(H) | i ∈ Zo}.
As for each interval i ∈ Zo there exists a transposition ti. These transpositions can be considered as automorphisms of the ordered set (P Zo, ⊆), the transposition group will be denoted by T. In fact this ordered set is a complete lattice which is invariant under transposition. The harmonic forms can be considered as the set of the orbits of the transpositions P Zo \\ T.
If we want to recognise a certain set of harmonies H we can build an automaton that can be described by a concept lattice. Let H = K(G, M, I) be the context defined by
G := [ P H,
H∈H
M := Zo, and
I := {(H, p) ∈ G × M | p ∈ H}.
(8) Then BH can be considered as automaton that recognises all finite words that consist of letters which are included in one of the harmonies of H. Starting in the concept (G, ∅), with each pitch p ∈ Zo the automaton switches state (A, B) to state (B ∪ {p})I , B ∪ {p} . The latter is a state as with every Harmony H the set of objects G includes each of its subsets H′ ⊆ H. If such a state doesn’t exist the automaton won’t recognise the word.
The naive approach to recognise harmonic forms uses the same idea. Let F := {F (H) | H ∈ H} a set of harmonic forms. Then we define the lattice as follows: F = K(G′, M ′, I′) with G := {ti(H), H ∈ H, i ∈ Zo},
M := Zo, and
I := {(H, p) ∈ G × M | p ∈ H}.
(9)
The concept lattice B(F) has all transpositions as automorphisms. Figure 6 shows a concept lattice that can be used to recognise the major seventh chord F ({0, 4, 7, 10}), the minor triad F ({0, 3, 7}) and all of their harmonic subforms. The nodes are arranged orbit-wise. That means, each cluster is an orbit of B(F) \\ T. Thus, the automorphisms can be seen as cyclic permutations of the endpoints of the edges. In comparison with the number of orbits the lattice is large: 14 orbits are formed by 140 concepts.
For an automaton that recognises harmonic forms it would be interesting to compress the data as the generation of the lattice can be very time and space consuming if the chroma system contains more chromas. E. g. considering the pitch bend parameter as part of a pitch in standard MIDI environments the number of pitches increases from 12 to 12 · 214. In such a case an orbifold based representation of the lattice does not necessarily increase in size. Starting by a hierarchical annotation of minimal acting automorphisms we can enhance the annotation by replacing each automorphism by a pair consisting of the automorphism and the character (pitch) that triggers its action. To avoid unnecessary operations the automaton could save the automorphism that must be applied to the pattern rather than applying it. In many cases (e. g., classification) it does not need to be applied at all.
This approach provides two additional advantages: As we know the context
automorphisms, we can use a folded context to compute the order relation of
the concept orbifolds as described in [
Outlook We have seen that orbifolds of certain lattices can be described using hierarchical annotations, and that it is possible to minimise the action of the annotating automorphisms without losing the possibility of unfolding such hierarchical orbifolds.
Nevertheless there are open topics that can improve the theory. In Lemma 6 Restriction (5) has technical reasons. At the moment it is an open question how to deal with arbitrary lattices. It might be helpful to use systems of generators for the annotation λ. That should be straight forward if care is taken on conjugated subgroups.
Another easy extension would be to elaborate the idea for arbitrary ordered sets.