Prove a relation $\mathcal R$ is reflexive if and only if its complement $\overline{\mathcal R}$ is irreflexive (strict).

Question

Given a homogeneous binary relation $\mathcal R$ over a set $A$, $\mathcal{R}$ is reflexive if:

$$\forall a \in A:(a,a) \in \mathcal R$$ Prove a relation $\mathcal R$ is reflexive if and only if its complement $\overline{\mathcal R}$ is irreflexive (strict).

---

$\Longrightarrow$

By the definition of complement relation:

$$\forall a,b \in A :(a,b) \in \mathcal R \implies (a,b) \notin \overline{\mathcal R}$$

Taking $a=b$ follows:

$$\forall a \in A :(a,a) \in \mathcal R \implies (a,a) \notin \overline{\mathcal R}$$

Which is true since $\mathcal R$ is reflexive.

$\Longleftarrow$

By the definition of complement relation:

$$\forall a,b \in A :(a,b) \in \overline{\mathcal R} \implies (a,b) \notin \mathcal R$$

Taking $a=b$ follows:

$$\forall a \in A :(a,a) \in \overline{\mathcal R} \implies (a,a) \notin \mathcal R$$

Since $ \overline{\mathcal R}$ is irreflexive, hence $\forall a \in A :(a,a) \in \overline{\mathcal R}$ is never true, and hence its negation is always true for all $a \in A$, however I still cannot finish the proof.

Another way is using contradiction argument, assume $\overline{\mathcal R}$ is irreflexive, but $\mathcal R$ is not reflexive, i.g.: $$\forall a \in A :(a,a) \notin \overline{\mathcal R}$$

And $$\exists a \in A :(a,a) \notin \mathcal R$$

From here we see that exists such $a \in A$ satisfying the two conditions $(a,a) \notin \overline{\mathcal R}$ and $(a,a) \notin \mathcal R$, but do we end up with a contradiction?

Can someone help me finishing this proof?

Answer 1

The $\implies$ part of the proof is fine.

Now for the $\Longleftarrow$ part:

Use proof by contraction. Suppose $\overline{\mathcal R}$ is irreflexive and $R$ is not reflexive. By definition of complement, we know that $\mathcal{R} \cup \overline{\mathcal R} = A \times A$. Let $a \in A$, such that $(a,a) \notin \overline{\mathcal R}$ (since $\overline{\mathcal R}$ is irreflexive) and $(a,a) \notin \mathcal{R}$ (since $\mathcal{R}$ is not reflexive, then such ordered pair in this conditions must exists). From here we deduce that $(a,a) \notin A \times A$, which is a contradiction. $\square$

Answer 2

Concise version:

Define: $$\Delta:=\{(a,a)\mid a\in A\}$$ which is the so-called diagonal.

Then $\mathcal R$ is reflexive iff $\Delta\subseteq\mathcal R$ and $\mathcal R$ is irreflexive iff $\Delta\cap\mathcal R=\varnothing$.

Observe that the last mentioned condition is equivalent with $\Delta\subseteq\mathcal R^{\complement}$, saying exactly that $\mathcal R^{\complement}$ is reflexive.

Answer 3

I wanted to add an extra answer that highlights the underlying logic. Start with the definition of $\overline{\mathcal{R}}$.

$$ \forall a \forall b : (a,b)\in \mathcal{R} \Leftrightarrow (a,b) \not\in \overline{\mathcal{R}} \tag{1} $$ Set $a=b$ to get: $$ \forall a : (a,a)\in \mathcal{R} \Leftrightarrow (a,a) \not\in \overline{\mathcal{R}} \tag{2} $$ In $(2)$ we can distribute the "for all" to get:$^*$ $$ (\forall a\space (a,a)\in\mathcal{R}) \Leftrightarrow (\forall a \space (a,a)\not\in\overline{\mathcal{R}}) \tag{3} $$ Now $(3)$ says precisely that $\mathcal{R}$ is reflexive iff $\overline{\mathcal{R}}$ is irreflexive.

---

$^*$In general, if you have properties $P(x)$ and $Q(x)$ of an object $x$, and you know that for any $x$, $P(x)$ holds iff $Q(x)$ holds (i.e., $\forall x(P(x)\leftrightarrow Q(x))$), then you know that $P(x)$ holds for all $x$ iff $Q(x)$ holds for all $x$ (i.e., $(\forall x\space P(x))\leftrightarrow (\forall x\space Q(x))$).