Skew lattice

Summary

In abstract algebra, a skew lattice is an algebraic structure that is a non-commutative generalization of a lattice. While the term skew lattice can be used to refer to any non-commutative generalization of a lattice, since 1989 it has been used primarily as follows.

Definition edit

A skew lattice is a set S equipped with two associative, idempotent binary operations   and  , called meet and join, that validate the following dual pair of absorption laws

 ,
 .

Given that   and   are associative and idempotent, these identities are equivalent to validating the following dual pair of statements:

  if  ,
  if  .[1]

Historical background edit

For over 60 years, noncommutative variations of lattices have been studied with differing motivations. For some the motivation has been an interest in the conceptual boundaries of lattice theory; for others it was a search for noncommutative forms of logic and Boolean algebra; and for others it has been the behavior of idempotents in rings. A noncommutative lattice, generally speaking, is an algebra   where   and   are associative, idempotent binary operations connected by absorption identities guaranteeing that   in some way dualizes  . The precise identities chosen depends upon the underlying motivation, with differing choices producing distinct varieties of algebras.

Pascual Jordan, motivated by questions in quantum logic, initiated a study of noncommutative lattices in his 1949 paper, Über Nichtkommutative Verbände,[2] choosing the absorption identities

 

He referred to those algebras satisfying them as Schrägverbände. By varying or augmenting these identities, Jordan and others obtained a number of varieties of noncommutative lattices. Beginning with Jonathan Leech's 1989 paper, Skew lattices in rings,[3] skew lattices as defined above have been the primary objects of study. This was aided by previous results about bands. This was especially the case for many of the basic properties.

Basic properties edit

Natural partial order and natural quasiorder

In a skew lattice  , the natural partial order is defined by   if  , or dually,  . The natural preorder on   is given by   if   or dually  . While   and   agree on lattices,   properly refines   in the noncommutative case. The induced natural equivalence   is defined by   if  , that is,   and   or dually,   and  . The blocks of the partition   are lattice ordered by   if   and   exist such that  . This permits us to draw Hasse diagrams of skew lattices such as the following pair:

 

E.g., in the diagram on the left above, that   and   are   related is expressed by the dashed segment. The slanted lines reveal the natural partial order between elements of the distinct  -classes. The elements  ,   and   form the singleton  -classes.

Rectangular Skew Lattices

Skew lattices consisting of a single  -class are called rectangular. They are characterized by the equivalent identities:  ,   and  . Rectangular skew lattices are isomorphic to skew lattices having the following construction (and conversely): given nonempty sets   and  , on   define   and  . The  -class partition of a skew lattice  , as indicated in the above diagrams, is the unique partition of   into its maximal rectangular subalgebras, Moreover,   is a congruence with the induced quotient algebra   being the maximal lattice image of  , thus making every skew lattice   a lattice of rectangular subalgebras. This is the Clifford–McLean theorem for skew lattices, first given for bands separately by Clifford and McLean. It is also known as the first decomposition theorem for skew lattices.

Right (left) handed skew lattices and the Kimura factorization

A skew lattice is right-handed if it satisfies the identity   or dually,  . These identities essentially assert that   and   in each  -class. Every skew lattice   has a unique maximal right-handed image   where the congruence   is defined by   if both   and   (or dually,   and  ). Likewise a skew lattice is left-handed if   and   in each  -class. Again the maximal left-handed image of a skew lattice   is the image   where the congruence   is defined in dual fashion to  . Many examples of skew lattices are either right- or left-handed. In the lattice of congruences,   and   is the identity congruence  . The induced epimorphism   factors through both induced epimorphisms   and  . Setting  , the homomorphism   defined by  , induces an isomorphism  . This is the Kimura factorization of   into a fibred product of its maximal right- and left-handed images.

 

Like the Clifford–McLean theorem, Kimura factorization (or the second decomposition theorem for skew lattices) was first given for regular bands (bands that satisfy the middle absorption identity,  ). Indeed, both   and   are regular band operations. The above symbols  ,   and   come, of course, from basic semigroup theory.[3][4][5][6][7][8][9][10]

Subvarieties of skew lattices edit

Skew lattices form a variety. Rectangular skew lattices, left-handed and right-handed skew lattices all form subvarieties that are central to the basic structure theory of skew lattices. Here are several more.

Symmetric skew lattices

