# Why `sort()` need `T` to be `Ord`?

Docs actually use both terms in the first statement:

Trait for equality comparisons which are equivalence relations.

I think there are two levels of description here:

• on the representation level, it's an equivalence relation
• on a higher, semantic level, it's equality

Ah okay! I guess you're right then.

In that case, either `Eq` would need to be redefined as "equality" (instead of "equivalence relation") or `Ord` would need to be redefined as "weak order" (instead of "total order").

Do I understand it correctly?

For instance:

Two `Vec` with different capacities but same sequence of values have different bit representations underneath, but represent the same mathematical object.

`==` implements the equivalence relation on representations, but it also means equality on the mathematical objects that are represented.

To give everything a name (feel free to point out mistakes)

`PartialEq` - partial equivalence relation
`Eq` - equivalence relation
`PartialOrd` - partial preorder (hard to find on English Wikipedia) Edit: that's not quite right...
`PartialOrd + Eq` - preorder
`Ord` - total preorder

(I'm ignoring `S: PartialEq<T>` or `S: PartialOrd<T>` between different types. Those are hard/impossible to characterize.)

Thanks for sharing, I'll look into that later. I have a preliminary comment already:

If I understand it right, then a "total preorder" is a weak order, and as such it doesn't need any equivalence relation being defined (but `Ord` does). (Even though you could derive an equivalence relation from a weak order, of course.)

I also noted @tczajka's comments that `==` often means equality when used with mathematical objects.

I'll look into it later again. Thanks for all your feedback so far!

Double-checked, turns out, no. The closest thing to the axioms given for `PartialOrd` in the docs is just:

`<=` is transitive

Yup, that's it. You can define the rest:
`a == b` iff `a <= b && b <= a`
`a != b` iff `!(a == b)`
`a < b` iff `a <= b && a != b`
`a > b` iff `b < a`
`a >= b` iff `b <= a`

But it appears there's actually an axiom missing in the documentation of `PartialOrd`. It doesn't state anywhere that `a < b` and `b == c` implies `a < c` (or similarly for `a == b` and `b < c`, giving `a < c`). That's most likely an oversight though, I doubt that's intentional. If you add those two implications, the characterization becomes truly equivalent to “`<=` is transitive”.

For the record, `f32` and `f64` do actually form partial preorders. They do fulfill the additional constraint that `a <= b` implies `a <= a` and `b <= b`. (Called "partial reflexivity", or "reflexivity where the relation is defined" in the German Wikipedia article.) So if `PartialOrd` is just about giving a trait that floating point numbers can implement, then "partial preorder" rather than "transitive relation" would've been a valid choice, too.

I'm unsure. Let me look at what @tczajka brought up:

But in `PartialEq` we find:

Trait for equality comparisons which are partial equivalence relations.

Now the mathematical "equality" (if I understand it right) is always an equivalence relation and never a partial equivalence relation. That is because equality is reflexive (see basic properties of equality).

So perhaps the term "equality comparisons" should be (or needs to be) interpreted more sloppy here.

Also note that there is no comma after "comparisons". The reference obviously refers to two different "equality comparisons" here (i.e. not "the" equality in the mathematical sense).

Following these thoughts, I'd say @steffahn is right with:

Now to the other traits:

Let's take a look at the return value of `PartialOrd::partial_cmp`, which is `Option<Ordering>`, where `Ordering` can be `Less`, `Equal`, or `Greater`.

Now that's pretty different from what a partial order is in the mathematical sense, which is only a binary relation (i.e. `partial_cmp` should return a bool, if we stick to the mathematical definition). Let's look at the properties of a partial order. A partial order requires:

I would say `PartialOrd` is a trait that denotes there is a partial order and(!) a partial equivalence relation (with some restrictions). This is also reflected by the supertrait: `PartialOrd<Rhs = Self>: PartialEq<Rhs>`.

Note that `PartialOrd::partial_cmp`'s return type has four different values:

• `None`
• `Some(Less)`
• `Some(Equal)`
• `Some(Greater)`

Along with the result of `PartialEq::eq`, we have eight possible results for `(a.eq(&b), a.partial_cmp(&b))` (of which only four are legit):

• `(false, None)` (allowed)
• `(false, Some(Less))` (allowed)
• `(false, Some(Equal))` (forbidden)
• `(false, Some(Greater))` (allowed)
• `(true, None)` (forbidden)
• `(true, Some(Less))` (forbidden)
• `(true, Some(Equal))` (allowed)
• `(true, Some(Greater))` (forbidden)

This seems to fit the observation that we have two binary relations, which would result in 4 possible outcomes.

(Edit: There is a flaw in my reasoning, see @steffahn's response below.)

Let's put this together, assuming our partial equivalence relation is `==` and the partial order relation is ≤.

• If `a == b` and `a``b`, we get `(true, Some(Equal))`.
• If `a == b` and not `a``b`, we get…
• If `a != b` and `a``b`, we get `(false, Some(Ordering::Less))`.
• If `a != b` and not `a``b`, then `(false, Some(Ordering::Greater))`.

The problem here is the second case. Now I'm really confused. I suspect that `PartialOrd` thus isn't actually a partial order. I suspect that `PartialOrd`'s consistency rules make `PartialOrd` inconsistent with the mathematical definition of a partial order.

Or maybe I overlooked something? Sorry if I caused more confusion, but I feel like there is something wrong.

So do I understand right that if the missing axiom was added, then `PartialOrd` is partial preorder?

I.e. `PartialOrd` isn't a partial order then, just like I suspected in my previous post?

No, the missing axioms “`a < b` and `b == c` implies `a < c`” and “`a == b` and `b < c` implies `a < c`” are necessary in order to ensure that `<=` is transitive. The partial preorder would furthermore require this

Note that, if you assume that `PartialOrd` only defines `<=` and all other comparisons are defined in terms of `<=` as I explained above

Then the

for `partial_cmp` are nothing more than the four different results of testing both `a <= b` and `b <= a`.

`a <= b` `b <= a` `PartialOrd::partial_cmp(&a, &b)`
`true` `true` `Some(Equal)`
`true` `false` `Some(Less)`
`false` `true` `Some(Greater)`
`false` `false` `None`

No, indeed not a partial order. The main point is that `PartialOrd` doesn't require reflexivity for `<=` (since it doesn't even require reflexivity for `==`).

2 Likes

I forgot that I can swap `a` and `b`, thus I need 4 results for a single binary relation already. Sorry for the confusion.

So `PartialOrd` is just a transitive relation then. Having to provide an implementation of `PartialEq` is merely an implementation detail (assuming you'd add the missing axioms).

Adding reflexivity would create a preorder, as you said:

And `Ord` would indeed be a total preorder like you said:

Which is the same as a "(non-strict) weak order", I think. Which, in turn, is cryptomorphic to a "strict weak order".

So summarizing it:

• `PartialEq` - partial equivalence relation
• `Eq` - equivalence relation
• `PartialOrd` - a transitive relation (requires implementing `PartialEq` such that if `a <= b && b <= a`, then `a == b`)
• `PartialOrd + Eq` - preorder
• `Ord` - total preorder or weak order (depending on p.o.v. / semantics)

Is that right?

yup

In terms of axioms:

transitive + symmetric: `==` in `PartialEq`
transitive + symmetric + reflexive: `==` in `Eq`
transitive: `<=` in `PartialOrd`
transitive + reflexive: `<=` in `PartialOrd + Eq`
transitive + reflexive + total: `<=` in `Ord`

1 Like

Then you're right that the documention of `std::cmp` is pretty imprecise / wrong.

Wow, the overview in `std::cmp` is kind-of sad; it doesn't even get `Eq` right anymore:

This module contains various tools for ordering and comparing values. In summary:

Well, at least it just calls it “equality”, which – to be fair – might be the right term in Rust context, since it's used to overload the “equality” operator.

You mean because it would need to say "equivalence relation" instead of "total equality"?

IDK, I guess the worst part is actually that it calls `PartialOrd` “partial ordering”, which is so far off that it cannot even be rectified: For `Eq` and `Ord` at least the description as “equality” and “total order” is “correct” if you interpret “equivalence” as “equality”, e.g. by reasoning about equivalence classes.

As you pointed out (before editing your comment) “partial equality” is a strange term, too, but at least it’s not misleading.

I would agree (but have to admit I'm not really a mathematician, disregarding my interest in math).

Yes. But if you do that, you could also claim that `Ord` is a total order, right?

I edited it, because I noticed you referred to `Eq` (sorry to have lost history now).

That’s what I said, isn’t it?

The point is that if you do that, you still cannot call “PartialOrd” a partial ordering. Only “PartialOrd + Eq” would be a partial ordering, if you interpret “equivalent” values to be “equal”. In-fact this process of considering “equivalent” values to be equal does really only work if you have an equivalence relation, so the `PartialEq` bound from `PartialOrd` is not enough.

No problem; I tend to edit posts, too.

No, you said total preorder.

I mean here:

My point was that if we interpret `Eq` as equality rather than "some equivalence relation", then we could interpret `Ord` as total order (opposed to just be a total preorder).

I agree.

Didn't we say "preorder" here? Not every preorder is a partial order.

Sure. But I also said

Calling `Ord` a trait for “total order” is okay if we interpret “equivalent” as “equal”. If we don't do that, then it's not okay. It's a conditional statement just like your statement

is a conditional statement. Hence my reaction “That’s what I said, isn’t it?”.

By the way, since interpreting “equivalent” as “equal” doesn't even work when there's no `Eq` implementation, it's more consistent to never adopt this convention, since it couldn't be used to properly describe `PartialEq` or `PartialOrd` anyways.

It's a preorder. But if we interpret “equivalent” as “equal” then it (also) becomes a partial order. Again, there's an `Eq` bound involved, so we can do this step of re-interpreting “equivalent” as “equal” in the first place.

I don't know what you mean by "equivalent" here. There are plenty of equivalence relations on `Vec<i32>`. You can't say "it just means an equivalence relation" without specifying which equivalence relation you're talking about.

`Eq` specifically implements semantic equality, which is a particular equivalence relation. It being an equivalence relation on objects is just a requirement on implementations, not the definition of what it means.