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.
 

Members online

No members online now.

Forum statistics

Threads
2,555
Messages
9,909
Members
706
Latest member
irlenBingus
Back
Top