# $R=\{ (a,b)\in A\times A\mid{}$ for every $X\subseteq A\smallsetminus\{a,b\}$, if $X \cup \{a\} \in F$ then $X\cup \{b\}\in F\}$ is transitive.

I am stuck on the following problem and still haven't the slightest clue how to proceed with the partial solution...

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

Partial solution: Suppose $aRb$ and $bRc$. To prove $aRc$, suppose that $X\subseteq A \smallsetminus \{a,c\}$ and $X\cup \{a\} \in F$; we must prove $X\cup \{c\} \in F$. To do this, you may find it helpful to consider two cases: $b\notin X$ or $b\in X$. In the latter case, work with the sets $X'=(X\cup\{a\}) \smallsetminus \{b\}$ and $X''=(X\cup \{c\})\smallsetminus\{b\}$.

I have no idea where $X'$ and $X''$ are from, e.g. are they assumptions or did I need to derive them? So I don't really know what kind of inference am I allowed to work on them. Even if I take them as assumptions, with the handful few things I have no idea what can I do with them. Frankly, the whole partial solution (apart from the givens and goal explanation) did more to confuse me than to help me.

If I apply $b\notin X$ to $X'$, I would even (seemingly mistakenly) get $b\in \{a\}$, which must mean $b=a$, which has gotta be wrong.

The only thing I can work out is this: by instantiating $X\subseteq A \smallsetminus \{a,c\}$, we get $b \in X \subseteq A$. So it follows that $b\in A$ - but this is already given in the definition of $R$.

I know I am supposed to have tried myself before asking; but I have been struggling with this for two weeks and still have no clue. Could anyone please help?

Thank you so much!

• Note that $\cup$ is normally used in things like $A\cup B$ and $A_1\cup\cdots\cup A_n$, and $\bigcup$ is normally used in things like $\displaystyle\bigcup_{k=1}^n A_k.$ I edited accordingly (and did lots of other MathJax improvements). $\qquad$ – Michael Hardy Oct 25 '16 at 16:55
• Thank you! Will be mindful of them in the future – Daniel Mak Oct 26 '16 at 16:47

HINT: When $b\notin X$ there is no reason to consider $X'$ and $X''$; that case goes through very directly.

Suppose that $b\notin X$. Then $X\subseteq A\setminus\{a,b\}$, $X\cup\{a\}\in F$, and $a\mathrel{R}b$, so $X\cup\{b\}\in F$. Moreover, $X\subseteq A\setminus\{b,c\}$ (why?), and $b\mathrel{R}c$, so $X\cup\{c\}\in F$, which is exactly what we wanted.

It’s when $b\in X$ that we have to be a little cleverer: in that case we don’t have $X\subseteq A\setminus\{a,b\}$, so we can’t directly use the fact that $a\mathrel{R}b$. The hint suggests that we consider the sets

$$X'=(X\cup\{a\})\setminus\{b\}$$

and

$$X''=(X\cup\{c\})\setminus\{b\}$$

that are obtained by removing $b$ from $X$ and replacing it with $a$ and $c$, respectively. We know that $X\subseteq A\setminus\{a,c\}$.

• Verify that $X'\subseteq A\setminus\{b,c\}$ and $X''\subseteq A\setminus\{a,b\}$.
• Show further that $X\cup\{a\}=X'\cup\{b\}$, $X'\cup\{c\}=X''\cup\{a\}$, and $X\cup\{c\}=X''\cup\{b\}$.

Now $b\mathrel{R}c$, and $X'\cup\{b\}=X\cup\{a\}\in F$, so $X'\cup\{c\}\in F$. And $X'\cup\{c\}=X''\cup\{a\}$, so $X''\cup\{a\}\in F$.

• Show that $X''\cup\{b\}\in F$, and conclude that $X\cup\{c\}\in F$, as desired.
• Thank you so much for your help Prof! But how did you get $X\subseteq A\smallsetminus \{a,b\}$? I know we have $X\subseteq A$, which is given, but what about the $\smallsetminus \{a,b\}$? In fact this has been where I got stuck; I knew I somehow gotta utilise the transitive relation. But I simply can't kickstart it since I can't think of how to get the said component above... – Daniel Mak Oct 26 '16 at 16:46
• @Daniel: You’re welcome! You’re starting with an $X\subseteq A\setminus\{a,c\}$, so you know that $a\notin X$. Thus, in the case $b\notin X$ you immediately have $X\subseteq A\setminus\{a,b\}$, because you know that neither $a$ nor $b$ is in $X$. – Brian M. Scott Oct 26 '16 at 17:32
• @Daniel: I think that you’re somehow making it much harder than it really is. You have a set $X$ that by hypothesis is a subset of $A\setminus\{a,c\}$; that’s your starting point. The object $a$ is clearly not an element of the set $A\setminus\{a,c\}$, so it cannot possibly belong to $X$. Neither can $c$, for the same reason. $X$ could conceivably contain any other element of $A$, but by hypothesis it absolutely cannot contain $a$ or $c$. Therefore we know for sure that $a\notin X$ and $c\notin X$. – Brian M. Scott Oct 29 '16 at 17:46
• @Daniel: The set operations like set difference, union, and intersection all take precedence over the subset/inclusion relations. And yes, we can apply any of the standard set operations to sets that we already have in order to make new sets. I’m in the midst of a few things at the moment, but I’ll come back to the specific questions in a bit. – Brian M. Scott Nov 6 '16 at 16:41
• @Daniel: You know that $X\subseteq A$ and $a\in A$, so $$X'=(X\cup\{a\})\setminus\{b\}\subseteq X\cup\{a\}\subseteq A\;.$$ We already know that $X\subseteq A\setminus\{b,c\}$, so in particular $b,c\notin X$, and therefore $a,b,c\notin X\setminus\{a\}$. Adding $b$ to the set $X\setminus\{a\}$ doesn’t add $a$ or $c$, so $a,c\notin X'$, and therefore $X'\subseteq A\setminus\{a,c\}$. I am assuming here that $b$ is different from both $a$ and $c$, because the result is trivial if $b=a$ or $b=c$. \\ For $X\cup\{a\}=X'\cup\{b\}$ it may help to realize that $X'$ is obtained from $X$ simply by ... – Brian M. Scott Nov 6 '16 at 21:50