UNIT 2

Lattices: Introduction, Partial order sets, Dual Order, Toset,Minimal and Maximal,Introduction of Lattices, Properties of Lattices, Types of Lattices,Join Irreducible Elements

POSETS AND LATTICES

INTRODUCTION

Order and precedence relationships appear in many different places in mathematics and computer science. This chapter makes these notions precise.We also define a lattice, which is a special kind of an ordered set.

PARTIALLY ORDERED SETS

Suppose R is a relation on a set S satisfying the following three properties:

[O1] (Reflexive) For any a ∈ S, we have aRa.

[O2] (Antisymmetric) If aRb and bRa, then a = b.

[O3] (Transitive) If aRb and bRc, then aRc.

Then R is called a partial order or, simply an order relation, and R is said to define a partial ordering of S. The set S with the partial order is called a partially ordered set or, simply, an ordered set or poset. We write (S,R) when we want to specify the relation R.
The most familiar order relation, called the usual order, is the relation ≤ (read “less than or equal”) on the positive integers N or, more generally, on any subset of the real numbers R. For this reason, a partial order relation is usually denoted by ; and a b is read “a precedes b.” In this case we also write:
a ≺ b means a b and a = b; read “a strictly precedes b.”
ba means a b; read “b succeeds a.”
b . a means a ≺ b; read “b strictly succeeds a.”
/, / ≺, /, and . are self-explanatory.
When there is no ambiguity, the symbols ≤, <, >, and ≥ are frequently used instead of , ≺, ., and , respectively.

EXAMPLE

(a) Let S be any collection of sets. The relation ⊆ of set inclusion is a partial ordering of S. Specifically, A ⊆ A for any set A; if A ⊆ B and B ⊆ A then A = B; and if A ⊆ B and B ⊆ C then A ⊆ C.

(b) Consider the set N of positive integers. We say “a divides b,” written a | b, if there exists an integer c such that ac = b. For example, 2 | 4, 3 | 12, 7 | 21, and so on. This relation of divisibility is a partial ordering of N.

(c) The relation “|” of divisibility is not an ordering of the set Z of integers. Specifically, the relation is not antisymmetric. For instance, 2|−2 and −2 | 2, but 2 = −2.

(d) Consider the set Z of integers. Define aRb if there is a positive integer r such that b = ar . For instance, 2 R 8 since 8 = 23. Then R is a partial ordering of Z.


