Every relation on a set has reflexive closure.

Question

Proof Attempt: Suppose $R$ is a relation on set $A$; $R=R_1 \times R_2 \subset A \times A$. We assert $S = R \cup i_{R_1 \times R_1}$ to be the closure of $R$ such that $i_{R_1 \times R_1}=\{(x,x) \vert x \in R_1\}$. We want to show $S$ is reflexive. Let $(r,r')\in S$. Then either $(r,r')\in R_1 \times R_2$ or $(r,r')\in i_{R_1 \times R_1}$. If $(r,r')\in R_1\times R_1$, then $r\in R_1$ so $(r,r)\in i_{R_1\times R_1}$. If $(r,r')\in i_{R_1\times R_1}$, then $r=r'$. In any case, $(r,r)\in S$ so $S$ is reflexive. Moreover, to show $S$ is the smallest reflexive relation that contains $R$, suppose $T=T_1\times T_2 \supseteq R$ and $T$ is reflexive. Then $(r,r')\in R \Rightarrow (r,r')\in T_1\times T_2 \Rightarrow r\in T_1 \land r'\in T_2$. Since $T$ is reflexive, then $(r,r)\in T_1\times T_2$ which means $r\in T_2$ and that implies $T_1 \subseteq T_2$. Furthermore, we have $R_1\subseteq T_1$ so $R_1 \subseteq T_2$. Thus, $i_{R_1\times R_1}\subseteq T_1\times T_2$. Therefore, $S=R_1\times R_2 \cup i_{R_1 \times R_2}\subseteq T$. Clearly, $R\subseteq S$ so S is the reflexive closure of $R$.

My concern: Is my argument correct? I was reading Velleman's text and he instead had $S=R \cup i_A$, which is what I don't understand why.

Answer 1

There are a few problems here.

First and foremost you seem to using a rather non-standard meaning of the word "reflexive". (Which is a polite way of saying I think you're misunderstanding what it means).

The usual definition is

A relation $R$ on $A$ is called reflexive if: For every $a\in A$ it holds that $(a,a)\in R$.

Your proof looks like you think it is something like

... if: For every $(a,b)\in R$ it holds that $(a,a)\in R$.

which is wrong. Do you see the difference? This misunderstanding dooms your attempt from the outset.

But there's more: You're assuming that $R$ is an arbitrary relation and then immediately write $R=R_1\times R_2$. Later you're writing $T=T_1\times T_2$ for an arbitrary $T$. But you can't assume that a random relation can be written as a cartesian product!

As a simple example, $R=\{(1,2),(3,4)\}$ cannot be written as $R_1\times R_2$ for any $R_1$ and $R_2$. Namely, $(1,2)\in R_1\times R_2$ can only be true $1\in R_1$. And $(3,4)\in R_1\times R_2$ can only be true if $4\in R_2$. But then certainly $(1,4)\in R_1\times R_2$, but $(1,4)$ is not in my $R$, so this $R$ cannot be $R_1\times R_2$.