Bounded, complemented and distributive lattices

Objectives and prerequisite

Use the existing meet/join and Hasse-diagram foundation to distinguish boundedness, complementation and distributivity. Build counterexamples instead of treating these properties as interchangeable, and connect their conjunction to Boolean algebra. All finite examples are nonempty lattices; 0 and 1 below denote bottom and top, not necessarily the numbers zero and one.

1. Boundedness is global

A bounded lattice has a least element 0 and greatest element 1: 0≤x≤1 for every x. Consequently x∧0=0, x∨0=x, x∧1=x and x∨1=1. A lattice guarantees meets and joins of pairs; it does not automatically guarantee endpoints when the carrier is infinite.

Every finite nonempty lattice is bounded. Enumerate its elements x₁,…,xₙ and form their iterated meet m and join j. Meet/join associativity follows from their greatest-lower/least-upper-bound meaning. Then m is below every element and j above every element, so m=0 and j=1. By contrast, integers under ordinary ≤ form a lattice with min/max, but have no least or greatest integer. Finiteness is doing work in the theorem.

2. A complement must pass two tests

In a bounded lattice, y is a complement of x if x∧y=0 AND x∨y=1. A complemented lattice gives every element at least one complement. The definition alone does not promise uniqueness. Bottom and top complement each other.

Consider the three-element chain 0<a<1. Meet=min and join=max. Candidate y=0 gives a∨0=a≠1; y=a gives a∧a=a≠0; y=1 gives a∧1=a≠0. Thus a has no complement. This lattice is bounded and, as proved below, distributive, but not complemented. A diagram having a top and bottom is insufficient.

3. Distributive identities and a useful proof

A distributive lattice satisfies both x∧(y∨z)=(x∧y)∨(x∧z) and x∨(y∧z)=(x∨y)∧(x∨z) for every triple. In lattice theory either identity implies its dual, but here direct checks or known models suffice. One failing triple disproves distributivity; one successful triple does not prove it.

Every chain is distributive. Suppose y≤z, so y∨z=z. Then x∧y≤x∧z, so (x∧y)∨(x∧z)=x∧z=x∧(y∨z). The dual argument with min/max proves the other identity. This covers every triple because y,z are always comparable.

In P(U), meet is intersection and join is union. An element belongs to X∩(Y∪Z) iff it belongs to X and to at least one of Y,Z, equivalently to (X∩Y)∪(X∩Z). The dual identity follows similarly. Therefore every power-set lattice is distributive.

4. The diamond M₃ separates complement from distributivity

Define M₃={0,p,q,r,1}, with three pairwise-incomparable middle elements p,q,r. Each lies above 0 and below 1; there are no other strict comparisons. For distinct middle elements, meet=0 and join=1. Comparable pairs use the lower element as meet and upper as join, so every pair is covered and this is a lattice.

It is complemented: 0 and 1 complement each other; each middle element has either of the other two as a complement. For example p∧q=0, p∨q=1, and the same holds with r instead of q. But

p∧(q∨r)=p∧1=p,

(p∧q)∨(p∧r)=0∨0=0.

Since p≠0, distributivity fails. Thus complemented does not imply distributive, and complements may be nonunique. Conversely, the three-element chain shows distributive does not imply complemented.

5. Unique complements and Boolean structure

In a bounded distributive lattice, if b and c both complement a, then

b=b∧1=b∧(a∨c)=(b∧a)∨(b∧c)=0∨(b∧c)=b∧c.

Similarly c=b∧c, so b=c. Distributivity guarantees uniqueness when a complement exists; it does not guarantee existence. The three-element chain is the warning.

A Boolean algebra can be described as a bounded distributive complemented lattice. Write the unique complement of x as x′. P(U) is the standard model: bottom ∅, top U, meet ∩, join ∪ and complement U\X. With U={a,b,c}, the complement of {a,c} is {b}; both disjointness and union=U must be checked. Under characteristic bit-vectors, meet/join/complement become bitwise AND/OR/NOT. This supplies the mathematical bridge to Boolean logic without replacing circuit-design lessons.

De Morgan's identity (x∨y)′=x′∧y′ follows from uniqueness: distributivity gives (x∨y)∧(x′∧y′)=0, and (x∨y)∨(x′∧y′)=((x∨y)∨x′)∧((x∨y)∨y′)=1. Thus x′∧y′ is the complement of x∨y. The dual proof gives (x∧y)′=x′∨y′.

