View Single Post
HallsofIvy
#2
Mar6-12, 07:59 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,534
Quote Quote by dawoodvora View Post
1. The problem statement, all variables and given/known data


Show by induction that if the finite sets A and B have m and n elements,
respectively, then
(i) A X B has mn elements;
(ii) A has 2m subsets;
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.

(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.
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.