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.

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.

(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.

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.

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.

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

(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.

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 bthat 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.

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)

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.

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:

(1b) a ∨ b = b ∨ a

(2b) (a ∨ b) ∨ c = a ∨ (b ∨ c)

(3b) a ∨ (a ∧ b) = a

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

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

An important property of lattices follows directly from the absorption laws.

(ii) a ∨ a = a.

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

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.

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 = 0for 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 ∧ · · · ∧ anare upper and lower bounds for L, respectively. Thus we have

Every finite lattice L is bounded.

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, ≤).

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.

Lattice L is nondistributive if and only if it contains a sublattice isomorphic to (a) or (b)

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.

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.

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.

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 ∨ · · · ∨ dnwhere 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.