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.


1 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.

  • 1
    $\begingroup$ To absorb this some time I need. :) (Wish I was as good at this as Yoda is in wielding the Force...) $\endgroup$ Jan 23, 2013 at 1:21
  • $\begingroup$ @LavaScornedOven: Just try to follow it one step at a time; don’t try to see the whole picture right away. $\endgroup$ Jan 23, 2013 at 1:29
  • $\begingroup$ Thanks for the help. I think I get the steps, but now for the big picture. BTW, is there some good book that could help me getting intuitive about relations? There's a load of books where I can learn about relations, but most textbooks I found are pretty dry/overly theoretical about it. $\endgroup$ Jan 23, 2013 at 1:42
  • $\begingroup$ @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? $\endgroup$ Jan 23, 2013 at 1:48
  • 2
    $\begingroup$ Unfortunately, I'm not in school anymore (I'm 30. :D ), but I use Amazon. This is more of a hobby that started with me bumping on this list: amazon.com/gp/richpub/syltguides/fullview/R1GE1P236K3YSV $\endgroup$ Jan 23, 2013 at 2:25

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.