Suppose that R and S are reflexive relations on a set A. Prove or disprove each of these statements.

16.8k Views Asked by At

I am doing this question with my own attempt. Can anyone help me with the formal way of proving? Thanks!

Suppose that $R$ and $S$ are reflexive relations on a set $A$. Prove or disprove each of these statements.
1. $R \cup S$ is reflexive.
2. $R \cap S$ is reflexive.
3. $R - S$ is NOT reflexive.
4. $S \circ R$ is reflexive.

My answer:

1. Is $\forall x \in A, R \cup S$ reflexive? True, because $\forall x \in A, xRx$ and $\forall x \in A, xSx$

2. Is $\forall x \in A, R \cap S$ reflexive? True, because $\forall x \in A, xRx$ and $\forall x \in A, xSx$

3. By the definitions of $R - S$, since $xSx$, it cannot be in $S'$. So the statement is true.

4.True, \begin{align*} (x,x) &\in R \\ (x,x) &\in S \\ \therefore S &\circ R \end{align*}

1

There are 1 best solutions below

0
On BEST ANSWER

I preassume that $A$ is a non-empty set. Denoting $\Delta:=\{\langle a,a\rangle\mid a\in A\}$ we can say that a relation on $A$ is reflexive if and only if it contains $\Delta$ as a subset.

1) $R\cup S$ is reflexive. This because $\Delta\subseteq R\subseteq R\cup S$ (or $\Delta\subseteq S\subseteq R\cup S$).

Your reasoning is somehow rejectable because it has a redundant character. Note that the statement would also be true if only one of the relations $R,S$ is reflexive. For 2) you use the same reasoning, but there it is correct.

2) $R\cap S$ is reflexive. This because $\Delta\subseteq R\wedge\Delta\subseteq S\implies\Delta\subseteq R\cap S$

3) $R\setminus S=R\cap S^c$ is not reflexive. From $\Delta\subseteq S$ (combined with the assumption that $A\neq\varnothing$ and consequently $\Delta\neq\varnothing$) it follows that $\Delta$ is not a subset of $S^c$ hence not of $R\cap S^c$.

4) $S\circ R$ is reflexive. For every $a\in A$ we have $\langle a,a\rangle\in R\wedge\langle a,a\rangle\in S$ and consequently $\langle a,a\rangle\in S\circ R$. This means exactly that $\Delta\subseteq S\circ R$.