A *strict weak ordering* (swo for short) is a binary relation < on a set *A* such that its complementary relation ≥ = *A*x*A* − < is a total preorder (reflexive, transitive and such that *x* ≥ *y* or *y* ≥ *x*, or both, for all *x*, *y* in *A*).

We introduce the notion of an extension to a strict weak ordering: Given <_{A} a swo on A, a swo extension of <_{A} to B, where B is a set disjoint with A, is a pair of relations <_{A→B} from A to B and <_{B}_{→A} from B to A for which there is some swo <_{AUB} on AUB such that <_{A }= <_{AUB} ∩ AxA, <_{A→B} = <_{AUB} ∩ AxB, <_{B}_{→A} = <_{AUB} ∩ BxA.

Theorem. (<_{A→B},<_{B}_{→A}) is a swo extension of <_{A} iff for all a, a' in A, b in B.

- a <
_{A→B}b → not(b <_{B→A}a), - not(a <
_{A→B}b) and not(a' <_{A}a) → not(a' <_{A→B}b), - not(b <
_{B}_{→A}a) and not(a <_{A}a') → not(b <_{B}_{→A}a').

_{A→B},<

_{B}

_{→A}) is a swo extension of <

_{A}, 1, 2 and 3 follow trivially from the properties of a swo on AUB. As for the converse, let us define the binary relation <

_{B}on B as follows: b <

_{B}b' iff there is some a in A such that at least one of the following two conditions hold:

- not(a <
_{A→B}b) and a <_{A→B}b', - b <
_{B→A}a and not(b' <_{B→A}a) .

We will prove that <_{AUB} = <_{A} U <_{A→B} U <_{B→A} U <_{B} is a swo on B by showing that ≥_{AUB} = (AUB)x(AUB) − <_{AUB} is a total preorder. In the following we will consider x, y, z in AUB:

- Reflexivity (x ≥
_{AUB}x): if x is in A, reflexivity follows from the properties of <_{A}. If x is in B and x <_{AUB}x, there would be some a in A verifying the contradictory (not(a <_{A→B}x) and a <_{A→B}x) or (x <_{B→A}a and not(x <_{B→A}a)). - Transitivity (x ≥
_{AUB}y and y ≥_{AUB}z → x ≥_{AUB}z):- x, y, z in A: from the properties of <
_{A}. - x, y in A, z in B: from property 2.
- x in A, y in B, z in A: If x <
_{A}z then not(z <_{A}x), which along with the hypothesis not(x <_{A→B}y) implies by property 2 that not(z <_{A→B}y), in contradiction with not(y <_{B→A}z) by property 1. - x in A, y, z in B: if x <
_{A→B}z, we would have by the hypothesis not(y <_{B}z) and the definition of <_{B}that x <_{A→B}y, in contradiction with the hypothesis not(x <_{A→B}y). - x in B, y, z in A: from property 3.
- x in B, y in A, z in B: for any a in A, if not(a <
_{A}y) then by property 2 not(a <_{A→B}z); and if not(y <_{A}a) we have by property 3 that not(x <_{B→A}a). So, the conditions for x <_{B}z are never satisfied. - x, y in B, z in A: if x <
_{B→A}z then by the hypothesis not(y <_{B}z) and the definition of <_{B}we would have the contradictory x <_{B}y. - x, y, z in B: for any a in A, if not(a <
_{A→B}x) then not(a <_{A→B}y) and thus not(a <_{A→B}z); whereas if x <_{B→A}a then y <_{B→A}a and hence z <_{B→A}a; so, it is not the case that x <_{B}z.

- x, y, z in A: from the properties of <
- Comparability (x ≥
_{AUB}y or y ≥_{AUB}x):- x, y in A: from the properties of <
_{A}. - x in A, y in B: from property 1.
- x in B, y in A: from property 1.
- x, y in B: if x <
_{B}y then there exists some a in A such either not(a <_{A→B}x) and a <_{A→B}y, which implies not(a <_{A→B}x) and not(y <_{B→A}a); or else x <_{B→A}a and not(y <_{B→A}a), which also implies not(a <_{A→B}x) and not(y <_{B→A}a). Thus in either case y≥_{AUB}a ≥_{AUB}x, and by the transitivity of ≥_{AUB}, it follows that x ≥_{AUB}y.

- x, y in A: from the properties of <

Swos are important in C++ because sorting algorithms take comparison objects with swo semantics. The swo extension concept that we have developed is related to the notion of partitioning introduced by the C++ standard to describe binary search algorithms, as we will see in a later entry.

## No comments :

## Post a Comment