This is Words and Buttons Online — a collection of interactive #tutorials, #demos, and #quizzes about #mathematics, #algorithms and #programming.

Partial order and non-Boolean logic

Numbers. Numbers are easy. All you need to know to sort them out is that

• if 1 ≤ 2 and 2 ≤ 3 then 1 ≤ 3;
• either 4 ≤ 5 or 5 ≤ 4...
• ...or both, but if 6 ≤ 6 and 6 ≤ 6 then 6 = 6.

Oh, shit! I forgot to put a smart face on. Let's start over.

A total order, also known as linear order is a relation “≤” on a set S. For a, b, c ∈ S, the three properties hold.

The first one is called transitivity.

a ≤ b ∧ b ≤ c ⇒ a ≤ c.

The second one is connexity.

a ≤ b ∨ b ≤ a

And the third one is antisymmetry.

a ≤ b ∧ b ≤ a ⇒ a = b

With rules established for ≤, we can also tell either a < b or a > b or a = b for every a and b.

These things are draggable ↑

Real numbers are comparable. That implies that you can sort them. Of course, not only numbers are comparable. Names are comparable and sortable in alphabetical order. Skyscrapers are comparable and sortable by height. A lot of things are comparable and sortable.

But a few things aren't. Like the intervals, we use to represent numbers with errors. We use them when we don't know the exact number x but we know its error ε and therefore have all the reasons to believe that it's jammed somewhere between x₁ and x₂ where

x₁ = x − ε
x₂ = x + ε

These intervals are helpful when we want to measure a computational error of some calculation or to see if some algorithm is stable enough. They aren't comparable or truly sortable though.

Consider two overlapping intervals. Let's say, [3, 6] and [5, 8]. We know that the fist interval actually means a number between 3 and 6. The second — another number between 5 and 8. Intuitively, the latter should be greater than the former. But what if it is 5 and the former is 6? Then it's obviously less. There is a chance they are equal even.

There is some kind of order, for instance, [6, 8] is definitely greater than [3, 5]. But this order doesn't hold for every possible pair of intervals.

This makes things unpleasant. For the very least, we can't now use binary logic since all the comparisons now return three states. E. g. a ≤ b can now be true, false or none of the above.

Consequently, this means the conventional if... else statement now has to be redesigned. And all the algorithms that use it.

We wouldn't have to give up binary logic completely if we agree to “split” the semantics of the predicates into two. For every predicate on the two intervals, we can still say whether the numbers they represent definitely suffice the predicate, or whether they possibly do so.

For instance, [3, 5] is definitely less than [6, 8], and [3, 6] is possibly less than [5, 8]. The most unpleasant case for us is when intervals overlap. Everything is indefinite, and everything is possible then.

These things are draggable, too ↑

Still, every if... else works. Within its semantics that is. However, the algebra behind the logic isn't yet Boolean. Now ¬ (a < b) ≢ a ≥ b. Computational algorithms may be technically built using the same building blocks as if the intervals were numbers, but that's it.

Speaking of building stuff. Let's talk about programming. Programming non-Boolean interval logic in C++ or Python is fairly easy. You have to reimplement every predicate for the interval type — and you're golden!

struct Interval {
    Number lb; // lower bound
    Number ub; // upper bound
}

// Interval-specific predicates.
bool coincide(const Interval& l, const Interval& r){
    return l.lb == r.lb && l.ub == r.ub;
}

bool intersect(const Interval& l, const Interval& r){
    return (l.ub >= r.lb && l.lb <= r.ub)
        || (r.ub >= l.lb && r.lb <= l.ub);
}

// The "definite" interval logic.
// The relation should keep for every number in l and in r.
bool operator==(const Interval& l, const Interval& r){
    return l.lb == l.ub && coincide(l, r);
}

bool operator<(const Interval& l, const Interval& r){
    return l.ub < r.lb;
}

