6.8 Partial orders (optional)

This is optional material

This page is optional material, provided for those who might be interested in fuller details. Feel free to skip ahead.

Introduction and example

A partial order is a relation between elements of a set. You already know an instance of a partial order, namely ≤ on numbers. For example:

  • 1 ≤ 2
  • 2 ≤ 4
  • 1 ≤ 4
  • 2 ≤ 2

The three axioms defining partial orders

In the following, think of a, b, and c as natural numbers. Then think of the following three axioms in terms of natural numbers:

  1. A partial order operator is reflexive:

    For all a: a ≤ a. (Reflexivity)

    For example, 2 ≤ 2.

  2. A partial order operator is transitive:

    For all a,b,c: If a ≤ b and b ≤ c, then a ≤ c. (Transitivity)

    For example, since 1 ≤ 2 and 2 ≤ 4, it is also true that 1 ≤ 4.

  3. A partial order operator is antisymmetric:

    For all a,b: If a ≤ b and a ≥ b, then a = b. (Antisymmetry)

    For example, since 2 ≤ 2 and 2 ≥ 2, it is also true that 2 = 2.

Application to subtype relation

All of these axioms are satisfied by every partial order. Since the subtype relation on a type hierarchy is a partial order, these axioms are also satisfied by the subtype relation.

For example, "Animate ≥ Bird", since Bird is a subtype of Animate. The three axioms above apply as follows:

  1. Reflexivity: "Bird ≤ Bird".
  2. Transitivity: Since "Penguin ≤ Bird" and "Bird ≤ Animal", it follows that "Penguin ≤ Animal".
  3. Antisymmetry: Since "Bird ≤ Bird" and "Bird ≥ Bird", it follows that "Bird = Bird".


Prev: 6.7 Quiz: Types
Up: 6 Core ontological ideas
Next: 7 Lambda expressions