# Posets, Lattices, Boolean Algebra and Groups — Hasse Diagrams, LUB/GLB and Algebraic Structures

Source: https://skills101.in/learn/discrete-math/posets-lattices-groups — Skills101 free tutorial (Discrete Mathematics). Updated 2026-11-09.

This lesson covers the "structures" part of discrete maths: ways to **order** things that aren't simply in a line (task dependencies, versions, sets), and sets with **operations** that behave nicely (the algebra behind cryptography, error-correcting codes and circuits). These topics are regular in GATE and university papers.

## 1. Partially ordered sets (posets)

A **partial order** ≤ on a set is **reflexive, antisymmetric and transitive** (lesson 1). "Partial" because some pairs may be **incomparable**.

Examples: "divides" on {1, 2, 3, 4, 6, 12}; ⊆ on subsets; "must finish before" on tasks. With "divides", 4 and 6 are incomparable (neither divides the other).

A **total order** (chain) compares every pair — like ≤ on numbers.

## 2. Hasse diagrams

Draw the poset without clutter:

- put smaller elements **lower**;
- draw an edge only for **covering** relations (a < b with nothing in between);
- omit self-loops and edges implied by transitivity.

![Hasse diagram of the divisors of 12 under divides: 1 at the bottom, 2 and 3 above it, 4 and 6 above those, 12 at the top; 4 and 6 are incomparable, 12 is the greatest element and 1 the least](https://skills101.in/learn-img/discrete-math/hasse-12.svg)

```python
D = [1, 2, 3, 4, 6, 12]
leq = lambda a, b: b % a == 0          # a "divides" b

covers = [(a, b) for a in D for b in D
          if a != b and leq(a, b) and not any(c not in (a, b) and leq(a, c) and leq(c, b) for c in D)]
print("Hasse edges:", covers)
print("incomparable pairs:", [(a, b) for i, a in enumerate(D) for b in D[i + 1:] if not leq(a, b) and not leq(b, a)])
```

```text
Hasse edges: [(1, 2), (1, 3), (2, 4), (2, 6), (3, 6), (4, 12), (6, 12)]
incomparable pairs: [(2, 3), (3, 4), (4, 6)]
```

## 3. Special elements and bounds

| Term | Meaning (in the divisors-of-12 poset) |
|---|---|
| **Maximal** | nothing above it → 12 |
| **Minimal** | nothing below it → 1 |
| **Greatest (top)** | above everything → 12 |
| **Least (bottom)** | below everything → 1 |
| **Upper bound** of {a, b} | anything ≥ both |
| **LUB / join (a ∨ b)** | the smallest upper bound → here **lcm** |
| **GLB / meet (a ∧ b)** | the largest lower bound → here **gcd** |

Maximal ≠ greatest: in {2, 3, 4} under divides, 3 and 4 are both maximal, but there's no greatest element.

## 4. Lattices

A **lattice** is a poset in which **every pair** has both a LUB and a GLB. Divisors of n under "divides" always form a lattice (join = lcm, meet = gcd). The power set under ⊆ is a lattice (join = ∪, meet = ∩).

```python
from math import gcd

D = [1, 2, 3, 4, 6, 12]
lcm = lambda a, b: a * b // gcd(a, b)
print("join(4, 6) = lcm =", lcm(4, 6), "| meet(4, 6) = gcd =", gcd(4, 6))
print("is a lattice:", all(lcm(a, b) in D and gcd(a, b) in D for a in D for b in D))

S = [1, 2, 3, 4, 6]          # remove 12: is it still a lattice?
print("without 12 is a lattice:", all(lcm(a, b) in S for a in S for b in S), "(4 and 6 have no join)")
```

```text
join(4, 6) = lcm = 12 | meet(4, 6) = gcd = 2
is a lattice: True
without 12 is a lattice: False (4 and 6 have no join)
```

Special lattices you'll meet: **bounded** (has top and bottom), **distributive**, **complemented** (every element a has a′ with a ∨ a′ = top and a ∧ a′ = bottom). A lattice that is both distributive and complemented is a **Boolean algebra** — the power set of a set is the classic example, and **Boolean algebra of bits** (∨ = OR, ∧ = AND, ′ = NOT) is the foundation of digital circuits (COA track).

## 5. Algebraic structures

A set with an operation `*`:

| Structure | Closure | Associative | Identity | Inverses | Commutative |
|---|---|---|---|---|---|
| Semigroup | ✓ | ✓ | | | |
| Monoid | ✓ | ✓ | ✓ | | |
| **Group** | ✓ | ✓ | ✓ | ✓ | |
| **Abelian group** | ✓ | ✓ | ✓ | ✓ | ✓ |

![Ladder of algebraic structures: a closed associative operation makes a semigroup; add an identity to get a monoid; add inverses to get a group; add commutativity to get an abelian group](https://skills101.in/learn-img/discrete-math/algebraic-structures.svg)

Examples:
- (strings, concatenation) → **monoid** (identity = empty string; no inverses).
- (integers, +) → **abelian group** (identity 0, inverse −a).
- ({0, 1, 2, 3, 4}, + mod 5) → abelian group.
- ({1, 2, 3, 4}, × mod 5) → abelian group (5 is prime, so every element has an inverse).
- ({1, 2, 3}, × mod 4) → **not** closed (2 × 2 = 0).

Let's check the group axioms automatically:

```python
from itertools import product

def check(S, op):
    closure = all(op(a, b) in S for a, b in product(S, S))
    assoc = closure and all(op(op(a, b), c) == op(a, op(b, c)) for a, b, c in product(S, S, S))
    identity = next((e for e in S if all(op(e, a) == a == op(a, e) for a in S)), None)
    inverses = identity is not None and all(any(op(a, b) == identity for b in S) for a in S)
    commutative = all(op(a, b) == op(b, a) for a, b in product(S, S))
    kind = ("abelian group" if inverses and commutative else "group" if inverses else
            "monoid" if identity is not None and assoc else "semigroup" if assoc else "not even a semigroup")
    return f"closed={closure} identity={identity} -> {kind}"

print("Z5 under + mod 5   :", check([0, 1, 2, 3, 4], lambda a, b: (a + b) % 5))
print("{1..4} under x mod 5:", check([1, 2, 3, 4], lambda a, b: a * b % 5))
print("{0..3} under x mod 4:", check([0, 1, 2, 3], lambda a, b: a * b % 4))
print("{1,2,3} under x mod 4:", check([1, 2, 3], lambda a, b: a * b % 4))
```

```text
Z5 under + mod 5   : closed=True identity=0 -> abelian group
{1..4} under x mod 5: closed=True identity=1 -> abelian group
{0..3} under x mod 4: closed=True identity=1 -> monoid
{1,2,3} under x mod 4: closed=False identity=1 -> not even a semigroup
```

## 6. Cyclic groups and subgroups

- **Order of a group** = number of elements; **order of an element** a = smallest k with aᵏ = identity.
- A group is **cyclic** if one element (a **generator**) produces all elements by repeated operation. (Z₅, +) is cyclic, generated by 1 (or 2, 3, 4).
- **Lagrange's theorem:** the order of any subgroup **divides** the order of the group. So a group of prime order has no non-trivial subgroups and is cyclic.

These ideas power cryptography: Diffie–Hellman key exchange and elliptic-curve crypto (used in UPI and HTTPS) work inside large cyclic groups.

## Common mistakes

- Drawing transitive edges in a Hasse diagram.
- Confusing maximal (nothing above) with greatest (above everything).
- Calling a monoid a group without checking that **every** element has an inverse.
- Forgetting to check closure first.

## Quick recap

- Poset = reflexive + antisymmetric + transitive; Hasse diagram shows only covering edges.
- LUB = join, GLB = meet (for divisibility: lcm and gcd); lattice = every pair has both.
- Boolean algebra = complemented distributive lattice.
- Semigroup ⊂ monoid ⊂ group ⊂ abelian group (closure, associativity, identity, inverses, commutativity).
- Cyclic groups have a generator; Lagrange: subgroup order divides group order.


Practice quiz and free certificate: https://skills101.in/learn/discrete-math/posets-lattices-groups