1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Zakon Vol 1, Ch2, Sec-6, Prob-19 : Cardinality of union of 2 sets

  1. Mar 5, 2012 #1
    1. The problem statement, all variables and given/known data

    Show by induction that if the fi nite sets A and B have m and n elements,
    respectively, then
    (i) A X B has mn elements;
    (ii) A has 2m subsets;
    (iii) If further A [itex]\cap[/itex] B = [itex]\varphi[/itex], then A [itex]\cup[/itex] B has m+ n elements.

    NOTE : I am only interested in the (iii) section of the problem. Section (i) and (ii), I was able to solve albeit with some help.

    2. Relevant equations

    3. The attempt at a solution
    Here is the attempt at the solution

    I am using mathematical induction to solve the query.

    P(n) : |A| = m, |B| = n; |A [itex]\cup[/itex] B| = m + n if A [itex]\cap[/itex] B = [itex]\varphi[/itex].

    Basis Step:

    P(n = 1) to be proven as true.

    Let A = { a1, a2,......am} => |A| = m
    Let B = {b1} => |B| = 1

    Now A [itex]\cup[/itex] B = {a1, a2,...am,b1}
    |A [itex]\cup[/itex] B| = m + 1 elements, since A and B are disjoint(given) Thus P(1) holds true.
    Basis Step is proven.

    Let us redefine B = {b1, b2, ....., bk, bk+1} => |B| = k+1.
    Also |A [itex]\cap[/itex] B| = [itex]\varphi[/itex]
    Now consider Bk = {b1, b2,..., bk} => Bk [itex]\subset[/itex] B, |Bk| = k

    Inductive hypothesis:
    Assume P(k) holds true for n = k i.e.,

    |A [itex]\cup[/itex] Bk| = m + k, when A [itex]\cap[/itex] Bk = [itex]\varphi[/itex]

    Inductive Step:

    Bk [itex]\subset[/itex] B => B = Bk [itex]\cup[/itex] {bk+1}
    A [itex]\cup[/itex] B = A [itex]\cup[/itex] (Bk [itex]\cup[/itex] {bk+1}) = (A [itex]\cup[/itex] Bk) [itex]\cup[/itex] {Bk+1} = m + k + 1 = m + (k + 1) => P(k+1) holds true. Thus Induction is complete.

    Somehow, I am not convinced with the solution that I have attempted. Please let me know if I am missing something.
  2. jcsd
  3. Mar 6, 2012 #2


    User Avatar
    Science Advisor

    This is wrong. What you have written is 2 times m while, in fact, A has 2m subsets. If you don't want to use LaTeX (as you have below) use 2^m.

    That's correct but seems overly complicated. If A and B have no members in common, [itex]A\cup B[/itex] contains every member of A and B- thus has m+ n members.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook