Suppose that R and S are reflexive relations on a set A. Show that R-S is irreflexive.

Question

Suppose that R and S are reflexive relations on a set A. Show that R - S is irreflexive, i.e.,

$$\forall x \in A, (x,x) \notin R\setminus S$$

We have:

$$\forall r\in R, (r,r) \in R\\ \forall s\in S, (s,s) \in S$$

Or is that not correct? So R - S does what? I'm confused. Not sure how to subtract relations. I'm most confused by the definition given for irreflexivity above, since it says (x,x) is not in R, rather than R - S... when R was already declared to be reflexive...

Answer 1

Assume that the relations $R,S$ on a set $A$ are both reflexive, i.e. :

for all $x \in A$, $(x,x) \in R$ and $(x,x) \in S$.

The relation $R-S$ on $A$ is the set

$\{ (x,y) | x,y \in A \land (x,y) \in R \land (x,y) \notin S \}$

i.e. we have to start from $R$ and "throw away" from it all couples belonging to $S$.

Due to the fact that both $R,S$ are reflexive, we have that for all $x \in A, (x,x) \in R$ and $(x,x) \in S$.

Thus, no couple $(x,x)$ will be in $R-S$, and so $R-S$ is irreflexive.

Answer 2

Hint: Since $R$ and $S$ are reflexive, we know that given any $a \in A$, we have that $(a,a) \in R$ and $(a,a) \in S$. The set difference $B - C$ is defined to be: $$ B - C = \{b \in B \mid b \notin C\} $$ So for example: $$ \{(1, 2), (3, 4), (2, 5)\} - \{(2, 3), (4, 3), (2, 5)\} = \{(1, 2), (3, 4)\} $$

---

To get things started, consider a proof by contradiction. Suppose instead that there exists some $x \in A$ such that $(x,x) \in R - S$. Then what can we conclude?

Answer 3

By definition, $R$ and $S$ are subsets of $A\times A$. Since both relations are reflexive, every pair $(x,x)\in A$ is also in $R$ and $S$. The subtraction of relations comes down to the subtraction of subsets of $A$: $$R\setminus S = \{(x,y)\in A\times A \mid (x,y)\in R , (x,y)\not\in S\}$$

This is also a subset of $A\times A$, and thus defines a relation in A. However this relation cannot be reflexive, because any pair $(x,x)$ is in $R$ and in $S$, and hence cannot be in $R\setminus S$.