Wednesday, January 23, 2008

Strict weak ordering extensions

A strict weak ordering (swo for short) is a binary relation < on a set A such that its complementary relation ≥ = AxA − < is a total preorder (reflexive, transitive and such that xy or yx, 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 <AB from A to B and <BA from B to A for which there is some swo <AUB on AUB such that <A = <AUBAxA, <AB = <AUBAxB, <BA = <AUBBxA.

Theorem. (<AB,<BA) is a swo extension of <A iff for all a, a' in A, b in B.

  1. a <AB b → not(b <BA a),
  2. not(a <AB b) and not(a' <A a) → not(a' <AB b),
  3. not(b <BA a) and not(a <A a') → not(b <BA a').
Proof. If (<AB,<BA) 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:
  1. not(a <AB b) and a <AB b',
  2. b <BA a and not(b' <BA a) .

We will prove that <AUB = <A U <AB U <BA 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 (xAUB 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 <AB x) and a <AB x) or (x <BA a and not(x <BA a)).
  • Transitivity (xAUB y and yAUB zxAUB z):
    1. x, y, z in A: from the properties of <A.
    2. x, y in A, z in B: from property 2.
    3. 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 <AB y) implies by property 2 that not(z <AB y), in contradiction with not(y <BA z) by property 1.
    4. x in A, y, z in B: if x <AB z, we would have by the hypothesis not(y <B z) and the definition of <B that x <AB y, in contradiction with the hypothesis not(x <AB y).
    5. x in B, y, z in A: from property 3.
    6. 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 <AB z); and if not(y <A a) we have by property 3 that not(x <BA a). So, the conditions for x <B z are never satisfied.
    7. x, y in B, z in A: if x <BA z then by the hypothesis not(y <B z) and the definition of <B we would have the contradictory x <B y.
    8. x, y, z in B: for any a in A, if not(a <AB x) then not(a <AB y) and thus not(a <AB z); whereas if x <BA a then y <BA a and hence z <BA a; so, it is not the case that x <B z.
  • Comparability (xAUB y or yAUB x):
    1. x, y in A: from the properties of <A.
    2. x in A, y in B: from property 1.
    3. x in B, y in A: from property 1.
    4. x, y in B: if x <B y then there exists some a in A such either not(a <AB x) and a <AB y, which implies not(a <AB x) and not(y <BA a); or else x <BA a and not(y <BA a), which also implies not(a <AB x) and not(y <BA a). Thus in either case yAUB aAUB x, and by the transitivity of ≥AUB, it follows that xAUB y.

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