Question

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

Answer 1

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.