# Proving that this relation is transitive

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)

• Is the relation dependent on $F$? Then you should really write $R_F$ or something like that for notational purposes. – Kyle Aug 6 '14 at 8:13
• I am sorry, I will change it now, thank you. @KyleGannon – ciceksiz kakarot Aug 6 '14 at 18:39

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.
• I could not get the last bit. Am I not looking for $Y\cup \{a,c \} \in F$ ? You wrote it in the wrong order, and I did not get the logic actually. – ciceksiz kakarot Aug 6 '14 at 20:52
• You are given $Y \cup \{a,b\} \in F$ where $a,b,c \not\in Y$. To show that $aRc$, we have to show that $Y \cup \{b,c\} \in F$. – user133281 Aug 6 '14 at 21:28