Proof that the cartesian product of $n \in \mathbb{N}$ countably infinite sets is countably infinite - Induction

54 Views Asked by At

Suppose we have $A_1, A_2, A_3, ..., A_n$ countably infinite sets. Their Cartesian product is countably infinite.

Proof by induction:

  1. $n=1$

For n=1 the statement clearly holds.

  1. Suppose that $A_1 \times A_2 \times ... \times A_k$ is countably infinite,

  2. Prove that for $n=k+1$ the statement is true:

$A_1 \times A_2 \times ... \times A_k \times A_{k+1} = (A_1 \times A_2 \times ... \times A_k) \times A_{k+1} $

If we rewrite this in such a way so that we have a cartesian product of a set we know is countably infinite ($A_{k+1}$), and a cartesian product of sets we assumed is countably infinite (assumption in $2.$), does this mean that if I show that a Cartesian product of two countably infinite sets is countably infinite, my statement holds?

Note: I know that this has been asked (and answered before), but it was in a way I didn't understand. I need help in figuring out if my proof would be sufficient.