Theory Computation Show Cartesian Product Finite Number Countable Sets Countable Q37060393

Theory of computation

Show that the Cartesian product of a finite number of countablesets is countable

Answer

Let the X1, X2 ,…….. Xn are thecountable sets.

Yk= X1 * X2 * …….*Xk when k =1……. N). Thus

Yn := X1 * X2 * · · · *Xn

Using the induction:

In case k = 1 then Y1 = X1 iscountable.

Assuming that Yk (k ∈ n, 1 ≤ k < n) iscountable;

Then Yk+1 = ( X1 * X2 * …….*Xk) * Xk+1 = Yk * Xk+1where the Yk and the Xk+1 can be calledcountable. Hence the cartesian product of the countable set isalways countable. So, Yk+1

OR

 

OR