Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have been doing some thinking about the compostition of relations and I've had trouble remembering a number of simple facts about what happens when we compose specific types of relations. I've had to verify them mentally over and over again and still haven't commited them to memory. So I decided to make a list of them and have a good long look at it once and for all. But then I noticed that some things seem to be missing on this list.

The general question that this list was supposed to answer was: if $R,S\subseteq X\times X$ are relations of a specific kind $\mathscr F$, when is $R\circ S$ also of this kind? I have answers that satisfy me (even though they're not full) for the following list of kinds of relations.

(1) Reflexive relations.

If $R,S$ are reflexive, then $R\circ S$ is reflexive.

(2) Symmetric relations.

If $R, S$ are symmetric, then $R\circ S$ is symmetric iff $R\circ S=S\circ R.$

(3) Transitive relations

If $R,S$ are transitive, then $R\circ S=S\circ R$ implies that $R\circ S$ is transitive. The transitivity of $R\circ S$ doesn't imply $R\circ S=S\circ R.$

(4) Idempotent relations.

If $R, S$ are idempotent relations, then $R\circ S=S\circ R$ implies that $R\circ S$ is idempotent. The idempotence of $R\circ S$ doesn't imply $R\circ S=S\circ R.$

(5) Preorders.

If $R,S$ are preorders, then $R\circ S$ is a preorder iff $R\circ S=S\circ R.$

(6) Equivalence relations.

If $R,S$ are equivalence relations, then $R\circ S$ is an equivalence relation iff $R\circ S=S\circ R.$

I would like to know if we can give any simple sufficient and/or necessary conditions for $R\circ S$ to be in the family of relations $\mathscr F\subseteq 2^{X\times X}$ when $R,S\in \mathscr F,$ where

(7) $\mathscr F$ is the family of anti-symmetric relations on $X$;

(8) $\mathscr F$ is the family of partial orders on $X$;

(9) $\mathscr F$ is the family of total orders on $X.$

I would be especially interested in (8). I have not been able to find any such conditions for those families, but I also don't see why they shouldn't exist.

EDIT 1. Please don't hesitate to post more complex conditions, or anything regarding this for that matter.

EDIT 2. No one has replied so far, and maybe it's because I've not put enough effort into this question. I'll add something I have found out.

Let $R$ be a total order on a set $X$ with $\operatorname{card}(X)>1.$ Then $R^{-1}$ is also a total order and we have that

(a) $R\circ R^{-1}$ is not anti-symmetric;

(b) $R\circ R$ is a total order.

For (a), let's take $x,y\in X,$ $x\neq y.$ We may assume that $(x,y)\in R$ and $(y,x)\in R^{-1}.$ Then $(x,y)\in R$ and $(y,y)\in R^{-1},$ so $(x,y)\in R\circ R^{-1},$ and also $(y,y)\in R$ and $(y,x)\in R^{-1},$ so $(y,x)\in R\circ S.$ This proves (a).

For (b), it's easy to check that any preorder, so any total order too, is an idempotent relation so $R\circ R=R$ and (b) is proven.

From (a), it follows that

(7a) A composition of anti-symmetric relations may not be anti-symmetric;

(8a) A composition of partial orders may not be a partial order;

(9a) A composition of total orders may not be a total order.

From (b), it follows that

(7b) A composition of anti-symmetric relations may be anti-symmetric;

(8b) A composition of partial orders may be a partial order;

(9b) A composition of total orders may be a total order.

Therefore all possibilities are actual. But I still don't see any conditions apart from the very simple ones (a) and (b) give.

EDIT 3. A tiny bit of apparent progress. Every total relation is reflexive and the composition of two reflexive relations contains both composed relations. Also, if a relation $T$ contains a total relation $U$, then $T$ is total. So we get

(10) If $R,S$ are total relations, then $R\circ S$ is total.

For (9), this gives us

If $R,S$ are total orders, and $R\circ S$ is a partial order, then $R\circ S$ is a total order.

That's not much though.

EDIT 4. Buling on (a), I've found that commuting doesn't seem to have much to do with these questions, unlike (2)-(6). If $R$ is a total order on a set $X$, then $R\circ R^{-1}=X\times X=R^{-1}\circ R,$ which fails to be anti-symmetric for $\operatorname{card}(X)>1.$

share|improve this question
    
I suspect that the reason you haven't gotten any answers yet is not so much that you haven't put enough effort into this question (I'd say you've put quite a bit of effort into it :-) but that composing partial orders isn't something that comes up a lot; there don't seem to be any "natural" conditions here, except what one might call the two partial orders being "compatible", but I suspect spelling that out might not lead to anything other than the condition that their composition should be anti-symmetric and transitive. –  joriki Mar 6 '12 at 16:17
    
@joriki Thanks for the comment. Is this word, "compatible" a term that's actually used? You are saying that something could be spelled out, but I'm not sure what. –  user23211 Mar 6 '12 at 16:28
    
No, I put it in scare quotes to indicate that it's just me trying to express a vague intuition, and I think that trying to nail down that intuition may well result in nothing more than the conditions of anti-symmetry and transitivity, much like it turned out with dtldarek's answer (which was posted right after my comment). –  joriki Mar 6 '12 at 17:01

1 Answer 1

up vote 1 down vote accepted

What I will prove is that $R \circ S$ is a partial order if and only if it is transitive (1) and $$\forall a \neq b \in X.\ (a R b \Rightarrow \neg b S a) \land (b S a \Rightarrow \neg a R b)\,. \quad\quad\quad(2) $$

Let $T = R \circ S$. If there exist two different $a$ and $b$ such that $aRb \land bSa$ then $a T b \land b T a$ and this contradicts antisymmetry. On the other hand, there is no such pair, then

  • $a T a$, because $a R a$ and $a S a$,
  • $a T b \land b T c \Rightarrow a T c$, because of (1),
  • $a T b \land b T a \Rightarrow a = b$ because of (2).

I know that this is a bit trivial, but from this follows that $R\circ S$ is a total order if and only if $R = S$ (otherwise (2) fails). What's more it seems that there may be arbitrary nasty examples for the lack of transitivity, so the condition that implies it has to be really strong, for example $R \subseteq S$ or $S \subseteq R$ or $\forall a,x,b,y,c \in X.\ aRxSbRySc \Rightarrow aRy \lor xSc $ are all sufficient (but not necessary).

share|improve this answer
    
This is even more trivial than I thought it was -- (2) is just antisymmetry :-( Left post as it was, because the argument for total order is easier than with ordinary definition. –  dtldarek Mar 6 '12 at 16:50
    
Thank you. I did not notice the fact about total orders so your post was helpful. –  user23211 Mar 6 '12 at 21:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.