bool operator>(const Interval& l, const Interval& r){
    return r < l;
}

bool operator<=(const Interval& l, const Interval& r){
    return l.lb < r.ub && l.ub == r.lb;
}

bool operator>=(const Interval& l, const Interval& r){
    return r <= l;
}

bool operator!=(const Interval& l, const Interval& r){
    return r < l || l < r;
}

Nobody cares if the relationships between predicates are Boolean enough. They are all just some arbitrary functions, so with them, you can easily define both the “definite” and the “possible” logic. It's all a little verbose but doable.

It gets a little bit trickier in Rust which relies on the notion of order pretty much.

The comparison operators for a custom type are usually introduced using an std::cmp::Ord trait. It requires that:

∀ a, b: (a < b) ⊕ (a = b) ⊕ (a > b)
a ≤ b ∧ b ≤ c ⇒ a ≤ c.

The first reads as for every a and b, one and only one is true: either (a < b) or (a = b) or (a > b). This doesn't work for us. When intervals intersect, in the “definite” logic none of the predicates are true. And in the “possible” logic, they all are.

Luckily, there is another more relaxed trait that represents not total order, but partial order: std::cmp::PartialOrd. Which only requires asymmetry (not even antisymmetry) and transitivity (we've seen it before):

a < b ⇒ ¬(a > b)
a ≤ b ∧ b ≤ c ⇒ a ≤ c.

The first now reads as a could not be both less and greater than b at the same time. Аnd for the “definite” logic, this works.

impl std::cmp::PartialEq for RB32{
    // the same as operator == in C++ or __eq__(self, other) in Python
    fn eq(&self, other: &Self) -> bool {
        self.lb == other.lb && self.ub == other.ub
    }
}

impl std::cmp::PartialOrd for RB32{
    // this is usually enough to replace all the rest
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        if self.ub < other.lb {
            Some(std::cmp::Ordering::Less)
        } else if self.lb > other.ub {
            Some(std::cmp::Ordering::Greater)
        } else if self.lb == other.lb && self.ub == other.ub {
            Some(std::cmp::Ordering::Equal)
        } else {
            None // this is what differentiates Ord and PartialOrd
        }
    }

    // but since in out logic, (a < b) ∨ (a = b) ≢ a ≤ b,
    // we have to define ≤ and ≥ explicitly.
    fn le(&self, other: &Self) -> bool {
        (self.lb == other.lb && self.lb == self.ub) ||
        (self.ub == other.ub && other.lb == other.ub)
    }
    fn ge(&self, other: &Self) -> bool {
        (self.ub == other.ub && self.lb == self.ub) ||
        (self.lb == other.lb && other.lb == other.ub)
    }
}

The code is less verbose than in C++ or Python, and it would have been even less so if we were relying on Boolean algebra. With it, you don't even have to write le or ge methods explicitly, cmp is enough. With Boolean algebra, Rust can deduce the rest for you.

Ok, but that was the “definite” logic. But what about the “possible”?

I'm afraid, for this particular task, Rust comes short. In the “possible” interval logic, the intersecting intervals may be a < b, and a = b, and a > b, all at the same time. Every predicate is true since everything is possible. You can't program that with Rust Ordering. However, this is not a flaw, this is a design choice.

Non-Boolean logics are rare, and relations more general than partial order are almost never useful. If you really really want this kind of logic, you can still implement it using functions and not operators. At the same time, you can expect that if a class implements the std::cmp::Ord trait, then all the sorting algorithms will work with it correctly. While in C++, a sorting algorithm will run on anything with the operator< reloaded with no correctness guaranteed or even pinky-promised.

Conclusion

Non-Boolean logics are rare but not extinct. Interval logic is one example. Sometimes, you can implement a logic you want within total order or partial order but sometimes even that isn't enough and you need an even more general relation. With operator overloading, you have the freedom to go there but you also have less assurance when working within the known realms of the total order.