# Set Theory/Orderings

## OrderingsEdit

### DefinitionsEdit

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.

### BoundsEdit

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.

## EquivalencesEdit

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.