2- Aleph 0 is the infinite cardinality of natural, and natural and rational numbers. Can it really be the cardinality of the set of prime numbers as well? It seems so starkly counterintuitive.
According to Cantor's theorem, the powerset of a set has a larger cardinality.
So, starting with, for example, the naturals numbers (whose cardinality is Aleph_0, the "smallest" infinity) its powerset has the cardinality of the continuum (c, which is equal to Bet_1, and, if the continuum hypothesis holds, it is equal to Aleph_1, too). The powerset of this second set, has a cardinality of Bet_2 (equal to Aleph_2 if the generalized continuum hypothesis holds), and so on...
Then, if the generalized continuum hypothesis is true, Aleph_4 is simply the cardinality of P(P(P(P(Naturals)))).
If these hypothesis are false, then there are cardinalities that lie in between the Bet numbers (i.e., larger than the cardinal of a set, but smaller than the cardinal of its powerset).
In fact, by definition, Aleph_4 is the "successor" of Aleph_3 (i.e., the smallest cardinality larger than Aleph_3). So, it exists independently of these hypothesis.
2.- Yes, the prime numbers cardinality is Aleph_0, too.
They are a subset of the naturals, so their cardinality cannot be larger, but there are an infinite amount of them, so their cardinality cannot be smaller either (remember that Aleph_0 is the "smallest" infinite).
According to Cantor's theorem, the powerset of a set has a larger cardinality.
So, starting with, for example, the naturals numbers (whose cardinality is Aleph_0, the "smallest" infinity) its powerset has the cardinality of the continuum (c, which is equal to Bet_1, and, if the continuum hypothesis holds, it is equal to Aleph_1, too). The powerset of this second set, has a cardinality of Bet_2 (equal to Aleph_2 if the generalized continuum hypothesis holds), and so on...
Then, if the generalized continuum hypothesis is true, Aleph_4 is simply the cardinality of P(P(P(P(Naturals)))).
If these hypothesis are false, then there are cardinalities that lie in between the Bet numbers (i.e., larger than the cardinal of a set, but smaller than the cardinal of its powerset).
In fact, by definition, Aleph_4 is the "successor" of Aleph_3 (i.e., the smallest cardinality larger than Aleph_3). So, it exists independently of these hypothesis.
2.- Yes, the prime numbers cardinality is Aleph_0, too.
They are a subset of the naturals, so their cardinality cannot be larger, but there are an infinite amount of them, so their cardinality cannot be smaller either (remember that Aleph_0 is the "smallest" infinite).
Santi, thanks, great answers, but first, 2 comments on 1):
1- The continuum hypothesis is not proven yet .
2- Hence my 2nd question : Do you have a definite incontrovertible proof that a Bet number has a higher cardinality than its underset Aleph number ? Pardon my ignorance, but I'm not aware of any smoking gun proof
On the second question: I'm aware that this is what the proof says, but I find it excruciatingly hard to have a proper feel for it.
The "bijection " proof is the only one we have on that, hence I wonder - somewhat idly, I'll own up to that - whether it could conceivably be falsified (bear with me) : The number of primes grows logarithmically slowly and asymptotically tends to become parallel to the x axis; whereas obviously it's not the case at all for a number of other Aleph-naught sets. Just wondering whether there would be any way that this could serve as an ansatz for a ad absurdum proof that primes somehow are less than aleph naught - perhaps some Aleph minus 1. I realize that this is a bit of a tilting at the windmills question ....
And therefore I concur with you that the odds are vanishingly wee - but I just can't quite get my mind around the cardinality of primes being the same as that of rational numbers .... It was hard enough, but immensely easier, to accept that natural numbers and rationals have the same cardinality ....
I know that neither the continuum hypothesis (CH) nor its generalized version (GCH) are proven yet. I used them to simplify my argument.
The fact is, if the set of infinite cardinals is an infinite sequence with each member larger than the previous, then this cardinals are (by definition) the Aleph numbers.
The Cantor's theorem proves that there exists a sequence of this kind (the Bet numbers).
But we don't know if this Bet sequence contains all the cardinals or there are some other cardinals in between. Then, we have two options:
- If the GCH is true, then Aleph_k = Bet_k for all k, so, in that case, Aleph_4 exists and is equal to Bet_4
- If the GCH is false, then the Aleph numbers still exist, but some of them are "filling the holes" of the Bet numbers, so, even if we don't know where is Aleph_4 we know that it is somewhere (for example, Aleph_4 could be equal to Bet_2, or it could lie between Bet_0 and Bet_1).
About the second comment:
We don't have a proof that Bet numbers are larger than Aleph numbers.
We know that Bet_0 = Aleph_0 (i.e. the smallest infinite cardinal)
Then, a proof of the falsehood of CH implies Bet_1 > Aleph_1
and a proof of the falsehood of GCG implies Bet_k > Aleph_k (except for k=0)
But we don't know if CH and GCH are true or false.
About the primes:
The problem is the definition of "size" used. If you use the concept of cardinals, then what we use to compare two sets are the functions between them. And, in that case, the existence of a bijection implies that they are equal.
But I agree that, intuitively, one could say that there are double integers than even numbers, or infinite more integers than primes.
There are other possibilities, with measure theory being one of them. I don't know the details of all of them, but I'm sure that one of them will satisfy you.
There is a thing in which all definitions of the size of a set will agree:
- For two sets A and B, with A being a subset of B, the size of A cannot be larger than the size of B.
@ H Chris Ransford. I am refering to the conceptual problem of the cardinality of prime numbers. Without trying to diminish future results concerning anything related to the continuum hypothesis or anything in between, I will focus on what you said about the primes becoming scarcer and scarcer, until their number amounts to something which (I am quoting yourself) "[...] asymptotically tends to become parallel to the x axis". This observation is correct, provided you notice that it is always a *Local* observation of the density of prime numbers with respect to amount of natural numbers. It does not says anything about their cardinality (*global property*). As for the question about books mentioning denumerabiity, I can mention "Real and Functional Analysis", Serge Lang, 3rd edition, page 7 and onwards, which I am sorry that it will tell you the same "bijection" argument which you were not conviced of in the first place. However it will refresh us of something important: cardinality is a *Global* property of a set.
If I am emphasizing *Local* vs. *Global*, it is because you can have many properties of a set which are true locally, but are not necesarily carried over the entire set. Taking the set of primes that concerns you: The Riemann Hypothesis has been tested up to well above 10**34 and still this is *not* a proof, because we are not sure that RiemannZeta(a+i*t)==0 for those "t" making the equality true, and *only* when the real part = a=1/2. Another example, still on the Riemann Hypothesis: you can have 100 % of the zeros of RiemannZeta (with Re(s)=a=1/2) and still you do not necesarily have all the zeros to make it a proof (see, for example, Marcus du Sautoy's "Music of the Primes", 2003, page 103). The reasoning is not that hard: if you have 9/10, you have one left out; 98/100 you have *two* left out; 980/1000, you have *twenty* left out, and so on and so forth, so you can see and asymptote approaching both 100% and at the same time leaving out infinitely many numbers out! At any rate, infinity is truly something that does crushes down many Local effects, like the proportion of prime numbers against the naturals (and yet, primes are denumerable, according to Lang and other books).