- #1

dawoodvora

- 5

- 0

## 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;

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

## 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 [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.**