Proving reflexivity, symmetry and transitivity on a relation.

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.