Lattice

structure

A partially ordered set in which each two-element subset has both a least upper and a greatest lower bound. This implies the existence of such bounds for every non-empty finite subset.

Examples.[edit]

1) A linearly ordered set (or chain) $M$ where for $a,b\in M$, if $a\le b$, then

$$sup\{a,b\}=b,inf\{a,b\}=a.$$

2) The subspaces of a vector space ordered by inclusion, where

$$sup\{A,B\}=\{x:x=a+b,a\in A,b\in B\},$$

$$inf\{A,B\}=A\cap B.$$

3) The subsets of a given set ordered by inclusion, where

$$sup\{A,B\}=A\cup B,$$

$$inf\{A,B\}=A\cap B.$$

4) The non-negative integers ordered by divisibility: $a\le b$ if $b=ac$ for a certain $c$; where $sup\{a,b\}$ is the least common multiple of $a$ and $b$, and $inf\{a,b\}$ is the greatest common divisor of $a$ and $b$.

5) The real-valued functions defined on the interval $[0,1]$ and ordered by the condition: $f\le g$ if $f(t)\le g(t)$ for all $t\in [0,1]$, where

$$sup\{f,g\}=u,$$

in which

$$u(t)=max\{f(t),g(t)\},$$

and

$$inf\{f,g\}=v,$$

in which

$$v(t)=min\{f(t),g(t)\}.$$

Let $M$ be a lattice. $M$ becomes a universal algebra with two binary operations if one defines

$$a+b=sup\{a,b\},$$

$$a\cdot b=inf\{a,b\}$$

(the symbols $\cup$ and $\cap$ or $\vee$ and $\wedge$ are often used instead of $+$ and $\cdot$). This universal algebra satisfies the following identities:

$$\begin{array}{l}(1)a+a=a;\\ (2)a+b=b+a;\\ (3)(a+b)+c=a+(b+c);\\ (4)a(a+b)=a;\end{array}\begin{array}{l}(1^{\prime })a\cdot a=a;\\ (2^{\prime })a\cdot b=b\cdot a;\\ (3^{\prime })(a\cdot b)\cdot c=a\cdot (b\cdot c);\\ (4^{\prime })a+a\cdot b=a.\end{array}$$

Conversely, if $M$ is a set with two binary operations that have the properties –, ( $1^{\prime }$)–( $4^{\prime }$) mentioned above, then an order $\le$ can be imposed on $M$ by setting $a\le b$ if $a+b=b$( it turns out in this case that $a\le b$ if and only if $a\cdot b=a$). The resulting partially ordered set will be a lattice in which

$$sup\{a,b\}=a+b\text{ and }inf\{a,b\}=a\cdot b.$$

In this way a lattice can be defined as a universal algebra satisfying the identities –, ( $1^{\prime }$)–( $4^{\prime }$), i.e. lattices form a variety of universal algebras.

If a partially ordered set is regarded as a small category, then it is a lattice if and only if has products and coproducts of pairs of objects.

If $P$ and $P^{\prime }$ are lattices and if $f$: $P\to P^{\prime }$ is an isomorphism of partially ordered sets, then $f$ is also an isomorphism of the corresponding universal algebras, i.e.

$$f(x+y)=f(x)+f(y)\text{ and }f(xy)=f(x)\cdot f(y)$$

for any $x,y\in P$. However, an arbitrary isotone mapping of $P$ into $P^{\prime }$ is not necessarily a homomorphism of these lattices considered as universal algebras. Thus, for any $a\in P$, the mappings $f(x)=x+a$ and $g(x)=x\cdot a$ are isotone mappings of the lattice $P$ into itself, but they are homomorphisms if and only if $P$ is a distributive lattice. However, the first of these mappings is a homomorphism of the semi-lattice $P$ with the operation $+$, and the second is a homomorphism of the semi-lattice $P$ with the operation $\cdot$. The class of all lattices forms a category if homomorphisms are taken as morphisms.

An anti-homomorphism of a lattice $P$ into a lattice $P^{\prime }$ is a mapping $f:P\to P^{\prime }$ such that

$$f(x+y)=f(x)\cdot f(y)\text{ and }f(x\cdot y)=f(x)+f(y),$$

for any $x,y\in P$. A composite of two anti-homomorphisms is a homomorphism. A partially ordered set that is anti-isomorphic to a lattice is a lattice.

By coordinatization of a lattice is meant the finding of an algebraic system (most often a universal algebra) such that the given lattice is isomorphic to the lattice of subsystems, to the lattice of congruences or to some other lattice associated with this algebraic system or universal algebra. An arbitrary lattice with a 0 and a 1 is coordinatized by the partially ordered semi-group of its residual mappings (cf. Residual mapping) into itself, and turns out to be isomorphic to the lattice of right annihilators of this semi-group. The semi-group itself is a Baer semi-group, i.e. the right and left annihilators of each of its elements are generated by idempotents.

The most important results are obtained for lattices subjected to some kind of additional restrictions (see Algebraic lattice; Atomic lattice; Brouwer lattice; Vector lattice; Modular lattice; Distributive lattice; Multiplicative lattice; Orthomodular lattice; Complete lattice; Continuous lattice; Free lattice; Lattice with complements; Boolean algebra). For specific problems in the theory of lattices see Ideal; Filter; Completion, MacNeille (of a partially ordered set). Algebraic systems that are at the same time lattices play a special role (see Lattice-ordered group). The majority of applications of the theory of lattices are associated with Boolean algebras. Other classes of lattices have been used in quantum mechanics and physics.

The concept of a lattice first arose in the late 19th century and was connected with the fact that many results about the set of ideals of a ring or the set of normal subgroups of a group seemed analogous and could be proved in the framework of modular lattices. As an independent branch of algebra, the theory of lattices was developed in the 1930s.

References[edit]

Comments[edit]

Naturally, most theorems in lattice theory require some hypothesis about the lattice. The remarkable exception is the Funayama–Nakayama theorem: The lattice of congruence relations on any lattice is distributive (see e.g. [1] or [2]). There is also one major unsolved (in 1989) problem about arbitrary finite lattices. Every finite lattice is complete and algebraic, and therefore is representable as the lattice of congruence relations on some universal algebra $A$. Can $A$ be taken finite? P.P. Pálfy and P. Pudlák showed [a4] that this is closely related to a problem in finite group theory, which they solved for solvable groups. W. Feit [a1] began the study of the problem in simple groups.

In topology, the awkwardness of Krull dimension (called $\mathrm{adim}$ in Dimension of an associative ring) has been shown to reside only in the rigidity of the definition. Instead, define the dimension $\dim L$ of a distributive lattice $L$, like $\mathrm{Kdim}$, as the maximum length of a chain of prime ideals of $L$. Define the dimension $\mathrm{gdim}X$ of a topological space $X$ as the minimum of $\dim L$ over lattices of open sets $L$ which form a basis for $X$. Then $\mathrm{gdim}=\mathrm{adim}$ for the Noetherian spaces for which $\mathrm{adim}$ is really used; $\mathrm{gdim}=\dim$ for separable metrizable spaces [a2]; for general metrizable spaces $X$, $\mathrm{ind}X\le \mathrm{gdim}X\le \dim X$, [a3].

The first significant work on lattices was done by E. Schröder [a5] and R. Dedekind [a6]. The development of the subject in the 1930-s was largely the work of G. Birkhoff [a7] and O. Ore ; the latter used the term "structure" instead of "lattice" , but this quickly became obsolete except in Russia, where it survived until the 1960-s.

References[edit]