MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let there be > included in AxB as a binary relation. What does (x)>^2(y) mean? What is the meaning of an order relation raised to a power? My first tought was that >^2 = >x> which is a cartesian product of > included in AxB. I have a solution in a Linear Algebra book : (x)>^2(y) = x+2 >= y , wich is a bit confusing; I see that the digit 2 summed from nowhere has to do something with the exponent but I don't quite comprehend the logical flow.

share|cite|improve this question
Although I gave an answer to your question without considering the issue, this question might have been better placed at, and in the future I would encourage you to consider posting questions in that forum. – Joel David Hamkins Aug 14 '11 at 11:23
Uhh, what do you mean? Isn't this forum dedicated to mathematics? – NemeXis Aug 14 '11 at 18:13
Oh, I understand that this forum is for research level questions only. I should have read the FAQ. – NemeXis Aug 14 '11 at 18:21
up vote 2 down vote accepted

If $R$ and $S$ are binary relations, then the composition relation $R\circ S$ is usually defined by $a\mathrel{R\circ S} c$ if and only if there is $b$ such that $a\mathrel{R}b$ and $b\mathrel{S}c$.

In the special case where the relations are the (graphs) of functions $f$ and $g$, this produces the (graph) of the usual composition function $f\circ g$, since $z=(f\circ g)(x)\iff \exists y\ z=f(y)$ and $y=g(x)$. (But if one understands the graph with the variables in the order $(x,y)$, as is usual, then the composition relation technically is $g\circ f$.)

In the case of an order $\lt$, what the relation $\lt^2$ would mean is ${\lt}\circ{\lt}$, which would be defined by $a\mathrel{\lt^2} c$ if and only if there is $b$ such that $a\lt b\lt c$.

In a discrete order, such as the usual order $\lt$ on the integers $\mathbb{Z}$, this means that $r\mathrel{\lt^2} t$ if and only if there is $s$ with $r\lt s\lt t$, which is the same relation as $r+2\leq t$, which may explain the confusing $+2$ issue you mention. Similarly, in the integers we have $r\mathrel{\lt^n} t$ if and only if $r+n\leq t$.

Meanwhile, in a dense order $\lt$, such as the order on the rationals, we have $\lt^2=\lt$, since $a\lt c\iff\exists b\ a\lt b\lt c$. Also, in any reflexive relation $\leq$, we have $\leq^2=\leq$, since $a\leq b\iff a\leq a\leq b$.

share|cite|improve this answer
Already figured, thanks anyway; what about <∘<∘< ? What are the couples implied and how are they mixed in the conditions for that to be true? I mean let there be (A,B;<) , (C,D;<) , (E,F;<) , a<∘<∘<f , what does that imply? What are the existance conditions, and for what couples? And what are the included sets that work along with this composition? ; if for (A,B;<) , (C,D;<) , a<∘<d <=> ∃ x∈B∩C so that (a,x)∈< and (x,d)∈< – NemeXis Aug 14 '11 at 18:07
Composition is associative, so it doesn't matter how you group the compositions. As for the domain and range, the situation for composing relations is just like that for composing functions, in that the codomain of one relation should generally line up with the domain of the next, but one can in any case make the definition exactly as I made it, if one understands a binary relation as a set of ordered pairs. – Joel David Hamkins Aug 14 '11 at 20:32

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.