My Math Forum Cardinality of subsets of naturals
 User Name Remember Me? Password

 Number Theory Number Theory Math Forum

 December 4th, 2018, 05:01 AM #1 Newbie   Joined: Dec 2018 From: Germany Posts: 5 Thanks: 0 Cardinality of subsets of naturals 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!
December 4th, 2018, 05:06 AM   #2
Senior Member

Joined: Oct 2009

Posts: 781
Thanks: 280

Quote:
 Originally Posted by dodo 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.

Quote:
 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.

 December 4th, 2018, 05:28 AM #3 Newbie   Joined: Dec 2018 From: Germany Posts: 5 Thanks: 0 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
December 4th, 2018, 06:00 AM   #4
Senior Member

Joined: Sep 2016
From: USA

Posts: 609
Thanks: 378

Math Focus: Dynamical systems, analytic function theory, numerics
Quote:
 Originally Posted by 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
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.

December 4th, 2018, 06:28 AM   #5
Senior Member

Joined: May 2016
From: USA

Posts: 1,310
Thanks: 551

Quote:
 Originally Posted by sdk 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

 December 4th, 2018, 07:04 AM #6 Newbie   Joined: Dec 2018 From: Germany Posts: 5 Thanks: 0 So, just like the rest of the internet. Add a few work environments as well... Thanks all again
December 4th, 2018, 09:05 AM   #7
Math Team

Joined: Dec 2013
From: Colombia

Posts: 7,654
Thanks: 2632

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by dodo 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.

 Tags cardinality, naturals, subsets

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post chris7789 Number Theory 0 January 27th, 2017 07:19 PM BenFRayfield Number Theory 0 February 15th, 2014 02:55 PM mobel Applied Math 2 December 16th, 2013 12:46 PM shunya Applied Math 1 October 2nd, 2013 01:14 AM jstarks4444 Number Theory 7 November 19th, 2010 01:40 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top