Power set of a countably infinite set

Solution Preview

(a) Since A is countably infinite, there is a one-to-one correspondence between A and the set N of all natural numbers; hence the elements of A can be listed as follows:

a_0, a_1, a_2, a_3, ..., a_n, ...

Let E be a subset of A, and let s_E be the countably infinite sequence (s_0, s_1, s_2, s_3, ..., s_n, ...) of 0's and 1's such that, for every natural number n,

s_n = 1 if a_n is an element of E

s_n = 0 if a_n is not an element of E

Since E is an ARBITRARY subset of A (hence an ARBITRARY element of P(A)), this gives us a mapping f: P(A) -> S that maps E to s_E.

To show that this mapping is a one-to-one correspondence, we have to show that f is one-to-one and onto.

--------------------------------------

Proof that f is one-to-one:

Assume that f(E_1) = f(E_2) for subsets E_1, E_2 of A. We will show that E_1 = E_2.

Let f(E_1) = (s_0, s_1, s_2, s_3, ..., s_n, ...) (= f(E_2)).

Then for every natural number ...