# Need help with proving transitivity property

• Apr 8th 2010, 05:37 PM
swtdelicaterose
Need help with proving transitivity property
Here is the basic question:

[n] = {1, 2, 3, ..., n}

Define the relationship $\mathcal{R}$ on the powerset $\mathcal{P}([n])$ by: $\forall$ sets $A, B \in \mathcal{P}([n]), A \mathcal{R}B$ iff $A-B\subseteq{1,2}$. Explain why this is transitive.

I know transitivity means that $\forall A, B, C \in \mathcal{P}([n]),$ if $A \mathcal{R}B, B \mathcal{R}C,$ then $A \mathcal{R}C$

This doesn't have to be a direct proof, it just says give reasons why it's transitive. So, I'm thinking of using an element argument, but that doesn't seem to cover everything. And there seems to be cases.

Here's what I was thinking of saying:

Suppose A is a set with arbitrary elements. Assuming A-B is a subset of {1, 2} and B-C is a subset of {1, 2}, there are two cases to consider.

First case, if A has other elements that are not 1, 2, then those elements must be in B since A-B is a subset of {1, 2}. Since B - C is a subset of {1, 2}, those elements must also be in C. Thus, A-C would remove the elements that aren't 1 or 2.

Second case, if A does not have other elements besides {1, 2}. Thus, no matter what B is, A-B is a subset of {1, 2} (even the empty set is a subset of {1, 2}, and similarly no matter what B-C is, it is also a subset of {1, 2}.

I know, this sounds like a horrible explanation. Can anyone help me explain it better? Using a single element argument doesn't seem to work logically in my mind...

Lemma. $A-B\subseteq\{1,2\}\Leftrightarrow A\subseteq B\cup\{1,2\}$.
Proof of transitivity. Suppose $A-B\subseteq\{1,2\}$ and $B-C\subseteq\{1,2\}$. By Lemma, this means $A\subseteq B\cup\{1,2\}$ and $B\subseteq C\cup\{1,2\}$. Therefore, $A\subseteq B\cup\{1,2\}\subseteq C\cup\{1,2\}\cup\{1,2\}=C\cup\{1,2\}$, which, again by Lemma, means that $A-C\subseteq\{1,2\}$.