There a ways to formulate &quot;the infinity of the prime numbers&quot; without any recourse to a previously-constructed set of all prime numbers (or even all natural numbers). Two such ways are:<p>1. &quot;For any natural number n, there is a prime number greater than n.&quot;<p>2. &quot;For any natural number m, and for any list of m prime numbers p_1, ..., p_m, there exists a prime number not on that list.&quot;<p>Both statements have a perfectly fine constructive proof. The second statement is more or less precisely what Euclid proved. The first statement follows from the second one with a bit more work.