Proof of countable powersets (bijection)

Joined
May 5, 2023
Messages
11
Reaction score
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.
 


Write your reply...

Members online

No members online now.

Forum statistics

Threads
2,529
Messages
9,858
Members
696
Latest member
fairdistribution
Back
Top