Set Theory/Orderings

From Wikibooks, open books for an open world
Jump to: navigation, search



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 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.


Let 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.


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 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.

Relations · Zorn's Lemma and the Axiom of Choice