Partial Order

We call a relation a partial order (in English: partial order) if three properties are satisfied: reflexive, antisymmetric, and transitive. This combination ensures that the relation creates an 'ordered' structure, although not necessarily a total order.

Formal Definition

Reflexive: every element is related to itself.

Antisymmetric: if one element is related to another and vice versa, then they are equal.

Transitive: if a is related to b and b to c, then a is related to c.

Examples of Partial Orders

• The ≤ relation on integers: reflexive, antisymmetric, transitive.
• The divisibility relation on natural numbers: reflexive, antisymmetric, transitive.
• The subset relation ⊆ on sets: reflexive, antisymmetric, transitive.

Counterexamples (Non-Partial Orders)

• The < relation: not reflexive (no number is less than itself).
• The friend of relation among people: not antisymmetric (if A is friend of B and B of A, they are still different people).
• The sibling of relation among people: not antisymmetric (siblings are different people).

Partially Ordered Set (Poset)

A set with a partial order is called a partially ordered set (poset). In a poset, not every pair of elements needs to be comparable, but where they are, the relation shows ordered behavior.

For example, in the subset relation, {1,2} and {2,3} sets cannot be compared because neither is a subset of the other. Therefore, the structure is 'partially' ordered, not completely.

Summary

A partial order is thus a relation that is reflexive, antisymmetric, and transitive. This combination allows us to establish a partial ordering among the elements of the set, which is a basic concept in many mathematical and computer science areas (e.g., graphs, hierarchies, data structures).

Practice Exercise