Question

What is the cardinality of the power set of all primes?

Answer 1

I ask because I thought since the cardinality of the primes is \(\aleph_0\) that the power set of the primes would have to have cardinality \(2^{\aleph_0}\). But I know that every combination of all the primes can be put into a 1 to 1 correspondence with the square-free integers which has cardinality \(\aleph_0\).

So \(2^{\aleph_0} = \aleph_0\) ? This seems wrong because supposedly there is something called the continuum hypothesis which is unproven which says \(2^{\aleph_0} = \aleph_1\) so clearly I have made a mistake.

Answer 2

Yes the cardinality of the set of primes is ℵ0, but the power set of primes contains some sets of infinite cardinality.

The cardinality of the primes is basically that of the natural numbers. Since the power-set of the natural numbers is uncountable, the power set of the primes is also uncountable.

https://proofwiki.org/wiki/Power_Set_of_Natural_Numbers_Not_Countable

Answer 3

@sandsalamand So why can I not put the sets of the power series of the primes in a 1 to 1 correspondence with the square free numbers?

Answer 4

Sorry but I don't really understand your question. How did you get to 2ℵ0=ℵ0?

Answer 5

The power set of primes looks like this:
{\(\emptyset\),{2},{3},{5},{2,3},{7},{2,5},{11},{13},{2,7},...}
If you take the elements in each of these sets and multiply them together you get (setting the empty set to 1)
{1,2,3,5,6,7,10,11,13,14,...}

which are the square free numbers.

Answer 6

Ok I understand your question and your logic makes sense to me, but I just told you that the cardinality of the power set of the primes is uncountable, which means your original question about 2ℵ0=ℵ0 is invalid, since the power set of the primes does not have the cardinality of 2ℵ0.

Answer 7

yeah, but I just made a bijection between the sets, so isn't that sufficient to show they have the same cardinality?

Answer 8

No, because the power set of the primes has some sets of infinite cardinality. I'm sorry I can't show you specifically which sets those are but the ones you've shown have only been a set of finite subsets of the primes.

Answer 9

There are infinitely many primes, then if you were to combine these in every possible way somehow we get more than just the total number of numbers despite every number having a unique prime factorization? Why should I believe any of what you're telling me

Answer 10

I already provided you the proof.

Answer 11

You can look up any more proofs about the primes being uncountable as well, here let me find one.

Answer 12

No, there is some kind of fundamental misunderstanding. None of this makes sense.

Answer 13

Why do you seem to accept this so easily? I don't get it. Clearly a power set of a finite number of primes is a subset of the natural numbers. There's some alternate definition here that I am unaware of, despite there being an infinitely many primes.

Answer 14

Ok do you agree that the sub-sets of the natural numbers are uncountable?

Answer 15

I don't know either way

Answer 16

Ok tell me what you think of this

https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

Answer 17

In his first proof he showed that the set of all real numbers is uncountably infinite.
https://en.wikipedia.org/wiki/Georg_Cantor%27s_first_set_theory_article

Answer 18

Since the set of all reals is uncountable, so is the set of the natural numbers.

Answer 19

I've seen it used before to prove the uncountability of the real numbers.

Here, I figured out a way to put all the subsets of the natural numbers into a 1 to 1 correspondence with the natural numbers.

Take every power of a prime in the natural numbers. Look at its exponents in base 2 and that will tell you what numbers to include in the subset, like so:

\[\{2^0, 2^1,2^{10},2^{11},2^{100},...\}\]
\[\{\{\}, \{1\}, \{2\}, \{1,2\}, \{3\},...\}\]

So no, the subsets of the natural numbers are not uncountable.

Answer 20

I'll let you and Cantor debate that out. I'm no mathematician; and I'm sorry I failed to help you. I wish you the best of luck in finding someone qualified enough to debate you on this.

Answer 21

I am just trying to get to the bottom of this cause I am completely confused haha. Thanks for trying.

Answer 22

Yah I kinda want to know the answer now as well. I'll be checking back to see if you've come to any solid conclusion, good luck.

Answer 23

Hmm apparently there's something called "supernatural numbers" http://math.stackexchange.com/questions/100764/is-it-useful-to-think-of-the-natural-numbers-as-a-powerset-of-the-primes

I am not really satisfied with this, but I think I'll just forget about caring about set theory at this point since infinite sets seem to be both nonsense and useless so far to my learning about topology so I think I'll just leave it at that for now haha. I'll keep it in the back of my mind though.

Answer 24

Yah I'm not really sure how that would be useful to you. In my opinion it's not useful to anyone (lol) which is why I kinda gave up debating you. But if one day Cantor himself comes on here and answers your question, I'd still be interested in knowing what he has to say.

Answer 25

Yeah, for fun, even though I know my reasoning is somehow mysteriously flawed, I can show that a subset of the naturals is in 1 to 1 correspondence with the unit interval... LOL

Take powers of 1337 in base 2, and use the digits in reverse order as the decimal expansion of the fraction in base 2.

\[\{p^0,p^1,p^{10},p^{11},p^{100},p^{101},...\}\]\[\{0,.1,.01,.11,.001,.101,...\}\]

At least this will be charming to bring up at dinner parties... uhhh right? xD

Answer 26

Well I don't know what kind of dinner parties you go to but at the one's I'm used to the highest level of conversation we ever get to is what happened on the news yesterday. Where is this secret mathematicians' dinner party club? I want in! (Unless all they talk about is set theory, in which case I want no part of it.)

Answer 27

I'm not good at this.. but let's see.. \(\mathcal P\) is the set of primes.
\(\mathrm{card}(\mathbb N) \ge \mathrm{card}(\mathcal P)\)
and \(2^{\aleph} \ge 2^{\aleph_0} > \aleph_0 = \aleph\)
if \(\aleph\) is the cardinality of primes... Does this make sense?

Answer 28

*typo* \(\aleph\) is the cardinality of the natural numbers..

Answer 29

In a trivial setting, it feels like looking at "\(]1,2] \cap \mathbb N\)". "1 or 2" but not "1".

Answer 30

\(\mathrm{card}(\mathbb N) = \mathrm{card}(\mathcal P)\) right..

Answer 31

@sandsalamand Yeah, you're right, if I talk about set theory at any party, it's probably a party I'm wanting to get kicked out of.

@reemii I honestly don't know. I feel like my brain has sorta been turned to mush after thinking about this whole thing so I don't know if I'm gonna be able to really read through anything you say tonight but I'll definitely read it tomorrow. I'll still try right now though while you're here if you're willing but no guarantees lol

Answer 32

\(card(\mathbb N) = card(\mathcal P)\) . they are "the same"..: first, second, third, ...
Isn't that the only argument needed?