# 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}))$

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.

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.
• @LavaScornedOven: I’m not sure that there really is any way to get an intuitive feel for relations in general. For the common properties of relations (e.g., transitivity) I think that your best bet is simply working with them and seeing lots of examples. It may also help to see more than one way of viewing a relation on $A$: a subset of $A\times A$, an $|A|\times|A|$ matrix of $0$s and $1$s, a directed bipartite graph. Have you seen either of the last two yet? Jan 23, 2013 at 1:48