In Figure 10.8 we give a list of primes that comes in handy for many considerations of primes. Use it to count how many primes there are between certain numbers. You will see that as the numbers become larger there are fewer primes.
In Theorem 9.22 we saw that there are infinitely many natural numbers. Certainly, not every natural number is prime because there are composites, too. However, an ancient number theory result [5] asserts that there are still infinitely many primes.
Let \(\PP\) denote the set of all prime numbers. We show that for any finite subset \(Q\) of \(\PP\) there is an element in \(\PP\) that is not an element of the finite subset \(Q\text{.}\)
Let \(Q\) be a finite subset of the set \(\PP\text{.}\) Denote the elements of \(Q\) by \(p_1, p_2, \dots,p_n\) and let \(q = p_1 \cdot p_2\cdot \ldots \cdot p_n\text{.}\)
By Theorem 4.22\(q\) and \(q+1\) are coprime. So there is at least one prime number that divides \(q+1\) but does not divide \(q\text{.}\) Call that prime number \(t\text{.}\) Then \(t \not\in Q\text{.}\)
Theorem 2. Let \(B\) be a set. If for each finite subset \(S\) of \(B\) there is an element \(x\in B\) with \(x\not\in S\text{,}\) then \(B\) is infinite.
So we have shown that for any finite set of prime numbers \(Q\text{,}\) we can find another prime number that is not in the set \(Q\text{.}\) Thus, by Theorem 2, we have that \(\mathbb{P}\) is