Set Theory/Orderings

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

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 \le and an ordered set is denoted by the ordered pair ( S , \le ) where \le 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 \le b or b \le 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[edit]

Let (S, \le) be a preordered set and let T be a subset of S. If there exists an element u in S such that x \le 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 \le 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, \le) 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 \le 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, \le) 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 \le 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[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 \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.

Relations · Zorn's Lemma and the Axiom of Choice