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

[dawoodvora]

Homework Statement

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 $\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.

Homework Equations

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 = { a₁, a₂,...a_m} => |A| = m
Let B = {b₁} => |B| = 1

Now A $\cup$ B = {a₁, a₂,...a_m,b₁}
|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 = {b₁, b₂, ..., b_k, b_k+1} => |B| = k+1.
Also |A $\cap$ B| = $\varphi$
Now consider B_k = {b₁, b₂,..., b_k} => B_k $\subset$ B, |B_k| = k

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

|A $\cup$ B_k| = m + k, when A $\cap$ B_k = $\varphi$

Inductive Step:

B_k $\subset$ B => B = B_k $\cup$ {b_k+1}
A $\cup$ B = A $\cup$ (B_k $\cup$ {b_k+1}) = (A $\cup$ B_k) $\cup$ {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.

 

[HallsofIvy]

Homework Statement

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 $\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.

Homework Equations

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 = { a₁, a₂,...a_m} => |A| = m
Let B = {b₁} => |B| = 1

Now A $\cup$ B = {a₁, a₂,...a_m,b₁}
|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 = {b₁, b₂, ..., b_k, b_k+1} => |B| = k+1.
Also |A $\cap$ B| = $\varphi$
Now consider B_k = {b₁, b₂,..., b_k} => B_k $\subset$ B, |B_k| = k

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

|A $\cup$ B_k| = m + k, when A $\cap$ B_k = $\varphi$

Inductive Step:

B_k $\subset$ B => B = B_k $\cup$ {b_k+1}
A $\cup$ B = A $\cup$ (B_k $\cup$ {b_k+1}) = (A $\cup$ B_k) $\cup$ {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, $A\cup B$ contains every member of A and B- thus has m+ n members.