Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
To absorb this some time I need. :) (Wish I was as good at this as Yoda is in wielding the Force...) –  LavaScornedOven Jan 23 '13 at 1:21
    
@LavaScornedOven: Just try to follow it one step at a time; don’t try to see the whole picture right away. –  Brian M. Scott Jan 23 '13 at 1:29
    
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. –  LavaScornedOven Jan 23 '13 at 1:42
    
@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? –  Brian M. Scott Jan 23 '13 at 1:48
    
I've seen the directed graph approach, but never worked with $|A|\times|A|$ matrices. I'm really new to all this, so I guess I just need to work it through. Once again, thanks a lot for all the help. –  LavaScornedOven Jan 23 '13 at 1:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.