HomeContents: |
## 6.8 Partial orders (optional)## This is optional materialThis page is optional material, provided for those who might be interested in fuller details. Feel free to skip ahead. ## Introduction and exampleA 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 ordersIn the following, think of a, b, and c as natural numbers. Then think of the following three axioms in terms of natural numbers: - A partial order operator is
*reflexive*:*For all a: a ≤ a.*(Reflexivity)For example, 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. - 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 relationAll 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: *Reflexivity:*"Bird ≤ Bird".*Transitivity:*Since "Penguin ≤ Bird" and "Bird ≤ Animal", it follows that "Penguin ≤ Animal".*Antisymmetry:*Since "Bird ≤ Bird" and "Bird ≥ Bird", it follows that "Bird = Bird".
Prev: 6.7 Quiz: TypesUp: 6 Core ontological ideasNext: 7 Lambda expressions |