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)

  • $\begingroup$ Is the relation dependent on $F$? Then you should really write $R_F$ or something like that for notational purposes. $\endgroup$ – Kyle Aug 6 '14 at 8:13
  • $\begingroup$ I am sorry, I will change it now, thank you. @KyleGannon $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – ciceksiz kakarot Aug 6 '14 at 20:52
  • $\begingroup$ 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$. $\endgroup$ – user133281 Aug 6 '14 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.