Q:

Let A, B, C and D be sets. Prove that A \ B and C \ D are disjoint if and only if A ∩ C ⊆ B ∪ D

Accepted Solution

A:
Step-by-step explanation:We have to prove both implications of the affirmation. 1) Let's assume that A \ B and C \ D are disjoint, we have to prove that A ∩ C ⊆ B ∪ D. We'll prove it by reducing to absurd. Let's suppose that A ∩ C ⊄ B ∪ D. That means that there is an element x that belongs to A ∩ C but not to B ∪ D. As x belongs to A ∩ C, x ∈ A and x ∈ C. As x doesn't belong to B ∪ D, x ∉ B and x ∉ D. With this, we can say that x ∈ A \ B and x ∈ C \ D. Therefore, x ∈ (A \ B) ∩ (C \ D), absurd! It's absurd because we were assuming that A \ B and C \ D were disjoint, therefore their intersection must be empty. The absurd came from assuming that A ∩ C ⊄ B ∪ D. That proves that A ∩ C ⊆ B ∪ D. 2) Let's assume that A ∩ C ⊆ B ∪ D, we have to prove that A \ B and C \ D are disjoint (i.e.  A \ B ∩ C \ D is empty) We'll prove it again by reducing to absurd. Let's suppose that  A \ B ∩ C \ D is not empty. That means there is an element x that belongs to  A \ B ∩ C \ D. Therefore, x ∈ A \ B and x ∈ C \ D. As x ∈ A \ B, x belongs to A but x doesn't belong to B.  As x ∈ C \ D, x belongs to C but x doesn't belong to D. With this, we can say that x ∈ A ∩ C and x ∉ B ∪ D. So, there is an element that belongs to A ∩ C but not to B∪D, absurd! It's absurd because we were assuming that A ∩ C ⊆ B ∪ D, therefore every element of A ∩ C must belong to B ∪ D. The absurd came from assuming that A \ B ∩ C \ D is not empty. That proves that A \ B ∩ C \ D is empty, i.e. A \ B and C \ D are disjoint.