2
$\begingroup$

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!

  • 0
    Hi Arturo, how to tell if a question belongs to elementary set theory or set theory? Thanks!2010-11-26
  • 3
    An order is a special kind of binary relation; it satisfies several additional properties that an arbitrary binary relation doesn't, which are clearly spelled out in the corresponding Wikipedia article.2010-11-26
  • 3
    Your first question is answered in the first sentence of the first article you linked to. The second question is answered in the rest of that article.2010-11-26
  • 1
    @Tim: "Elementary-set-theory" is used to tag questions like this, about the basic theory of sets. "Set theory" is used to tag the kinds of questions that people who work in set theory think about: cardinal arithmetic, cofinality, models, forcing, independence of axioms, etc. We're trying to make sure the (set-theory) tag is not used for elementary questions, which is what (elementary-set-theory) is for.2010-11-26
  • 0
    Okay, I am obviously not smart. I don't find where in the article of order theory the definition for an order is defined. What I see are the informal background of order and definitions for various kinds of orders.2010-11-26
  • 0
    @Tim: "basic definitions."2010-11-26
  • 0
    @Tim, the article says that order theory is concerned with "various kinds of binary relations". Then you can go to the section on partially ordered sets to start seeing some of the particular properties considered.2010-11-26
  • 0
    @Tim: the article on order theory gives the definition right here: http://en.wikipedia.org/wiki/Order_theory#Partially_ordered_sets2010-11-26

1 Answers 1

9

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.

  • 3
    Arturo, please don't take this the wrong way, but I really do not see the point of giving these kinds of answers when the answer is in a link that the _OP himself_ has provided.2010-11-26
  • 0
    Thanks, Arturo! The definition is for a partial order. I think a partial order is just a special kind of order, isn't it? There are also other orders, such as preorder and the order for a directed set, which are not partial orders. Am I correct? So what is the definition for an order then?2010-11-26
  • 0
    @Qiaochu: Yes, I think you are right in the abstract. It is hard to see whether the OP is having trouble because he has not thought about it, or because he is not understanding what the links say. I agree that he did not give us an indication of which one it is. In the former case, this answer is a bad idea (it encourages mental laziness); in the latter, simply trying to repeat things in perhaps a slightly different way may help get the penny to drop (think about the student coming to office hours who has read the book but doesn't get it; just going over it again in different words can help).2010-11-26
  • 1
    Condition 2. is not what you meant it to be, I presume.2010-11-26
  • 1
    @Tim: "order" is synonymous with "partial order." In particular, preorders that are not partial orders are not orders. (In hindsight I agree this is slightly confusing. "Partial order" is named in contrast with "total order," although a total order is also a partial order. That is, order theory is the study of partial orders.)2010-11-26
  • 0
    @Tim: Please try reading what I wrote and what you linked to. "Order" is the generic term with which one refers to any kind of partial order, whether it be total or not. A pre-order is not a partial order (It does not satisfy anti-symmetry), but that can be used to define a partial order in a slightly different set; this "margin", alas, is not enough to contain a good answer to that query. If you would add it to the question, and give some indication of why the links you provide do not answer your questions, I'll add to the answer.2010-11-26
  • 0
    @Jonas Meyer: Oops; must be thinking equivalence relations... Thanks.2010-11-26
  • 0
    @Arturo and Qiaochu: Sorry about that. I understand why you are so *angry*. I just updated my original post for clarification.2010-11-26
  • 0
    @Tim: Ehr... I'm not angry at all. What made it look like I was?2010-11-26
  • 0
    @Arturo: That's good to know! :^)2010-11-26
  • 1
    @Tim: No, seriously; what made it look like I was angry? So I can not do it in the future (unless I *am* angry, at any rate).2010-11-26
  • 0
    @Arturo: I have to admit I used the word *angry* too arbitrarily. Honestly, I felt hurt when you guys were talking about the hypotheses about me from being too lazy to give some thinking to not being able to read.2010-11-26
  • 2
    @Tim: well, for the future, if you are confused about something for which you "explanations" or "links" in front of you, it is best to explain *why* you are confused. That will show to one and all that you have tried to figure it out on your own but cannot. We can all miss the obvious from time to time, but it is best to show that you are at least trying before asking others to do it for you.2010-11-26