As I understand it, partial orders are binary relations that are:
- Reflexive
- Anti-symmetric
- Transitive
An example would be $\subseteq$ for sets
And if we add totality to this, we get a total (or linear) order, so a total order is
- Reflexive (this one is implied by totality, so can be removed from definition)
- Anti-symmetric
- Transitive
- Total
An example would be $\leq$ for numbers
But we also have strict linear orders, which are:
- Irreflexive (implied by asymmetry)
- Asymmetric (implied by transitivity + irreflexivity)
- Transitive
- Connex (for any $a \not = b$: either $aRb$ or $bRa$)
An example would be $<$ for numbers
So (first question), is there likewise something called a strict partial order, that would be:
- Irreflexive (implied by asymmetry)
- Asymmetric (implied by transitivity + irreflexivity)
- Transitive
an example of which would be $\subset$ for sets? I can't find any reference for a such a term …
But this also leads me to my second and main question. I do see references that say that 'order' is just short-hand for 'partial order' and that, as such, could be a total order. But if an 'order' has to be a partial order, then it has to be reflexive, and hence cannot be a strict total order. … which is weird, because you'd think a strict total order would still be considered some kind of 'order' …
I know there is such a thing as a 'preorder' which is reflexive and transitive, but without it being anti-symmetric or assymmetric, doesn;t really feel like an 'order'. In fact, if symmetric, this would be an equivalence relation, which doesn't feel like it has any 'ordering' at all. Indeed, as the name implies, a 'preorder' seems to fall short of it being an 'order'.
OK, but isn't there an obvious candidate for defining an 'order' (whether partial or linear/total) as any binary relation that is:
- Anti-symmetric
- Transitive
Interestingly, if we want to make this a 'strict order' by changing anti-symmetry into the stronger asymmetry:
- Asymmetric (and thus also anti-symmetric)
- Transitive
we obtain the 'strict partial order' from earlier, since asymmetry and transitivity imply irreflexivity. But the more general 'order' is not the same as a partial order, as an 'order' would not insist on reflexivity … nor irreflexivity … indeed it would merely indicate that there is an 'ordering' between the different objects, i.e. how an object relates to itself a general 'order' wouldn't care about.
So, is there anyone that does this? Or are we implicitly doing this (but then: what about the references that say 'order' means 'partial order'?). Or is there a good reason not to do this?
Best Answer
Transitivity is the fundamental property of all relations that we call "something something" order. Of course, an equivalence relation is also transitive, and in fact is also a preorder.
So, maybe, one can start from transitive relations, split them according to whether they are reflexive, irreflexive, or neither. (Obviously, there's nothing new in this taxonomy.) On the irreflexive branch one gets exactly the strict partial orders. On the reflexive branch one gets preorders and their specializations, namely, partial orders and equivalence relations.
On the third branch we find the riff-raff transitive relations, and I'm not sure anybody calls them orders. There are also preorders that are neither partial orders nor equivalence relations, of course. So, maybe one could adopt the definition that an ordering relation is a binary relation that is transitive and either reflexive and antisymmetric or irreflexive.
The only main difference from the definition you consider is that a relation that is transitive and antisymmetric, but neither reflexive not irreflexive, is not considered an order relation.
Totality (linearity) can be specified by saying that for all $a$ and $b$, if $a \neq b$, then either $a R b$ or $b R a$. This works for both reflexive and irreflexive relations. (Thanks to @mlc for reminding me to cover this detail.)