Proving that this relation is transitive

94 Views Asked by At

I have seen this question on a book I am reading and could not figure it out fully. The question is as follows: "Suppose A is a set, and $F\subseteq P(A)$. Let $$R_F=\{ (a,b)\in AxA|\text{ for every }X\subseteq A \setminus \{a,b \},\text{ if }X\cup \{a\}\in F \text{ then }\space X\cup \{b\} \in F \}.$$ Prove that $R_F$ is transitive. Well, I started my proof with saying aRb and bRc exists, and try to prove aRc exists. However, because of the condition that we have the sets X as subsets of A without {a,b}, we have to consider two cases. Case 1 is when $b \notin X$ and case two is when $b \in X$. The first case is not so difficult, as our premises aRb and bRc does not include b as well, hence case 1 follows directly. However for case 2, I am stuck. Thank you very much in advance. (The book I have seen this question was "How to prove it; A structured approach" by Daniel J. Velleman)

1

There are 1 best solutions below

2
On BEST ANSWER

Suppose $aRb$ and $bRc$. We will show $aRc$. Let $a,c \not\in X$ and suppose that $X \cup \{a\} \in F$. If $b \not\in X$ then we have $X \cup \{b\} \in F$ since $aRb$ and $X \cup \{c\} \in F$ since $bRc$, as desired. Now suppose that $b \in X$. Write $X = Y \cup \{b\}$, where $a,b,c \not\in Y$. Since $Y\cup\{a,b\} \in F$ and $bRc$ we have $Y \cup \{a,c\} \in F$. Since $aRb$ we have $Y \cup \{b,c\} \in F$, as desired.