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$(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
  • either $k

and the desired conclusion is

  • either $i

You could systematically investigate all of the combinations: $i

$$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

(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.