Course contentsShow
← Mathematics
Lesson 2546 of 3,12151. Discrete Math — Sets, Relations, FunctionsFree lesson

Combining Properties: Partial Orders

Define partial orders as reflexive, antisymmetric, and transitive relations and explore examples like divisibility and subset relations.

Combining Properties: Partial Orders

What You'll Learn

You'll learn how partial orders combine reflexivity, antisymmetry, and transitivity to create ordering structures that appear throughout mathematics.

The Core Idea

A partial order is a special type of relation that satisfies three properties simultaneously:

  1. Reflexive: Every element is related to itself (a ≤ a)
  2. Antisymmetric: If a ≤ b and b ≤ a, then a = b
  3. Transitive: If a ≤ b and b ≤ c, then a ≤ c

The word "partial" means that not every pair of elements needs to be comparable—some elements might be incomparable to each other. This contrasts with "total orders" (like regular ≤ on real numbers) where you can compare any two elements.

Classic Examples

The Divisibility Relation

On the set of positive integers, define a | b (read "a divides b") if there exists an integer k such that b = ak.

  • Reflexive: n | n because n = n·1
  • Antisymmetric: If a | b and b | a, then a = b (for positive integers)
  • Transitive: If a | b and b | c, then a | c

Notice that 3 and 5 are incomparable under divisibility—neither divides the other.

The Subset Relation

On a power set P(S), the relation ⊆ is a partial order:

  • Reflexive: A ⊆ A for any set A
  • Antisymmetric: If A ⊆ B and B ⊆ A, then A = B
  • Transitive: If A ⊆ B and B ⊆ C, then A ⊆ C

Sets like {1, 2} and {3, 4} are incomparable—neither is a subset of the other.

Why "Partial Orders" Matter

Partial orders model hierarchies, dependencies, and comparison structures where not everything needs to be directly comparable. They appear in task scheduling, type systems, taxonomy, and countless other domains.

Key Takeaway: A partial order is a reflexive, antisymmetric, and transitive relation that creates a hierarchy where some elements may be incomparable—like divisibility among integers or subset relationships among sets.