Thread: Need help with proving transitivity property

Here is the basic question:

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

Define the relationship on the powerset by: sets iff . Explain why this is transitive.

I know transitivity means that if then


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

Please and thank you!

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.

I think this is correct, and this explanation works regardless whether A has other elements besides 1, 2. Any other elements, whether their set is empty or not, must be in B. (Recall that the empty set is a subset of any set.)

A similar, but more formal, way to write this is the following.

Lemma. .
Proof. ...

Proof of transitivity. Suppose and . By Lemma, this means and . Therefore, , which, again by Lemma, means that .