Exercise 1.9

Formulate and prove DeMorgan’s laws for arbitrary unions and intersections.

Answers

In following suppose that A is a set and B is a nonempty collection of sets. For arbitrary unions, we claim that

A −⋃ B∈BB = ⋂ B∈B(A − B).

Proof. The simplest way to show this is with a series of logically equivalent statements. For any x we have that

x ∈ A −⋃ B∈BB ⇔ x ∈ A ∧ x∉⋃ B∈BB ⇔ x ∈ A ∧¬ ⁡∃ ⁡B ∈B(x ∈ B) ⇔ x ∈ A ∧∀ ⁡B ∈B(x∉B) ⇔∀ ⁡B ∈B(x ∈ A ∧ x∉B) ⇔∀ ⁡B ∈B(x ∈ A − B) ⇔ x ∈⋂ B∈B(A − B),

which of course shows the desired result. □

For intersections, we claim that

A −⋂ B∈BB = ⋃ B∈B(A − B).

Proof. Similarly, we show this with a series of logically equivalent statements. For any x we have

x ∈ A −⋂ B∈BB ⇔ x ∈ A ∧ x∉⋂ B∈BB ⇔ x ∈ A ∧¬ ⁡∀ ⁡B ∈B(x ∈ B) ⇔ x ∈ A ∧∃ ⁡B ∈B(x∉B) ⇔∃ ⁡B ∈B(x ∈ A ∧ x∉B) ⇔∃ ⁡B ∈B(x ∈ A − B) ⇔ x ∈⋃ B∈B(A − B),

which shows the desired result. □

User profile picture
2019-12-01 00:00
Comments