(i) Show that if the sets A and B are countable, then so is A times B. For a fix
ID: 3142305 • Letter: #
Question
(i) Show that if the sets A and B are countable, then so is A times B. For a fixed a elementof A, let B_a = {(a, b) elementof A times B|b elementof B}. Since B is countable, each B_a is countable. Note that union_a elementof A B_a is the countable union of a countable set, and hence is countable. Since A times B = union_a elementof A B_a we have that A times B is countable. Use the previous result to deduce that if A is countable and n elementof N then A^n is countable. From part (i), it would follow that A^2 = A times A is countable.Explanation / Answer
We shall prove by induction:
Base case:
n = 1: The result is true as A is countable.
n = 2: From part (i) When A = B,
A2 = AxA is countable.
Inductive hypothesis: Let the result be true for some n = m.
=> Am is countable.
To prove: That the result is true for n = m+1 or that Am+1 is countable.
Proof: From result (i), since Am is countable and A is countable,
Am x A is countable
=> Am+1 is countable.
Thus by induction, An is countable for all n.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.