Editing Weak ordering (section)

===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>).