Partial Orders

students, today you will learn how to describe situations where some things can be compared, but not always in a single line from smallest to largest. Think about folders inside folders 💻, tasks that must happen before others, or students sorted by prerequisites in school. These are all examples of partial orders.

Learning objectives

By the end of this lesson, you should be able to:

Explain the main ideas and terminology behind partial orders.
Use discrete mathematics reasoning to test whether a relation is a partial order.
Connect partial orders to sets, relations, and the broader study of discrete mathematics.
Describe real-world examples of partial orders.

Partial orders are important because they show how a set can be organized when not every pair of objects is directly comparable. This makes them useful in computer science, scheduling, databases, and many other areas ⚙️

What is a partial order?

A partial order is a relation on a set that satisfies three important properties:

Reflexive: every element is related to itself.
Antisymmetric: if one element is related to another and the second is related to the first, then the two elements must be the same.
Transitive: if one element is related to a second, and the second is related to a third, then the first is related to the third.

If a relation $R$ on a set $A$ has all three properties, then $R$ is called a partial order on $A$.

A common notation for a partial order is $\leq$, but many other symbols can be used depending on the context. For example, the relation "$\subseteq$" on sets is a partial order, and the relation "divides" on positive integers is also a partial order.

Why is it called “partial”?

It is called partial because not every pair of elements must be comparable. In a total order, like the usual order on numbers, any two numbers can be compared. In a partial order, this is not always true.

For example, consider the set of subsets of $\{1,2,3\}$ ordered by inclusion $\subseteq$. The sets $\{1\}$ and $\{2\}$ are not comparable, because neither $\{1\} \subseteq \{2\}$ nor $\{2\} \subseteq \{1\}$ is true.

The three properties in detail

1. Reflexive

A relation $R$ on a set $A$ is reflexive if every element is related to itself:

$$\forall a \in A,\; aRa$$

This means nothing in the set is left out of the relation with itself.

Example: For the relation $\leq$ on integers, we always have $a \leq a$.

Non-example: The relation $<$ is not reflexive, because $a < a$ is never true.

2. Antisymmetric

A relation $R$ on a set $A$ is antisymmetric if:

$$\forall a,b \in A,\; (aRb \land bRa) \rightarrow a=b$$

This does not mean the relation cannot go both ways. It means that if it does go both ways, then the two elements must actually be the same.

Example: For $\subseteq$, if $A \subseteq B$ and $B \subseteq A$, then $A=B$.

Non-example: The relation "is friends with" is often symmetric instead of antisymmetric, because if $A$ is friends with $B$, then $B$ is friends with $A$, even when $A \neq B$.

3. Transitive

A relation $R$ on a set $A$ is transitive if:

$$\forall a,b,c \in A,\; (aRb \land bRc) \rightarrow aRc$$

This property lets us move along a chain of relationships.

Example: If $2 \mid 6$ and $6 \mid 18$, then $2 \mid 18$.

Non-example: The relation "is a parent of" is not transitive. If Alice is a parent of Ben, and Ben is a parent of Cara, then Alice is a grandparent of Cara, not a parent.

Examples of partial orders

Example 1: The usual order on numbers

The relation $\leq$ on the set of integers $\mathbb{Z}$ is a partial order.

Reflexive: $a \leq a$
Antisymmetric: if $a \leq b$ and $b \leq a$, then $a=b$
Transitive: if $a \leq b$ and $b \leq c$, then $a \leq c$

This is also a total order, because any two integers can be compared.

Example 2: Set inclusion

The relation $\subseteq$ on the power set of a set is a partial order.

If the universal set is $U$, then the power set $\mathcal{P}(U)$ is the set of all subsets of $U$.

For any subsets $A,B,C \subseteq U$:

$A \subseteq A$ so it is reflexive.
If $A \subseteq B$ and $B \subseteq A$, then $A=B$.
If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.

This example is very important in discrete mathematics because it shows how sets can be arranged by containment.

Example 3: Divisibility

On the positive integers, define $aRb$ when $a \mid b$, meaning $a$ divides $b$.

This relation is a partial order because:

