Editing Order theory (section)

=== Partially ordered sets ===<!-- This section is linked from [[Indifference curve]] -->
Orders are special binary relations. Suppose that ''P'' is a set and that ≤ is a relation on ''P'' ('relation ''on'' a set' is taken to mean 'relation ''amongst'' its inhabitants', i.e. ≤ is a subset of the cartesian product ''P'' × ''P''). Then ≤ is a '''partial order''' if it is [[reflexive relation|reflexive]], [[antisymmetric relation|antisymmetric]], and [[transitive relation|transitive]], that is, if 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 [[partially ordered set|partial order]] on it is called a '''partially ordered set''', '''poset''', or just '''ordered set''' if the intended meaning is clear. By checking these properties, one immediately sees that the well-known orders on [[natural number]]s, [[integer]]s, [[rational number]]s and [[real number|reals]] are all orders in the above sense. However, these examples have the additional property that any two elements are comparable, that is, for all ''a'' and ''b'' in ''P'', we have that:

: ''a'' ≤ ''b'' or ''b'' ≤ ''a''.

A partial order with this property is called a [[total order]]. These orders can also be called '''linear orders''' or '''chains'''. While many familiar 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-[[divisor|factor]]-of") relation |. For two natural numbers ''n'' and ''m'', we write ''n''|''m'' if ''n'' [[division (mathematics)|divides]] ''m'' without remainder. One easily sees that this yields a partial order. For example neither 3 divides 13 nor 13 divides 3, so 3 and 13 are not comparable elements of the divisibility relation on the set of integers.
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]] because it satisfies both the antisymmetry property of partial orders and the [[Symmetric relation|symmetry]] property of equivalence relations. Many advanced properties of posets are interesting mainly for non-linear orders.