A skew lattice S is symmetric if for any   ,   if  . Occurrences of commutation are thus unambiguous for such skew lattices, with subsets of pairwise commuting elements generating commutative subalgebras, i.e., sublattices. (This is not true for skew lattices in general.) Equational bases for this subvariety, first given by Spinks[11] are:   and  . A lattice section of a skew lattice   is a sublattice   of   meeting each  -class of   at a single element.   is thus an internal copy of the lattice   with the composition   being an isomorphism. All symmetric skew lattices for which   admit a lattice section.[10] Symmetric or not, having a lattice section   guarantees that   also has internal copies of   and   given respectively by   and  , where   and   are the   and   congruence classes of   in   . Thus   and   are isomorphisms.[8] This leads to a commuting diagram of embedding dualizing the preceding Kimura diagram.

 

Cancellative skew lattices

A skew lattice is cancellative if   and   implies   and likewise   and   implies  . Cancellatice skew lattices are symmetric and can be shown to form a variety. Unlike lattices, they need not be distributive, and conversely.

Distributive skew lattices

Distributive skew lattices are determined by the identities:

  (D1)

  (D'1)

Unlike lattices, (D1) and (D'1) are not equivalent in general for skew lattices, but they are for symmetric skew lattices.[9][12][13] The condition (D1) can be strengthened to

  (D2)

in which case (D'1) is a consequence. A skew lattice   satisfies both (D2) and its dual,  , if and only if it factors as the product of a distributive lattice and a rectangular skew lattice. In this latter case (D2) can be strengthened to

  and  . (D3)

On its own, (D3) is equivalent to (D2) when symmetry is added.[3] We thus have six subvarieties of skew lattices determined respectively by (D1), (D2), (D3) and their duals.

Normal skew lattices

As seen above,   and   satisfy the identity  . Bands satisfying the stronger identity,  , are called normal. A skew lattice is normal skew if it satisfies

 

For each element a in a normal skew lattice  , the set   defined by { } or equivalently { } is a sublattice of  , and conversely. (Thus normal skew lattices have also been called local lattices.) When both   and   are normal,   splits isomorphically into a product   of a lattice   and a rectangular skew lattice  , and conversely. Thus both normal skew lattices and split skew lattices form varieties. Returning to distribution,   so that   characterizes the variety of distributive, normal skew lattices, and (D3) characterizes the variety of symmetric, distributive, normal skew lattices.

Categorical skew lattices

A skew lattice is categorical if nonempty composites of coset bijections are coset bijections. Categorical skew lattices form a variety. Skew lattices in rings and normal skew lattices are examples of algebras in this variety.[4] Let   with  ,   and  ,   be the coset bijection from   to   taking   to  ,   be the coset bijection from   to   taking   to   and finally   be the coset bijection from   to   taking   to  . A skew lattice   is categorical if one always has the equality  , i.e. , if the composite partial bijection   if nonempty is a coset bijection from a   -coset of   to an  -coset of   . That is  . All distributive skew lattices are categorical. Though symmetric skew lattices might not be. In a sense they reveal the independence between the properties of symmetry and distributivity.[3][4][6][9][10][11][13][14]

Skew Boolean algebras edit

A zero element in a skew lattice S is an element 0 of S such that for all     or, dually,   (0)

A Boolean skew lattice is a symmetric, distributive normal skew lattice with 0,   such that   is a Boolean lattice for each   Given such skew lattice S, a difference operator \ is defined by x \ y =   where the latter is evaluated in the Boolean lattice  [1] In the presence of (D3) and (0), \ is characterized by the identities:

  and   (S B)

One thus has a variety of skew Boolean algebras   characterized by identities (D3), (0) and (S B). A primitive skew Boolean algebra consists of 0 and a single non-0 D-class. Thus it is the result of adjoining a 0 to a rectangular skew lattice D via (0) with  , if   and   otherwise. Every skew Boolean algebra is a subdirect product of primitive algebras. Skew Boolean algebras play an important role in the study of discriminator varieties and other generalizations in universal algebra of Boolean behavior.[15][16][17][18][19][20][21][22][23][24][25]

Skew lattices in rings edit

Let   be a ring and let   denote the set of all idempotents in  . For all   set   and  .

Clearly   but also   is associative. If a subset   is closed under   and  , then   is a distributive, cancellative skew lattice. To find such skew lattices in   one looks at bands in  , especially the ones that are maximal with respect to some constraint. In fact, every multiplicative band in   that is maximal with respect to being right regular (= ) is also closed under   and so forms a right-handed skew lattice. In general, every right regular band in   generates a right-handed skew lattice in  . Dual remarks also hold for left regular bands (bands satisfying the identity  ) in  . Maximal regular bands need not to be closed under   as defined; counterexamples are easily found using multiplicative rectangular bands. These cases are closed, however, under the cubic variant of   defined by   since in these cases   reduces to   to give the dual rectangular band. By replacing the condition of regularity by normality  , every maximal normal multiplicative band   in   is also closed under   with  , where  , forms a Boolean skew lattice. When   itself is closed under multiplication, then it is a normal band and thus forms a Boolean skew lattice. In fact, any skew Boolean algebra can be embedded into such an algebra.[26] When A has a multiplicative identity  , the condition that   is multiplicatively closed is well known to imply that   forms a Boolean algebra. Skew lattices in rings continue to be a good source of examples and motivation.[23][27][28][29][30]

Primitive skew lattices edit

Skew lattices consisting of exactly two D-classes are called primitive skew lattices. Given such a skew lattice   with  -classes   in  , then for any   and  , the subsets

 { }   and   { }  

are called, respectively, cosets of A in B and cosets of B in A. These cosets partition B and A with   and  . Cosets are always rectangular subalgebras in their  -classes. What is more, the partial order   induces a coset bijection   defined by:

  iff  , for   and  .

Collectively, coset bijections describe   between the subsets   and  . They also determine   and   for pairs of elements from distinct  -classes. Indeed, given   and  , let   be the cost bijection between the cosets   in   and   in  . Then:

  and  .

In general, given   and   with   and  , then   belong to a common  - coset in   and   belong to a common  -coset in   if and only if  . Thus each coset bijection is, in some sense, a maximal collection of mutually parallel pairs  .

Every primitive skew lattice   factors as the fibred product of its maximal left and right- handed primitive images  . Right-handed primitive skew lattices are constructed as follows. Let   and   be partitions of disjoint nonempty sets   and  , where all   and   share a common size. For each pair   pick a fixed bijection   from   onto  . On   and   separately set   and  ; but given   and  , set

  and  

where   and   with   belonging to the cell   of   and   belonging to the cell   of  . The various   are the coset bijections. This is illustrated in the following partial Hasse diagram where   and the arrows indicate the   -outputs and   from   and  .

 

One constructs left-handed primitive skew lattices in dual fashion. All right [left] handed primitive skew lattices can be constructed in this fashion.[3]

The coset structure of skew lattices edit

A nonrectangular skew lattice   is covered by its maximal primitive skew lattices: given comparable  -classes   in  ,   forms a maximal primitive subalgebra of   and every  -class in   lies in such a subalgebra. The coset structures on these primitive subalgebras combine to determine the outcomes   and   at least when   and   are comparable under  . It turns out that   and   are determined in general by cosets and their bijections, although in a slightly less direct manner than the  -comparable case. In particular, given two incomparable D-classes A and B with join D-class J and meet D-class   in  , interesting connections arise between the two coset decompositions of J (or M) with respect to A and B.[4]

 

Thus a skew lattice may be viewed as a coset atlas of rectangular skew lattices placed on the vertices of a lattice and coset bijections between them, the latter seen as partial isomorphisms between the rectangular algebras with each coset bijection determining a corresponding pair of cosets. This perspective gives, in essence, the Hasse diagram of the skew lattice, which is easily drawn in cases of relatively small order. (See the diagrams in Section 3 above.) Given a chain of D-classes   in  , one has three sets of coset bijections: from A to B, from B to C and from A to C. In general, given coset bijections   and  , the composition of partial bijections   could be empty. If it is not, then a unique coset bijection   exists such that  . (Again,   is a bijection between a pair of cosets in   and  .) This inclusion can be strict. It is always an equality (given  ) on a given skew lattice S precisely when S is categorical. In this case, by including the identity maps on each rectangular D-class and adjoining empty bijections between properly comparable D-classes, one has a category of rectangular algebras and coset bijections between them. The simple examples in Section 3 are categorical.

See also edit

References edit

  1. ^ a b Leech, J, Skew lattices in rings, Algebra Universalis, 26(1989), 48-72.
  2. ^ Jordan, P. Uber Nichtkommutative Verbände, Arch. Math. 2 (1949), 56–59.
  3. ^ a b c d e Leech, J, Skew lattices in rings, Algebra Universalis, 26(1989), 48-72
  4. ^ a b c d Leech, J, Recent developments in the theory of skew lattices, Semigroup Forum, 52(1996), 7-24.
  5. ^ Leech, J, Magic squares, finite planes and simple quasilattices, Ars Combinatoria 77(2005), 75-96.
  6. ^ a b Leech, J, The geometry of skew lattices, Semigroup Forum, 52(1993), 7-24.
  7. ^ Leech, J, Normal skew lattices, Semigroup Forum, 44(1992), 1-8.
  8. ^ a b Cvetko-Vah, K, Internal decompositions of skew lattices, Communications in Algebra, 35 (2007), 243-247
  9. ^ a b c Cvetko-Vah, K, A new proof of Spinks’ Theorem, Semigroup Forum 73 (2006), 267-272.
  10. ^ a b c Laslo, G and Leech, J, Green’s relations on noncommutative lattices, Acta Sci. Math. (Szeged), 68 (2002), 501-533.
  11. ^ a b Spinks, M, Automated deduction in non-commutative lattice theory, Tech. Report 3/98, Monash U, GSCIT, 1998
  12. ^ Spinks, M, Automated deduction in non-commutative lattice theory, Tech. Report 3/98, Monash University, Gippsland School of Computing and Information Technology, June 1998
  13. ^ a b Spinks, M, On middle distributivity for skew lattices, Semigroup Forum 61 (2000), 341-345.
  14. ^ Cvetko-Vah, Karin ; Kinyon, M. ; Leech, J. ; Spinks, M. Cancellation in skew Lattices. Order 28 (2011), 9-32.
  15. ^ Bignall, R. J., Quasiprimal Varieties and Components of Universal Algebras, Dissertation, The Flinders University of South Australia, 1976.
  16. ^ Bignall, R J, A non-commutative multiple-valued logic, Proc. 21st International Symposium on Multiple-valued Logic, 1991, IEEE Computer Soc. Press, 49-54.
  17. ^ Bignall, R J and J Leech, Skew Boolean algebras and discriminator varieties, Algebra Universalis, 33(1995), 387-398.
  18. ^ Bignall, R J and M Spinks, Propositional skew Boolean logic, Proc. 26th International Symposium on Multiple-valued Logic, 1996, IEEE Computer Soc. Press, 43-48.
  19. ^ Bignall, R J and M Spinks, Implicative BCS-algebra subreducts of skew Boolean algebras, Scientiae Mathematicae Japonicae, 58 (2003), 629-638.
  20. ^ Bignall, R J and M Spinks, On binary discriminator varieties (I): Implicative BCS-algebras, International Journal of Algebra and Computation, to appear.
  21. ^ Cornish, W H, Boolean skew algebras, Acta Math. Acad. Sci. Hung., 36 (1980), 281-291.
  22. ^ Leech, J, Skew Boolean algebras, Algebra Universalis, 27(1990), 497-506.
  23. ^ a b Leech and Spinks, Skew Boolean algebras generated from generalized Boolean algebras, Algebra Universalis 58 (2008), 287-302, 307-311.
  24. ^ Spinks, M, Contributions to the Theory of Pre-BCK Algebras, Monash University Dissertation, 2002.
  25. ^ Spinks, M and R Veroff, Axiomatizing the skew Boolean propositional calculus, J. Automated Reasoning, 37 (2006), 3-20.
  26. ^ Cvetko-Vah, K, Skew lattices in matrix rings, Algebra Universalis 53 (2005), 471-479.
  27. ^ Cvetko-Vah, K, Pure skew lattices in rings, Semigroup Forum 68 (2004), 268-279.
  28. ^ Cvetko-Vah, K, Pure ∇-bands, Semigroup Forum 71 (2005), 93-101.
  29. ^ Cvetko-Vah, K, Skew lattices in rings, Dissertation, University of Ljubljana, 2005.
  30. ^ Cvetko-Vah, K and J Leech, Associativity of the ∇-operation on bands in rings, Semigroup Forum 76 (2008), 32-50