Prove a relation $\mathcal R$ is reflexive if and only if its complement $\overline{\mathcal R}$ is irreflexive (strict). 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?
 A: 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$
A: 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.
A: 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))$).