Dual Order

  • Let  be any partial ordering of a set S. The relation , that is, a succeeds b, is also a partial ordering of S; it is called the dual order.
  • Observe that a b if and only if ba; hence the dual order  is the inverse of the relation , that is,  =−1.
  • Ordered Subsets

    Let A be a subset of an ordered set S, and suppose a, b ∈ A. Define a b as elements of A whenever a b as elements of S.

  • This defines a partial ordering of A called the induced order on A.
  • The subset A with the induced order is called an ordered subset of S.
  • Unless otherwise stated or implied, any subset of an ordered set S will be treated as an ordered subset of S.
  • Directed graph representation of a finite poset

    Often we represent a nonempty finite poset (X,≤) by a picture. The process is described below.
    (a) Put a dot for each element of X and label it.
    (b) If a ≤ b, then join the dot for a and the dot for b by an arrow (a directed line).
    (c) Put a loop at the dot of a, for each a ∈ X.
    A directed graph representation of A = {1, 2, 3, 9, 18} with the ‘divides’ relation (a ≤ b if a | b) is given below.

    img

    TOSET

  • Total Ordered Set
  • It is a POSET in which each element is comparable to other.
  • Definition : When every two element in the set are comparable it is a TOSET.
  • Example : (z,<=) = ((2,3),(4,6),(8,9))
  • HASSE DIAGRAMS OF PARTIALLY ORDERED SETS

    Let S be a partially ordered set, and suppose a, b belong to S.We say that a is an immediate predecessor of b, or that b is an immediate successor of a, or that b is a cover of a, written

    a / b

    if a < b but no element in S lies between a and b, that is, there exists no element c in S such that a < c < b. Suppose S is a finite partially ordered set. Then the order on S is completely known once we know all pairs a, b in S such that a / b, that is, once we know the relation / on S. This follows from the fact that x < y if and only if x / y or there exist elements a1, a2, . . . , am in S such that

    x / a1 / a2 /· · ·/am / y

  • The Hasse diagram of a finite partially ordered set S is the directed graph whose vertices are the elements of S and there is a directed edge from a to b whenever a / b in S. (Instead of drawing an arrow from a to b, we sometimes place b higher than a and draw a line between them. It is then understood that movement upwards indicates succession.) In the diagram thus created, there is a directed edge from vertex x to vertex y if and only if x / y. Also, there can be no (directed) cycles in the diagram of S since the order relation is antisymmetric.
  • The Hasse diagram of a poset S is a picture of S; hence it is very useful in describing types of elements in S. Sometimes we define a partially ordered set by simply presenting its Hasse diagram.We note that the Hasse diagram of a poset S need not be connected.
  • EXAMPLE

    (a) Let A = {1, 2, 3, 4, 6, 8, 9, 12, 18, 24} be ordered by the relation “x divides y.” The diagram of A is given in Figure (b) (Unlike rooted trees, the direction of a line in the diagram of a poset is always upward.)

    (b) Let B = {a, b, c, d, e}. The diagram in Figure (b) defines a partial order on B in the natural way. That is, d ≤ b, d ≤ a, e ≤ c and so on.

    (c) The diagram of a finite linearly ordered set, i.e., a finite chain, consists simply of one path. For example, Figure (c) shows the diagram of a chain with five elements.

    img

    MINIMAL AND MAXIMAL

    Let S be a partially ordered set.An element a in S is called a minimal element if no other element of S strictly precedes (is less than) a. Similarly, an element b in S is called a maximal element if no element of S strictly succeeds (is larger than) b. Geometrically speaking, a is a minimal element if no edge enters a (from below), and b is a maximal element if no edge leaves b (in the upward direction).We note that S can have more than one minimal and more than one maximal element.

    If S is infinite, then S may have no minimal and no maximal element. For instance, the set Z of integers with the usual order ≤ has no minimal and no maximal element. On the other hand, if S is finite, then S must have at least one minimal element and at least one maximal element

    An element a is S is called a first element if for every element x in S,

    a x

    that is, if a precedes every other element in S. Similarly, an element b in S is called a last element if for every element y in S,

    y b

    that is, if b succeeds every other element in S. We note that S can have at most one first element, which must be a minimal element, and S can have at most one last element, which must be a maximal element. Generally speaking, S may have neither a first nor a last element, even when S is finite.

    INTRODUCTION OF LATTICES

    Definition

    1. A poset (L,≤) is called a lattice if each pair x, y ∈ L has a lub denoted ‘x ∨ y’ and a glb denoted ‘x ∧ y’.
    2. A lattice is called a distributive lattice if it satisfies the following two properties.
        a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c).
        a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c).
    (Distributive Law)

    Example

    Let L = {0, 1} ⊆ Z and define a ∨ b = max{a, b} and a ∧ b = min{a,b}.
    Then, L is a chain as well as a distributive lattice.
       2. The set N with usual order and ∨ := max and ∧ := min is a distributive lattice. We consider two cases to verify that a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c). The second distributive identity is left as an exercise for the reader.
    (a) Case 1: a ≥ min{b, c}. Then, either a ≥ b or a ≥ c, say a ≥ b. Hence,
       a ∨ (b ∧ c) = max{a,min{b, c}} = a = min{max{a, b} = a,max{a, c} ≥ a} = (a ∨ b) ∧ (a ∨ c).
    (b) Case 2: a < min{b, c}. Then, a < b and a < c. Hence,
       a ∨ (b ∧ c) = max{a,min{b, c}} = min{b, c} = min{max{a, b} = b,max{a, c} = c} = (a ∨ b) ∧ (a ∨ c).
       3. Prove that the first figure in Figure 5.1 is a distributive lattice.
       4. Prove that the second figure in Figure 5.1 is a lattice but not a distributive lattice.
       5. Let S = {a, b, c}. On P(S), we define A ∨ B = A∪B and A ∧ B = A ∩ B. Then, it can be easily verified that P(S) is a lattice.
       6. Fix a positive integer n and let D(n) denote the poset obtained using the ‘divides’ partial order with ∨ := lcm and ∧ := gcd. Then, prove that D(n) is a distributive lattice.

    Properties of Lattices

    Let L be a nonempty set closed under two binary operations called meet and join, denoted respectively by ∧ and ∨. Then L is called lattice if the following axioms hold where a, b, c are elements in L:

  • Commutative law:
  •    (1a) a ∧ b = b ∧a
       (1b) a ∨ b = b ∨ a

  • Associative law:
  •    (2a) (a ∧ b) ∧ c = a ∧ (b ∧ c)
       (2b) (a ∨ b) ∨ c = a ∨ (b ∨ c)

  • Absorption law:
  •    (3a) a ∧ (a ∨ b) =a
       (3b) a ∨ (a ∧ b) = a

    We will sometimes denote the lattice by (L,∧,∨) when we want to show which operations are involved.

    Duality and the Idempotent Law

    The dual of any statement in a lattice (L,∧,∨) is defined to be the statement that is obtained by interchanging ∧ and ∨. For example, the dual of
    a ∧ (b ∨ a) = a ∨ a is a ∨ (b ∧ a) = a ∧ a

  • Principle of Duality
  • This follows from the fact that the dual theorem can be proven by using the dual of each step of the proof of the original theorem.
    An important property of lattices follows directly from the absorption laws.
  • Idempotent Law
  •    (i) a ∧ a = a;
       (ii) a ∨ a = a.

    Lattices and Order

    Given a lattice L, we can define a partial order on L as follows:
    a b if a ∧ b = a
    Analogously, we could define
    a b if a ∨ b = b

    Sublattices, Isomorphic Lattices

    Suppose M is a nonempty subset of a lattice L. We say M is a sublattice of L if M itself is a lattice (with respect to the operations of L).We note thatM is a sublattice of L if and only ifM is closed under the operations of ∧ and ∨ of L. For example, the set Dm of divisors of m is a sublattice of the positive integers N under divisibility. Two lattices L and L are said to be isomorphic if there is a one-to-one correspondence f: L → L such that f (a ∧ b) = f (a) ∧ f (b) and f (a ∨ b) = f (a) ∨ f (b) for any elements a, b in L.

    Types of Lattices

    1. BOUNDED LATTICES

    A lattice L is said to have a lower bound 0 if for any element x in L we have 0x. Analogously, L is said to have an upper bound I if for any x in L we have x I . We say L is bounded if L has both a lower bound 0 and an upper bound I . In such a lattice we have the identities

    a ∨ I = I, a ∧ I = a, a ∨ 0 = a, a ∧ 0 = 0
    for any element a in L. The nonnegative integers with the usual ordering,
    0 < 1 < 2 < 3 < 4 < · · ·

    have 0 as a lower bound but have no upper bound. On the other hand, the lattice P(U) of all subsets of any universal set U is a bounded lattice with U as an upper bound and the empty set  as a lower bound. Suppose L = {a1, a2, . . . , an} is a finite lattice. Then

    a1 ∨ a2 ∨ · · · ∨ an and a1 ∧ a2 ∧ · · · ∧ an
    are upper and lower bounds for L, respectively. Thus we have
    Every finite lattice L is bounded.

    2. COMPLETE LATTICE

    A lattice is said to be complete if every non empty subset of set L has a Least Upper Bound and a Greatest Lower Bound.
    a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). Complete lattices appear in many applications in mathematics and computer science. Being a special instance of lattices, they are studied both in order theory and universal algebra. A partially ordered set (L, ≤) is a complete lattice if every subset A of L has both a greatest lower bound (the infimum, also called the meet) and a least upper bound (the supremum, also called the join) in (L, ≤).

    3. DISTRIBUTIVE LATTICES

    A lattice L is said to be distributive if for any elements a, b, c in L we have the following:

    Distributive law:
    (4a) a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) (4b) a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
    Otherwise, L is said to be nondistributive.We note that by the principle of duality the condition (4a) holds if and only if (4b) holds.
    Given Figure
    (a) is a nondistributive lattice since
    a ∨ (b ∧ c) = a ∨ 0 = a but (a ∨ b) ∧ (a ∨ c) = I ∧ c = c
    (b) is also a nondistributive lattice. In fact, we have the following characterization of such lattices.
    img
    Lattice L is nondistributive if and only if it contains a sublattice isomorphic to (a) or (b)

    4. COMPLEMENTED LATTICES

    A lattice L is said to be complemented if L is bounded and every element inLhas a complement. shows a complemented lattice where complements are not unique. On the other hand, the latticeP(U) of all subsets of a universal set U is complemented, and each subset A of U has the unique complement Ac = U\A.
    In the mathematical discipline of order theory, a complemented lattice is a bounded lattice (with least element 0 and greatest element 1), in which every element a has a complement, i.e. an element b satisfying a ∨ b = 1 and a ∧ b = 0. Complements need not be unique. A relatively complemented lattice is a lattice such that every interval [c, d], viewed as a bounded lattice in its own right, is a complemented lattice. A complemented lattice is a bounded lattice (with least element 0 and greatest element 1), in which every element a has a complement, i.e. an element b such that
    a ∨ b = 1 and a ∧ b = 0.
    In general an element may have more than one complement. However, in a (bounded) distributive lattice every element will have at most one complement. A lattice in which every element has exactly one complement is called a uniquely complemented lattice.
    A lattice with the property that every interval (viewed as a sublattice) is complemented is called a relatively complemented lattice. In other words, a relatively complemented lattice is characterized by the property that for every element a in an interval [c, d] there is an element b such that
    a ∨ b = d and a ∧ b = c.
    Such an element b is called a complement of a relative to the interval.
    A distributive lattice is complemented if and only if it is bounded and relatively complemented.
    The lattice of subspaces of a vector space provide an example of a complemented lattice that is not, in general, distributive.

    img

    5. MODULAR LATTICE

    x ≤ b implies x ∨ (a ∧ b) = (x ∨ a) ∧ b,
    where ≤ is the partial order, and ∨ and ∧ (called join and meet respectively) are the operations of the lattice. Modular lattices arise naturally in algebra and in many other areas of mathematics. For example, the subspaces of a vector space (and more generally the submodules of a module over a ring) form a modular lattice. Every distributive lattice is modular. In a not necessarily modular lattice, there may still be elements b for which the modular law holds in connection with arbitrary elements a and x (≤ b).
    Such an element is called a modular element. Even more generally, the modular law may hold for a fixed pair (a, b).
    Such a pair is called a modular pair, and there are various generalizations of modularity related to this notion and to semimodularity.

    Join Irreducible Elements, Atoms

    Let L be a lattice with a lower bound 0. An element a in L is said to be join irreducible if a = x ∨ y implies a = x or a = y. (Prime numbers under multiplication have this property, i.e., if p = ab then p = a or p = b where p is prime.) Clearly 0 is join irreducible. If a has at least two immediate predecessors, say, b1 and b2 as in (a), then a = b1 ∨ b2, and so a is not join irreducible. On the other hand, if a has a unique immediate predecessor c, then a = sup(b1, b2) = b1 ∨ b2 for any other elements b1 and b2 because c would lie between the b’s. In other words, a = 0, is join irreducible if and only if a has a unique immediate predecessor. Those elements which immediately succeed 0, called atoms, are join irreducible. However, lattices can have other join irreducible elements. For example, the element c in Figure given above is not an atom but is join irreducible since a is its only immediate predecessor.

    img

    If an element a in a finite lattice L is not join irreducible, then we can write a = b1 ∨ b2. Then we can write b1 and b2 as the join of other elements if they are not join irreducible; and so on. Since L is finite we finally have

    a = d1 ∨ d2 ∨ · · · ∨ dn

    where the d’s are join irreducible. If di precedes dj then di ∨dj = dj ; so we can delete the di from the expression. In other words, we can assume that the d’s are irredundant, i.e., no d precedes any other d. We emphasize that such an expression need not be unique, e.g., I = a ∨ b and I = b ∨ c in both lattices in Figure given above.We now state the main theorem of this section.