For a bounded lattice, these semigroups are in fact commutative monoids. Because meet and join both commute and associate, a lattice can be viewed as consisting of two commutative semigroups having the same domain. Lattices have some connections to the family of group-like algebraic structures. In particular, each semilattice is the dual of the other.Ī bounded lattice is an algebraic structure of the form ( L, ∨, ∧, 0, 1) such that ( L, ∨, ∧) is a lattice, 0 (the lattice's bottom) is the identity element for the join operation ∨, and 1 (the lattice's top) is the identity element for the meet operation ∧.Ĭonnection to other algebraic structures The absorption laws, the only axioms above in which both meet and join appear, distinguish a lattice from an arbitrary pair of semilattices and assure that the two semilattices interact appropriately. These axioms assert that both ( L, ∨) and ( L, ∧) are semilattices. The following two identities are also usually regarded as axioms, even though they follow from the two absorption laws taken together. Lattices as algebraic structures General lattice Īn 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.Ĭommutative laws a ∨ b = b ∨ a, a ∧ b = b ∧ a.Īssociative laws a ∨ ( b ∨ c) = ( a ∨ b) ∨ c, a ∧ ( b ∧ c) = ( a ∧ b) ∧ c.Ībsorption laws a ∨ ( a ∧ b) = a, a ∧ ( a ∨ b) = a. In addition to this extrinsic definition as a subset of some other algebraic structure (a lattice), a partial lattice can also be intrinsically defined as a set with two partial binary operations satisfying certain axioms. The resulting structure on H is called a partial lattice. Given a subset of a lattice, H ⊂ L, meet and join restrict to partial functions – they are undefined if their value is not in the subset H. The value of the rank function for a lattice element is called its rank. Ī lattice element y is said to cover another element x, if y > x, but there does not exist a z such that y > z > x.Ī lattice ( L, ≤) is called graded, sometimes ranked (but see Ranked poset for an alternative meaning), if it can be equipped with a rank function r from L to ℕ, sometimes to ℤ, compatible with the ordering (so r( x) < r( y) whenever x < y) such that whenever y covers x, then r( y) = r( x) + 1. A set may have many lower bounds, or none at all, but can have at most one greatest lower bound.Ī partially ordered set ( L, ≤) is called a join-semilattice if each two-element subset. A lower bound l of S is said to be its greatest lower bound, or meet, or infimum, if x ≤ l for each lower bound x of S. Dually, l ∈ L is said to be a lower bound of S if l ≤ s for each s ∈ S. A set need not have a least upper bound, but it cannot have more than one. An upper bound u of S is said to be its least upper bound, or join, or supremum, if u ≤ x for each upper bound x of S. A set may have many upper bounds, or none at all. If ( L, ≤) is a partially ordered set (poset), and S ⊆ L is an arbitrary subset, then an element u ∈ L is said to be an upper bound of S if s ≤ u for each s ∈ S. 11.1 Applications that use lattice theory.3 Connection between the two definitions.2.3 Connection to other algebraic structures.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |