Strict weak ordering

Strict weak ordering
The 13 possible strict weak orderings on a set of three elements {a, b, c}. The only partially ordered sets are coloured, while totally ordered ones are in black. Two orderings are shown as connected by an edge if they differ by a single dichotomy.

In mathematics, especially order theory, a strict weak ordering is a binary relation < on a set S that is a strict partial order (a transitive relation that is irreflexive, or equivalently, that is asymmetric) 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 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 {abc} 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.

Contents

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 xy, if x < y then it is not the case that y < x (asymmetric).
  • For all x, y, and z, if x < y and y < z then x < z (transitivity).
  • 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).

Semiorders 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 that is total; that is, no pair of items is incomparable. A total preorder \lesssim satisfies the following properties:

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

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

The complement 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 of the complement: for a strict weak ordering <, define a total preorder \lesssim by setting x \lesssim y whenever it is not the case that y < x. In the other direction, to define a strict weak ordering < from a total preorder \lesssim, set x < y whenever it is not the case that y \lesssim 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 \lesssim b and b \lesssim a, while in the (non-strict) partial order we get neither ab nor ba. 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.

In any preorder there is a corresponding equivalence relation where two elements x and y are defined as equivalent if x \lesssim y and y \lesssim 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 \lesssim b if and only if f(a) ≤ f(b)

and the associated equivalence by

  • a  \sim \! b if and only if f(a) = f(b)

The relations do not change when f is replaced by g o f (composite function), where g is a strictly increasing real-valued function defined on at least the range of f.

Thus e.g. a utility function defines a preference relation.

If X is finite or countable, every weak order can be represented by a function in this way (see, e.g., Roberts 1979, 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 Rn. Thus, while in most preference relation models the relation defines a utility function up to order-preserving transformations, there is no such function for lexicographic preferences.

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 \lesssim b if and only if f(a) \lesssim f(b)

and the associated equivalence by

  • a \sim\! b if and only if f(a) \sim\! f(b)

f is not necessarily an injective function, 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, 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 (sequence A000670 in OEIS):

Number of n-element binary relations of different types
n all transitive reflexive preorder partial order total preorder total order equivalence relation
0 1 1 1 1 1 1 1 1
1 2 2 1 1 1 1 1 1
2 16 13 4 4 3 3 2 2
3 512 171 64 29 19 13 6 5
4 65536 3994 4096 355 219 75 24 15
OEIS A002416 A006905 A053763 A000798 A001035 A000670 A000142 A000110

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 orders)
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 numbers, 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.

References

  • Fishburn, Peter C. (1970), "Intransitive indifference in preference theory: a survey", Operations Research 18 (2): 207–228, doi:10.1287/opre.18.2.207 .
  • Roberts, Fred S. (1979), Measurement Theory, with Applications to Decisionmaking, Utility, and the Social Sciences, Encyclopedia of Mathematics and its Applications, 7, Addison-Wesley, ISBN 9780201135060 .

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Partially ordered set — The Hasse diagram of the set of all subsets of a three element set {x, y, z}, ordered by inclusion. In mathematics, especially order theory, a partially ordered set (or poset) formalizes and generalizes the intuitive concept of an ordering,… …   Wikipedia

  • Standard Template Library — C++ Standard Library fstream iomanip ios iostream sstream string …   Wikipedia

  • Preference — (also called taste or penchant ) is a concept, used in the social sciences, particularly economics. It assumes a real or imagined choice between alternatives and the possibility of rank ordering of these alternatives, based on happiness,… …   Wikipedia

  • Order theory — For a topical guide to this subject, see Outline of 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… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Permutohedron — In mathematics, the permutohedron of order n is an ( n − 1) dimensional polytope embedded in an n dimensional space, the vertices of which are formed by permuting the coordinates of the vector (1, 2, 3, ..., n ).Examples* Order 1: A single point …   Wikipedia

  • map (C++) — Not to be confused with Map (higher order function). C++ Standard Library fstream iomanip ios iostream sstre …   Wikipedia

  • 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 . Transitivity is a key property of both partial order… …   Wikipedia

  • Ranking — A ranking is a relationship between a set of items such that, for any two items, the first is either ranked higher than , ranked lower than or ranked equal to the second.In mathematics, this is known as a ml|Strict weak ordering|Total… …   Wikipedia

  • Level of measurement — The levels of measurement , or scales of measure are expressions that typically refer to the theory of scale types developed by the psychologist Stanley Smith Stevens. Stevens proposed his theory in a 1946 Science article titled On the theory of… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”