Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Weak ordering
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
==Axiomatizations== Suppose throughout that <math>\,<\,</math> is a [[Homogeneous relation|homogeneous]] [[binary relation]] on a set <math>S</math> (that is, <math>\,<\,</math> is a subset of <math>S \times S</math>) and as usual, write <math>x < y</math> and say that {{em|<math>x < y</math> holds}} or {{em|is true}} if and only if <math>(x, y) \in \,<.\,</math> ===Strict weak orderings=== '''Preliminaries on incomparability and transitivity of incomparability''' Two elements <math>x</math> and <math>y</math> of <math>S</math> are said to be '''{{em|[[Comparability|incomparable]]}}''' with respect to <math>\,<\,</math> if neither <math>x < y</math> nor <math>y < x</math> is true.<ref name="fr11"/> A [[strict partial order]] <math>\,<\,</math> is a strict weak ordering if and only if incomparability with respect to <math>\,<\,</math> is an [[equivalence relation]]. Incomparability with respect to <math>\,<\,</math> is always a homogeneous [[symmetric relation]] on <math>S.</math> It is [[Reflexive relation|reflexive]] if and only if <math>\,<\,</math> is [[Irreflexive relation|irreflexive]] (meaning that <math>x < x</math> is always false), which will be assumed so that [[Transitive relation|transitivity]] is the only property this "incomparability relation" needs in order to be an [[equivalence relation]]. Define also an induced homogeneous relation <math>\,\lesssim\,</math> on <math>S</math> by declaring that <math display="block">x \lesssim y \text{ is true } \quad \text{ if and only if } \quad y < x \text{ is false}</math> where importantly, this definition is {{em|not}} necessarily the same as: <math>x \lesssim y</math> if and only if <math>x < y \text{ or } x = y.</math> Two elements <math>x, y \in S</math> are incomparable with respect to <math>\,<\,</math> if and only if <math>x \text{ and } y</math> are {{em|equivalent}} with respect to <math>\,\lesssim\,</math> (or less verbosely, {{em|<math>\,\lesssim</math>-equivalent}}), which by definition means that both <math>x \lesssim y \text{ and } y \lesssim x</math> are true. The relation "are incomparable with respect to <math>\,<</math>" is thus identical to (that is, equal to) the relation "are <math>\,\lesssim</math>-equivalent" (so in particular, the former is transitive if and only if the latter is). When <math>\,<\,</math> is irreflexive then the property known as "[[#Transitivity of incomparability|transitivity of incomparability]]" (defined below) is {{em|exactly}} the condition necessary and sufficient to guarantee that the relation "are <math>\,\lesssim</math>-equivalent" does indeed form an equivalence relation on <math>S.</math> When this is the case, it allows any two elements <math>x, y \in S</math> satisfying <math>x \lesssim y \text{ and } y \lesssim x</math> to be identified as a single object (specifically, they are identified together in their common [[equivalence class]]). '''Definition''' A '''strict weak ordering''' on a set <math>S</math> is a [[strict partial order]] <math>\,<\,</math> on <math>S</math> for which the {{em|incomparability relation}} induced on <math>S</math> by <math>\,<\,</math> is a [[transitive relation]].<ref name="fr11"/> Explicitly, a strict weak order on <math>S</math> is a [[homogeneous relation]] <math>\,<\,</math> on <math>S</math> that has all four of the following properties: <ol> <li>{{em|[[Irreflexive relation|Irreflexivity]]}}: For all <math>x \in S,</math> it is not true that <math>x < x.</math> * This condition holds if and only if the induced relation <math>\,\lesssim\,</math> on <math>S</math> is [[Reflexive relation|reflexive]], where <math>\,\lesssim\,</math> is defined by declaring that <math>x \lesssim y</math> is true if and only if <math>y < x</math> is {{em|false}}.</li> <li>{{em|[[Transitive relation|Transitivity]]}}: For all <math>x, y, z \in S,</math> if <math>x < y \text{ and } y < z</math> then <math>x < z.</math></li> <li>{{em|[[Asymmetric relation|Asymmetry]]}}: For all <math>x, y \in S,</math> if <math>x < y</math> is true then <math>y < x</math> is false.</li> <li>{{em|{{visible anchor|Transitivity of incomparability}}}}: For all <math>x, y, z \in S,</math> if <math>x</math> is incomparable with <math>y</math> (meaning that neither <math>x < y</math> nor <math>y < x</math> is true) and if <math>y</math> is incomparable with <math>z,</math> then <math>x</math> is incomparable with <math>z.</math> * Two elements <math>x \text{ and } y</math> are incomparable with respect to <math>\,<\,</math> if and only if they are equivalent with respect to the induced relation <math>\,\lesssim\,</math> (which by definition means that <math>x \lesssim y \text{ and } y \lesssim x</math> are both true), where as before, <math>x \lesssim y</math> is declared to be true if and only if <math>y < x</math> is false. Thus this condition holds if and only if the [[symmetric relation]] on <math>S</math> defined by "<math>x \text{ and } y</math> are equivalent with respect to <math>\,\lesssim\,</math>" is a transitive relation, meaning that whenever <math>x \text{ and } y</math> are <math>\,\lesssim</math>-equivalent and also <math>y \text{ and } z</math> are <math>\,\lesssim</math>-equivalent then necessarily <math>x \text{ and } z</math> are <math>\,\lesssim</math>-equivalent. This can also be restated as: whenever <math>x \lesssim y \text{ and } y \lesssim x</math> and also <math>y \lesssim z \text{ and } z \lesssim y</math> then necessarily <math>x \lesssim z \text{ and } z \lesssim x.</math></li> </ol> Properties (1), (2), and (3) are the defining properties of a strict partial order, although there is some redundancy in this list as asymmetry (3) implies irreflexivity (1), and also because irreflexivity (1) and transitivity (2) together imply asymmetry (3).<ref>{{citation|last1=Flaška|first1=V.|last2=Ježek|first2=J.|last3=Kepka|first3=T.|last4=Kortelainen|first4=J.|title=Transitive Closures of Binary Relations I|year=2007|publisher=School of Mathematics - Physics Charles University|location=Prague|page=1|s2cid=47676001|url=https://pdfs.semanticscholar.org/3c4d/5e71464107b1cc612ba2c3a6a1c7aeb78007.pdf|archive-url=https://web.archive.org/web/20180406230752/https://pdfs.semanticscholar.org/3c4d/5e71464107b1cc612ba2c3a6a1c7aeb78007.pdf|url-status=dead|archive-date=2018-04-06}}, Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".</ref> The incomparability relation is always [[Symmetric relation|symmetric]] and it will be [[Reflexive relation|reflexive]] if and only if <math>\,<\,</math> is an irreflexive relation (which is assumed by the above definition). Consequently, a strict partial order <math>\,<\,</math> is a strict weak order if and only if its induced incomparability relation is an [[equivalence relation]]. In this case, its [[equivalence class]]es [[Partition of a set|partition]] <math>S</math> and moreover, the set <math>\mathcal{P}</math> of these equivalence classes can be [[Strict total order|strictly totally ordered]] by a [[binary relation]], also denoted by <math>\,<,</math> that is defined for all <math>A, B \in \mathcal{P}</math> by: :<math>A < B \text{ if and only if } a < b</math> for some (or equivalently, for all) representatives <math>a \in A \text{ and } b \in B.</math> Conversely, any [[strict total order]] on a [[Partition (set theory)|partition]] <math>\mathcal{P}</math> of <math>S</math> gives rise to a strict weak ordering <math>\,<\,</math> on <math>S</math> defined by <math>a < b</math> if and only if there exists sets <math>A, B \in \mathcal{P}</math> in this partition such that <math>a \in A, b \in B, \text{ and } A < B.</math> Not every partial order obeys the transitive law for incomparability. For instance, consider the partial order in the set <math>\{ a, b ,c \}</math> defined by the relationship <math>b < c.</math> The pairs <math>a, b \text{ and } a, c</math> are incomparable but <math>b</math> and <math>c</math> are related, so incomparability does not form an equivalence relation and this example is not a strict weak ordering. For transitivity of incomparability, each of the following conditions is [[Necessity and sufficiency|necessary]], and for strict partial orders also [[Necessity and sufficiency|sufficient]]: * If <math>x < y</math> then for all <math>z,</math> either <math>x < z \text{ or } z < y</math> or both. * If <math>x</math> is incomparable with <math>y</math> then for all <math>z</math>, either (<math>x < z \text{ and } y < z</math>) or (<math>z < x \text{ and } z < y</math>) or (<math>z</math> is incomparable with <math>x</math> and <math>z</math> is incomparable with <math>y</math>). ===Total preorders<!--This section is linked from [[Preference (economics)]]-->=== 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]] in which any two elements are comparable.<ref>Such a relation is also called [[Connected relation|strongly connected]].</ref> A total preorder <math>\,\lesssim\,</math> satisfies the following properties: * {{em|Transitivity}}: For all <math>x, y, \text{ and } z,</math> if <math>x \lesssim y \text{ and } y \lesssim z</math> then <math>x \lesssim z.</math> * {{em|Strong connectedness}}: For all <math>x \text{ and } y,</math> <math>x \lesssim y \text{ or } y \lesssim x.</math> ** Which implies {{em|reflexivity}}: for all <math>x,</math> <math>x \lesssim x.</math> A [[total order]] is a total preorder which is antisymmetric, in other words, which is also a [[Partially ordered set|partial order]]. Total preorders are sometimes also called '''preference relations'''. The [[Complement (set theory)|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 [[Converse relation|converse]] of the complement: for a strict weak ordering <math>\,<,</math> define a total preorder <math>\,\lesssim\,</math> by setting <math>x \lesssim y</math> whenever it is not the case that <math>y < x.</math> In the other direction, to define a strict weak ordering < from a total preorder <math>\,\lesssim,</math> set <math>x < y</math> whenever it is not the case that <math>y \lesssim x.</math><ref>{{citation|title=Multicriteria Optimization|first=Matthias|last=Ehrgott|publisher=Springer|year=2005|isbn=9783540276593|url=https://books.google.com/books?id=AwRjo6iP4_UC&pg=PA10|at=Proposition 1.9, p. 10}}.</ref> In any preorder there is a [[Preorder#Constructions|corresponding equivalence relation]] where two elements <math>x</math> and <math>y</math> are defined as '''equivalent''' if <math>x \lesssim y \text{ and } y \lesssim x.</math> In the case of a {{em|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. ===Ordered partitions=== A [[partition of a set]] <math>S</math> is a family of non-empty disjoint subsets of <math>S</math> that have <math>S</math> as their union. A partition, together with a [[total order]] on the sets of the partition, gives a structure called by [[Richard P. Stanley]] an '''ordered partition'''<ref>{{citation|first=Richard P.|last=Stanley|authorlink=Richard P. Stanley|title=Enumerative Combinatorics, Vol. 2|series=Cambridge Studies in Advanced Mathematics|volume=62|page=297|publisher=Cambridge University Press|year=1997}}.</ref> and by [[Theodore Motzkin]] a '''list of sets'''.<ref>{{citation|last=Motzkin|first=Theodore S.|authorlink=Theodore Motzkin|contribution=Sorting numbers for cylinders and other classification numbers|location=Providence, R.I.|mr=0332508|pages=167–176|publisher=Amer. Math. Soc.|title=Combinatorics (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., 1968)|year=1971}}.</ref> An ordered partition of a finite set may be written as a [[finite sequence]] of the sets in the partition: for instance, the three ordered partitions of the set <math>\{a, b\}</math> are <math display=block>\{a\}, \{b\},</math> <math display=block>\{b\}, \{a\}, \; \text{ and }</math> <math display=block>\{a, b\}.</math> In a strict weak ordering, the equivalence classes of incomparability give a set partition, in which the sets inherit a total ordering from their elements, giving rise to an ordered partition. In the other direction, any ordered partition gives rise to a strict weak ordering in which two elements are incomparable when they belong to the same set in the partition, and otherwise inherit the order of the sets that contain them. ===Representation by functions=== For sets of sufficiently small [[cardinality]], a fourth axiomatization is possible, based on real-valued functions. If <math>X</math> is any set then a real-valued function <math>f : X \to \R</math> on <math>X</math> induces a strict weak order on <math>X</math> by setting <math display=block>a < b \text{ if and only if } f(a) < f(b).</math> The associated total preorder is given by setting <math>a {}\lesssim{} b \text{ if and only if } f(a) \leq f(b)</math> and the associated equivalence by setting <math>a {}\sim{} b \text{ if and only if } f(a) = f(b).</math> The relations do not change when <math>f</math> is replaced by <math>g \circ f</math> ([[Function composition|composite function]]), where <math>g</math> is a [[Monotonic function|strictly increasing]] real-valued function defined on at least the range of <math>f.</math> Thus for example, a [[Utility#Utility functions|utility function]] defines a [[preference]] relation. In this context, weak orderings are also known as '''preferential arrangements'''.<ref>{{citation|last=Gross|first=O. A.|doi=10.2307/2312725|journal=The American Mathematical Monthly|mr=0130837|pages=4–8|title=Preferential arrangements|volume=69|year=1962|issue=1|jstor=2312725}}.</ref> If <math>X</math> is finite or countable, every weak order on <math>X</math> can be represented by a function in this way.<ref name="roberts">{{citation|last=Roberts|first=Fred S.|authorlink=Fred S. Roberts|year=1979|title=Measurement Theory, with Applications to Decisionmaking, Utility, and the Social Sciences|at=[https://archive.org/details/measurementtheor0000robe/page/ Theorem 3.1]|series=Encyclopedia of Mathematics and its Applications|volume=7|isbn=978-0-201-13506-0|publisher=Addison-Wesley|url-access=registration|url=https://archive.org/details/measurementtheor0000robe/page/}}.</ref> However, there exist strict weak orders that have no corresponding real function. For example, there is no such function for the [[lexicographic order]] on <math>\R^n.</math> 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 <math>X</math> is a set, <math>Y</math> is a set with a strict weak ordering <math>\,<,\,</math> and <math>f : X \to Y</math> is a function, then <math>f</math> induces a strict weak ordering on <math>X</math> by setting <math display=block>a < b \text{ if and only if } f(a) < f(b).</math> As before, the associated total preorder is given by setting <math>a {}\lesssim{} b \text{ if and only if } f(a) {}\lesssim{} f(b),</math> and the associated equivalence by setting <math>a {}\sim{} b \text{ if and only if } f(a) {}\sim{} f(b).</math> It is not assumed here that <math>f</math> is an [[injective function]], so a class of two equivalent elements on <math>Y</math> may induce a larger class of equivalent elements on <math>X.</math> Also, <math>f</math> is not assumed to be a [[surjective function]], so a class of equivalent elements on <math>Y</math> may induce a smaller or empty class on <math>X.</math> However, the function <math>f</math> induces an injective function that maps the partition on <math>X</math> to that on <math>Y.</math> Thus, in the case of finite partitions, the number of classes in <math>X</math> is less than or equal to the number of classes on <math>Y.</math>
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)