Lattice and Recurrence Relation: Posets, Hasse Diagrams and Solved Examples

In discrete mathematics, a lattice is a partially ordered set (poset) in which every pair of elements a, b has a least upper bound, called the join a ∨ b, and a greatest lower bound, called the meet a ∧ b. A recurrence relation is an equation that defines each term of a sequence from earlier terms, such as aₙ = 5aₙ₋₁ − 6aₙ₋₂. Both topics sit in the same unit of most B.Tech discrete-maths syllabi, which is why they are often taught together.

This page covers lattices in depth (posets, Hasse diagrams, examples and types) and then gives a short introduction to recurrence relations with one fully solved example.

Part 1: Lattices

Start with a partially ordered set

A partial order ≤ on a set A is a relation that is:

• Reflexive: a ≤ a for every a.
• Antisymmetric: if a ≤ b and b ≤ a, then a = b.
• Transitive: if a ≤ b and b ≤ c, then a ≤ c.

The pair (A, ≤) is a poset. “Partial” means some pairs may be incomparable. Under divisibility, 4 and 6 are incomparable because neither divides the other. If you need a refresher on relations and their properties, see the sets, relations and functions page.

Hasse diagrams

A Hasse diagram is a compact drawing of a poset. You draw an element higher than another when it is larger, and join b above a with a line only when b covers a (a < b with nothing strictly between them). Loops (from reflexivity) and lines implied by transitivity are left out.

Upper bound, lower bound, LUB and GLB

• An upper bound of a and b is any element u with a ≤ u and b ≤ u.
• The least upper bound (LUB), or join a ∨ b, is the smallest such u.
• A lower bound is any l with l ≤ a and l ≤ b; the greatest lower bound (GLB), or meet a ∧ b, is the largest such l.

A poset is a lattice when the join and the meet exist for every pair of elements.

What is a lattice? Two standard examples

Example 1: divisors of 12 under divisibility

Let D₁₂ = {1, 2, 3, 4, 6, 12}, with a ≤ b meaning “a divides b”. The cover relations are 1–2, 1–3, 2–4, 2–6, 3–6, 4–12 and 6–12, giving this Hasse diagram:

          12
         /  \
        4    6
         \  / \
          2    3
           \  /
            1

Here the join is the LCM and the meet is the GCD:

• 4 ∨ 6 = lcm(4, 6) = 12, and 4 ∧ 6 = gcd(4, 6) = 2.
• 4 ∨ 3 = 12, and 4 ∧ 3 = 1.
• 2 ∨ 3 = 6, and 2 ∧ 3 = 1.

The LCM and GCD of two divisors of 12 are again divisors of 12, so every pair has a join and a meet. D₁₂ is a lattice.

Example 2: the power set under ⊆

For S = {a, b, c}, the power set P(S) has 2³ = 8 subsets ordered by inclusion. The join of two subsets is their union and the meet is their intersection. For example, {a} ∨ {b, c} = {a, b, c} and {a, b} ∧ {b, c} = {b}. Every power set is a lattice, with ∅ at the bottom and S at the top.

A poset that is not a lattice

Take {1, 2, 3} under divisibility. The elements 2 and 3 have no common multiple in the set, so they have no upper bound at all, and 2 ∨ 3 does not exist. This is a poset but not a lattice. Adding 6 to the set fixes it.

Types of lattices

Bounded lattice

A lattice is bounded if it has a least element 0 (with 0 ≤ a for all a) and a greatest element 1 (with a ≤ 1 for all a). In D₁₂, 0 is the number 1 and 1 is the number 12. In P(S), 0 is ∅ and 1 is S. Every finite lattice is bounded; the integers under ≤ form a lattice that is not bounded.

Distributive lattice

A lattice is distributive if, for all a, b, c:

a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c), and equivalently a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c).

Power sets are distributive because union and intersection distribute over each other. D₁₂ is distributive too. Check one case with a = 4, b = 6, c = 3: the left side is gcd(4, lcm(6, 3)) = gcd(4, 6) = 2; the right side is lcm(gcd(4, 6), gcd(4, 3)) = lcm(2, 1) = 2. They match.

Counterexample: the diamond M₃ is not distributive

M₃ has five elements: a bottom 0, a top 1, and three incomparable middle elements a, b, c.

          1
        / | \
       a  b  c
        \ | /
          0

Any two different middle elements join to 1 and meet at 0. Now test the law:

• Left side: a ∧ (b ∨ c) = a ∧ 1 = a.
• Right side: (a ∧ b) ∨ (a ∧ c) = 0 ∨ 0 = 0.

Since a ≠ 0, M₃ is a lattice that is not distributive. The pentagon N₅ is the other standard non-distributive lattice, and a known theorem says a lattice is distributive exactly when it contains no sublattice shaped like M₃ or N₅.

