Order theory Order theory is a branch of mathematics which investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary. Orders are everywhere in mathematics and related fields like computer science. The first order often discussed in primary school is the standard order on the natural numbers e.g. "2 is less than 3", "10 is greater than 5", or "Does Tom have fewer cookies than Sally?". This intuitive concept can be extended to orders on other sets of numbers, such as the integers and the reals. The idea of being greater than or less than another number is one of the basic intuitions of number systems (compare with numeral systems) in general (although one usually is also interested in the actual difference of two numbers, which is not given by the order). Other familiar examples of orderings are the alphabetical order of words in a dictionary and the genealogical property of lineal descent within a group of people. The notion of order is very general, extending beyond contexts that have an immediate, intuitive feel of sequence or relative quantity. In other contexts orders may capture notions of containment or specialization. Abstractly, this type of order amounts to the subset relation, e.g., "Pediatricians are physicians," and "Circles are merely special-case ellipses." Some orders, like "less-than" on the natural numbers and alphabetical order on words, have a special property: each element can be compared to any other element, i.e. it is smaller (earlier) than, larger (later) than, or identical to. However, many other orders do not. Consider for example the subset order on a collection of sets: though the set of birds and the set of dogs are both subsets of the set of animals, neither the birds nor the dogs constitutes a subset of the other. Those orders like the "subset-of" relation for which there exist incomparable elements are called partial orders; orders for which every pair of elements is comparable are total orders. Order theory captures the intuition of orders that arises from such examples in a general setting. This is achieved by specifying properties that a relation ≤ must have to be a mathematical order. This more abstract approach makes much sense, because one can derive numerous theorems in the general setting, without focusing on the details of any particular order. These insights can then be readily transferred to many less abstract applications. Driven by the wide practical usage of orders, numerous special kinds of ordered sets have been defined, some of which have grown into mathematical fields of their own. In addition, order theory does not restrict itself to the various classes of ordering relations, but also considers appropriate functions between them. A simple example of an order theoretic property for functions comes from analysis where monotone functions are frequently found. Basic definitions This section introduces ordered sets by building upon the concepts of set theory, arithmetic, and binary relations. Partially ordered sets Orders are special binary relations. Suppose that P is a set and that ≤ is a relation on P. Then ≤ is a partial order if it is reflexive, antisymmetric, and transitive, i.e., for all a, b and c in P, we have that: a ≤ a (reflexivity) if a ≤ b and b ≤ a then a = b (antisymmetry) if a ≤ b and b ≤ c then a ≤ c (transitivity). A set with a partial order on it is called a partially ordered set, poset, or just an ordered set if the intended meaning is clear. By checking these properties, one immediately sees that the well-known orders on natural numbers, integers, rational numbers and reals are all orders in the above sense. However, they have the additional property of being total, i.e., for all a and b in P, we have that: a ≤ b or b ≤ a (connexity). These orders can also be called linear orders or chains. While many classical orders are linear, the subset order on sets provides an example where this is not the case. Another example is given by the divisibility (or "is-a-factor-of") relation "|". For two natural numbers n and m, we write n|m if n divides m without remainder. One easily sees that this yields a partial order. The identity relation = on any set is also a partial order in which every two distinct elements are incomparable. It is also the only relation that is both a partial order and an equivalence relation. Many advanced properties of posets are interesting mainly for non-linear orders. Total order In mathematics, a linear order, total order, simple order, or (non-strict) ordering is a binary relation on some set {X}, which is antisymmetric, transitive, and a connex relation. A set paired with a total order is called a totally ordered set, a linearly ordered set, a simply ordered set, or a chain. Formally, a binary relation {\displaystyle \leq } \leq is a total order on a set {\displaystyle X} X if the following statements hold for all {\displaystyle a,b} a,b and {\displaystyle c} c in {\displaystyle X} X: Antisymmetry If {\displaystyle a\leq b} a\leq b and {\displaystyle b\leq a} {\displaystyle b\leq a} then {\displaystyle a=b} a=b; Transitivity If {\displaystyle a\leq b} a\leq b and {\displaystyle b\leq c} {\displaystyle b\leq c} then {\displaystyle a\leq c} {\displaystyle a\leq c}; Connexity {\displaystyle a\leq b} a\leq b or {\displaystyle b\leq a} {\displaystyle b\leq a}. Antisymmetry eliminates uncertain cases when both {\displaystyle a} a precedes {\displaystyle b} b and {\displaystyle b} b precedes {\displaystyle a} a.:325 A relation having the connex property means that any pair of elements in the set of the relation are comparable under the relation. This also means that the set can be diagrammed as a line of elements, giving it the name linear.:330 The connex property also implies reflexivity, i.e., a = a. Therefore, a total order is also a (special case of a) partial order, as, for a partial order, the connex property is replaced by the weaker reflexivity property. An extension of a given partial order to a total order is called a linear extension of that partial order. Strict total order For each (non-strict) total order ≤ there is an associated asymmetric (hence irreflexive) relation <, called a strict total order, which can be defined in two equivalent ways: a < b if a ≤ b and a ≠ b a < b if not b ≤ a (i.e., < is the inverse of the complement of ≤) Properties: The relation is transitive: a < b and b < c implies a < c. The relation is trichotomous: exactly one of a < b, b < a and a = b is true. The relation is a strict weak order, where the associated equivalence is equality. We can work the other way and start by choosing < as a transitive trichotomous binary relation; then a total order ≤ can be defined in two equivalent ways: a ≤ b if a < b or a = b a ≤ b if not b < a Two more associated orders are the complements ≥ and >, completing the quadruple {<, >, ≤, ≥}. We can define or explain the way a set is totally ordered by any of these four relations; the notation implies whether we are talking about the non-strict or the strict total order. Examples The letters of the alphabet ordered by the standard dictionary order, e.g., A < B < C etc. Any subset of a totally ordered set X is totally ordered for the restriction of the order on X. The unique order on the empty set, ∅, is a total order. Any set of cardinal numbers or ordinal numbers (more strongly, these are well-orders). If X is any set and f an injective function from X to a totally ordered set then f induces a total ordering on X by setting x1 < x2 if and only if f(x1) < f(x2). The lexicographical order on the Cartesian product of a family of totally ordered sets, indexed by a well ordered set, is itself a total order. The set of real numbers ordered by the usual less than (<) or greater than (>) relations is totally ordered, hence also the subsets of natural numbers, integers, and rational numbers. Each of these can be shown to be the unique (to within isomorphism) smallest example of a totally ordered set with a certain property, (a total order A is the smallest with a certain property if whenever B has the property, there is an order isomorphism from A to a subset of B): The natural numbers comprise the smallest totally ordered set with no upper bound. The integers comprise the smallest totally ordered set with neither an upper nor a lower bound. The rational numbers comprise the smallest totally ordered set which is dense in the real numbers. The definition of density used here says that for every a and b in the real numbers such that a < b, there is a q in the rational numbers such that a < q < b. The real numbers comprise the smallest unbounded totally ordered set that is connected in the order topology (defined below). Ordered fields are totally ordered by definition. They include the rational numbers and the real numbers. Every ordered field contains an ordered subfield that is isomorphic to the rational numbers. Any Dedekind-complete ordered field is isomorphic to the real numbers.