Set Theory Proof

Question

Let S1,S2,S3 be sets. Prove that (S1\S2)∪(S2\S3) ⊆ (S1 ∪S2)\(S1 ∩S2 ∩S3).

Answer 1

To show that A is a subset of B, we can show that every element a of A is also an element of B. This is our strategy to prove the statement.

So let x be an element of the left-side set, that is, an element of (S1\S2)∪(S2\S3). Then by definition of union U, we have x in (S1\S2) or x in (S2\S3). In either case, x is in S1 or in S2, that is, x is in the union S1 U S2. Now, in the first case where x in (S1\S2), we get x is not in S2 (by the definition of set difference). In the second case where x in (S2\S3), we get x is not in S3. In either case, x is not in one of S2 or S3, which implies that x cannot be in the intersection of all three sets S1, S2, S3, that is, x is not in (S1 ∩S2 ∩S3).

We have shown that x is in S1 U S2 but not in (S1 ∩S2 ∩S3), or equivalently, that x is in (S1 ∪S2)\(S1 ∩S2 ∩S3). This means that x is also a member of the right-side set.

Therefore, (S1\S2)∪(S2\S3) ⊆ (S1 ∪S2)\(S1 ∩S2 ∩S3, since we have shown that every element of the left-side set is also a member of the right-side set.