# Set Theory/Orderings

## Orderings

edit### Definitions

editRelations 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 and an ordered set is denoted by the ordered pair where 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 or . 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

editLet be a preordered set and let be a subset of . If there exists an element in such that for all , then is called an **upper bound** for . Similarly, if there exists an element in such that for all then is a **lower bound** for . 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 be a partially ordered set and let be a subset of . If an element is an upper bound for and if whenever is an upper bound for then is called the **least upper bound** or **supremum** of . Similarly, a lower bound of that is greater than or equal to every other lower bound for is the **greatest lower bound** or **infimum** of . 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 be a partially ordered set and be a subset of . A **maximal element** of is any element such that if then for all . If the inequality in the previous sentence is reversed, then the element is called a **minimal element**. If is greater than every other element in , then 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

editAnother 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 or . A set equipped with an equivalence relation is also known as a **setoid**.

If is an equivalence relation on a set , we define for an element the **equivalence class** of as . This is usually denoted by . The set of all equivalence classes of is known as the **quotient set** of by , which we denote by .

A **partition** of a set is a family of sets such that is pairwise disjoint and . The proof of the following theorems about equivalence relations are left to the reader.

**Theorem:** If is a set and is an equivalence relation on , then is a partition of .

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