[Math] order and binary relation

elementary-set-theoryorder-theoryrelations

Are order and binary relation the same thing, or order is just some special binary relation? If it is the latter, what kinds of properties distinguish an order from a general binary relation?

Thanks and regards!


Sorry for the confusion already caused. What I thought was that a partial order is just some special order, and there are other orders that are not partial orders, such as preorder, the order on a directed set. So I was wondering how an order was defined then, and I saw there was no definition for an order in the Wikipedia page for order theory.

I believe I was not lazy or could not read, what I understood was different from yours, and I did not realize that when I first posted my question. So sorry about that!

At the end, if possible, I would like to know if there is a concept that can include partial order, preorder and the "order" on a directed set, but more special than a binary relation.

Thanks!

Best Answer

Orders are a special kind of binary relation.

A binary relation $R$ on a set $A$ is just a collection of ordered pairs $R\subseteq A\times A$, with absolutely no conditions on $R$. So long as it is a subset, it is a binary relation.

A (partial) order on $A$, by contrast, is a subset $P\subseteq A\times A$ which satisfies three conditions:

  1. The relation is reflexive: For every $a\in A$, $(a,a)\in P$.
  2. The relation is anti-symmetric: for every $a,b\in A$, if $(a,b)\in P$ and $(b,a)\in P$, then $a=b$.
  3. The relation is transitive: for every $a,b,c\in A$, if $(a,b)\in P$ and $(b,c)\in P$, then $(a,c)\in P$.

The partial order is a total or linear order if, in addition, for every $a,b\in A$, either $(a,b)\in P$ or $(b,a)\in P$.

So an order on $A$ is a special kind of binary relation, because it must satisfy the three properties above, whereas a "general binary relation" doesn't have to satisfy anything other than being a collection of ordered pairs of elements of the set.


Okay, addressing your additions.

The most basic notion is "partial order". Every other kind of order is a "partial order with extra conditions".

The one exception is a pre-order, because, as the name indicates, a pre-order is something which is not yet an order (again, "order" is just a short way of saying "partial order"), but may become one (when it grows up, so to speak).

Pre-orders

A pre-order is a binary relation which is reflexive and transitive, but is not necessarily anti-symmetric. An example of this is the relation "divides" in the integers: define $a\preceq b$, with $a$ and $b$ integers, if and only if $a$ divides $b$. This is reflexive (every integer divides itself), and transitive (if $a$ divides $b$ and $b$ divides $c$, then $a$ divides $c$), but it is not anti-symmetric, because if $a$ divides $b$ and $b$ divides $a$, the best you can conclude is that $|a|=|b|$; for instance, $2$ and $-2$ are different, but $2\preceq -2$ and $-2\preceq 2$. So this relation is not a partial order because it lacks anti-symmetry.

One way to solve this lack is to use the relation to define something which is a partial order on a closely related set. We define an equivalence relation on the integers by saying $a\sim b$ if and only if $a\preceq b$ and $b\preceq a$ (in this case, if and only if $|a|=|b|$). Then we can consider the quotient set, and define the relation $\leq$ on the quotient set by $[a]\leq [b]$ if and only if $a\preceq b$ (here, $[a]$ is the equivalence class of $a$ under $\sim$, etc). Then one can show that this is a partial order on the quotient set; it is patently closely related to the original pre-order $\preceq$.

That's why relations that are reflexive and transitive are called pre-orders: you only need one further step to get to a partial order, though not usually on the set you started with.

Other kinds of orders

