Let T Aii 1n be a finite collection of finite sets Prove b

Let T = {A_i}_i = 1^n be a finite collection of finite sets. Prove by induction that A_1 times A_2 times ... times A_n is finite and |A_1 times A_2 times .... times A_n| = |A_1| |A_2| ... |A_n|

Solution

Let f={A_j}_j=1ⁿ be a finite colllection of finit set .

i.e each A_j is finit set

to prove that A₁ X A₂ X A ₃X------------------------------------------X An is finite

to prove by induction

step 1) to prove this for n=1

for n=1

since A₁ is finit

therfor for n=1 is this prove that

step 2)induction hypothesis

asumme that A₁ X A₂ X A ₃X------------------------------------------X A_kthis prove for n=k   (some k)

step 3)

noe to prove this for n=k+1

consider A₁ X A₂ X A ₃X------------------------------------------X A_k+1

since A₁      is finite and by step (2) A₂ X A ₃X------------------------------------------X A_k+1 is remaning k+1terms are also finite

therfore   it is clarely observe that A₁ X A₂ X A ₃X------------------------------------------X A_k+1 is also finite

therfoe by induction A₁ X A₂ X A ₃X------------------------------------------X An is finit

Part 2) to porve that | A₁ X A₂ X A ₃X-------X An | =| A₁ | |A₂ | | A ₃|-------------| An|

To prove this using induction

step 1)

to prove this for n=1

|A₁ |=|A₁ | this true for n=1

step 2) induction hypothesis

statement is true for n=k i.e

| A₁ X A₂ X A ₃X-------X A_k| =| A₁ | |A₂ | | A ₃|-------------| A_k|

step 3)

to prove for n=k+1

consider | A₁ X A₂ X A ₃X-------A_kX A_k+1 | =| A₁ X( A₂ X A ₃X-------A_kX A_k+1) |

                                                         = |A₁ | | A₂ X A ₃X-------A_kX A_k+1) |       by step 1

                                                         =|A₁ | |A₂ | | A ₃|-------------| A_k+1|           by step 2 (remaing are k )

                   this i sprove for n=k+1

therfoe by induction

| A₁ X A₂ X A ₃X-------X An | =| A₁ | |A₂ | | A ₃|-------------| An|