Question

how to prove distributive law in set theory?

Answer 1

Here's an example Proof

Subproof that (A ∪ B) ∩ C ⊆ (A ∩ C) ∪ (B ∩ C):

Suppose x ∈ (A ∪ B) ∩ C.

Then, by definition of intersection, x ∈ (A ∪ B) ∧ x ∈ C.

Then, x ∈ (A ∪ B) says x ∈ A ∨ x ∈ B. So, consider these as two cases:

Case x ∈ A:

Then, applying definition of "and" gives that x ∈ A ∧ x ∈ C.

So, by definition of intersection, x ∈ A ∩ C.

Next, by ∨ Introduction, we can say x ∈ A ∩ C ∨ x ∈ B ∩ C. But this meets the definition of union, so we may conclude x ∈ (A ∩ C) ∪ (B ∩ C).

Case x ∈ B:

Then, applying definition of "and" gives that x ∈ B ∧ x ∈ C.

So, by definition of intersection, x ∈ B ∩ C.

Next, by ∨ Introduction, we can say x ∈ A ∩ C ∨ x ∈ B ∩ C. But this meets the definition of union, so we may conclude x ∈ (A ∩ C) ∪ (B ∩ C).

In either case, x ∈ (A ∩ C) ∪ (B ∩ C). So, (A ∪ B) ∩ C ⊆ (A ∩ C) ∪ (B ∩ C).



Subproof that (A ∩ C) ∪ (B ∩ C) ⊆ (A ∪ B) ∩ C:

Suppose x ∈ (A ∩ C) ∪ (B ∩ C).

Then, by definition of union, x ∈ (A ∩ C) ∨ x ∈ (B ∩ C). So, we'll consider two cases:

Case x ∈ (A ∩ C):

Then, by definition of intersection, x ∈ A ∧ x ∈ C.

In particular (via ∧ Elimination), x ∈ A. We can apply ∨ Introduction to claim x ∈ A ∨ x ∈ B. So, by definition of union, x ∈ A ∪ B.

Also, we have that x ∈ C. Combining this with the last result gives x ∈ A ∪ B ∧ x ∈ C. We can apply the definition of intersection to get x ∈ (A ∪ B) ∩ C.

Case x ∈ (B ∩ C):

Then, by definition of intersection, x ∈ B ∧ x ∈ C.

In particular (via ∧ Elimination), x ∈ B. We can apply ∨ Introduction to claim x ∈ A ∨ x ∈ B. So, by definition of union, x ∈ A ∪ B.

Also, we have that x ∈ C. Combining this with the last result gives x ∈ A ∪ B ∧ x ∈ C. We can apply the definition of intersection to get x ∈ (A ∪ B) ∩ C.

In either case, x ∈ (A ∪ B) ∩ C. So, (A ∩ C) ∪ (B ∩ C) ⊆ (A ∪ B) ∩ C.



As we have (A ∪ B) ∩ C ⊆ (A ∩ C) ∪ (B ∩ C) and (A ∩ C) ∪ (B ∩ C) ⊆ (A ∪ B) ∩ C we may conclude (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C).