Orders, Partial Orders, Strict Partial Orders, Total Orders, Strict Total Orders, and Strict Orders

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?

• 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. Mar 30, 2017 at 18:05
• Considering your definition of strict linear order, you cannot have both irreflexivity and totality. F.i., you cannot claim $x < x$ for numbers.
– mlc
Mar 30, 2017 at 18:39
• @Bram28.In Barbara Partee, Mathematical methods in Linguistics, I find the term " strict orfder" for what you are looking for. " An order is a binary relation which is transitive and in addition is (1) either reflexive and an,antisymetric or (2) reflexive and asymetric. The former are weak orders, the latter are strict ( or strong)".
– user654868
Apr 25, 2019 at 20:34
• @Bram28.All this is not totally clear to me, but it seems as though 2 criteria had to be taken into account : (1) week or strict and (2) partial or total ( in case any two elements are comparable). That would give four cases. Partee adds " when an order, strict or weak, is also connected, then it is said to be total , or linear order". ( Math. Meth in Linguistics, Part A/ §3.5)
– user654868
Apr 25, 2019 at 20:35
• @Bram28. Your question is a very useful one.
– user654868
Apr 25, 2019 at 20:38

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

• 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? Mar 30, 2017 at 21:52
• @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. Mar 30, 2017 at 21:58

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.

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'

The fundamental problem is with the word “strict,” which doesn't act like a normal adjective: a strict total order is-not-a total order. I think it would be clearer if we always said “non-strict total order” or “non-strict order” rather than simply “total order” or “order” respectively, but that ship may have sailed.

• Yes, 'partial' and 'strict' don't work like normal adjectives, that's for sure :P Still, I am surprised we don;t have a term for something that just has the transitive and anti-symmetry property without mandating it to be reflexive or irreflexive. Sep 25, 2023 at 19:48
• Agreed. I am particularly frustrated that thereʻs no simpler way to say “(non-strict) weak order” that doesnʻt read as ambiguous to non-mathematicians. As a result, I think, we computer scientists end up using “strict weak order” to describe comparisons even though using the non-strict kind would simplify things. I may be missing something, but in what way does ʻpartialʻ not work normally? Sep 26, 2023 at 17:17
• As far as I can tell, a 'partial' order is always reflexive ... which I really don't get. To me, the 'partialness' of an order is that we can't always order any two objects .... the subset relation is of course the paradigmatic example of that. But that has nothing to do with reflexiveness ... Sep 26, 2023 at 17:47
• OK, but I don't think that the way the word "partial" is defined is causing that problem. I think it's the implicit "non-strict" that attaches to all orderings unless you explicitly say otherwise. I.e. weird "strict" bites again. Sep 28, 2023 at 4:08