Order

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 $R$ on set $A$ is a preorder on $A$ iff it is reflexive on $A$ and transitive.

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

Partial Orders

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

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

Equivalence Relations

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

Equivalence Classes

The set $[x{]}_R$ is defined by $[x{]}_R=\{t\mid xRt\}$. If $R$ is an equivalence relation and $x\in \mathrm{fld}R$, then $[x{]}_R$ is called the equivalence class of $x$ (modulo $R$). If the relation $R$ is fixed by the context, we just write $[x]$.

Partitions

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

Assume $\Pi$ is a partition of set $A$. Then the relation $R$ is an equivalence relation: $xRy\iff (\exists B\in \Pi ,x\in B\wedge y\in B)$

Quotient Sets

If $R$ is an equivalence relation on $A$, then the quotient set ”$A$ modulo $R$” is defined as $A/R=\{[x{]}_R\mid x\in A\}.$

The natural map (or canonical map) $\varphi :A\to A/R$ is given by $\varphi (x)=[x{]}_R.$

Note that $A/R$, the set of all equivalence classes, is a partition of $A$.

Total Order

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

A binary relation $R$ on set $A$ is a strict total order on $A$ iff it is irreflexive on $A$, 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.