# Thread: math induction and DeMorgan's Law

1. ## math induction and DeMorgan's Law

Given: Show that for any integer n greater than or equal to 2 given n sets A1,A2,.....An then the complement (A1 U A2 U...An) = complement A1 & complement A2 & ... complement An.

Proof: By DeMorgan's Law, complement (A1 U A2) = complement A1 & complement A2, so the result is true for n=2. Now suppose that for k greater than or equal to z, then the complement of the union of any k sets is the intersection of the complements. That is if A1, ... Ak are sets, then complement (A1 U ... Ak) = complement A1 & ... complement Ak. Let S1,S2,...Sk, S(k+1), be complement (S1 U S2 U ...Sk U S(k+1)) = complement (S1 U S2 U ... Sk & complement S(k+1) {by DeMorgan's Law} = complement S1 & complement S2 & ... complement Sk & complement S(k+1) {by the induction hypothesis}. Thus th result is true for k+1.

A1, S(k+1), An the 1, n, and (k+1) are subscripts.

Can this proof be done by not including sets of S? If not, then what does stating k is greater than or equal to z mean?

2. Originally Posted by Possible actuary
Given: Show that for any integer n greater than or equal to 2 given n sets A1,A2,.....An then the complement (A1 U A2 U...An) = complement A1 & complement A2 & ... complement An.

Proof: By DeMorgan's Law, complement (A1 U A2) = complement A1 & complement A2, so the result is true for n=2. Now suppose that for k greater than or equal to z, then the complement of the union of any k sets is the intersection of the complements. That is if A1, ... Ak are sets, then complement (A1 U ... Ak) = complement A1 & ... complement Ak. Let S1,S2,...Sk, S(k+1), be complement (S1 U S2 U ...Sk U S(k+1)) = complement (S1 U S2 U ... Sk & complement S(k+1) {by DeMorgan's Law} = complement S1 & complement S2 & ... complement Sk & complement S(k+1) {by the induction hypothesis}. Thus th result is true for k+1.

A1, S(k+1), An the 1, n, and (k+1) are subscripts.

Can this proof be done by not including sets of S? If not, then what does stating k is greater than or equal to z mean?

Assume it works for k.

~(S_1 u S_2 u ... u S_k) = ~S_1 & ~S_2 &... ~S_k

We will show it works with k+1:

~(S_1 u S_2 u ... u S_k u S_{k+1} ) = ~(S_1 u S_2 u... S_{k-1} u T}

Where, T= S_k u S_{k+1}.
Since you have "k" in total use de Morgan's negation:

~S_1 & ~S_2 & ... & ~S_{k-1} & ~T

But,

~T = ~(S_k u S_{k+1}) = ~S_k & ~S_{k+1}

Thus,

~S_1 & ~S_2 & ... & ~S_{k-1} & ~S_k & ~S_{k+1}
Q.E.D.

,
,

,

,

,

,

,

,

,

# mathematical induction method and de morgans law

Click on a term to search for related topics.