Explore BrainMass

Explore BrainMass

    Power set of a countably infinite set

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com March 4, 2021, 6:12 pm ad1c9bdddf
    https://brainmass.com/math/number-theory/power-set-of-a-countably-infinite-set-34601

    Attachments

    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 ...

    Solution Summary

    The solution consists of a detailed, step-by-step proof of the following: For a countably infinite set A, (a) there is a one-to-one correspondence between the power set of A and the set S of all countably infinite sequences of 0's and 1's; (b) the power set of A is uncountable.

    $2.49

    ADVERTISEMENT