Proof of countable powersets (bijection)

Discussion in 'Number Theory' started by Seff, May 6, 2023.

  1. Seff

    Seff

    Joined:
    May 6, 2023
    Messages:
    11
    Likes Received:
    2
    Claim: All power sets of countably infinite sets are also countable
    Proof using bijection

    • Create a bijection between S(n) and the square-free numbers > 1
      Denote each mapping by the index n:
    n: S(n) ⇒ s
    1: S(1) ⇒ 2
    2: S(2) ⇒ 3
    3: S(3) ⇒ 5
    4: …​
    • Create a bijection between the square-free numbers > 1 and the power set of all prime numbers P(p), which is identical to their prime factorizations by definition.
    S(1) ⇒ 1 ⇒ {}
    S(2) ⇒ 2 ⇒ {2}
    S(3) ⇒ 3 ⇒ {3}
    S(4) ⇒ 5 ⇒ {5}
    S(5) ⇒ 6 ⇒ {2,3}
    …​
    • Create a bijection between the power set of all prime numbers P(p) and the power set of natural numbers P(n)
    S(1) ⇒ 1 ⇒ {} ⇒ {}
    S(2) ⇒ 2 ⇒ {2} ⇒ {1}
    S(3) ⇒ 3 ⇒ {3} ⇒ {2}
    S(4) ⇒ 5 ⇒ {5} ⇒ {3}
    S(5) ⇒ 6 ⇒ {2,3} ⇒ {1,2}
    …​
    • Every element S(n) can now form a bijection with the powerset of S, denoted as P(S(n)),
      through the power set of n, denoted as P(n), and its bijection with P(S(n)).
    S(n) ⇒ Square-free ⇒ P(p) ⇒ P(n) ⇒ P(S(n))

    S(1) ⇒ 1 ⇒ {} ⇒ {} ⇒ {}
    S(2) ⇒ 2 ⇒ {2} ⇒ {1} ⇒ {S(1)}
    S(3) ⇒ 3 ⇒ {3} ⇒ {2} ⇒ {S(2)}
    S(4) ⇒ 5 ⇒ {5} ⇒ {3} ⇒ {S(3)}
    S(5) ⇒ 6 ⇒ {2,3} ⇒ {1,2} ⇒ {S(1),S(2)}
    S(6) ⇒ 7 ⇒ {7} ⇒ {5} ⇒ {S(5)}
    S(7) ⇒ 10 ⇒ {2,5} ⇒ {1,3} ⇒ {S(1),S(3)}
    …​

    Conclusion: Any countable set’s power set is also countable as we can use the properties of square-free numbers and said countable sets’ indexes to create a bijection between them (or the naturals) and their own power set.

    Am I making a mistake? This seems to contradict one of the pillars of set theory.
     
    Seff, May 6, 2023
    #1
Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.
Similar Threads
There are no similar threads yet.
Loading...