Apparent paradox in cardinalities

[zzedar]

I'm strictly amateur at number theory (Not even studying it, just playing around for fun), so forgive me if I'm being foolish here. I've found a "proof" of something that is clearly wrong, and I can't find my mistake, so I'd appreciate anybody's help in figuring out what I did wrong. Also please forgive me for changing the template provided, but the existing one didn't make any sense for this question.

1. Definitions

First, I define a "sturdy" number as any natural number that is not divisible by any perfect square other than 1. To put it another way, if you were to decompose a sturdy number into its prime factors, each prime factor would be raised to the first (or zeroth) power. Let S be the set of all sturdy numbers, {1, 2, 3, 5, 6, 7, 10,...}.

Let P be the set of all prime numbers, {2,3,5,7,...}.

Let Q denote the power set of P: {∅,{2},{3},{2,3},{5},{2,5},{3,5},{2,3,5},...}.

2. Relevant theorems

Cantor's theorem (for any set A, the power set of A has greater cardinality than A).
Euclid's proof of the infinitude of primes

3. My reasoning

For any sturdy number s, multiplying s by a prime that does not divide s yields another sturdy number. Since there are infinite primes, there are also infinite sturdy numbers.

Since the sturdy numbers are a subset of the natural numbers, S must be countable. Since S is countable and infinite, it has the same cardinality as the set of natural numbers, $\aleph_{0}$.

Since the primes are a subset of the natural numbers, P is countable. Since there are infinite primes, P is countably infinite, so it has the same cardinality as the set of natural numbers.

Therefore, P and S have the same cardinality, $\aleph_{0}$.

By Cantor's theorem, Q must have greater cardinality than P. Since P and S have the same cardinality, Q must have greater cardinality than S. However, there exists a one-to-one mapping from Q to S. Map the empty set to 1, and map each other set in Q to the product of its members. Therefore, Q and S must have the same cardinality. However, I've already shown that Q must have greater cardinality than S! How do I resolve this paradox?

 

[Dick]

I'm strictly amateur at number theory (Not even studying it, just playing around for fun), so forgive me if I'm being foolish here. I've found a "proof" of something that is clearly wrong, and I can't find my mistake, so I'd appreciate anybody's help in figuring out what I did wrong. Also please forgive me for changing the template provided, but the existing one didn't make any sense for this question.

1. Definitions

First, I define a "sturdy" number as any natural number that is not divisible by any perfect square other than 1. To put it another way, if you were to decompose a sturdy number into its prime factors, each prime factor would be raised to the first (or zeroth) power. Let S be the set of all sturdy numbers, {1, 2, 3, 5, 6, 7, 10,...}.

Let P be the set of all prime numbers, {2,3,5,7,...}.

Let Q denote the power set of P: {∅,{2},{3},{2,3},{5},{2,5},{3,5},{2,3,5},...}.

2. Relevant theorems

Cantor's theorem (for any set A, the power set of A has greater cardinality than A).
Euclid's proof of the infinitude of primes

3. My reasoning

For any sturdy number s, multiplying s by a prime that does not divide s yields another sturdy number. Since there are infinite primes, there are also infinite sturdy numbers.

Since the sturdy numbers are a subset of the natural numbers, S must be countable. Since S is countable and infinite, it has the same cardinality as the set of natural numbers, $\aleph_{0}$.

Since the primes are a subset of the natural numbers, P is countable. Since there are infinite primes, P is countably infinite, so it has the same cardinality as the set of natural numbers.

Therefore, P and S have the same cardinality, $\aleph_{0}$.

By Cantor's theorem, Q must have greater cardinality than P. Since P and S have the same cardinality, Q must have greater cardinality than S. However, there exists a one-to-one mapping from Q to S. Map the empty set to 1, and map each other set in Q to the product of its members. Therefore, Q and S must have the same cardinality. However, I've already shown that Q must have greater cardinality than S! How do I resolve this paradox?

So far you haven't listed any infinite sets in Q. The power set of P certainly contains a LOT of them. If you mean Q to be the set of all finite subsets of P (which is NOT the power set), then that is countable and has the same cardinality as P.