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
Please see
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?
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\}$.