Partially Ordered Sets and Lattices: The Combinatorics of Order

We develop the theory of partially ordered sets (posets), including Hasse diagrams, chains and antichains, and prove Dilworth's theorem and Mirsky's theorem. We then introduce lattices and the M\"obius function of the incidence algebra.

Folio Official

March 1, 2026

1 Fundamentals of Partially Ordered Sets

Definition 1 (Partially ordered set).

A binary relation

\leq

on a set

P

is a partial order if it satisfies the following three axioms:

Reflexivity: $x \leq x$ for all $x \in P$ .
Antisymmetry: if $x \leq y$ and $y \leq x$ , then $x = y$ .
Transitivity: if $x \leq y$ and $y \leq z$ , then $x \leq z$ .

The pair

(P, \leq)

is called a partially ordered set (or poset).

Definition 2 (Covering relation).

We say that

y

covers

x

, written

x ⋖ y

, if

x < y

and there is no element

z

with

x < z < y

Definition 3 (Hasse diagram).

The Hasse diagram of a finite poset

(P, \leq)

is the graph whose vertices are the elements of

P

, with an upward edge from

x

y

whenever

x ⋖ y

Example 4.

Consider

P = {1, 2, 3, 6, 12}

partially ordered by divisibility (

a ∣ b

). The covering relations are

1 ⋖ 2

1 ⋖ 3

2 ⋖ 6

3 ⋖ 6

, and

6 ⋖ 12

2 Chains and Antichains

Definition 5 (Chain and antichain).

A subset

C

of a poset

P

is a chain if every two elements of

C

are comparable (i.e.,

x \leq y

y \leq x

). A subset

A

is an antichain if no two distinct elements of

A

are comparable.

Definition 6.

The height of a poset

P

is the length of its longest chain (measured as the number of elements minus one). The width of

P

is the maximum size of an antichain.

3 Dilworth's Theorem

