 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/discrete-mathematics-continuous-mathematics-and-probability/1/b/solution

n = 2

is the two-set form of De Morgan's laws. For the union identity, suppose the result holds for

n

. Applying the two-set identity and then the inductive hypothesis gives

A ∖ i = 1 ⋃ n + 1 B_{i} = (A ∖ i = 1 ⋃ n B_{i}) \cap (A ∖ B_{n + 1}) = (i = 1 ⋂ n (A ∖ B_{i})) \cap (A ∖ B_{n + 1}) = i = 1 ⋂ n + 1 (A ∖ B_{i}) .

For the intersection identity, the corresponding step is

A ∖ i = 1 ⋂ n + 1 B_{i} = (A ∖ i = 1 ⋂ n B_{i}) \cup (A ∖ B_{n + 1}) = (i = 1 ⋃ n (A ∖ B_{i})) \cup (A ∖ B_{n + 1}) = i = 1 ⋃ n + 1 (A ∖ B_{i}) .

These close the two inductions.

 New to topics? Read the docs here!