Question

Problem 6 Suppose A and B are countable sets. Prove A × B is a countable set.

Answer 1

problem 6:-

suppose A and B are countable sets . Prove that A×B is countable

Proof:- three cases arise

case I:

If both A and B are finite say |A|=m and |B|=n

then it is easy to show

|A×B|=mn

so A×B is finite this implies A×B is countable

case II :-

If A is finite with |A|=n (say)

and B is countably infinite

then by definition of countability there exists bijective functions say

f:A→{1,2,3,...n}

and

g:B→N

now define a function

h:A×B→N

Such that for all (a,b) $\epsilon$ A×B

h(a,b)= 2^f(a) 3^g(b)

then clearly h is onto(injective) by unique factorization of each natural number

that means

|A×B|≤|N|

=> A×B is countable

case III :-

If both A and B countably infinite then by definition there exists bijective functions say f and g such that

f:A→N and g:B→N

now define

h:A×B→N and as in above 2nd case we get h as an injective (onto) function

and that means

|A×B|≤N

this implies A ×B is countable

and we are done