# 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 $\leq$  and an ordered set is denoted by the ordered pair $(S,\leq )$  where $\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 $a\leq b$  or $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 $(S,\leq )$  be a preordered set and let $T$  be a subset of $S$ . If there exists an element $u$  in $S$  such that $x\leq 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\leq 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,\leq )$  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\leq 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,\leq )$  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\leq 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.