Results 1 to 2 of 2

Math Help - math induction and DeMorgan's Law

  1. #1
    Junior Member
    Joined
    Mar 2007
    From
    Missouri
    Posts
    54

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Possible actuary View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Math Induction Help
    Posted in the Pre-Calculus Forum
    Replies: 12
    Last Post: December 6th 2009, 08:19 PM
  2. Math Induction
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: December 1st 2008, 10:24 AM
  3. Math Induction...PLEASE HELP!!!!!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 16th 2008, 02:01 AM
  4. Math Induction
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 29th 2008, 06:40 AM
  5. Math Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 15th 2007, 03:28 PM

Search Tags


/mathhelpforum @mathhelpforum