# ordered-set

## Types of Ordered Set

In order theory, different types of ordered set are studied, including:

* **Posets**, orderings in which not all pairs are comparable
* **Preorders**, generalization of poset allowing ties (represented as equivalences and distinct from incomparabilities)
* **Semiorders**, poset determined by comparison of numerical values, in which values that are too close to each other are incomparable; subfamily of posets with certain restrictions
* **Total orders**, orderings that specify order for all elements, all pairs are comparable
* **Well-orders**, total orders in which every non-empty subset has a least element
* **Well-quasi-orderings**, a class of preorders generalizing the well-orders
* **Weak orders**, generalizations of total orders allowing ties (represented either as equivalences or, in strict weak orders, as transitive incomparabilities)
* **Cyclic orders**, orderings in which triples of elements are either clockwise or counterclockwise
* **Lattices**, posets in which each pair of elements has a greatest lower bound (GLB) and a least upper bound (LUB).

Chains

* **Chain** is a totally ordered set or a totally ordered subset of a poset.
* **Chain complete** is a partially ordered set in which every chain has a least upper bound.
* **Antichain** is a poset in which no two elements are comparable, i.e. there are no two distinct elements x and y such that x ≤ y. In other words, the order relation of an antichain is just the identity relation.

Monotonicity A monotonic function, or monotone function, is a function between ordered sets that preserves or reverses the given order.

* **Order-reversing**: a function $$f$$, **antitone**, between posets $$P$$ and $$Q$$ is a function for which, for all elements $$x, y$$ of $$P$$, $$x \le y$$ (in P) implies $$f(y) \le f(x)$$ (in Q).
* **Monotonically decreasing** is the name of such function in the presence of total orders (in math.Analysis).
* **Order-preserving** or **monotone** as the dual notion is called.

Bounds

* **Bounded poset** is one that has a least element and a greatest element.
* Poset is **bounded complete** if every of its subsets with some upper bound also has a least such upper bound. The dual notion is not common.
* **Closure operator** on the poset P is a function $$C:P \to P$$ that is monotone, idempotent, and satisfies $$C(x) \ge x$$ for all x in P.

## Ordered Sets

* a binary relation R on a set S is reflexive if R relates every element of S to itself i.e. `sRs` or `(s,s) ∈ R` for all `s ∈ S`.
* R is symmetric if `sRt` implies `tRs`, for all s and t in S.
* R is transitive if `sRt` AND `tRu` imply `sRu`.
* R is antisymmetric if `sRt` and `tRs` imply that `s = t`
* A reflexive and transitive relation R on a set S is called a preorder on S.
* We denote a preorder by `s < t` "is-less-than" to mean `s ≤ t ∧ s ≠ t`.
* A preorder (on a set S) that is also antisymmetric is called a partial order

  on S.
* A partial order ≤ is called a total order if it also has the property that,

  for each s and t in S, either `s ≤ t` or `t ≤ s`.
* Suppose that ≤ is a partial order on a set S and s and t are elements of S. An element `j ∈ S` is said to be a join (or least upper bound) of s and t if `s ≤ j` and `t ≤ j`, AND for any element `k ∈ S` with `s ≤ k` and `t ≤ k`, we have `j ≤ k`.
* an element `m ∈ S` is a meet (or greatest lower bound) of s and t if `m ≤ s` and `m ≤ t`, AND for any element `n ∈ S` with `n ≤ s` and `n ≤ t`, we have `n ≤ m`
* a reflexive, transitive, and symmetric relation on a set S is called

  an equivalence on S.
* let R is a binary relation on a set S. The reflexive closure of R is the smallest reflexive relation R' that contains R. "Smallest" in the sense that if R'' is some other reflexive relation that contains all the pairs in R, then we have `R' ⊆ R''`
* the transitive closure of R is the smallest transitive relation R' that contains R
* The transitive closure of R is often written R+
* The reflexive and transitive closure of R is the smallest reflexive and transitive relation that contains R, often written R∗.
* Let preorder ≤ on a set S. A decreasing chain in ≤ is a sequence s1,s2,s3,... of elements of S such that each member of the sequence is strictly less than its predecessor: `si+1 < si` for every i.
* Chains can be either finite or infinite
* Suppose we have a set S with a preorder ≤. We say that ≤ is well

  founded if it contains no infinite decreasing chains. For example, the usual order on the natural numbers, with `0 < 1 < ...`, is well founded, but the same order on the integers, `...< −1 < 0 < 1 <...` is not. We sometimes omit mentioning ≤ explicitly and simply speak of S as a well-founded set.