1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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!

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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Zakon Prob Cardinality Date
Complex Plane Aug 22, 2017
Gelfand's "Algebra" prob. 42 - corrections & hints? Jan 3, 2017
Conditional PDF question -- I think anyway... Sep 27, 2015
Finding Cardinality of Power Set May 20, 2014
Limit prob Sep 12, 2013