# Cardinality of subsets of naturals

#### dodo

Hi there,
here's one question that's bugging me nuts.

Cantor defined different kinds of infinity, named aleph_0, aleph_1, ..., each one the size of the powerset of a set of the previous size. The naturals, and therefore all infinite subsets of it, are countably-infinite with cardinality aleph_0.

Take now the set of primes. It's an infinite subset of the naturals. Now take the powerset of the primes, and it's not difficult to see a one-to-one correspondence to the set of squarefree numbers: the unique factorization of each squarefree number corresponds to a subset of the primes.

But the squarefree are also a subset of the naturals. So what gives. (Likely it's my understanding of Cantor's theory that is flaky.)

Thanks!

#### [email protected]

Cantor defined different kinds of infinity, named aleph_0, aleph_1, ..., each one the size of the powerset of a set of the previous size.
Common beginner mistake! Aleph_1 is NOT the power set of aleph_0. It is under the continuum hypothesis, but not otherwise.

The naturals, and therefore all infinite subsets of it, are countably-infinite with cardinality aleph_0.

Take now the set of primes. It's an infinite subset of the naturals. Now take the powerset of the primes, and it's not difficult to see a one-to-one correspondence to the set of squarefree numbers: the unique factorization of each squarefree number corresponds to a subset of the primes.
It is not a one-one correspondence since to a squarefree number, there corresponds a FINITE subset of primes. You won't get ALL the primes this way.

#### dodo

Hi, thanks for the reply. (I think we have chatted before, back in the days were there was a number theory forum at PhysicsForums, if I'm not mistaken.)

Ah, now I see your point - the squarefree correspond only to finite subsets of primes - all infinite subsets of primes are not accounted for. Now I can sleep, thanks

#### SDK

Hi, thanks for the reply. (I think we have chatted before, back in the days were there was a number theory forum at PhysicsForums, if I'm not mistaken.)

Ah, now I see your point - the squarefree correspond only to finite subsets of primes - all infinite subsets of primes are not accounted for. Now I can sleep, thanks
This is the wrong answer. Here at MMF the correct thing to do when misunderstanding subtleties of infinite cardinalities is to double down on your misunderstanding, rewrite any common definitions as you see fit, and argue for 150+ pages with people trying to help educate you until you ultimately conclude that Cantor and the thousands of mathematicians who have verified his work are all wrong.

3 people

#### JeffM1

this is the wrong answer. Here at mmf the correct thing to do when misunderstanding subtleties of infinite cardinalities is to double down on your misunderstanding, rewrite any common definitions as you see fit, and argue for 150+ pages with people trying to help educate you until you ultimately conclude that cantor and the thousands of mathematicians who have verified his work are all wrong.
rofl

#### dodo

So, just like the rest of the internet. Add a few work environments as well...

Thanks all again

#### v8archie

Math Team
But the squarefree are also a subset of the naturals. So what gives.
You can, perhaps, make this more intuitively simple (or rather, less difficult), by considering the even naturals rather than the primes or the squarefree. There are "obviously" fewer even naturals than there are naturals as one is a strict subset of the other. But it is equally obvious that we can put the two sets into a 1-1 correspondence $2n \leftrightarrow n$. Hilbert's Hotel is the classic analogy for seeing the power of the idea.

Our intuitive view of counting is that it measures the number of elements in a set and thus the size. Cantor's genius was to see that this is not the truth. It works for our real world experience, just as Newton's laws of motion are fine for terrestrial applications of the pre-20th century. But the truth is that a generalisation of the concept of size is more accurate on a larger scale, just as Einstein's generalisation of the laws of motion is more accurate.

I often like to divorce the concept of cardinality entirely from that of "size" in my thinking and consider it as just some property. It makes understanding a little easier. It's not entirely accurate as cardinality is a measure of size, just not one that corresponds with our intuition when it comes to infinite sets.