# Proof of countable powersets (bijection)

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

1. ### Seff

Joined:
May 6, 2023
Messages:
11
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