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
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
It would suffice if you just proved it for two sets, as then .
So, you need to show that the Cartesian product of two denumerable sets (infinite, in the interesting case) has the cardinality of . This is equivalent to finding a 1-1 mapping .
There's plenty of those. You try!