Set Theory/Orderings

Orderings

Definitions

Relations with certain properties that impose a notion of order on a set are known as order relations or simply orderings. For the following definitions, let R be a binary relation.

• If R is reflexive and transitive, then it is known as a preorder.
• If R is a preorder and also antisymmetric, then it is known as a partial order.
• If R is a partial order and also total, then it is known as a total order or a linear order.

A set equipped with a preorder, partial order, or total order is known as a preordered set, partially ordered set (or poset), or totally ordered set (or linearly ordered set) respectively. An order relation is usually denoted by the symbol $\le$ and an ordered set is denoted by the ordered pair $( S , \le )$ where $\le$ is the order relation on S.

A totally ordered subset of a partially ordered set is known as a chain. For this reason, any totally ordered set may sometimes be referred to as a chain.

Two elements a and b in a preordered (and thus in a partially or totally ordered) set are called comparable if either $a \le b$ or $b \le a$. Note that while totality guarantees that every two elements in a totally ordered set are comparable, two elements in a pre or partially ordered set may not be so.

Bounds

Let $(S, \le)$ be a preordered set and let $T$ be a subset of $S$. If there exists an element $u$ in $S$ such that $x \le u$ for all $x \in T$, then $u$ is called an upper bound for $T$. Similarly, if there exists an element $l$ in $S$ such that $l \le x$ for all $x \in T$ then $l$ is a lower bound for $T$. If there exists an upper bound for a set then that set is said to be bounded above, or similarly if there is a lower bound then the set is bounded below.

Let $(P, \le)$ be a partially ordered set and let $T$ be a subset of $P$. If an element $u \in P$ is an upper bound for $T$ and if $u \le z$ whenever $z$ is an upper bound for $T$ then $u$ is called the least upper bound or supremum of $T$. Similarly, a lower bound of $T$ that is greater than or equal to every other lower bound for $T$ is the greatest lower bound or infimum of $T$. The following proposition states that we are justified in calling these elements the supremum or infimum rather than just a supremum or infimum. The proof is left to the reader.

Proposition: The supremum and infimum of a set are each unique.

Let $(P, \le)$ be a partially ordered set and $T$ be a subset of $P$. A maximal element of $T$ is any element $m$ such that if $m \le a$ then $m = a$ for all $a \in T$. If the inequality in the previous sentence is reversed, then the element is called a minimal element. If $t \in T$ is greater than every other element in $T$, then $t$ is the greatest element or maximum, and similarly if it is less than every other element it is the least element or minimum. Note that an element of a partially ordered set can be a maximal element while failing to be a maximum since not all elements of a partially ordered set may be comparable.

Equivalences

Another important type of relation is the equivalence relation. This is a relation R that is reflexive, symmetric, and transitive (or, simply a preorder that is also symmetric). When R is an equivalence relation, we usually denote it by $\sim$ or $\equiv$. A set equipped with an equivalence relation is also known as a setoid.

If $\sim$ is an equivalence relation on a set $S$, we define for an element $s \in S$ the equivalence class of $s$ as $\{a \in S : a \sim s\}$. This is usually denoted by $[s]$. The set of all equivalence classes of $S$ is known as the quotient set of $S$ by $\sim$, which we denote by $S/\!\sim\ = \{[x] : x \in S\}$.

A partition of a set $S$ is a family of sets $\mathfrak{S}$ such that $\mathfrak{S}$ is pairwise disjoint and $\bigcup \mathfrak{S} = S$. The proof of the following theorems about equivalence relations are left to the reader.

Theorem: If $S$ is a set and $\sim$ is an equivalence relation on $S$, then $S/\!\sim$ is a partition of $S$.

Theorem: Let $S$ be a set and $P$ a partition of $S$. Define a relation $\star$ such that for $a, b \in S$, $a \star b$ holds if and only if there exists a member of P which contains both $a$ and $b$. Then, $\star$ is an equivalence relation.