$a \mid a$ for every positive integer $a$.
If $a \mid b$ and $b \mid a$, then $a=b$ for positive integers.
If $a \mid b$ and $b \mid c$, then $a \mid c$.

For example, $2 \mid 6$ and $6 \mid 24$, so $2 \mid 24$.

This relation is not total. For example, $2$ and $3$ are not comparable, because neither $2 \mid 3$ nor $3 \mid 2$.

How to test whether a relation is a partial order

When you are given a relation, students, you can check it step by step.

Step 1: Check reflexive

Look at each element $a$ in the set and ask whether $aRa$ is true.

Step 2: Check antisymmetric

Look for pairs $a,b$ where both $aRb$ and $bRa$ are true. If this happens only when $a=b$, the relation passes.

Step 3: Check transitive

Look for chains $aRb$ and $bRc$. If every such chain implies $aRc$, the relation passes.

Example check

Suppose $A=\{1,2,3\}$ and the relation $R$ is defined by

$$R=\{(1,1),(2,2),(3,3),(1,2),(2,3),(1,3)\}$$

Reflexive? Yes, because $(1,1)$, $(2,2)$, and $(3,3)$ are all included.
Antisymmetric? Yes, because there is no pair like $(2,1)$ with $(1,2)$ unless the elements are the same.
Transitive? Yes, since $(1,2)$ and $(2,3)$ imply $(1,3)$, which is included.

So $R$ is a partial order.

Hasse diagrams and visualizing partial orders

A Hasse diagram is a drawing used to show a partial order more clearly. It removes repeated information and focuses on the most important connections.

In a Hasse diagram:

Higher positions represent “larger” elements in the order.
Edges are drawn only for immediate order relations, not for every transitive relation.
Loops are not drawn, because reflexivity is understood.

Example: divisibility on $\{1,2,3,6\}$

The order is based on divisibility:

$1 \mid 2$, $1 \mid 3$, and $1 \mid 6$
$2 \mid 6$
$3 \mid 6$

The Hasse diagram would place $1$ at the bottom, $6$ at the top, and $2$ and $3$ in the middle, each connected to $1$ and to $6$ through immediate steps.

Hasse diagrams are useful because they help you see the structure of a partial order quickly 👀

Partial orders in the bigger picture of discrete mathematics

Partial orders belong to the study of relations on sets. They are connected to many other ideas in discrete mathematics:

They are relations, so they use the language of ordered pairs and properties of relations.
They often appear with sets, especially set inclusion.
They are related to equivalence relations because both are special kinds of relations, but they behave differently.

An equivalence relation groups elements into classes of equal-type behavior, while a partial order organizes elements by comparison. In an equivalence relation, symmetry is essential; in a partial order, antisymmetry is essential.

This difference matters a lot. For example, "$a$ has the same parity as $b$" is an equivalence relation, but it is not a partial order. On the other hand, "$a \leq b$" is a partial order, but not an equivalence relation.

Conclusion

students, partial orders are a powerful way to describe structured relationships when some objects can be compared and others cannot. A relation is a partial order exactly when it is reflexive, antisymmetric, and transitive. Common examples include $\leq$, $\subseteq$, and divisibility. Partial orders help mathematicians and computer scientists organize information, build hierarchies, and solve real-world problems like scheduling and dependency tracking.

Study Notes

A partial order is a relation that is reflexive, antisymmetric, and transitive.
Reflexive means $\forall a \in A,\; aRa$.
Antisymmetric means $\forall a,b \in A,\; (aRb \land bRa) \rightarrow a=b$.
Transitive means $\forall a,b,c \in A,\; (aRb \land bRc) \rightarrow aRc$.
Examples of partial orders include $\leq$ on numbers, $\subseteq$ on sets, and divisibility $\mid$ on positive integers.
Partial orders are “partial” because not every pair of elements must be comparable.
A total order is a partial order where every pair is comparable.
Hasse diagrams help visualize partial orders by showing only the important comparison links.
Partial orders are part of the broader study of relations in discrete mathematics.
Equivalence relations and partial orders are different: equivalence relations use symmetry, while partial orders use antisymmetry.