Complemented lattice

In a bounded lattice, a complement of a is an element a′ with a ∨ a′ = 1 and a ∧ a′ = 0. The lattice is complemented if every element has at least one complement.

• P(S) is complemented: the complement of a subset is S minus that subset.
• D₁₂ is not complemented. 4 and 3 are complements (lcm 12, gcd 1), but 2 has none: the only x with gcd(2, x) = 1 are 1 and 3, and lcm(2, 1) = 2 and lcm(2, 3) = 6, neither of which is 12.
• M₃ is complemented, but a has two complements (b and c). In a distributive lattice a complement, when it exists, is unique.

A lattice that is both distributive and complemented is a Boolean algebra. The power set is the classic example, and so is D₃₀, the divisors of 30.

Part 2: Recurrence relations in brief

A recurrence relation expresses the n-th term of a sequence using one or more earlier terms, together with enough initial values to start it. The Fibonacci rule Fₙ = Fₙ₋₁ + Fₙ₋₂ with F₀ = 0, F₁ = 1 is the best-known example.

Linear homogeneous recurrences and the characteristic equation

A recurrence of the form aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + … + cₖaₙ₋ₖ, with constant coefficients and no extra term, is linear homogeneous of order k. Try aₙ = rⁿ, divide through, and you get the characteristic equation rᵏ − c₁rᵏ⁻¹ − … − cₖ = 0.

• Distinct roots r₁, r₂: aₙ = A·r₁ⁿ + B·r₂ⁿ.
• Repeated root r: aₙ = (A + Bn)·rⁿ.

The constants A and B come from the initial conditions.

Solved example: aₙ = 5aₙ₋₁ − 6aₙ₋₂, with a₀ = 1, a₁ = 4

1. Characteristic equation: r² − 5r + 6 = 0, which factors as (r − 2)(r − 3) = 0. Roots: r = 2 and r = 3.
2. General solution: aₙ = A·2ⁿ + B·3ⁿ.
3. n = 0: A + B = 1. n = 1: 2A + 3B = 4.
4. Subtract twice the first equation from the second: B = 2, so A = −1.
5. Solution: aₙ = 2·3ⁿ − 2ⁿ.

Check: from the recurrence, a₂ = 5(4) − 6(1) = 14 and a₃ = 5(14) − 6(4) = 46. From the formula, a₂ = 18 − 4 = 14 and a₃ = 54 − 8 = 46. Both agree.

Recurrences also describe the running time of recursive algorithms. Merge sort satisfies T(n) = 2T(n/2) + n, which solves to O(n log n); the recurrence relations study page covers non-homogeneous equations, generating functions and the substitution method in full, and asymptotic analysis explains the O-notation.

FAQs

What is a lattice in discrete mathematics?

A lattice is a partially ordered set in which every pair of elements has both a least upper bound (join, a ∨ b) and a greatest lower bound (meet, a ∧ b). The divisors of 12 under divisibility, with join = LCM and meet = GCD, form a lattice.

What is the difference between a poset and a lattice?

Every lattice is a poset, but a poset is a lattice only if every pair has a join and a meet. {1, 2, 3} under divisibility is a poset but not a lattice, because 2 and 3 have no upper bound in the set.

Why is the diamond lattice M₃ not distributive?

For its three middle elements a, b, c, a ∧ (b ∨ c) = a ∧ 1 = a, while (a ∧ b) ∨ (a ∧ c) = 0 ∨ 0 = 0. The two sides differ, so the distributive law fails.

What is a Boolean algebra in lattice terms?

A Boolean algebra is a lattice that is bounded, distributive and complemented. The power set of any set under ⊆ is the standard example.

How do you solve a linear homogeneous recurrence relation?

Write the characteristic equation, find its roots, write the general solution (A·r₁ⁿ + B·r₂ⁿ for distinct roots, (A + Bn)rⁿ for a repeated root), then use the initial values to find the constants. For aₙ = 5aₙ₋₁ − 6aₙ₋₂ with a₀ = 1, a₁ = 4, the answer is aₙ = 2·3ⁿ − 2ⁿ.

Related Topics on EngineeringHulk

• 👉 Classification of Computers
• 👉 Father of Computer Science
• 👉 Classifications of DBMS
• 👉 Graph Theory
• 👉 Recurrence Relations Generating Functions
• 👉 Dynamic Programming Complete Guide
• 👉 Sets, Relations & Functions
• 👉 Discrete Mathematics — Complete Formula Sheet
• 👉 Functions and Recursion in C — Complete Guide
• 👉 Combinatorics — Counting, Permutations, Combinations &
• 👉 Divide & Conquer