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.
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?

  • $\begingroup$ 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$. $\endgroup$ – Barry Cipra Nov 22 '18 at 17:39
  • $\begingroup$ @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. $\endgroup$ – CopyPasteIt Nov 22 '18 at 17:44
  • 1
    $\begingroup$ 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. $\endgroup$ – Bill Dubuque Nov 22 '18 at 18:05
  • 1
    $\begingroup$ @CopyPasteIt The least factor $> 1$ of $n$ is prime (i.e. irreducible) is already quite minimal. $\endgroup$ – Bill Dubuque Nov 22 '18 at 19:08
  • 1
    $\begingroup$ @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? $\endgroup$ – 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\}$.

  • 1
    $\begingroup$ @Copy It is poor form to change the question in a way that invalidates existing answers. $\endgroup$ – Tobias Kildetoft Nov 23 '18 at 17:08

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.