6. Divisor lattices: a calculation and a criterion

Let D(n) be all positive divisors of n ordered by divisibility. Bottom is numerical 1, top is n, meet=gcd and join=lcm. Factor n=p₁^e₁⋯pₖ^eₖ. Each divisor corresponds to an exponent vector (a₁,…,aₖ), with 0≤aᵢ≤eᵢ. Meet/join take coordinatewise min/max, so D(n) is distributive by the chain argument in each coordinate.

A complement of divisor d must satisfy gcd(d,c)=1 and lcm(d,c)=n. For each prime coordinate, min(aᵢ,bᵢ)=0 and max(aᵢ,bᵢ)=eᵢ. If 0<aᵢ<eᵢ, no bᵢ works. Thus d has a complement exactly when each exponent is either 0 or eᵢ; the complement is then n/d. Every divisor has a complement exactly when n is squarefree (including n=1 under the usual convention).

D(12)={1,2,3,4,6,12} is bounded and distributive. Divisor 3 has complement 4: gcd=1 and lcm=12. Divisor 2 has no complement: its exponent of 2 lies strictly between 0 and 2. The tempting 12/2=6 fails gcd(2,6)=1. D(30), where 30=2·3·5, is Boolean; each divisor selects a subset of three distinct primes, and complement selects the omitted primes.

Checklist and pitfalls

First verify the object is a lattice. Identify actual bottom/top within its carrier. Test both complement equations for each element. Prove distributivity generally or give one explicit failing triple. Call it Boolean only after boundedness, distributivity and complementation all hold. In D(n), the bottom label is 1, so requiring gcd=0 would be a category error. Never infer a Boolean lattice merely from the presence of complements or the visual shape of a small diagram.

Original practice: six single-correct MCQs

These are original questions, not previous-year questions. Choose exactly one option.

LT01. Which statement holds for every finite nonempty lattice?

A. It is complemented. B. It is distributive. C. It has a least and a greatest element. D. It is a total order.

Answer: C

A: The three-element chain has an uncomplemented middle element.

B: M₃ is a finite nondistributive lattice.

C: The meet of all elements is bottom and the join of all is top.

D: Incomparable elements occur in power-set lattices.

LT02. In the chain 0<a<1, what are the complements of a?

A. Only 0 B. Only 1 C. Both 0 and 1 D. None

Answer: D

A: a∨0=a, not top.

B: a∧1=a, not bottom.

C: Each candidate fails one of the two required equations.

D: 0 fails the join test, while a and 1 fail the meet test.

LT03. In M₃ with incomparable middle elements p,q,r, what are p∧(q∨r) and (p∧q)∨(p∧r), respectively?

A. p and 0 B. 0 and p C. 1 and 0 D. p and p

Answer: A

A: q∨r=1, so the left side is p; both pairwise meets on the right are 0.

B: This reverses the two evaluated sides.

C: Meet of p with top is p, not top.

D: This incorrectly assumes distributivity in the diamond.

LT04. Which is the complement of 3 in the divisor lattice D(12)?

A. 1 B. 4 C. 6 D. 12

Answer: B

A: gcd(3,1)=1 but lcm=3, not 12.

B: gcd(3,4)=1 and lcm(3,4)=12.

C: gcd(3,6)=3 and lcm=6; both tests fail.

D: The join is 12 but the meet is 3, not bottom 1.

LT05. Which full positive-divisor lattice is Boolean under divisibility?

A. D(8) B. D(12) C. D(30) D. D(18)

Answer: C

A: 8 has a repeated prime; divisor 2 has no complement.

B: 12 has a squared prime; divisor 2 has no complement.

C: 30 is squarefree; each prime is either present or absent, giving set complements.

D: 18 has 3²; divisor 3 has no complement.

LT06. In a bounded distributive lattice, what is guaranteed about complements?

A. Every element has exactly one. B. Every element has at least two. C. No element can have one. D. An element has at most one.

Answer: D

A: Existence needs the additional complemented property.

B: Distributivity forces uniqueness whenever complements exist.

C: Bottom and top already complement each other.

D: If b,c complement a, distributivity gives b=b∧c=c.

Source and scope

This bounded extension develops relations, lattices or groups under Section 1 of the GATE 2026 CS syllabus. It does not claim complete Discrete Mathematics coverage. Definitions, worked examples, proofs and practice are original.

Official GATE 2026 CS syllabus, Section 1

Source checked: 2026-10-14.