Prove transitivity of $\forall X( X\subseteq A\setminus\{a, b\}\rightarrow(X\cup \{a\}\in\mathcal{F}\rightarrow X\cup\{b\}\in\mathcal{F}))$

Question

This one is from Velleman's "How to Prove It, 2nd Ed.", exercise 4.3.23.

Suppose $A$ is set, and $\mathcal{F}\subseteq\mathcal{P}(A)$. Let $$R=\{(a,b)\in A\times A : \text{for every } X\subseteq A\setminus\{a, b\}\text{, if } X\cup \{a\}\in\mathcal{F}\text{ then } X\cup\{b\}\in\mathcal{F}))\}$$ Show that $R$ is transitive.

1. First of all, I'm not sure if I read this correctly and if my notation is correct: $$R=\{(a,b)\in A\times A : \forall X( X\subseteq A\setminus\{a, b\}\rightarrow(X\cup \{a\}\in\mathcal{F}\rightarrow X\cup\{b\}\in\mathcal{F}))\}$$
2. To prove that $R$ is transitive, we need to prove that $$\forall a\in A\;\forall b\in A\;\forall c\in A\;((aRb\wedge bRc) \rightarrow aRc),$$ so for starters we suppose and let all the usual stuff:
   • let $a,b,c\in A$
   • suppose $aRb \wedge bRc$
   • expand $aRc$ to $\forall X( X\subseteq A\setminus\{a, c\}\rightarrow(X\cup \{a\}\in\mathcal{F}\rightarrow X\cup\{c\}\in\mathcal{F}))$
   • let $X$ be arbitrary and suppose $X\subseteq A\setminus\{a,c\}$
   • suppose $X\cup\{a\}\in\mathcal{F}$
   • show that $X\cup\{c\}\in\mathcal{F}$
3. Now Velleman suggests splitting proof to cases: $b\not\in X$ and $b\in X$. Showing that $R$ is transitive for $b\not\in X$ is rather straightforward. All we need to do is to show from $b\not\in X \wedge X\subseteq A\setminus\{a,c\}$ that $X$ is also subset of both $A\setminus\{a,b\}$ and $A\setminus\{b,c\}$, and we just follow assumptions $aRb$ and $bRc$ to conclude $X\cup\{c\}\in\mathcal{F}$.
4. Now we must show transitivity when $b\in X$. For this case Velleman suggests working with $X'=(X\cup\{a\})\setminus\{b\}$ and $X''=(X\cup\{c\})\setminus\{b\}$, and this is the part I totally don't get. Why would using $X'$ and $X''$ work for this proof, and how do actually connect them with all the givens/assumptions? I can see how all this connects after expanding $aRb$ and $bRc$, but I fail to see how this makes a correct proof.

So my questions are: is the 1. correct notation for given relation $R$ and how does 4. connect to givens.

If there is some other approach, I would be most thankful for any pointers.

Answer 1

Yes, what you’ve written in (1) is equivalent to the definition in the problem, though I think that most readers will find the original version easier to absorb.

In the proof of transitivity, suppose that $b\in X\subseteq A\setminus\{a,c\}$; we want to show that if $X\cup\{a\}\in\mathscr{F}$, then $X\cup\{c\}\in\mathscr{F}$, so assume that $X\cup\{a\}\in\mathscr{F}$. Let $X_0=X\setminus\{b\}$; then Velleman’s sets $X'$ and $X''$ are given by $X'=X_0\cup\{a\}$, and $X''=X_0\cup\{c\}$.

Now $b,c\notin X'$, and $X'\cup\{b\}=X_0\cup\{a\}\cup\{b\}=X\cup\{a\}\in\mathscr{F}$, so $X'\cup\{c\}\in\mathscr{F}$, since $bRc$. Now $X'\cup\{c\}=X_0\cup\{a\}\cup\{c\}=X''\cup\{a\}$, so $X''\cup\{a\}\in\mathscr{F}$. Moreover, $X''\subseteq A\setminus\{a,b\}$, and $aRb$, so $X''\cup\{b\}\in\mathscr{F}$. Finally, $X''\cup\{b\}=X_0\cup\{c\}\cup\{b\}=X\cup\{c\}$, and we conclude that $X\cup\{c\}\in\mathscr{F}$, as desired.