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!

  • 1
    $\begingroup$ 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$ $\endgroup$ – Michael Hardy Oct 25 '16 at 16:55
  • $\begingroup$ Thank you! Will be mindful of them in the future $\endgroup$ – 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




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.
  • $\begingroup$ 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... $\endgroup$ – Daniel Mak Oct 26 '16 at 16:46
  • 1
    $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Oct 26 '16 at 17:32
  • 1
    $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Oct 29 '16 at 17:46
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Nov 6 '16 at 16:41
  • 1
    $\begingroup$ @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 ... $\endgroup$ – Brian M. Scott Nov 6 '16 at 21:50

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.