In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, especially order theory

Order theory

Order theory is a branch of mathematics which investigates our 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 gives some basic definitions...

, a strict weak ordering is a binary relation

Binary relation

In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...

 < on a set S that is a strict partial order (a transitive relation

Transitive relation

In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....

 that is irreflexive

Reflexive relation

In mathematics, a reflexive relation is a binary relation on a set for which every element is related to itself, i.e., a relation ~ on S where x~x holds true for every x in S. For example, ~ could be "is equal to".-Related terms:...

, or equivalently, that is asymmetric

Asymmetric relation

Asymmetric often means, simply: not symmetric. In this sense an asymmetric relation is a binary relation which is not a symmetric relation.That is,\lnot....

) in which the relation "neither a < b nor b < a" is transitive.

The equivalence classes of this "incomparability relation" partition the elements of S, and are totally ordered

Total order

In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...

 by <. Conversely, any total order on a partition of S gives rise to a strict weak ordering in which x < y if and only if there exists sets A and B in the partition with x in A, y in B, and A < B in the total order.

As a non-example, consider the partial order in the set {a, b, c} defined by the relationship b < c. The pairs a,b and a,c are incomparable but b and c are related, so incomparability does not form an equivalence relation and this example is not a strict weak ordering.

Properties

A strict weak ordering has the following properties. For all x and y in S,

• For all x, it is not the case that x < x (irreflexivity).
• For all x ≠ y, if x < y then it is not the case that y < x (asymmetric
  Asymmetric relation
  Asymmetric often means, simply: not symmetric. In this sense an asymmetric relation is a binary relation which is not a symmetric relation.That is,\lnot....
  
  ).
• For all x, y, and z, if x < y and y < z then x < z (transitivity
  Transitive relation
  In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
  
  ).
• For all x, y, and z, if x is incomparable with y, and y is incomparable with z, then x is incomparable with z (transitivity of equivalence).

Note that this list of properties is somewhat redundant, as asymmetry follows readily from irreflexivity and transitivity. Transitivity of equivalence can also be stated in the following simpler form:

• If x < y, then for all z either x < z or z < y (or both).

Semiorder

Semiorder

In order theory, a branch of mathematics, a semiorder is a type of ordering that may be determined for a set of items with numerical scores by declaring two items to be incomparable when their scores are within some threshold of each other and otherwise using the numerical comparison of their scores...

s generalize strict weak orderings, but do not assume transitivity of indifference.

Total preorders

Strict weak orders are very closely related to total preorders or (non-strict) weak orders, and the same mathematical concepts that can be modeled with strict weak orderings can be modeled equally well with total preorders. A total preorder or weak order is a preorder

Preorder

In mathematics, especially in order theory, preorders are binary relations that are reflexive and transitive.For example, all partial orders and equivalence relations are preorders...

 that is total

Total relation

In mathematics, a binary relation R over a set X is total if for all a and b in X, a is related to b or b is related to a .In mathematical notation, this is\forall a, b \in X,\ a R b \or b R a....

; that is, no pair of items is incomparable. A total preorder satisfies the following properties:

• For all x, y, and z, if x y and y z then x z (transitivity).
• For all x and y, x y or y x (totality).
  • Hence, for all x, x x (reflexivity).

A total order

Total order

In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...

 is a total preorder which is antisymmetric, in other words, which is also a partial order

Partially ordered set

In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...

.

The complement

Complement (set theory)

In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...

 of a strict weak order is a total preorder, and vice versa, but it seems more natural to relate strict weak orders and total preorders in a way that preserves rather than reverses the order of the elements. Thus we take the inverse

Inverse relation

In mathematics, the inverse relation of a binary relation is the relation that occurs when you switch the order of the elements in the relation. For example, the inverse of the relation 'child of' is the relation 'parent of'...

 of the complement: for a strict weak ordering <, define a total preorder by setting x y whenever it is not the case that y < x. In the other direction, to define a strict weak ordering < from a total preorder , set x < y whenever it is not the case that y x.

For a strict weak order "<" another associated reflexive relation is its reflexive closure, a (non-strict) partial order "≤". The two associated reflexive relations differ with regard to different a and b for which neither a < b nor b < a: in the total preorder we get a b and b a, while in the (non-strict) partial order we get neither a ≤ b nor b ≤ a. For strict total orders these two associated reflexive relations are the same: the corresponding (non-strict) total order. The reflexive closure of a strict weak ordering is a type of series-parallel partial order