Theorem 7 (Dilworth's theorem).

Let

w

be the width (maximum antichain size) of a finite poset

P

. Then

P

can be partitioned into exactly

w

chains (and no fewer).

Proof.

Since a chain can contain at most one element from any antichain, at least

w

chains are needed. It remains to show that

w

chains suffice, which we prove by induction on

∣ P ∣

Base case. If

∣ P ∣ = 1

, then

w = 1

and

P

itself is a single chain.

Inductive step. Assume

∣ P ∣ \geq 2

and the theorem holds for all posets of smaller size. Fix a maximum antichain

A = {a_{1}, \dots, a_{w}}

and define

P^{+} = {x \in P ∣ \exists a \in A, x \geq a}, P^{-} = {x \in P ∣ \exists a \in A, x \leq a} .

(i) $P = P^{+} \cup P^{-}$ : Every

a \in A

belongs to both

P^{+}

and

P^{-}

(since

a \geq a

and

a \leq a

). If some

x \in P ∖ (P^{+} \cup P^{-})

existed, then

x

would be incomparable to every element of

A

, making

A \cup {x}

an antichain of size

w + 1

, contradicting the maximality of

A

(ii) $P^{+} ⊊ P$ and $P^{-} ⊊ P$ : If

P = A

(i.e.,

P

is itself an antichain), the partition into

w

single-element chains is immediate. Otherwise, elements in

P ∖ A

exist, and a careful analysis using minimal and maximal elements shows that neither

P^{+}

nor

P^{-}

equals all of

P

(iii) Constructing the partition: Since

∣ P^{+} ∣ < ∣ P ∣

and

∣ P^{-} ∣ < ∣ P ∣

, and both

P^{+}

and

P^{-}

have width

w

(the antichain

A

witnesses

w

in each, and they are subposets of

P

), the induction hypothesis provides partitions

C_{1}^{+}, \dots, C_{w}^{+}

P^{+}

and

C_{1}^{-}, \dots, C_{w}^{-}

P^{-}

into chains. Since

A

is an antichain, each

a_{i}

lies in a different chain of each partition. After relabeling,

a_{i} \in C_{i}^{+}

and

a_{i} \in C_{i}^{-}

Setting

C_{i} = C_{i}^{+} \cup C_{i}^{-}

for each

i

, every two elements of

C_{i}

are comparable via

a_{i}

(elements of

C_{i}^{+}

are

\geq a_{i}

and elements of

C_{i}^{-}

are

\leq a_{i}

), so

C_{i}

is a chain. Since

C_{i}^{+} \cap C_{i}^{-} = {a_{i}}

and

P = P^{+} \cup P^{-}

, the chains

C_{1}, \dots, C_{w}

form a partition of

P

. □

4 Mirsky's Theorem

Theorem 8 (Mirsky's theorem).

Let

ℓ

be the maximum length (number of elements) of a chain in a finite poset

P

. Then

P

can be partitioned into exactly

ℓ

antichains.

Proof.

For each

x \in P

, let

h (x)

denote the length of the longest chain ending at

x

. Define

A_{k} = {x \in P ∣ h (x) = k}

for

k = 1, \dots, ℓ

. The sets

A_{1}, \dots, A_{ℓ}

partition

P

. Each

A_{k}

is an antichain: if

x, y \in A_{k}

with

x < y

, then

h (y) \geq h (x) + 1 > k

, contradicting

y \in A_{k}

. □

5 Lattices

Definition 9 (Lattice).

A poset

(L, \leq)

is a lattice if every pair of elements

x, y

has a least upper bound (the join,

x \lor y

) and a greatest lower bound (the meet,

x \land y

Example 10.

The positive integers under divisibility form a lattice with

a \lor b = lcm (a, b)

and

a \land b = g cd (a, b)

. The power set

2^{S}

of a set

S

, ordered by inclusion, is a lattice with

A \lor B = A \cup B

and

A \land B = A \cap B

Definition 11 (Distributive lattice).

A lattice

L

is distributive if

x \land (y \lor z) = (x \land y) \lor (x \land z)

for all

x, y, z \in L

6 The Möbius Function and the Incidence Algebra

Definition 12 (M\"obius function of a poset).

The Möbius function

μ : P \times P \to Z

of a finite poset

P

is defined recursively by:

μ (x, x) = 1, x \leq z \leq y \sum μ (x, z) = 0 (x < y) .

Equivalently,

μ (x, y) = - \sum_{x \leq z < y} μ (x, z)

for

x < y

. When

x \neq \leq y

, we set

μ (x, y) = 0

Theorem 13 (M\"obius inversion on a poset).

Let

P

be a locally finite poset and let

f, g : P \to R

. Then

g (x) = y \leq x \sum f (y) ⟺ f (x) = y \leq x \sum μ (y, x) g (y) .

Proof.

Substitute

g (y) = \sum_{z \leq y} f (z)

into the right-hand side:

y \leq x \sum μ (y, x) z \leq y \sum f (z) = z \leq x \sum f (z) z \leq y \leq x \sum μ (y, x) .

When

z < x

, the inner sum

\sum_{z \leq y \leq x} μ (y, x) = 0

by the defining property of

μ

. When

z = x

, it equals

μ (x, x) = 1

. Therefore the entire expression simplifies to

f (x)

. □

Example 14.

For the poset

P = (Z_{> 0}, ∣)

(positive integers ordered by divisibility),

μ (d, n) = μ_{M \overset{o}{¨} bius} (n / d)

, where

μ_{M \overset{o}{¨} bius}

is the classical number-theoretic Möö

Combinatorics Discrete Mathematics Textbook Partially Ordered Sets Lattices

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Partially Ordered Sets and Lattices: The Combinatorics of Order

Folio Official

March 1, 2026

1 Fundamentals of Partially Ordered Sets

Definition 1 (Partially ordered set).

A binary relation

\leq

on a set

P

is a partial order if it satisfies the following three axioms:

Reflexivity: $x \leq x$ for all $x \in P$ .
Antisymmetry: if $x \leq y$ and $y \leq x$ , then $x = y$ .
Transitivity: if $x \leq y$ and $y \leq z$ , then $x \leq z$ .

The pair

(P, \leq)

is called a partially ordered set (or poset).

Definition 2 (Covering relation).

We say that

y

covers

x

, written

x ⋖ y

, if

x < y

and there is no element

z

with

x < z < y

Definition 3 (Hasse diagram).

The Hasse diagram of a finite poset

(P, \leq)

is the graph whose vertices are the elements of

P

, with an upward edge from

x

y

whenever

x ⋖ y

Example 4.

Consider

P = {1, 2, 3, 6, 12}

partially ordered by divisibility (

a ∣ b

). The covering relations are

1 ⋖ 2

1 ⋖ 3

2 ⋖ 6

3 ⋖ 6

, and

6 ⋖ 12

2 Chains and Antichains

Definition 5 (Chain and antichain).

A subset

C

of a poset

P

is a chain if every two elements of

C

are comparable (i.e.,

x \leq y

y \leq x

). A subset

A

is an antichain if no two distinct elements of

A

are comparable.

Definition 6.

The height of a poset

P

is the length of its longest chain (measured as the number of elements minus one). The width of

P

is the maximum size of an antichain.

3 Dilworth's Theorem

Theorem 7 (Dilworth's theorem).

Let

w

be the width (maximum antichain size) of a finite poset

P

. Then

P

can be partitioned into exactly

w

chains (and no fewer).

Proof.

Since a chain can contain at most one element from any antichain, at least

w

chains are needed. It remains to show that

w

chains suffice, which we prove by induction on

∣ P ∣

Base case. If

∣ P ∣ = 1

, then

w = 1

and

P

itself is a single chain.

Inductive step. Assume

∣ P ∣ \geq 2

and the theorem holds for all posets of smaller size. Fix a maximum antichain

A = {a_{1}, \dots, a_{w}}

and define

P^{+} = {x \in P ∣ \exists a \in A, x \geq a}, P^{-} = {x \in P ∣ \exists a \in A, x \leq a} .

(i) $P = P^{+} \cup P^{-}$ : Every

a \in A

belongs to both

P^{+}

and

P^{-}

(since

a \geq a

and

a \leq a

). If some

x \in P ∖ (P^{+} \cup P^{-})

existed, then

x

would be incomparable to every element of

A

, making

A \cup {x}

an antichain of size

w + 1

, contradicting the maximality of

A

(ii) $P^{+} ⊊ P$ and $P^{-} ⊊ P$ : If

P = A

(i.e.,

P

is itself an antichain), the partition into

w

single-element chains is immediate. Otherwise, elements in

P ∖ A

exist, and a careful analysis using minimal and maximal elements shows that neither

P^{+}

nor

P^{-}

equals all of

P

(iii) Constructing the partition: Since

∣ P^{+} ∣ < ∣ P ∣

and

∣ P^{-} ∣ < ∣ P ∣

, and both

P^{+}

and

P^{-}

have width

w

(the antichain

A

witnesses

w

in each, and they are subposets of

P

), the induction hypothesis provides partitions

C_{1}^{+}, \dots, C_{w}^{+}

P^{+}

and

C_{1}^{-}, \dots, C_{w}^{-}

P^{-}

into chains. Since

A

is an antichain, each

a_{i}

lies in a different chain of each partition. After relabeling,

a_{i} \in C_{i}^{+}

and

a_{i} \in C_{i}^{-}

Setting

C_{i} = C_{i}^{+} \cup C_{i}^{-}

for each

i

, every two elements of

C_{i}

are comparable via

a_{i}

(elements of

C_{i}^{+}

are

\geq a_{i}

and elements of

C_{i}^{-}

are

\leq a_{i}

), so

C_{i}

is a chain. Since

C_{i}^{+} \cap C_{i}^{-} = {a_{i}}

and

P = P^{+} \cup P^{-}

, the chains

C_{1}, \dots, C_{w}

form a partition of

P

. □

4 Mirsky's Theorem

Theorem 8 (Mirsky's theorem).

Let

ℓ

be the maximum length (number of elements) of a chain in a finite poset

P

. Then

P

can be partitioned into exactly

ℓ

antichains.

Proof.

For each

x \in P

, let

h (x)

denote the length of the longest chain ending at

x

. Define

A_{k} = {x \in P ∣ h (x) = k}

for

k = 1, \dots, ℓ

. The sets

A_{1}, \dots, A_{ℓ}

partition

P

. Each

A_{k}

is an antichain: if

x, y \in A_{k}

with

x < y

, then

h (y) \geq h (x) + 1 > k

, contradicting

y \in A_{k}

. □

5 Lattices

Definition 9 (Lattice).

A poset

(L, \leq)

is a lattice if every pair of elements

x, y

has a least upper bound (the join,

x \lor y

) and a greatest lower bound (the meet,

x \land y

Example 10.

The positive integers under divisibility form a lattice with

a \lor b = lcm (a, b)

and

a \land b = g cd (a, b)

. The power set

2^{S}

of a set

S

, ordered by inclusion, is a lattice with

A \lor B = A \cup B

and

A \land B = A \cap B

Definition 11 (Distributive lattice).

A lattice

L

is distributive if

x \land (y \lor z) = (x \land y) \lor (x \land z)

for all

x, y, z \in L

6 The Möbius Function and the Incidence Algebra

Definition 12 (M\"obius function of a poset).

The Möbius function

μ : P \times P \to Z

of a finite poset

P

is defined recursively by:

μ (x, x) = 1, x \leq z \leq y \sum μ (x, z) = 0 (x < y) .

Equivalently,

μ (x, y) = - \sum_{x \leq z < y} μ (x, z)

for

x < y

. When

x \neq \leq y

, we set

μ (x, y) = 0

Theorem 13 (M\"obius inversion on a poset).

Let

P

be a locally finite poset and let

f, g : P \to R

. Then

g (x) = y \leq x \sum f (y) ⟺ f (x) = y \leq x \sum μ (y, x) g (y) .

Proof.

Substitute

g (y) = \sum_{z \leq y} f (z)

into the right-hand side:

y \leq x \sum μ (y, x) z \leq y \sum f (z) = z \leq x \sum f (z) z \leq y \leq x \sum μ (y, x) .

When

z < x

, the inner sum

\sum_{z \leq y \leq x} μ (y, x) = 0

by the defining property of

μ

. When

z = x

, it equals

μ (x, x) = 1

. Therefore the entire expression simplifies to

f (x)

. □

Example 14.

For the poset

P = (Z_{> 0}, ∣)

(positive integers ordered by divisibility),

μ (d, n) = μ_{M \overset{o}{¨} bius} (n / d)

, where

μ_{M \overset{o}{¨} bius}

is the classical number-theoretic Möö

Combinatorics Discrete Mathematics Textbook Partially Ordered Sets Lattices

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Partially Ordered Sets and Lattices: The Combinatorics of Order

1 Fundamentals of Partially Ordered Sets

2 Chains and Antichains

3 Dilworth's Theorem

4 Mirsky's Theorem

5 Lattices

6 The Möbius Function and the Incidence Algebra

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

Partially Ordered Sets and Lattices: The Combinatorics of Order

1 Fundamentals of Partially Ordered Sets

2 Chains and Antichains

3 Dilworth's Theorem

4 Mirsky's Theorem

5 Lattices

6 The Möbius Function and the Incidence Algebra

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry