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?

3 Answers 3

2

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 or

$i

Since these are the same statement, you'd have to prove that $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. 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 and $k\le j\le\ell$, or $k and $i\le\ell\le j$, and
  • either $k and $m\le\ell\le n$, or $m and $k\le n\le\ell$,

and the desired conclusion is

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

You could systematically investigate all of the combinations: $i and $k, $i and $m, $k and $k, and $k and $m. Or you could try to look ahead to see whether one combination seems especially problematic. Specifically, what if $i and $m Is there any guarantee from $(1)$ and $(2)$ that either $i or $m? 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

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

1

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 from $i (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?)

1

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.