Partially Ordered Set — Definition, Formula & Examples

A partially ordered set (poset) is a set paired with a binary relation that lets you compare some, but not necessarily all, pairs of elements in a consistent way. The relation must be reflexive, antisymmetric, and transitive.

A partially ordered set is an ordered pair $(S, \leq)$ where $S$ is a set and $\leq$ is a binary relation on $S$ satisfying three axioms for all $a, b, c \in S$ : (1) reflexivity: $a \leq a$ ; (2) antisymmetry: if $a \leq b$ and $b \leq a$ , then $a = b$ ; (3) transitivity: if $a \leq b$ and $b \leq c$ , then $a \leq c$ .

How It Works

To verify that a set with a relation forms a poset, check each of the three axioms. Reflexivity means every element relates to itself. Antisymmetry means two distinct elements cannot each be related to the other. Transitivity means the relation chains: if

a

relates to

b

and

b

relates to

c

, then

a

relates to

c

. Unlike a totally ordered set, a poset may have incomparable elements — pairs where neither

a \leq b

nor

b \leq a

holds.

Worked Example

Problem: Let

S = \{1, 2, 3, 6\}

with the relation

a \mid b

(a divides b). Show that

(S, \mid)

is a partially ordered set and identify a pair of incomparable elements.

Step 1: Reflexivity: Every element divides itself:

1\mid1

2\mid2

3\mid3

6\mid6

. Reflexivity holds.

a \mid a \text{ for all } a \in S

Step 2: Antisymmetry: If

a \mid b

and

b \mid a

for positive integers, then

a = b

. For instance,

2 \mid 6

but

6 \nmid 2

, so no contradiction arises. Antisymmetry holds.

a \mid b \text{ and } b \mid a \implies a = b

Step 3: Transitivity: If

a \mid b

and

b \mid c

, then

a \mid c

. For example,

1 \mid 2

and

2 \mid 6

, so

1 \mid 6

. Transitivity holds.

a \mid b \text{ and } b \mid c \implies a \mid c

Step 4: Incomparable pair: Consider

2

and

3

2 \nmid 3

and

3 \nmid 2

, so they are incomparable. This confirms the order is partial, not total.

Answer:

(\{1,2,3,6\}, \mid)

is a poset. The elements

2

and

3

are incomparable.

Why It Matters

Posets appear throughout computer science and mathematics — task scheduling uses them to model dependency ordering, and lattice theory in abstract algebra builds directly on poset structure. In discrete math courses, understanding posets is essential for topics like Hasse diagrams, topological sorting, and the study of Boolean algebras.

Common Mistakes

Mistake: Assuming every two elements in a poset are comparable.

Correction: A poset only requires the relation to satisfy reflexivity, antisymmetry, and transitivity. Some pairs may be incomparable. A poset where every pair is comparable is a special case called a totally ordered set (or chain).