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
- “Equivalence Relation,” in Wikipedia, July 21, 2024, https://en.wikipedia.org/w/index.php?title=Equivalence_relation.
- Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
- John B. Fraleigh, A First Course in Abstract Algebra, Seventh edition, Pearson new international edition (Harlow: Pearson, 2014).
- “Partially Ordered Set,” in Wikipedia, June 22, 2024, https://en.wikipedia.org/w/index.php?title=Partially_ordered_set.
- “Partition of a Set,” in Wikipedia, June 18, 2024, https://en.wikipedia.org/w/index.php?title=Partition_of_a_set.
- “Preorder,” in Wikipedia, July 21, 2024, https://en.wikipedia.org/w/index.php?title=Preorder.
- “Total Order.” In Wikipedia, April 9, 2024. https://en.wikipedia.org/w/index.php?title=Total_order.