Does greater operator ">" satisfy strict weak ordering?

Question

Definition:

Let < be a binary relation where a < b means "a is less than b".

Let > be a binary relation where a > b means "a is greater than b".

So, we assume < and > have meanings we usually use in a daily life. Though, in some programming languages (e.g. C++), we can overload them to give them different definitions, hereafter we don't think about that.

---

Context:

As far I read mathematical definition of strict weak ordering (e.g. Wikipedia), I think both < and > satify it. However, all examples I saw in many websites refer only to <. There is even a website which says

what they roughly mean is that a Strict Weak Ordering has to behave the way that "less than" behaves: if a is less than b then b is not less than a, if a is less than b and b is less than c then a is less than c, and so on.

Also, in N4140 (C++14 International Standard), strict weak ordering is defines as

(§25.4-4) If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations

where comp is defined as

(§25.4-2) Compare is a function object type (20.9). The return value of the function call operation applied to an object of type Compare, when contextually converted to bool (Clause 4), yields true if the first argument of the call is less than the second, and false otherwise. Compare comp is used throughout for algorithms assuming an ordering relation.

---

Question:

Does ">" satisfy strict weak ordering? I expect so, but have no confidence.

Corbeil

Short answer: Yes. – Rustyrut

The answer is yes. That's why you can sort a list of numbers in ascending order (using <) or descending order (using >). – Sheikh

@Rustyrut So N4140's explanation is wrong? – Corbeil

@RSahu Yes, I know the technique. But N4140's explanation confuses me. – Corbeil

It's not wrong. It's using "less than" to mean "less than when using this compare function", to mean that one value will appear before another when sorted using that comparison. – Kuomintang

@Corbeil even though the standard says less than you can subsitute greater than in it's place. It's the same semantic. with std::greater<>{}(5, 4) 5 is considered less than 4, so it needs to come first. Does that make sense? – Rustyrut

@ynn, that's a defect in wording. That obviously does not apply when sorting objects in descending order. – Sheikh

If this all comes from the same document, it's confusing. In the definition of <, the phrase "is less than" means it has a smaller magnitude whereas later on, the phrase "is less than" means that it comes first in the particular strict weak ordering we are interested in. – Octavla

@DavidSchwartz Sorry, the OP is badly written. The first and second block quotes are written by me. The third quote is cited from a website. Only the fourth and fifth quotes are found in N4140. – Corbeil

@Corbeil Ah, then there's no real contradiction or contradiction. There's just the use of the phrase "less than" to mean comes before. It obviously can't mean mathematically less than because we're talking about arbitrary types here. I see how that could confuse someone. – Octavla

but neither <= nor >= satisfies strict weak ordering. – Disenchant

@Disenchant Yes. So that is called strict weak ordering. (For my note: mathematically, "strict" here imposes irreflexive-ness. This is explicitly noted in §25.4-4.) – Corbeil

Answer 1

Does greater operator “>” satisfy strict weak ordering?

The mathematical strict greater than relation is a strict weak ordering.

As for the operator in C++ langauge: For all integers types: Yes. In general: No, but in most cases yes. Same applies to strict less than operator.

---

As for the confusing quote, "is less than" in that context intends to convey that means that the the end result of the sort operation is a non-decreasing sequence i.e. objects are "less" or equal to objects after them. If std::greater is used as comparison object, then greater values are "lesser" in order.

This may be confusing, but is not intended to exclude strict greater than operator.

---

what is the case where > doesn't satisfy strict weak ordering?

Some examples:

• Overloaded operators that don't satisfy the properties.
• > operator on pointers that do not point to the same array has unspecified result.
• > does not satisfy irreflexivity requirement for floating point types in IEEE-754 representation unless NaNs are excluded from the domain.

Melaniamelanic

In C++ (not in math), what is the case where > doesn't satisfy strict weak ordering? (Note: As written in OP, we don't think about user-defined overloaded >. So the targets are build-in types.) – Corbeil

Answer 2

Even if the standard refers to "less than" for arbitrary Compare functions, that only implies "less than" in the context of the ordering.

If I define an ordering by comparison function [](int a, int b) { return a > b; }, then an element is "less than" another in this ordering if its integer value is greater. That's because the ordering I've created is an ordering of the integers in reverse order. You shouldn't read < as "less than" in orderings. You should read it as "comes before".

Whenever x < y is a strict weak ordering then x > y is also a strict weak ordering, just with the reverse order.

Diplomat