Check the validity of the characterization of reflexive closure $\mathcal S$

55 Views Asked by At

Given a binary relation $\mathcal R$ over a set $A$,then the reflexive closure of $\mathcal R$ on $A$ denoted by $\mathcal S$ is the smallest reflexive relation on $A$ containing $\mathcal R$.

Equivalently it's the least reflexive relation on $A$ that is a superset of $\mathcal R$.

Reflexive closure is explicitly given by:$$\mathcal S=\text{id}_A \cup\mathcal R$$


Since $\mathcal S$ is reflexive,hence by definition of reflexivity $\text{id}_A \subseteq \mathcal S$,on the other hand since it contains $\mathcal R$,implies that:

$$\text{id}_A \cup \mathcal R \subseteq \mathcal S$$

Therefore $\mathcal S $ can be written as: $$\mathcal S=\text{id}_A \cup \mathcal R\cup B$$

It's left to show that $B=\varnothing$,assume for the sake of contradiction $B \ne \varnothing$,then there is another reflexive closure $\mathcal S '$ with $B=\varnothing$ which is indeed $\mathcal S'=\text{id}_A \cup \mathcal R$ ,from here it's seen that $\mathcal S' \subset \mathcal S$,contradicts the fact that $\mathcal S$ is the smallest such reflexive relation on $A$ containing $ \mathcal R$.$\blacksquare$


All I tried to show,was the validity of such characterization of the reflexive closure.

However I'm not sure if my arguments are right,it would be highly appreciated if someone check them.

1

There are 1 best solutions below

1
On BEST ANSWER

You can avoid the use of contradiction (which is a bit confusing).


It is enough to observe two things:

  • $\text{id}_A \cup\mathcal R$ is reflexive and contains $\mathcal R$
  • If $\mathcal S'$ is reflexive and contains $\mathcal R$ then $\text{id}_A \cup\mathcal R\subseteq\mathcal S'$.

This justifies the conclusion that $\text{id}_A \cup\mathcal R$ is the reflexive closure of $\mathcal R$.

Both bullets are evident.

You use the notation $\text{id}_A$ which is dubious (as commented).

Often notations $\Delta(A)$ or $\Delta_A$ are used in this context.

This subset of $A\times A$ is called the "diagonal".