7
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I think that order can be partial order, total order, quasi-order, and perhaps other things. I mean it can be each or all of these. Each author may apply the term according to contextual convenience, if (s)he uses only a specific setting. Usually it is said what it is. Once I attended a talk in which the person (I don't remember his name) would call order to a total order, and partial order to what it is. I think most people don't like this and order would preferably used to refer to all relations above or perhaps others similar. $\endgroup$ – amrsa Mar 30 '17 at 18:05
  • $\begingroup$ There is a community using preorder for a relation that is reflexive and transitive. This is more general than partial or total order. $\endgroup$ – mlc Mar 30 '17 at 18:37
  • 1
    $\begingroup$ Considering your definition of strict linear order, you cannot have both irreflexivity and totality. F.i., you cannot claim $x < x$ for numbers. $\endgroup$ – mlc Mar 30 '17 at 18:39
  • $\begingroup$ @mic Correct, but the definition of totality for strict orders usually includes an exception clause (if $a \neq b$...). $\endgroup$ – Fabio Somenzi Mar 30 '17 at 18:41
  • $\begingroup$ @mlc Yes, right. I read somewhere that $R$ is 'connex' when for any $a \not b$: either $$a R b$ or $b R a$. So that's what I should have used instead of total. Thanks! $\endgroup$ – Bram28 Mar 30 '17 at 21:45
3
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Thanks for your thoughts and interesting suggestions. But from what I gather form your answer ... there doesn't seem to be a clear mathematical definition (or at least concensus on such a definition) of what an 'order' is... would you agree with that? How about 'strict partial order' though: is it at least clear what that is? $\endgroup$ – Bram28 Mar 30 '17 at 21:52
  • $\begingroup$ @Bram28 Agreed. Most people jump right in the middle and define some type(s) of order. That was my impression and has been slightly reinforced by a whole 10 minutes of googling. I believe "strict partial order" is a standard concept and is simply a relation that is transitive and irreflexive, or, equivalently, transitive and asymmetric. $\endgroup$ – Fabio Somenzi Mar 30 '17 at 21:58
2
$\begingroup$

A strict partial order is a relation that's irreflexive and transitive (asymmetric is a consequence). This is the most common definition.

Actually, this notion is completely equivalent to the notion of partial order (a reflexive, antisymmetric and transitive relation).

Indeed, if $X$ is a set and $\Delta_X=\{(x,x):x\in X\}$, we have that

  • if $S$ is a strict partial order on $X$, then $S^+=S\cup\Delta_X$ is a partial order;

  • if $R$ is a partial order on $X$, then $R^{-}=R\setminus\Delta_X$ is a strict partial order on $X$;

  • if $S$ is a strict partial order on $X$, then $S=(S^+)^-$;

  • if $R$ is a partial order on $X$, then $R=(R^-)^+$.

You can try your hand in proving the statements.

So any strict partial order determines a unique partial order and conversely. Passing from $S$ to $S^+$ is essentially the same we do when passing from $<$ on numbers to $\le$.

The property of being a linear (or total) order can be expressed by

for all $a,b\in X$, if $a\ne b$, then either $a\mathrel{T}b$ or $b\mathrel{T}a$

where $T$ is a (strict) partial order.

Are strict partial orders useful? Yes. If you compare the two definitions, you see that equality is not necessary in the definition of a strict partial order (not for linear ones, though), which makes them attractive for certain logic frameworks where equality has no particular status with respect to other predicates.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.