1
$\begingroup$

I kind of feel this question may have been asked in some way before, but I could not find it.

I know there are infinite prime numbers (because Euclid tells us), and there are infinite integers. For any given range of posative whole numbers there are always more integers then there are prime numbers.

So it appears that there should be "more" integers in total then there are prime numbers. Is this statement true? How do you compare two infinite series when one is a subset of the other?

$\endgroup$
3
  • 5
    $\begingroup$ This is not how you measure the size of infinite sets. I can attach two integers to every prime, and have no integers left over. So there are more primes than integers, right? (read the answers below) $\endgroup$
    – Henry Swanson
    Jan 9, 2014 at 7:42
  • $\begingroup$ All good answers and comments, thanks very much :) $\endgroup$
    – code_fodder
    Jan 9, 2014 at 7:53
  • $\begingroup$ Yes it is true, provided you use the correct measure of size. To capture the degree to which the prime numbers are a proper subset of the integers, it is best to use the concept that the prime numbers are not dense in the integers. I think this fact is under-taught in set theory when discussing cardinality, as without it students immediately see and are dissatisfied with, the obvious shortcomings of cardinality as a measure of size. $\endgroup$
    – samerivertwice
    Jun 30, 2017 at 19:27

4 Answers 4

Reset to default
6
$\begingroup$

The sets have the same cardinality, so there are "as many" integers as primes.

However, you can consider the density of the primes as a subset of the integers. (This is different from considering the set of prime numbers itself, which is indistinguishable from any other countable set.) This characterization is given by the prime number theorem, which you can read about on Wikipedia.

$\endgroup$
4
  • $\begingroup$ Ah, ok, so density of the sets makes no difference to the size, if they are a countable set then they are equal in size, thanks :) $\endgroup$
    – code_fodder
    Jan 9, 2014 at 7:40
  • 2
    $\begingroup$ @code_fodder A similar example in the real numbers is that $[0,1]$ and $[0,2]$ have the same cardinality, since we have a bijection given by $x\mapsto 2x$. However the length of $[0,1]$ is half that of $[0,2]$. $\endgroup$
    – Baby Dragon
    Jan 9, 2014 at 7:44
  • $\begingroup$ @code_fodder: Correct. Similarly, there are as many even integers as integers; as many positive integers as integers; and as many rational numbers as integers. (The last two take a little work to show.) $\endgroup$
    – Daniel McLaury
    Jan 9, 2014 at 7:44
  • $\begingroup$ Thanks both, I am getting the hand of this now I think :) $\endgroup$
    – code_fodder
    Jan 9, 2014 at 7:52
4
$\begingroup$

Prime numbers and integers have the same cardinality which means there is a bijection between integers and prime numbers.

In other words: For every prime number you are able to find an related integer and vice versa.

$\endgroup$
4
  • $\begingroup$ Thanks for that, does that mean that the set of fractions is larger then the set of integers (because there are infinite fractions between each integer? - i.e. different cardinality? $\endgroup$
    – code_fodder
    Jan 9, 2014 at 7:39
  • $\begingroup$ I guess you mean rational numbers? Then the answer is no, rational numbers and integers also have the same cardinality. $\endgroup$
    – user127.0.0.1
    Jan 9, 2014 at 7:40
  • $\begingroup$ Yes, sorry I am more from a software background then maths. So I will have to look up on non-countable sets. Thanks :) $\endgroup$
    – code_fodder
    Jan 9, 2014 at 7:42
  • 1
    $\begingroup$ One would first think that there would be more fractions. However, there also is a surjective transformation from the natural numbers to the fractions, "counting" the fractions. Look here: homeschoolmath.net/teaching/rational-numbers-countable.php and here en.wikipedia.org/wiki/Cantor%27s_diagonal_argument $\endgroup$
    – Bernd
    Jan 9, 2014 at 7:42
2
$\begingroup$

Well there are more than one ways of infinity. In this case both integers and prime numbers are "countable" - meaning there are as many of integers as prime numbers.

You can take a look here: http://en.wikipedia.org/wiki/Countable_set

To be a bit clearer: A set is countable, if can find a surjective transformation from the natural numbers to that set. This is the case for both integers and primes are therefore both integers and primes are countable (and have the same "number of elements" or better "type of infinite number of elements" = cardinality)

$\endgroup$
1
  • $\begingroup$ Thanks for the answer, I am just reading up on that now :o $\endgroup$
    – code_fodder
    Jan 9, 2014 at 7:39
0
$\begingroup$

By the measure of cardinality, which it is most conventional to use when measuring infinite sets, there are the same number of prime numbers as there are integers. This measure is defined by being able to place the sets in bijection which means you can place them into 1:1 correspondence and never have either a prime left over with no corresponding natural number, nor can you have a natural number left over with no corresponding prime.

However there are those who would argue that identity is a stronger measure of correspondence than bijection. And by this argument we can see that the prime numbers are a proper subset of the integers and therefore no matter how many prime numbers we might count, every single one will not just be in $1:1$ correspondence with an integer, it it will actually be an integer, and will be in the set of integers. The set of integers contains all of those and all of the compound numbers on top.

This second measure is best captured by the notion of density. We can say that the integers have density $1$ in themselves while the prime numbers have a density lower than $1$ among the integers.

Cardinality is useful when we need to compare sizes of infinite sets and we're unable to compare them by the identities of the elements within, which is frequently the case.

If trees continue producing apples and oranges for eternity, density will correctly measure the fact that the fruit basket would need to be bigger if you planned to pick both types of fruits. Cardinality on the other hand would simply tell you that you need a really big basket either way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.