Set Theory/Orderings

Orderings

edit

Definitions

edit

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.

Bounds

edit

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.

Equivalences

edit

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