Overview

An order refers to a binary relation that defines how elements of a set relate to one another in terms of “less than”, “equal to”, or “greater than”.

Preorders

A binary relation on set is a preorder on iff it is reflexive on and transitive.

A binary relation on set is a strict preorder on iff it is irreflexive on and transitive.

Partial Orders

A binary relation on set is a partial order on iff it is reflexive on , antisymmetric, and transitive. In other words, a partial order is an antisymmetric preorder.

A binary relation on set is a strict partial order on iff it is irreflexive on , antisymmetric, and transitive.

Equivalence Relations

A binary relation on set is an equivalence relation on iff it is reflexive on , symmetric, and transitive. In other words, an equivalence relation is a symmetric preorder.

Equivalence Classes

The set is defined by . If is an equivalence relation and , then is called the equivalence class of (modulo ). If the relation is fixed by the context, we just write .

Partitions

A partition of a set is a set of nonempty subsets of that is disjoint and exhaustive.

Assume is a partition of set . Then the relation is an equivalence relation:

Quotient Sets

If is an equivalence relation on , then the quotient set modulo ” is defined as

The natural map (or canonical map) is given by

Note that , the set of all equivalence classes, is a partition of .

Total Order

A binary relation on set is a total order on iff it is reflexive on , antisymmetric, transitive, and strongly connected. In other words, a total order is a strongly connected partial order.

A binary relation on set is a strict total order on iff it is irreflexive on , antisymmetric, transitive, and connected. In other words, a strict total order is a connected strict partial order.

Bibliography