Quote by dawoodvora
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 2
^{m} 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 = { a_{1}, a_{2},......a_{m}} => A = m
Let B = {b_{1}} => B = 1
Now A [itex]\cup[/itex] B = {a_{1}, a_{2},...a_{m},b_{1}}
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 = {b_{1}, b_{2}, ....., b_{k}, b_{k+1}} => B = k+1.
Also A [itex]\cap[/itex] B = [itex]\varphi[/itex]
Now consider B_{k} = {b_{1}, b_{2},..., b_{k}} => B_{k} [itex]\subset[/itex] B, B_{k} = k
Inductive hypothesis:
Assume P(k) holds true for n = k i.e.,
A [itex]\cup[/itex] B_{k} = m + k, when A [itex]\cap[/itex] B_{k} = [itex]\varphi[/itex]
Inductive Step:
B_{k} [itex]\subset[/itex] B => B = B_{k} [itex]\cup[/itex] {b_{k+1}}
A [itex]\cup[/itex] B = A [itex]\cup[/itex] (B_{k} [itex]\cup[/itex] {b_{k+1}}) = (A [itex]\cup[/itex] B_{k}) [itex]\cup[/itex] {B_{k+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.