Show that $R_1 ⊕ R_2$ is irreflexive if $R_1$ and $R_2$ are reflexive.

Question

This problem has already been asked and very poorly answered on the site. The question is as follows:

Suppose that $R_1$ and $R_2$ are reflexive relations on a set $A$. Show that $R_1 ⊕ R_2$ is irreflexive.

Intuitively, I know why this is true. The symmetric difference ⊕ is defined as "in the first set and not in the second set, or in the second set and not in the first set". Here is my line of thinking. I actually reached a contradiction (unless I did something wrong).

---

$R_1 ⊕ R_2$ is irreflexive if for all $a \in A$, we have that $(a, a) \notin R_1 ⊕ R_2$

$(a, a) \in R_1 ⊕ R_2$ if:

• $(a, a) \in (R_1 \cap \overline{R_2}) \vee (a, a) \in (\overline{R_1} \cap R_2)$

Negating, $(a, a) \notin R_1 ⊕ R_2$ if:

• $(a, a) \notin (R_1 \cap \overline{R_2}) \wedge (a, a) \notin (\overline{R_1} \cap R_2)$

The latter statement translates to:

• $(a, a) \notin R_1 \wedge (a, a) \notin \overline{R_2} \wedge (a, a) \notin \overline{R_1} \wedge (a, a) \notin R_2$

But from what we were told, $R_1$ and $R_2$ are reflexive, so this can't be right.

I'm just really exhausted after having spent like 20 minutes on this one problem. Any help is appreciated.

Answer 1

Your final expansion should flip the intersections into logical disjunctions (use De Morgan's)

Thus, we would go from

$$(a,a) \notin (R_1 \cap \overline{R_2}) \land (a,a) \notin (\overline{R_1} \cap R_2)$$

to

$$((a,a) \notin R_1 \lor (a,a) \in R_2) \land ((a,a) \in R_1 \lor (a,a) \notin R_2)$$

which is always true.