1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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, ... )

$\endgroup$
1
$\begingroup$

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?)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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