View Single Post

Recognitions:
Gold Member
 (iii) If further A $\cap$ B = $\varphi$, then A $\cup$ 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 $\cup$ B| = m + n if A $\cap$ B = $\varphi$. Basis Step: P(n = 1) to be proven as true. Let A = { a1, a2,......am} => |A| = m Let B = {b1} => |B| = 1 Now A $\cup$ B = {a1, a2,...am,b1} |A $\cup$ 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 $\cap$ B| = $\varphi$ Now consider Bk = {b1, b2,..., bk} => Bk $\subset$ B, |Bk| = k Inductive hypothesis: Assume P(k) holds true for n = k i.e., |A $\cup$ Bk| = m + k, when A $\cap$ Bk = $\varphi$ Inductive Step: Bk $\subset$ B => B = Bk $\cup$ {bk+1} A $\cup$ B = A $\cup$ (Bk $\cup$ {bk+1}) = (A $\cup$ Bk) $\cup$ {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.
That's correct but seems overly complicated. If A and B have no members in common, $A\cup B$ contains every member of A and B- thus has m+ n members.