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 ${\displaystyle \leq }$ and an ordered set is denoted by the ordered pair ${\displaystyle (S,\leq )}$ where ${\displaystyle \leq }$ 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 ${\displaystyle a\leq b}$ or ${\displaystyle b\leq 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 ${\displaystyle (S,\leq )}$ be a preordered set and let ${\displaystyle T}$ be a subset of ${\displaystyle S}$. If there exists an element ${\displaystyle u}$ in ${\displaystyle S}$ such that ${\displaystyle x\leq u}$ for all ${\displaystyle x\in T}$, then ${\displaystyle u}$ is called an upper bound for ${\displaystyle T}$. Similarly, if there exists an element ${\displaystyle l}$ in ${\displaystyle S}$ such that ${\displaystyle l\leq x}$ for all ${\displaystyle x\in T}$ then ${\displaystyle l}$ is a lower bound for ${\displaystyle 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 ${\displaystyle (P,\leq )}$ be a partially ordered set and let ${\displaystyle T}$ be a subset of ${\displaystyle P}$. If an element ${\displaystyle u\in P}$ is an upper bound for ${\displaystyle T}$ and if ${\displaystyle u\leq z}$ whenever ${\displaystyle z}$ is an upper bound for ${\displaystyle T}$ then ${\displaystyle u}$ is called the least upper bound or supremum of ${\displaystyle T}$. Similarly, a lower bound of ${\displaystyle T}$ that is greater than or equal to every other lower bound for ${\displaystyle T}$ is the greatest lower bound or infimum of ${\displaystyle 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 ${\displaystyle (P,\leq )}$ be a partially ordered set and ${\displaystyle T}$ be a subset of ${\displaystyle P}$. A maximal element of ${\displaystyle T}$ is any element ${\displaystyle m}$ such that if ${\displaystyle m\leq a}$ then ${\displaystyle m=a}$ for all ${\displaystyle a\in T}$. If the inequality in the previous sentence is reversed, then the element is called a minimal element. If ${\displaystyle t\in T}$ is greater than every other element in ${\displaystyle T}$, then ${\displaystyle 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 ${\displaystyle \sim }$ or ${\displaystyle \equiv }$. A set equipped with an equivalence relation is also known as a setoid.

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

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

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

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