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 am trying to see if the following relation is reflective, symmetric and transitive:

$(i, j),(k, l)$ are in relation R if:
$(i < k$ $\land $ $k \le j \le l) \lor (k < i$ $\land$ $i \le l \le j )$

The only exercices I had on this subject was to prove reflexivity/symmetry/transitiviy for really simple binary relations such as:

$(x, y) R (s, t) = (x + y) = (s + t)$

For a simple case like this, I know how to proceed. The thing that confuses me is when I have to deal with couples and inequalities. I simply don't know how to approach the problem.

Anyone could point me in the right direction so I know how to deal with these couples/inequalities?

share|improve this question

4 Answers 4

up vote 2 down vote accepted

It’s the same process as for a simpler relation; the notation just gets a bit more cumbersome.

To show that $R$ is reflexive, you’d have to show that $(i,j)\,R\,(i,j)$ for every $(i,j)$. Now translate that into more basic terms, using the definition of $R$: you’d have to show that for each $(i,j)$, either

$$i<i\text{ and }i\le j\le j$$ or

$$i<i\text{ and }i\le j\le j\;.$$

Since these are the same statement, you'd have to prove that $i<i$ and $i\le j\le j$ for each $(i,j)$. But you can do at most half of this: if $i\le j$, then it’s true that $i\le j\le j$, but it’s never true that $i<i$. Thus, $R$ is not reflexive: it’s not true that $(i,j)\,R\,(i,j)$ for each $(i,j)$. In fact, it’s not true for any $(i,j)$, so $R$ is irreflexive.

I’m going to leave symmetry for you; it’s pretty easy if you think about the form of the definition of $R$, and transitivity is a bit messier.

To show that $R$ is transitive, you’d have to show that for any $(i,j),(k,\ell)$, and $(m,n)$, if $(i,j)\,R\,(k,\ell)$ and $(k,\ell)\,R\,(m,n)$, then $(i,j)\,R\,(m,n)$. Here again your automatic first step should be to translate this:

  • either $i<k$ and $k\le j\le\ell$, or $k<i$ and $i\le\ell\le j$, and
  • either $k<m$ and $m\le\ell\le n$, or $m<k$ and $k\le n\le\ell$,

and the desired conclusion is

  • either $i<m$ and $m\le j\le n$, or $m<i$ and $i\le n\le j$.

You could systematically investigate all of the combinations: $i<k$ and $k<m$, $i<k$ and $m<k$, $k<i$ and $k<m$, and $k<i$ and $m<k$. Or you could try to look ahead to see whether one combination seems especially problematic. Specifically, what if $$i<k\text{ and }k\le j\le\ell\tag{1}$$ and $$m<k\text{ and }k\le n\le\ell\;?\tag{2}$$ Is there any guarantee from $(1)$ and $(2)$ that either $i<m$ or $m<i$? No, because it might be the case that $i=m$. Is this possibility actually consistent with $(1)$ and $(2)$? If $i=m$ they say that

$$i<k\text{ and }k\le j\le\ell\text{ and }k\le n\le\ell\;,$$

which is certainly possible. Thus, we can’t in general infer $(i,j)\,R\,(m,n)$ from $(i,j)\,R\,(k,\ell)$ and $(k,\ell)\,R\,(m,n)$: if $i=m<k$ and $k\le j,n\le\ell$, $(i,j)\,R\,(k,\ell)$ and $(k,\ell)\,R\,(m,n)$ will be true, but $(k,\ell)\,R\,(m,n)$ won’t be. In particular, if $(m,n)=(i,j)$ and $i<k$ and $k\le j\le\ell$, we get a counterexample to transitivity of $R$.

(Actually, if you show first that $R$ is irreflexive and symmetric, you can take a shortcut to show that it can’t be transitive. Just find two different pairs $(i,j)$ and $(k,\ell)$ such that $(i,j)\,R\,(k,\ell)$. Then by symmetry $(k,\ell)\,R\,(i,j)$, so if $R$ were transitive, we could deduce that $(i,j)\,R\,(i,j)$. However, ... )

share|improve this answer

It isn't reflexive. (Why? Try letting $k=i$ and $l=j$ and see if things still work.)

To see why it's symmetric, notice that we can obtain $k<i\wedge i\le l\le j$ from $i<k\wedge k\le j\le l$ (and vice versa) by simply swapping $i$ with $k$, and $j$ with $l$.

Since it's symmetric, but not reflexive, then it can't be transitive. (Why?)

share|improve this answer

There really is nothing different about this sort of problem even if the relation involves inequalities.

Reflexive: Is is true that that for all $(i,j)$, $(i,j)R(i,j)$?

Symmetric: Is it true that if $(i,j)R(k,l)$, then $(k,l)R(i,j)$?

Transitive: Is it true that if $(i,j)R(k,l)$ and $(k,l)R(m,n)$, then $(i,j)R(m,n)$?

Write out what these statements would mean by the definition of $R$, then determine if the statement is true or false.

share|improve this answer

Start by writing down exactly what you have to prove. E.g. to show reflexivity for your provided much easier relation, one has to show x + y = x + y for all x and y, which obviously holds. What has to hold for your more complicated relation to be reflexive?

share|improve this answer

Your Answer

 
discard

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.