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

Question

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!

Answer 1

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.