# standard definitions when talking about ordered sets

What is the standardization if any when it comes to ordered sets?.

Specifically I'm always confused in the following cases:

1) When someone say "a partial ordered set": to me it can mean a strict partial ordered set (The relation is asymmetric and transitive) or a non strict partial ordered set (the relation is antisymmetric, reflexive and transitive), but many books refer to partial ordered sets like they were non strict and excluding the other case, why?.

2) When someone say "a total ordering": to me it can mean a strict total ordered set or it can mean a non strict total ordered set, but many books refer to total orders like they were non strict and excluding the other case.

3) When someone say "an ordered set" : to me it can mean any ordered set, partial, complete, strict, or non strict, but many books don't make this distintion and they refer to a "non strict partial orderd".

Am I missing something? Is it just me the one making these distintions?, please help me clarify this.

-
Hi, I give an answer to the question, maybe helpful for you. – Paul Jun 12 '13 at 4:50

In my experience the term partial order usually — I might even go so far as to say almost always — means a reflexive, transitive, antisymmetric relation; this is the standard definition. A reflexive, transitive, asymmetric relation is usually termed a strict partial order. I have occasionally seen the term partial order used as you suggest, ambiguously to mean either a (non-strict) partial order or a strict partial, so that the reader is forced to rely on context to determine which is meant in any particular instance; in my opinion this usage is better avoided. (The one exception is when one wants to talk about several partial orders at once, some strict and some non-strict, and wants a cover term for the both kinds as well as the specific terms strict partial order and non-strict partial order.)

The same applies to total (or, as I prefer, linear) orders, though not so strongly: I’m pretty sure that I see linear order used ambiguously more often than I do partial order. Still, I’d say that the most common definition is that a linear order is a partial order (in the narrow sense) in which every two elements are comparable, and that a strict linear order is a strict partial order in which every two distinct elements are comparable.

Without a context I would not even attempt to guess what someone means by ordered set, and I would not use the term without defining what class of orders I had in mind. The term can be used very broadly, but I’ve also seen it used very narrowly to mean simply linear order.

-
So, basically you say that if someone should mean "strict" he should make it explicit, otherwise we should understand "non-strict", right?. I'm just studying these concepts for the first time so its a little confusing... – Daniela Diaz Jun 12 '13 at 6:06
@Daniela: That’s definitely the way that I would use and recommend using the terms, and it’s the safest default interpretation. However, you will sometimes find people using them differently, so you always have to look out for that possibility. For instance, if someone says partial order but consistently writes $\prec$, say, and not $\preceq$, there’s a decent chance — far from a certainty, but a decent chance — that he actual means strict partial order. – Brian M. Scott Jun 12 '13 at 6:13
I have been seeing the term "linear order" used in recent research papers almost always in the strict sense. So I would personally go for "total order" to mean a transitive, reflexive, antisymmetric relation in which $\forall a,b: (a\le b)\lor(b\le a)$ and "linear order" to mean a transitive, antireflexive relation in which $\forall a,b:(a<b)\lor(b<a)\lor(a=b)$. – dfeuer Jun 12 '13 at 6:24
@dfeuer: That may be, but I’d have words with anyone who wanted to make a distinction between linear order and total order. – Brian M. Scott Jun 12 '13 at 6:27
@BrianM.Scott: The strangest I've ever seen was Kelley, who defined an order as a transitive relation (that's right, not even antisymmetric, and neither reflexive nor antireflexive) and a total order in some way I don't recall exactly, but which I don't think required it to be either reflexive or antireflexive. – dfeuer Jun 12 '13 at 7:01

The definition an ordered set is the same as a partial ordered set, i.e.,

Let $X$ be a set and $\le$ a relation on $X$. We say that $\le$ orders $X$, or that $\le$ is an order in $X$, if $\le$ has the following properties:

1) If $x\le y$ and $y\le z$, then $x\le z$.

2) For every $x\in X$, $x\le x$.

3) If $x \le y$ and $y\le x$, then $x=y$.

A set $X$ together with an order $\le$ in $X$ is called an ordered set, or partial ordered set. They are same.

Note that two elements $x$ and $y$ of an ordered set $X$ can be incomparable, i.e., it can happen that neither $x\le y$ nor $y\le x$ holds.

Totally ordered set, is also called linearly ordered set or chain. Its definition is this:

Let $X$ be a set and $<$ a relation on $X$. We say that $X$ is a totally ordered set if $<$ has the following properties:

1) If $x\not= y$ and then $x<y$ or $y<x$.

2) If $x<y$, then $y<x$ doesn't hold.

3) If $x < y$ and $y<z$, then $x<z$.

Note that two elements $x$ and $y$ of an ordered set $X$ can be comparable.

-
Hey Paul, thanks for your answer. It seems like that's what I'm looking for... So accordingly ordered set= partially ordered set= non strict partially ordered set. right? – Daniela Diaz Jun 12 '13 at 5:14
The condition 1) of being totally ordered set says that two elements must be comparable, but you say that they can be comparable, so I'm confused – Daniela Diaz Jun 12 '13 at 5:15
@DanielaDiaz: It means that for any two distinct elements $x$ and $y$ they are comparable, i.e., $x <y$ or $y <x$. I'm not familar with strict partially ordered. I guess it is the same as totally ordered set. – Paul Jun 12 '13 at 5:28
Your definition of totally order set doesn't allow equallity because of condition 2). Then it only aplies to strict ordered sets . But what about non strict ordered sets in which all its elements are comparable, they are also ordered sets right? – Daniela Diaz Jun 12 '13 at 5:32