Prove that there is a one-to-one correspondence between the power set of a countably infinite set A and the set S of all countably infinite sequences of 0's and 1's, and that the power set of A is an uncountable set.

For any set B, let P(B) denote the power set of B (the collection of all subsets of B):

P(B) = {E: E is a subset of B}

Let A be a countably infinite set (an infinite set which is countable), and do the following:

(a) Prove that there is a one-to-one correspondence between P(A) and the set S of all countably infinite sequences of 0's and 1's.

(b) Using the result of part (a) or otherwise, prove that P(A) is uncountable.

Attached file(s):

m7.doc  View File