Properties of the symmetric difference in lattices with complementation
Václav Cenker, Ivan Chajda, Helmut Länger · 2025
Read Properties of the symmetric difference in lattices with complementation by Václav Cenker, Ivan Chajda, Helmut Länger (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-19980.txt.
Introduction
Václav Cenker, Ivan Chajda, and Helmut Länger study the symmetric difference operation beyond Boolean lattices, in a 2025 paper. In Boolean settings the operation has two classic definitions that agree. In any bounded lattice with complements, both definitions still make sense, but they can part ways. The authors examine the class of lattices where the two forms coincide and name some notable subclasses.
Using a result of Berman, they estimate the sizes of free algebras in those subclasses. The headline theorem is sharp: the symmetric difference is associative exactly when the lattice is Boolean. A single two-variable identity also captures Booleanness on its own. They further characterize lattices carrying an operation that obeys the De Morgan laws. The paper sorts out where Boolean behavior truly comes from.
Catalog record
| CREATOR | Václav Cenker, Ivan Chajda, Helmut Länger |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-19980
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Properties of the symmetric difference in lattices with complementation Václav Cenker, Ivan Chajda, Helmut Länger Abstract The symmetric difference in Boolean lattices can be defined in two different but equivalent forms. However, it can be introduced also in every bounded lattice with complementation where these two forms need not coincide. We study lattices with complementation and the variety of such lattices where these two expressions coincide and point out explicitly some interesting subvarieties. Using a result of J. Berman we estimate the size of free algebras in these subvarieties. It is well-known that the symmetric difference is associative in every Boolean lattice. We prove that it is just the property of Boolean lattices, namely the symmetric difference in a lattice with complementation is associative if and only if this lattice is Boolean. Similarly, we prove that a lattice with complementation is Boolean if and only if the symmetric difference satisfies a certain simple identity in two variables. We also characterize lattices with a unary operation satisfying De Morgan’s laws. 0 0 footnotetext: Support of the research of the first author by the Czech Science Foundation (GAČR), project 24-14386L, support of the research of the first two authors by IGA, project PřF 2025 008, support of the research of the second author by the Czech Science Foundation (GAČR), project 25-20013L, and support of the research of the third author by the Austrian Science Fund (FWF), project 10.55776/PIN5424624, is gratefully acknowledged. AMS Subject Classification: 06D05, 06B05, 06B20, 06F25, 06C15, 06E20 Keywords: Complemented lattice, lattice with complementation, symmetric difference, De Morgan’s laws, distributivity, associativity, variety of lattices with complementation, free algebra 1 Introduction The aim of this paper is to show several important properties of the symmetric difference in complemented lattices where the complementation is a unary operation. Because the symmetric difference can be defined in two different ways which coincide in Boolean lattices, we are interested in lattices which need not be distributive but these two forms of symmetric difference coincide. It is well-known that in a Boolean algebra the symmetric difference is associative. We show that also, conversely, associativity of the symmetric difference yields distributivity of the complemented lattice in question. We start with definitions of several basic concepts. Let \mathbf{L}=(L,\vee,\wedge,0,1) be a bounded lattice and a\in L . An element b of L is called a complement of a if a\vee b=1 and a\wedge b=0 . The lattice \mathbf{L} is called complemented if every element of L has a complement which need not be unique. Let \,{}^{\prime} be a unary operation on L . Then \,{}^{\prime} is called (i) antitone if, for all x,y\in L , x\leq y implies y^{\prime}\leq x^{\prime} , (ii) an involution if x^{\prime\prime}=x for all x\in L , (iii) a complementation if, for every x\in L , x\vee x^{\prime}=1 and x\wedge x^{\prime}=0 . In (iii), x^{\prime} is a complement of x for every x\in L . The algebra \mathbf{L}=(L,\vee,\wedge,{}^{\prime},0,1) where \,{}^{\prime} is a complementation will be called a lattice with complementation . If, moreover, \,{}^{\prime} is an antitone involution then \mathbf{L} is called an ortholattice . At first we prove an auxiliary result using identites similar to those studied in [ 6 ] and [ 7 ] . Lemma 1.1 . Let \mathbf{L}=(L,\vee,\wedge,{}^{\prime},0,1) be a lattice with complementation satisfying one of the following identities: (i) x\wedge y\approx x\wedge(x^{\prime}\vee y) , (ii) x\vee y\approx x\vee(x^{\prime}\wedge y) . Then \mathbf{L} satisfies the identity x^{\prime\prime}\approx x . Proof. Assume (i). Then x\wedge x^{\prime\prime}\approx x\wedge(x^{\prime}\vee x^{\prime\prime})\approx x\wedge 1\approx x. (1) Hence x^{\prime}\approx x^{\prime}\wedge x^{\prime\prime} and x^{\prime\prime\prime}\vee x^{\prime}\approx x^{\prime\prime\prime}\vee(x^{\prime}\wedge x^{\prime\prime\prime})\approx x^{\prime\prime\prime} whence x\vee x^{\prime\prime\prime}\approx x\vee x^{\prime\prime\prime}\vee x^{\prime}\approx 1. Using this, ( 1 ) and (i) we obtain x\approx x\wedge x^{\prime\prime}\approx x^{\prime\prime}\wedge x\approx x^{\prime\prime}\wedge(x^{\prime\prime\prime}\vee x)\approx x^{\prime\prime}\wedge 1\approx x^{\prime\prime}. By dualizing the preceding proof we see that (ii) implies x^{\prime\prime}\approx x . ∎ It is well-known (see e.g. [ 8 ] ) that in a distributive bounded lattice every element has at most one complement. A distributive lattice with complementation is an ortholattice which is called a Boolean lattice . Hence in Boolean lattices \mathbf{L} , for every x\in L , x^{\prime} is the unique complement of x . It is evident that if (L,\vee,\wedge,{}^{\prime},0,1) is a lattice with complementation and a\in L then a=0 if and only if a^{\prime}=1 and, conversely, a=1 if and only if a^{\prime}=0 . In every bounded lattice \mathbf{L}=(L,\vee,\wedge,{}^{\prime},0,1) with a unary operation \,{}^{\prime} one can introduce two so-called symmetric differences , i.e. the term operations \displaystyle x+_{1}y \displaystyle:=(x^{\prime}\wedge y)\vee(x\wedge y^{\prime}), \displaystyle x+_{2}y \displaystyle:=(x\vee y)\wedge(x^{\prime}\vee y^{\prime}). which coincide if \mathbf{L} is a Boolean lattice, see e.g. [ 4 ] . The question is whether this holds only in Boolean lattices. Hence, in what follows, we are interested in lattices with complementation satisfying the identity (x^{\prime}\wedge y)\vee(x\wedge y^{\prime})\approx(x\vee y)\wedge(x^{\prime}\vee y^{\prime}). (2) We call this identity the coincidence identity . Let us note that varieties of lattices with complementation where the complementation satisfies certain adjointness properties were already studied by the authors in [ 5 ] . Example 1.2 . Consider the modular lattice \mathbf{M}_{3}=(M_{3},\vee,\wedge) depicted in Fig. 1. There are exactly six possibilities how to define a complementation \,{}^{\prime} on \mathbf{M}_{3} . Each of these complementations is antitone, but none is an involution. One such complementation is given by \begin{array}[]{l|ccccc}x&0&a&b&c&1\\ \hline\cr x^{\prime}&1&b&c&a&0\end{array} We have \displaystyle a+_{1}b \displaystyle=(a^{\prime}\wedge b)\vee(a\wedge b^{\prime})=(b\wedge b)\vee(a\wedge c)=b\vee 0=b\neq 1=1\wedge(b\vee c)= \displaystyle=(a\vee b)\wedge(a^{\prime}\vee b^{\prime})=a+_{2}b, i.e., the lattice (M_{3},\vee,\wedge,{}^{\prime},0,1) with complementation does not satisfy identity ( 2 ) ( cf. Corollary 2.4 ) . For lattices with complementation satisfying identity ( 2 ) we can show the following result. Lemma 1.3 . Let \mathbf{L}=(L,\vee,\wedge,{}^{\prime},0,1) be a lattice with complementation satisfying identity ( 2 ) and let a\in L . Then the following hold: (i) \mathbf{L} satisfies the identity x^{\prime}\vee(x\wedge x^{\prime\prime})\approx 1 , (ii) a\wedge a^{\prime\prime}\leq a^{\prime} if and only if a=0 . Proof. (i) Identity ( 2 ) implies x^{\prime}\vee(x\wedge x^{\prime\prime})\approx(x^{\prime}\wedge x^{\prime})\vee(x\wedge x^{\prime\prime})\approx(x\vee x^{\prime})\wedge(x^{\prime}\vee x^{\prime\prime})\approx 1\wedge 1\approx 1 . (ii) Because of (i) the following are equivalent a\wedge a^{\prime\prime}\leq a^{\prime} , a^{\prime}\vee(a\wedge a^{\prime\prime})=a^{\prime} , a^{\prime}=1 , a=0 . ∎ Recall that the identities (x\vee y)^{\prime}\approx x^{\prime}\wedge y^{\prime} and (x\wedge y)^{\prime}\approx x^{\prime}\vee y^{\prime} for lattices (L,\vee,\wedge,{}^{\prime}) with a unary operation \,{}^{\prime} are called De Morgan’s laws . 2 Lattices and varieties of lattices satisfying the coincidence identity for symmetric differences The following lemma presents two identities holding in any ortholattice satisfying identity ( 2 ). Lemma 2.1 . Let (L,\vee,\wedge,{}^{\prime},0,1) be an ortholattice satisfying identity ( 2 ) . Then it satisfies the identities \displaystyle(x\wedge y)\vee(x\wedge y^{\prime})\vee(x^{\prime}\wedge y)\vee(x^{\prime}\wedge y^{\prime}) \displaystyle\approx 1, \displaystyle(x\vee y)\wedge(x\vee y^{\prime})\wedge(x^{\prime}\vee y)\wedge(x^{\prime}\vee y^{\prime}) \displaystyle\approx 0. Proof. We have (x\wedge y)\vee(x\wedge y^{\prime})\vee(x^{\prime}\wedge y)\vee(x^{\prime}\wedge y^{\prime})\approx(x+_{1}y)\vee(x+_{2}y)^{\prime}\approx(x+_{1}y)\vee(x+_{1}y)^{\prime}\approx 1. The second identity is dual to the first one. ∎ In the previous example, every of the elements a,b,c has two incomparable complements which, moreover, are complements of each other. We can show that there exist lattices satisfying identity ( 2 ) having an element with two incomparable complements that are not complements of each other, see the following example. Example 2.2 . In Fig. 2 and 3 ortholattices satisfying identity ( 2 ) are visualized: As one can see, in the ortholattice depicted in Fig. 2 the elements c^{\prime} and d^{\prime} are incomparable complements of c , but c^{\prime} and