1

I am trying to understand what is a reflexive closure and, more or less, I understood the properties:

Let $R$ be a relation on $A$.

Then the reflexive closure of $R$ is the smallest set $S \in A \times A$, such that $R \subseteq S$ and $S$ is reflexive, if there's such a smallest set. In other words, the relation $S \in A \times A$ is the reflexive closure of $R$ if it has the following properties:

  1. $S$ is reflexive

  2. $R \subseteq S$

  3. For each relation $T \in A \times A$, if $R \subseteq T$ and $T$ is reflexive, then $S \subseteq T$.

What I am really not fully understanding is the following syntax in the theorem that a reflexive closure always exist:

Let S = $R \cup i_{A}$

$R$ is a relation on $A$, and we know that a relation is nothing else than a subset of $A^2$ or $A \times A$. But what does it mean to make a union between $R$ and $i_A$ (which happens to be equal to $S$)?

2 Answers2

4

The relation $S$ is characterized by 1 and 2 and being "the smallest relation" with these properties 1 and 2.

It is not quite correct to say that $R$ is a subset of $A$, it is rather a subset of $A^2$ [added: meanwhile corrected]. The set $i_A$ is, in all likelihood, the diagonal of $A^2$, that is $\{(a,a) \colon a \in A \}$. Presumably, the notation $i_A$ is used as $\{(a,a) \colon a \in A \}$ is the relation that is/gives the identity-function on $A$.

So, both $R$ and $i_A$ are subsets of $A^2$ and their union is also a subset of $A^2$, whence a relation on $A$

quid
  • 42,135
  • As I wrote it is just the set ${(a,a) \colon a \in A }$. It is sometimes called "diagonal" on the grounds that if one thinks of the elements of $A^2$ written as a grid, then one would find those elements on the diagonal (assuming one lines the elements of $A$ up in the same way for colons and lines). – quid Jan 08 '15 at 15:59
0

Note: based on some more readings and new things I have learnt, I will also try to give my answer. Feel free to modify it in order to improve it.

I found the complete theorem, which by itself answers also to my question:

Let $S = R \cup i_A$, where as usual $i_A$ is the identity relation on $A$. We will show that S is the reflexive closure of A. Thus, we must show that $S$ has the 3 properties of a reflexive closure.

The first property is obviously true, since clearly $R \subseteq R \cup i_A = S$.

For the second and third, we use the following theorem:

Theorem 4.3.4:

Suppose $R$ is a relation on a set $A$.

  1. $R$ is reflexive iff $i_A \subseteq R$, where as before $i_A$ is the identity relation on $A$.

  2. $R$ is symmetric iff $R = R^{-1}$.

  3. $R$ is transitive iff $R \circ R \subseteq R$.

Clearly $i_A \subseteq R \cup i_A =S$, so S is reflexive.

Finally, to prove the third property, suppose $T$ is a relation on $A$, $R\subseteq T$ , and $T$ is reflexive. Then by Theorem $4.3.4$, since $T$ is reflexive, $i_A \subseteq T$.

Combining this with the fact that $R \subseteq T$, we can conclude that $S=R \cup i_A\subseteq T$, as required.

Essentially, to get $S$, the reflexive closure, we should start from $R$, and then add all those ordered pairs of $A$, which is exactly what this syntax $S = R \cup i_A$ means.