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.(adsbygoogle = window.adsbygoogle || []).push({});

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, [itex]\aleph_{0}[/itex].

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, [itex]\aleph_{0}[/itex].

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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Apparent paradox in cardinalities

**Physics Forums | Science Articles, Homework Help, Discussion**