Citizendia
Your Ad Here

The name "lattice" is suggested by the form of the Hasse diagram depicting it.
The name "lattice" is suggested by the form of the Hasse diagram depicting it. In the mathematical discipline known as Order theory, a Hasse diagram (ˈhɑːsə HAHS uh) named after Helmut Hasse (1898&ndash1979 is a
For other uses, see lattice.

In mathematics, a lattice is a partially ordered set (also called a poset) in which every pair of elements has a unique supremum (the elements' least upper bound; called their join) and an infimum (greatest lower bound; called their meet). Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Mathematics, especially Order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering sequencing or arrangement In mathematical Order theory, join is a Binary operation on a Partially ordered set that gives the Supremum (least upper bound of its arguments In Mathematics the infimum of a Subset of some set is the Greatest element, not necessarily in the subset that is less than or equal to all elements of In mathematics a meet on a set is defined either as the unique Infimum (greatest lower bound with respect to a Partial order on the set provided an infimum exists Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities. In Algebra, a branch of Pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations, In traditional Logic, an axiom or postulate is a proposition that is not proved or demonstrated but considered to be either self-evident, or subject In Mathematics, the term identity has several different important meanings An identity is an equality that remains true regardless of the values of Since the two definitions are equivalent, lattice theory draws on both order theory and universal algebra. Order theory is a branch of Mathematics that studies various kinds of Binary relations that capture the intuitive notion of ordering providing a framework for saying Universal algebra (sometimes called general algebra) is the field of Mathematics that studies Algebraic structures themselves not examples ("models" Semilattices include lattices, which in turn include Heyting and Boolean algebras. A semilattice is a mathematical concept with two definitions one as a type of Ordered set, the other as an Algebraic structure. In Mathematics, Heyting algebras are special Partially ordered sets that constitute a generalization of Boolean algebras named after Arend Heyting In Abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. These "lattice-like" structures all admit order-theoretic as well as algebraic descriptions.

Contents

Lattices as posets

A poset (L, ≤) is a lattice if it satisfies the following two axioms. In Mathematics, especially Order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering sequencing or arrangement

Existence of binary joins
For any two elements a and b of L, the set {a, b} has a join (also known as least upper bound or supremum). In mathematical Order theory, join is a Binary operation on a Partially ordered set that gives the Supremum (least upper bound of its arguments
Existence of binary meets
For any two elements a and b of L, the set {a, b} has a meet (also known as greatest lower bound or infimum). In mathematics a meet on a set is defined either as the unique Infimum (greatest lower bound with respect to a Partial order on the set provided an infimum exists

The join and meet of a and b are denoted by a∨b and a∧b, respectively. This definition makes ∨ and ∧ binary operations. In Mathematics, a binary operation is a calculation involving two Operands, in other words an operation whose Arity is two The first axiom says that L is a join-semilattice; the second says that L is a meet-semilattice. A semilattice is a mathematical concept with two definitions one as a type of Ordered set, the other as an Algebraic structure. A semilattice is a mathematical concept with two definitions one as a type of Ordered set, the other as an Algebraic structure. Both operations are monotone with respect to the order: a1 ≤ a2 and b1 ≤ b2 implies that a1∨b1 ≤ a2∨b2 and a1∧b1 ≤ a2∧b2.

It follows by an induction argument that every non-empty finite subset of a lattice has a join (supremum) and a meet (infimum). Mathematical induction is a method of Mathematical proof typically used to establish that a given statement is true of all Natural numbers It is done by proving that With additional assumptions, further conclusions may be possible; see Completeness (order theory) for more discussion of this subject. In the mathematical area of Order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered That article also discusses how one may rephrase the above definition in terms of the existence of suitable Galois connections between related posets – an approach of special interest for the category theoretic approach to lattices. In Mathematics, especially in Order theory, a Galois connection is a particular correspondence between two Partially ordered sets (posets In Mathematics, category theory deals in an abstract way with mathematical Structures and relationships between them it abstracts from sets

A bounded lattice has a greatest and least element, denoted 1 and 0 by convention (also called top and bottom). In Mathematics, especially in Order theory, the greatest element of a subset S of a Partially ordered set (poset is an element of S In Mathematics, especially in Order theory, the greatest element of a subset S of a Partially ordered set (poset is an element of S Any lattice can be converted into a bounded lattice by adding a greatest and least element, and every finite lattice is bounded, by taking the join (resp. , meet) of all elements. Since the least element 0 is by convention the join of an empty set of elements, and the greatest element 1 is the meet of the empty set, a poset is a bounded lattice if and only if every finite set of elements (including the empty set) has a join and a meet.

Lattices as algebraic structures

An algebraic structure (L, ∨, ∧), consisting of a set L and two binary operations ∨ and ∧ on L is a lattice if the following axiomatic identities hold for all elements a, b, c of L. In Algebra, a branch of Pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations, In its simplest meaning in Mathematics and Logic, an operation is an action or procedure which produces a new value from one or more input values

Commutative laws
a∨b = b∨a,
a∧b = b∧a. In Mathematics, commutativity is the ability to change the order of something without changing the end result
    
Associative laws
a∨(b∨c) = (a∨b)∨c,
a∧(b∧c) = (a∧b)∧c. In Mathematics, associativity is a property that a Binary operation can have
    
Absorption laws
a∨(a∧b) = a,
a∧(a∨b) = a. In Algebra, the absorption law is an identity linking a pair of Binary operations Any two Binary operations, say $ and % are subject to

The following identity can be derived from the axioms.

Idempotent laws
a∨a = a,
a∧a = a. Idempotence ˌaɪdɨmˈpoʊtəns describes the property of operations in Mathematics and Computer science which means that multiple applications of the operation

These axioms assert that both (L,∨) and (L,∧) are semilattices. A semilattice is a mathematical concept with two definitions one as a type of Ordered set, the other as an Algebraic structure. The absorption laws, the only axioms above in which both meet and join appear, distinguish a lattice from a random pair of semilattices and assure that the two semilattices interact appropriately. In particular, each semilattice is the dual of the other. In the mathematical area of Order theory, every Partially ordered set P gives rise to a dual (or opposite) partially ordered set which

A bounded lattice is an algebraic structure of the form (L, ∨, ∧, 1, 0) such that (L, ∨, ∧) is a lattice, 0 is a neutral element for the join operation ∨, and 1 is a neutral element for the meet operation ∧. (See semilattice for further details. A semilattice is a mathematical concept with two definitions one as a type of Ordered set, the other as an Algebraic structure. )

Lattices have some connections to the family of group-like algebraic structures. In Abstract algebra, a magma (or groupoid) is a basic kind of Algebraic structure. Because meet and join both commute and associate, a lattice can be viewed as consisting of two commutative semigroups having the same domain. In Mathematics, a semigroup is an Algebraic structure consisting of a nonempty set S together with an Associative Binary operation For a bounded lattice, these semigroups are in fact commutative monoids. In Abstract algebra, a branch of Mathematics, a monoid is an Algebraic structure with a single Associative Binary operation The absorption law is the only defining identity that is peculiar to lattice theory. In Algebra, the absorption law is an identity linking a pair of Binary operations Any two Binary operations, say $ and % are subject to

By commutatitivity and associativity one can think of join and meet as operations that are defined on non-empty finite sets, rather than pairs, of elements. In a bounded lattice the empty join and the empty meet can also be defined (as 0 and 1, respectively). This makes bounded lattices somewhat more natural than general lattices, and many authors require all lattices to be bounded.

The algebraic interpretation of lattices plays an essential role in universal algebra. Universal algebra (sometimes called general algebra) is the field of Mathematics that studies Algebraic structures themselves not examples ("models"

Connection between the two definitions

An order-theoretic lattice gives rise to the two binary operations ∨ and ∧. Since the commutative, associative and absorption laws can easily be verified for these operations, they make (L, ∨, ∧) into a lattice in the algebraic sense. The ordering can be recovered from the algebraic structure because a ≤ b holds if and only if a = a∧b. ↔

The converse is also true. Given an algebraically defined lattice (L, ∨, ∧), one can define a partial order ≤ on L by setting

a ≤ b if and only if a = a∧b, or
a ≤ b if and only if b = a∨b,

for all elements a and b from L. The laws of absorption ensure that both definitions are equivalent. One can now check that the relation ≤ introduced in this way defines a partial ordering within which binary meets and joins are given through the original operations ∨ and ∧.

Since the two definitions of a lattice are equivalent, one may freely invoke aspects of either definition in any way that suits the purpose at hand.

Examples

Further examples are given for each of the additional properties discussed below.

Morphisms of lattices

The appropriate notion of a morphism between two lattices flows easily from the above algebraic definition. In Mathematics, a morphism is an abstraction derived from structure-preserving mappings between two Mathematical structures The study of morphisms and Given two lattices (L, ∨L, ∧L) and (M, ∨M, ∧M), a homomorphism of lattices or lattice homomorphism is a function f : L → M such that

f(a∨Lb) = f(a) ∨M f(b), and
f(a∧Lb) = f(a) ∧M f(b).

Thus f is a homomorphism of the two underlying semilattices. In Abstract algebra, a homomorphism is a structure-preserving map between two Algebraic structures (such as groups rings or Vector A semilattice is a mathematical concept with two definitions one as a type of Ordered set, the other as an Algebraic structure. When lattices with more structure are considered, the morphisms should 'respect' the extra structure, too. Thus, a morphism f between two bounded lattices L and M should also have the following property:

f(0L) = 0M , and
f(1L) = 1M .

In the order-theoretic formulation, these conditions just state that a homomorphism of lattices is a function preserving binary meets and joins. In the mathematical area of Order theory, one often speaks about functions that preserve certain limits i For bounded lattices, preservation of least and greatest elements is just preservation of join and meet of the empty set.

Any homomorphism of lattices is necessarily monotone with respect to the associated ordering relation; see preservation of limits. In the mathematical area of Order theory, one often speaks about functions that preserve certain limits i The converse is of course not true: monotonicity by no means implies the required preservation of meets and joins, although an order-preserving bijection is a homomorphism if its inverse is also order-preserving. In Mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property In Mathematics, if &fnof is a function from A to B then an inverse function for &fnof is a function in the opposite direction from B

Given the standard definition of isomorphisms as invertible morphisms, a lattice isomorphism is just a bijective lattice homomorphism. In Abstract algebra, an isomorphism ( Greek: ἴσος isos "equal" and μορφή morphe "shape" is a bijective In Mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property Similarly, a lattice endomorphism is a lattice homomorphism from a lattice to itself, and a lattice automorphism is a bijective lattice endomorphism. Lattices and their homomorphisms form a category. In Mathematics, category theory deals in an abstract way with mathematical Structures and relationships between them it abstracts from sets

Properties of lattices

We now introduce a number of important properties that lead to interesting special classes of lattices. One, boundedness, has already been discussed.

Completeness

Main article: Complete lattice

A poset is called a complete lattice if all its subsets have both a join and a meet. In Mathematics, a complete lattice is a Partially ordered set in which all subsets have both a Supremum (join and an Infimum (meet In particular, every complete lattice is a bounded lattice. While bounded lattice homomorphisms in general preserve only finite joins and meets, complete lattice homomorphisms are required to preserve arbitrary joins and meets.

Every poset that is a complete semilattice is also a complete lattice. Related to this result is the interesting phenomenon that there are various competing notions of homomorphisms for this class of posets, depending on whether they are seen as complete lattices, complete join-semilattices, complete meet-semilattices, or as join-complete or meet-complete lattices.

Distributivity

Main article: Distributive lattice

Since lattices come with two binary operations, it is natural to ask whether one of them distributes over the other, i. In Mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other In Mathematics, and in particular in Abstract algebra, distributivity is a property of Binary operations that generalises the distributive law e. whether one or the other of the following dual laws holds for any three elements a, b, c of L:

Distributivity of ∨ over ∧
a∨(b∧c) = (a∨b) ∧ (a∨c). In the mathematical area of Order theory, every Partially ordered set P gives rise to a dual (or opposite) partially ordered set which
Distributivity of ∧ over ∨
a∧(b∨c) = (a∧b) ∨ (a∧c).

A lattice that satisfies the first or, equivalently (as it turns out), the second axiom, is called a distributive lattice.

For an overview of stronger notions of distributivity which are appropriate for complete lattices and which are used to define more special classes of lattices such as frames and completely distributive lattices, see distributivity in order theory. In Mathematics, especially in Order theory, a complete Heyting algebra is a Heyting algebra which is complete as a lattice. In the mathematical area of Order theory, a completely distributive lattice is a Complete lattice in which arbitrary joins distribute over arbitrary meets In the mathematical area of Order theory, there are various notions of the common concept of Distributivity, applied to the formation of suprema and

Modularity

Main article: Modular lattice

For some applications the distributivity condition is too strong, and the following weaker property is often useful. In the branch of mathematics called Order theory, a modular lattice is a lattice that satisfies the following self-dual condition Modular law: x A lattice (L, ∨, ∧) is modular if, for all elements a, b, c of L, the following identity holds.

Modular identity
(a ∧ c) ∨ (b ∧ c) = [(a ∧ c) ∨ b] ∧ c.

This condition is equivalent to the following axiom.

Modular law
a ≤ c implies a ∨ (b ∧ c) = (a ∨ b) ∧ c.

Besides distributive lattices, examples of modular lattices are the lattice of submodules of a module, and the lattice of normal subgroups of a group. In Abstract algebra, the concept of a module over a ring is a generalization of the notion of Vector space, where instead of requiring the scalars In Mathematics, more specifically in Abstract algebra, a normal subgroup is a special kind of Subgroup. In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element

Semimodularity

Main article: Semimodular lattice

A finite lattice is modular if and only if it is both upper and lower semimodular. In the branch of mathematics known as Order theory, a semimodular lattice, is a lattice that satisfies the following conditionSemimodular law a  ∧  In the branch of mathematics known as Order theory, a semimodular lattice, is a lattice that satisfies the following conditionSemimodular law a  ∧  For a graded lattice, (upper) semimodularity is equivalent to the following condition on the rank function r:

r(x)+r(y) \ge r(x \wedge y) + r(x \vee y). In Mathematics, a graded poset, sometimes called a ranked poset (but see the article for an alternative meaning is a Partially ordered set

Another equivalent (for graded lattices) condition is Birkhoff's condition:

for each x and y in L, if x and y both cover x \wedge y, then x \vee y covers both x and y.

A lattice is called lower semimodular if its dual is semimodular. For finite lattices this means that the previous conditions hold with \vee and \wedge exchanged, "covers" exchanged with "is covered by", and inequalities reversed. [1]

Continuity and algebraicity

In domain theory, it is natural to seek to approximate the elements in a partial order by "much simpler" elements. Domain theory is a branch of Mathematics that studies special kinds of Partially ordered sets (posets commonly called domains. This leads to the class of continuous posets, consisting of posets where any element can be obtained as the supremum of a directed set of elements that are way-below the element. In Mathematics, a directed set (or a directed preorder or a filtered set) is a nonempty set A together with a reflexive Domain theory is a branch of Mathematics that studies special kinds of Partially ordered sets (posets commonly called domains. If one can additionally restrict these to the compact elements of a poset for obtaining these directed sets, then the poset is even algebraic. In the mathematical area of Order theory, the compact or finite elements of a Partially ordered set are those elements that cannot be subsumed In the mathematical area of Order theory, the compact or finite elements of a Partially ordered set are those elements that cannot be subsumed Both concepts can be applied to lattices as follows:

Both of these classes have interesting properties. For example, continuous lattices can be characterized as algebraic structures (with infinitary operations) satisfying certain identities. While such a characterization is not known for algebraic lattices, they can be described "syntactically" via Scott information systems. In Domain theory, a branch of Mathematics and Computer science, a Scott information system is a primitive kind of logical Deductive system often

Complements and pseudo-complements

Let L be a bounded lattice with greatest element 1 and least element 0. Two elements x and y of L are complements of each other if and only if:

x \vee y = 1 and x \wedge y = 0.

In this case, we write ¬x = y and equivalently, ¬y = x. A bounded lattice for which every element has a complement is called a complemented lattice. In the mathematical discipline of Order theory, and in particular in lattice theory, a complemented lattice is a bounded lattice (with The corresponding unary operation over L, called complementation, introduces an analogue of logical negation into lattice theory. In its simplest meaning in Mathematics and Logic, an operation is an action or procedure which produces a new value from one or more input values In Logic and Mathematics, negation or not is an operation on Logical values for example the logical value of a Proposition The complement is not necessarily unique, nor does it have a special status among all possible unary operations over L. A complemented lattice that is also distributive is a Boolean algebra. In Abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. For a distributive lattice, the complement of x, when it exists, is unique.

Heyting algebras are an example of distributive lattices having at least some members lacking complements. In Mathematics, Heyting algebras are special Partially ordered sets that constitute a generalization of Boolean algebras named after Arend Heyting Every element x of a Heyting algebra has, on the other hand, a pseudo-complement, also denoted ¬x. The pseudo-complement is the greatest element y such that x\wedgey = 0. If the pseudo-complement of every element of a Heyting algebra is in fact a complement, then the Heyting algebra is in fact a Boolean algebra.

Sublattices

A sublattice of a lattice L is a nonempty subset of L which is a lattice with the same meet and join operations as L. That is, if L is a lattice and M\not=\varnothing is a subset of L such that for every pair of elements a, b in M both a\wedgeb and a\veeb are in M, then M is a sublattice of L. [2]

A sublattice M of a lattice L is a convex sublattice of L, if x ≤ z ≤ y and x, y in M implies that z belongs to M, for all elements x, y, z in L.

Free lattices

Main article: Free lattice

Any set X may be used to generate the free semilattice FX. In Mathematics, in the area of Order theory, a free lattice is the Free object corresponding to a lattice. The free semilattice is defined to consist of all of the finite subsets of X, with the semilattice operation given by ordinary set union. In Set theory, the term Union (denoted as ∪ refers to a set operation used in the convergence of set elements to form a resultant set containing the elements of both sets The free semilattice has the universal property. In various branches of Mathematics, certain constructions are frequently defined or characterised by an abstract property which requires the existence of a unique Morphism

Important lattice-theoretic notions

In the following, let L be a lattice. We define some order-theoretic notions that are of particular importance in lattice theory.

An element x of L is called join irreducible if and only if

When the first condition is generalized to arbitrary joins Vai, x is called completely join irreducible. The dual notion is called meet irreducibility. Sometimes one also uses the terms v-irreducible and ^-irreducible, respectively.

An element x of L is called join prime if and only if

Again, this can be generalized to obtain the notion completely join prime and dualized to yield meet prime. Any join-prime element is also join irreducible, and any meet-prime element is also meet irreducible. If the lattice is distributive the converse is also true.

An element x of L is an atom, if L has a 0, 0 < x, and there exists no element y of L such that 0 < y < x. We say that L is atomic (or a point lattice), if every nonzero element of L is a join of atoms. We say that L is atomistic, if every element of L is a supremum of atoms, that is, for all a, b in L such that a\nleq b, there exists an atom x of L such that x\leq a and x\nleq b.

Other important notions in lattice theory are ideal and its dual notion filter. In mathematical Order theory, an ideal is a special subset of a Partially ordered set (poset In Mathematics, a filter is a special Subset of a Partially ordered set. Both terms describe special subsets of a lattice (or of any partially ordered set in general). Details can be found in the respective articles.

See also

References

Monographs available free online:

Elementary texts recommended for those with limited mathematical maturity:

The standard contemporary introductory text, somewhat harder than the above:

Advanced monographs:

On free lattices:

Notes

  1. ^ Stanley, Richard P. Richard Peter Stanley (born 1944) is the Norman Levinson Professor of Applied Mathematics at the Massachusetts Enumerative Combinatorics (vol. 1). Cambridge University Press, 103-104. ISBN 0521663512.  
  2. ^ Burris, Stanley N. , and H. P. Sankappanavar, H. P. , 1981. A Course in Universal Algebra. Springer-Verlag. ISBN 3-540-90578-2.

External links

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic