# 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