Series-parallel partial order

In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations....

.

In any preorder there is a corresponding equivalence relation where two elements x and y are defined as equivalent if x y and y x. In the case of a total preorder the corresponding partial order on the set of equivalence classes is a total order. Two elements are equivalent in a total preorder if and only if they are incomparable in the corresponding strict weak ordering.

Representing weak orderings by functions

If X is any set and f a real-valued function on X then f induces a strict weak order on X by setting

• a < b if and only if f(a) < f(b)

The associated total preorder is given by

• a b if and only if f(a) ≤ f(b)

and the associated equivalence by

• a b if and only if f(a) = f(b)

The relations do not change when f is replaced by g o f (composite function

Function composition

In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...

), where g is a strictly increasing

Monotonic function

In mathematics, a monotonic function is a function that preserves the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory....

 real-valued function defined on at least the range of f.

Thus e.g. a utility function defines a preference

Preference

-Definitions in different disciplines:The term “preferences” is used in a variety of related, but not identical, ways in the scientific literature. This makes it necessary to make explicit the sense in which the term is used in different social sciences....

 relation.

If X is finite or countable, every weak order can be represented by a function in this way (see, e.g., , Theorem 3.1).
However, there exist strict weak orders that have no corresponding real function. For example, there is no such function for the lexicographic order on Rⁿ. Thus, while in most preference relation models the relation defines a utility function up to

Up to

In mathematics, the phrase "up to x" means "disregarding a possible difference in  x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...

 order-preserving transformations, there is no such function for lexicographic preferences

Lexicographic preferences

Lexicographic preferences describe comparative preferences where an economic agent infinitely prefers one good to another . Thus if offered several bundles of goods, the agent will choose the bundle that offers the most X, no matter how much Y there is...

.

More generally, if X is a set, and Y is a set with a strict weak ordering "<", and f a function from X to Y, then f induces a strict weak ordering on X by setting

• a < b if and only if f(a) < f(b)

The associated total preorder is given by

• a b if and only if f(a) f(b)

and the associated equivalence by

• a b if and only if f(a) f(b)

f is not necessarily an injective function

Injective function

In mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...

, so for example a class of 2 equivalent elements on Y may induce a class of 5 equivalent elements on X. Also f is not necessarily an surjective function

Surjective function

In mathematics, a function f from a set X to a set Y is surjective , or a surjection, if every element y in Y has a corresponding element x in X so that f = y...

, so a class of 2 equivalent elements on Y may induce a class of only one element on X, or no class at all. There is a corresponding injective function g that maps the partition on X to that on Y. Thus, in the case of finite partitions, the number of classes in X is less than or equal to the number of classes on Y.

Examples

On the 2-dimensional real plane:

• f(x, y) = x + y
• f(x, y) = min(x, y)

In the case of preferences with regard to an amount of x of one product and y of the other, the first corresponds to the case that the products can replace each other, the other that they can only be used in combination.

The number of total preorders

The number of distinct total preorders on an n-element set is given by the following sequence :
These numbers are also called the Fubini numbers or ordered Bell numbers.

As explained above, there is a 1-to-1 correspondence between total preorders and pairs (partition, total order). Thus the number of total preorders is the sum of the number of total orders on every partition. For example:

• for n = 3:
  • 1 partition of 3, giving 1 total preorder (each element is related to each element)
  • 3 partitions of 2 + 1, giving 3 × 2 = 6 total preorders
  • 1 partition of 1 + 1 + 1, giving 6 total preorders (the total order
    Total order
    In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
    
    s)

i.e. together 13 total preorders.

• for n = 4:
  • 1 partition of 4, giving 1 total preorder (each element is related to each element)
  • 7 partitions with two classes (4 of 3 + 1 and 3 of 2 + 2), giving 7 × 2 = 14 total preorders
  • 6 partitions of 2+1+1, giving 6 × 6 = 36 total preorders
  • 1 partition of 1+1+1+1, giving 24 total preorders (the total orders)

i.e. together 75 total preorders.

Compare the Bell number

Bell number

In combinatorics, the nth Bell number, named after Eric Temple Bell, is the number of partitions of a set with n members, or equivalently, the number of equivalence relations on it...

s, here 5 and 15: the number of partitions, i.e., the number of equivalence relations.

Strict total order

A strict weak order that is trichotomous is called a strict total order. The total preorder which is the inverse of its complement is in this case a total order

Total order

In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...

.