Code:`Prove the following statement using induction on n: if A1, . . . ,An are`

denumerable sets, then the set of all n-tuples

{(a1, . . . , an} | ai belongs to Ai for i=1, . . . , n} is denumerable

Printable View

- Jan 23rd 2008, 05:22 AManncardenumerable setsCode:
`Prove the following statement using induction on n: if A1, . . . ,An are`

denumerable sets, then the set of all n-tuples

{(a1, . . . , an} | ai belongs to Ai for i=1, . . . , n} is denumerable

- Feb 20th 2008, 10:08 AMRebesques
It would suffice if you just proved it for two sets, as then $\displaystyle A_1\times A_2\times\ldots\times A_n=(\ldots(A_1\times A_2)\times \ldots)\times A_n)$.

So, you need to show that the Cartesian product of two denumerable sets (infinite, in the interesting case) has the cardinality of $\displaystyle \mathbb{N}$. This is equivalent to finding a 1-1 mapping $\displaystyle f:\mathbb{N}^2\rightarrow \mathbb{N}$.

There's plenty of those. You try!