$$\newcommand{\tsf}[1]{{\sf{#1}}} \newcommand{\lb}{\left<} \newcommand{\rb}{\right>} \newcommand{\pair}[1]{\lb #1 \rb} \newcommand{\BB}{\mathbb{B}} \newcommand{\RR}{\mathbb{R}} \newcommand{\Pow}{\tsf{Pow}} \newcommand{\List}{\tsf{List}} \newcommand{\TwoPow}[1]{2^{#1}} \renewcommand{\implies}{⇒} \newcommand{\pto}{\to_{\text{?}}}\newcommand{\NNplus}{ℕ^{+}} $$

∞-many primes


Variables x, y, n, m are reserved for sort $\NNplus$.
Sort $\NNplus$ - Positive integers
Divides : $\NNplus$ × $\NNplus$ → 𝔹 - The first number divides the second.
< : $\NNplus$ × $\NNplus$ → 𝔹 - The usual ordering on the natural numbers.
1, 2 : $\NNplus$
Defn Prime : $\NNplus$ → 𝔹 - n is a prime iff it's at least 2 and no smaller (prime) divides it. This combines a normal definition of prime with the lemma: "Every non-prime number > 1 is divisible by a prime."
n. Prime(n) ⇔ ((n 2) ∧ ¬(∃m < n. Divides(m, n) ∧ Prime(m)))
Defn MaxPrime : $\NNplus$ → 𝔹 - True iff n is the largest prime number.
n. MaxPrime(n) ⇔ (Prime(n) ∧ (∀m > n. ¬Prime(m)))

$\tsf{Theorem}$: There are infinitely-many primes.
∀n. ¬MaxPrime(n)
Note that the theorem is a logical consequence (verified by a first-order theorem prover) of AXIOM3, Lemma 1, and the definitions and axioms that precede the statement of the theorem.
! : $\NNplus$$\NNplus$ - factorial
+ : $\NNplus$ × $\NNplus$$\NNplus$ - addition
Axiom 4: n. n + 1 > n
Axiom 5: n. n! n
Lemma 1: n. MaxPrime(n) ⇒ Prime(n! + 1)
Lemma 2: n. ¬(n! + 1 < 2)
Lemma 3: n,m. MaxPrime(n) ∧ Prime(m) ⇒ (m n)
Axiom 8: n. ∀m n. Divides(m, n!)
Axiom 9: x. ∀m 2. Divides(m, x) ⇒ ¬Divides(m, x + 1)