# Proving transitive property

I have been working on this problem from Velleman's How to prove book:

Suppose A is a set, and F ⊆ P (A). Let R = {(a, b) ∈ A × A | for every X ⊆ A \ {a, b}, if X ∪ {a} ∈ F then X ∪ {b} ∈ F}. Show that R is transitive.

Now, I have been solving the proof like this:

Let $a, b, c$ be arbitrary elements of A such that $(a,b) \in R$ and $(b,c) \in R$. Suppose $F \subseteq P(A)$. Let $X$ be arbitrary set. Suppose $X \subseteq A \setminus \{a,c\}$ and $X \cup \{a\} \in F$, we have to prove that $X \cup \{c\} \in F$. From $X \subseteq A \setminus \{a,c\}$, it follows that $a,c \notin X$. We can consider two cases:

1) $b \notin X$. This is straightforward to prove.

2) $b \in X$

Now the second part confuses me. How to proceed the second part ?

Frankly,your proof confuses ME. To prove R is transitive, you have to show if $(a,b) \in R$ and $(b,c)\in R$, then $(a,c)\in R$. Consider what it means for $(a,b),(b,c)\in R$. If $(a,b) \in R$, then for every $X\subseteq$ $A\backslash{\{a,b\}}$ then $A\cup{\{a\}}$ $\in F\subset P(A)$ $\rightarrow$ $A\cup {\{b\}}\in F\subset P(A)$. Similarly, if $(b,c) \in R$, then for every $Y\subseteq$ $A\backslash {\{b,c\}}$, then $A\cup {\{b\}}\in F$ $\subset P(A)$ $\rightarrow$ $A\cup {\{c\}}\in F\subset P(A)$. Therefore, considering $X \cup Y$ $\subseteq$ $A\backslash{\{a,b\}}$ $\cup$ $A\backslash{\{b,c\}}$ = $A\backslash {\{a},{b},{c}\}$. This implies $A\cup{\{a\}}$ $\in F\subset P(A)$ $\rightarrow$ $A\cup {\{b\}}\in F\subset P(A)$ $\rightarrow A\cup {\{c\}}\in F$ $\subset$ P(A).But that means $(a,c)\in R$ and thus R is transitive. Q.E.D.
Hint: Consider $Y=X\backslash{\{b\}}$.
The definition of $R$ can be reworded slightly. Let $$R = \big\{(a,b)\in A\times A \big|\forall X\in F, a\in X \implies(X\backslash\{a\})\cup\{b\}\in F\big\}$$ Show that this is equivalent to your original definition of $R$.