# Another Proof of Euclid's Theorem (infinite number of primes)?

Here $$\mathbb N = \{2,3,4,\dots\}$$ with the binary operation of addition.

If $$m \in \mathbb N$$ we denote by $$G_{\mathbb N} (m)$$ the semigroup generated by $$m$$.

Definition: A number $$p$$ is said to be prime if for all $$m \lt p$$, $$\;p \notin G_{\mathbb N} (m)$$.

We denote the set of non-empty finite subsets of $$\mathbb N$$ by $$\mathcal F (\mathbb N)$$.

Let $$\mathtt E$$ be a function

$$\quad \mathtt E: \mathbb N \to \mathcal F (\mathbb N)$$

satisfying the following:

$$\quad \quad\quad\forall n \in \mathbb N$$

$$\tag 0 \mathtt E (2) = \{2\}$$

$$\tag 1 \text{ If } (\forall \text{ prime } p \lt n) \; n \notin G_{\mathbb N} (p) \text{ then } \mathtt E (n) = \{n\}$$

$$\tag 2 \text{ If } \, (\exists \text{ prime } p \lt n) \; n \in G_{\mathbb N} (p) \text{ then } \mathtt E (n) \text{ is the union of all such primes}$$

$$\tag 3 \mathtt E (n+1) \cap \mathtt E (n) = \emptyset$$

We have the following result:

Theorem 1: There exist one and only one function $$\mathtt E$$ satisfying $$\text{(0)}$$ thru $$\text{(2)}$$; it will also satisfy $$\text{(3)}$$. Moreover, for every $$n$$, all the numbers in the set $$\mathtt E (n)$$ are prime (the prime 'factors').

Question: Can the theorem be proved in this $$(\mathbb N,+)$$ setting?

If yes, we can continue.

Theorem 2: The set of all prime numbers is an infinite set.
Proof
If $$a_1$$ is any number, consider the 'next further out' number

$$\tag 4 a_2 = \sum_{i=1}^{a_1+1}\, a_1 = \sum_{i=1}^{a_1}\,( a_1 + 1)$$.

A simple argument using $$\text{(3)}$$ shows that $$\mathtt E (a_1) \subsetneq \mathtt E (a_2)\;$$ (c.f. Bill Dubuque's remark).

Employing recursion we get a sequence $$a_1, a_2, a_3,\dots$$ with a corresponding chain of strictly increasing sets

$$\quad \mathtt E (a_1) \subsetneq \mathtt E (a_2) \subsetneq E (a_3) \dots$$

So there are sets of prime numbers with more elements than any finite set. $$\blacksquare$$

My Work

Using the recursion theorem to implement the Sieve of Eratosthenes.

The proof of theorem 2 is along the lines found in the proof given by Filip Saidak. Also, if we set $$a_1$$ to $$1$$ in theorem 2 we get the researched OEIS sequence A007018.

Note that the proof supplied by Filip Saidak has most likely been known for many years; see Bill Dubuque's answer to the math.stackexchange.com question

Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?

• Note, multiplication (of positive integers) is recursive addition. That is, we define $a\cdot1$ to be $a$ and $a\cdot(n+1)$ to be $a\cdot n+a$. – Barry Cipra Nov 22 '18 at 17:39
• @BarryCipra Yes I know. But I get excited when something that appears 'bound to multiplication' - the prime numbers - can get released into a more elementary framework. – CopyPasteIt Nov 22 '18 at 17:44
• The proof via $\,n(n\!+\!1)\,$ has more prime factors than $n$ for $\,n\ge 1$ is surely much older than Saidak's 2005 paper. The generated sequence is OEIS A007018. Note: adding $1$ yields Sylvestoer sequence $a_{n+1} = a_n^2 - a_n + 1 =$ OEIS A000058. See the OEIS notes for other connections. – Bill Dubuque Nov 22 '18 at 18:05
• @CopyPasteIt The least factor $> 1$ of $n$ is prime (i.e. irreducible) is already quite minimal. – Bill Dubuque Nov 22 '18 at 19:08
• @CopyPasteIt Well one can unwind everything down to Peano arithmetic, but that won't be very arithmetically enlightening. Why prefer assembly language over the beautiful higher-level language carefully crafted by number theorists over many centuries? – Bill Dubuque Nov 22 '18 at 19:37

It is valid, but seems to be fundamentally the same as the classical proof; both hinge upon the fact that $$p_1\times p_2\times \cdots\times p_n+1$$ is divisible by some prime not in $$\{p_1,p_2,\dots,p_n\}$$.