BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Saturday , July 22 2017
Home / Lattices and Boolean Algebras / Define two definitions of lattices and show that two definitions of lattices is equivalence.

Define two definitions of lattices and show that two definitions of lattices is equivalence.

Definition I(according to poset): A poset (L, ≤) is said to form a lattice if for every a, b ∈ L, Sup{a, b} and

Inf{a, b} exist in L.

In that case, we write

Sup{a, b} = a ˅ b

Inf{a, b} = a ˄ b

Definition II(algebraic): A non empty set L together with two binary operations ˄ and ˅ is said to form a lattice if ∀ a, b c ∈ L, the following conditions hold:

L1: Idempotency: a ˄ a = a, a ˅ a = a

L2: Commutativity: a ˄ b = b ˄ a, a ˅ b = b ˅ a

L3: Associativity: a ˄ (b ˄ c) = (a ˄ b) ˄ c, a ˅ (b ˅ c) = (a ˅ b) ˅ c

L4: Absorption: a ˄ (a ˅ b) = a, a ˅ (a ˄ b) = a.

Proof: By definition, I we find if L is a lattice then for any a, b ∈ L Inf{a, b} = a ˄ b exists and unique. Thus ˄ is a binary operation on L. Similarly ˅ will be a binary operation on L.

Now we have to prove that definition I ⟹ definition II.

Idempotency: a ˄ a = Inf{a, a} = Inf{a} = a

and a ˅ a = Sup{a, a} = Sup{a} = a

Commutativity: a ˄ b = inf {a, b} = inf{b, a} = b ˄ a

and a ˅ b = sup{a, b} = sup{b, a} = b ˅ a

Associativity: Let b ˄ c = d, then d = Inf{b, c}

⟹ d ≤ b, d ≤ c

Let e = Inf{a, d} then e ≤ a, e ≤ d

Thus e ≤ a, e ≤ b, e ≤ c [using transitivity]

⟹ e is a lower bound of {a, b, c}

If f is any lower bound of {a, b, c} then

f ≤ a, f ≤ b, f ≤ c

Now, f ≤ a, f ≤ b and d = inf{a, b} gives f ≤ d

f ≤ c, f ≤ d and e = inf{c, d} gives f ≤ e

Hence e = inf{a, b, c}

Similarly we can show that (a ˄ b) ˄ c = inf{a, b, c}

Absorption: Since a ˅ (a ˄ b) is the join of a and (a ˄ b) then

a ˅ (a ˄ b) ≥ a ——————–(i)

Since a ≥ a and a ≥ a ˄ b which implies that

(a ˅ a) ≥ a ˅(a ˄ b)

⟹ a ≥ a ˅(a ˄ b) ——————-(ii)

From (i) and (ii) we get

a ˅ (a ˄ b) = a

Hence from above we can say that definition I ⟹ definition II (Proved)

Now we have to show that definition II⟹ definition I

Let now L be a lattice according to definition II. We first show that L forms a poset. For this we define a relation ≤ on L by a ≤ b ⇔ a ˄ b = a

It is an easy job to show that ≤ so defined is a partial order relation. Thus (L, ≤) is a poset.

Let now a, b ∈ L be any elements, then by definition II, a ˄ b ∈ L. We show a ˄ b = Inf{a, b} with respect to ≤ defined above.

 

We have (a ˄ b) ˄ a = a ˄ (b ˄ a)   By L3

= a ˄ (a ˄ b)     By L2

= (a ˄ a) ˄ b

= a ˄ b

⟹ a ˄ b ≤ a

Similarly, a ˄ b ≤ b

⟹ a ˄ b is a lower bound of {a, b}

Suppose c is any lower bound of {a, b} then c ≤ a, c ≤ b

⟹ c ˄ a = c, c ˄ b = c

Thus c ˄ (a ˄ b) = (c ˄ a) ˄ b = c ˄ b = c or that c ≤ a ˄ b is greatest lower bound of {a, b} proving our assertion.

We now show that

a ≤ b ⇔ a ˄ b = a ⇔ a ˅ b = b

Now a ˄ b = a ⟹ (a ˄ b) ˅ b = a ˅ b

⟹ b = a ˅ b by L4

Also a ˅ b = b ⟹ a ˄ (a ˅ b) = a ˄ b

⟹ a = a ˄ b by L4

Hence a ˄ b = a ⇔ a ˅ b = b (⇔ a ≤ b)

Thus by duality we can say that Sup{a, b} will be a ˅ b. Hence definition I hold. (Proved)

Check Also

Prime ideals and theorem and problem

Definition: An ideal A of a lattice L is called a prime ideal of L ...

Leave a Reply

Your email address will not be published. Required fields are marked *