The basic notion, as I said above, is "partial order". There are lots of extra conditions one can put on a partially ordered set to make it a "nicer" kind of ordered set. These extra conditions define special kinds of orders. A random sampling off the top of my head (I'm using $\leq$ to denote whatever the partial order relation in question is; $a\leq b$ means $(a,b)$ is in the relation that defines the order):

  • Total or linear orders. In a partial order, it is possible for two elements to not be comparable at all, that is, you have neither $a\leq b$ nor $b\leq a$. For example, if you take a set $X$, you can define a partial order on $\mathcal{P}(X)$, the power set of $X$ (the set of all subsets of $X$) by saying that $A\leq B$ if and only if $A\subseteq B$ (in fact, this is in a sense the most basic kind of "partial order"). If $X$ has more than one element, though, then you have elements of $\mathcal{P}(X)$ that cannot be compared: take $x,y\in X$, $x\neq y$; then $\{x\}\not\leq \{y\}$ and $\{y\}\not\leq\{x\}$. This in contrast to the order relations we are used to in the natural numbers, real numbers, etc., where any two elements can be compared: one is bigger than the other. So we add a condition: the partially ordered set $A$ is totally ordered or linearly ordered if the partial order also satisfies the condition that for every $a,b\in A$, either $a\leq b$ or $b\leq a$.

  • Well order. This is a very strong generalization of total orders. In a total order, any subset with finitely many elements has a smallest element. A partially ordered set $A$ is said to be well-ordered if any nonempty subset $B$ of $A$ has a smallest element. For instance, the natural numbers with their usual order is well-ordered, but the real numbers with their usual order are not (the positive reals have no least element). A well-order must be a total order, but the converse is not true in general.

  • Lattice order. A lattice order is a partial order where, even though it is not true that any two elements are comparable, it is nevertheless the case that any two elements have a least upper bound (given $a,b\in A$, there exists a $c\in A$ such that $a\leq c$, $b\leq c$, and for every $d\in A$, if $a\leq d$ and $b\leq d$, then $c\leq d$), and a greatest lower bound (the dual concept; just reverse all the inequalities in the definition above). The typical example is going back to the partially ordered set of subsets of a given $X$ under inclusion; the least upper bound of $A$ and $B$ is $A\cup B$, and the greatest lower bound is $A\cap B$. You can weaken the definition to require only least upper bounds (upper semi-lattice) or just greatest upper bounds (lower semi-lattices). Or you can strengthen it to require least upper bound and/or greatest lower bounds for any nonempty subset (complete lattices); you can also require the existence of a smallest element and/or a greatest elements, or the existence of "complements" (if $0$ is the smallest element and $1$ is the greatest element, then a complement of $a\in A$ is an element $b\in A$ such that the least upper bound of $\{a,b\}$ is $1$ and the greatest lower bound of $\{a,b\}$ is $0$; in the case of $\mathcal{P}(X)$, the complement is the usual set-complement relative to $X$).

  • Directed sets. This is a kind of compromise between partially ordered sets and linear sets, in one direction: a partially ordered set $A$ is directed if and only if for every $a,b\in A$ there exists a $c\in A$ such that $a\leq c$ and $b\leq c$ (any two elements have a common upper bound). the dual notion, where any two elements have a common lower bound, is called an inversely directed sets. They play an important role in many areas of mathematics to construct special kinds of limits; when the index set is a directed system, you get something called a directed limit; when the index set is an inversely directed set, you get something called an "inverse limit". The $p$-adic integers are an example of an inverse limit.

Note: These are just a few of the ones I know, and they are likely a very limited sample of the ones that people who actually work with orders know. I don't do research anywhere near these topics, I just use orders all the time, like most mathematicians.

Strict orders

In addition, there is a "sister" notion to partial orders, called "strict orders". A binary relation $\prec$ is a strict order if and only if it is:

  1. Anti-reflexive: for every $a\in A$, $a\not\prec a$.
  2. Asymmetric: for all $a,b\in A$, if $a\prec b$, then $b\not\prec a$.
  3. Transitive: for every $a,b,c\in A$, if $a\prec b$ and $b\prec c$, then $a\prec c$.

However, strict and partial orders are actually closely connected. If you have a partial order $\preceq$, then you can define a strict order $\prec$ by $$a\prec b \Longleftrightarrow a\preceq b\text{ and }a\neq b.$$

Conversely, if you have a strict order $\prec$, then you can use it to define a partial order $\preceq$ by $$a\preceq b \Longleftrightarrow a\prec b\text{ or } a=b.$$

So you can take either notion as your "original" notion, and define the other one in terms of it. These days, it is more common to take "partial order" as the original, and define strict order in terms of it.

Related Question