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.
- 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}))\}$$
- 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}$
- 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}$.
- 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.