- #1
zzedar
- 1
- 0
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?
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?