TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Euclid's theorem: for every $n \in N$ and every list $p : n \to Z$ of primes there is a prime not among $p_{0}, \dots, p_{n - 1}$ ; consequently the set of primes is not finite

Statement

Write $P : = {x \in Z : x is prime}$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ), and take finite products in the commutative monoid $(Z, \cdot, 1)$ of $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ as in The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity.

For every $n \in N$ and every list $p : n \to Z$ of primes there is a prime $q$ with $q \neq p_{i}$ for every $i < n$ .
Consequently $P$ is not finite: there is no $m \in N$ with $P \approx m$ (Finite, countably infinite, countable, uncountable, Equinumerous sets, $A \approx B$ and $A ⪯ B$ ).

Clause 1 holds at $n = 0$ as well, where the empty product is $1$ and the witness produced by the proof is a prime divisor of $2$ .

Facts & Assumptions

Given: The set $P$ of primes.

[L1]

$\prod_{i < 0} g_{i} = e$ and $\prod_{i < σ (n)} g_{i} = (\prod_{i < n} g_{i}) \cdot g_{n}$ ; the value depends only on $g_{0}, \dots, g_{n - 1}$ (The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity, $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ , Semigroup and monoid).

[L2]

Splitting law: $\prod_{i < m + k} g_{i} = (\prod_{i < m} g_{i}) \cdot (\prod_{l < k} g_{m + l})$ for all $m, k \in N$ (Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either).

[L3]

Every finite product of primes is $\geq 1$ (Every integer $n \geq 1$ is a finite product of primes: there are $r \in N$ and a list $p : r \to Z$ of primes with $n = \prod_{i < r} p_{i}$ , the case $n = 1$ being the empty product).

[L4]

Every integer $> 1$ has a prime divisor (Every integer $n > 1$ has a prime divisor; indeed the least divisor of $n$ that exceeds $1$ is prime).

[L5]

Every prime satisfies $u > 1$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L6]

$u ∣ 1$ exactly when $u = 1$ or $u = - 1$ ( $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ ).

[L7]

Divisibility is reflexive and transitive, and is linear: $d ∣ a$ and $d ∣ b$ give $d ∣ a x + b y$ , in particular $d ∣ a - b$ (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ , Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L8]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $x + 0 = x$ , $x \cdot 1 = x$ , and every $x$ has an additive inverse (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L9]

The order on $Z$ is total, antisymmetric and transitive and is compatible with addition (The integers form a totally ordered ring, Order on the integers); $ι : N \to Z$ is injective, preserves the order, and has as image the nonnegative integers, with $ι (0) = 0$ , $ι (1) = 1$ (The naturals embed in the integers, The natural numbers $N$ (von Neumann)).

[L10]

On $N$ : $j < n$ exactly when $σ (j) \leq n$ (Discreteness: $σ (n)$ is the immediate successor); $a \leq b$ means $a + c = b$ for some $c \in N$ (Order on the natural numbers, Addition of natural numbers); and $n = {m : m < n}$ with $j < σ (j)$ (On $N$ the order is membership: $m < n ⟺ m \in n$ ).

[L11]

A function is injective when it identifies no two points, surjective when its image is the whole codomain, and bijective when it is both (Injection, surjection, bijection); $A \approx B$ means a bijection $A \to B$ exists, and $A$ is finite when $A \approx m$ for some $m \in N$ (Equinumerous sets, $A \approx B$ and $A ⪯ B$ , Finite, countably infinite, countable, uncountable).

Proof

technique · contradiction

1.1

$0 < 1$ in $Z$ , since $1 = ι (1)$ is nonnegative and differs from $0 = ι (0)$ by injectivity of $ι$ ; adding $1$ gives $1 < 1 + 1$ .

1.2

Fix $n \in N$ and a list $p : n \to Z$ of primes, and put $Π : = \prod_{i < n} p_{i}$ and $N : = Π + 1$ .

L1choose

1.3

Suppose, for contradiction, that $P$ is finite: fix $m \in N$ and a bijection $g : P \to m$ .

assume-contraL11choose

2.1

$Π \geq 1$ by [L3], so $N = Π + 1 \geq 1 + 1 > 1$ by compatibility of the order with addition.

step 1.1step 1.2L3L9

2.2

Suppose, for contradiction, that $q = p_{j}$ for some $j < n$ . Since $j < n$ we have $σ (j) \leq n$ , so $n = σ (j) + c$ for some $c \in N$ .

assume-contrastep 1.2L10

2.3

Define $f : m \to Z$ by letting $f (i)$ be the unique $x \in P$ with $g (x) = i$ ; such an $x$ exists because $g$ is surjective and is unique because $g$ is injective. Then $f$ is a list of primes of length $m$ , and $f (g (x)) = x$ for every $x \in P$ .

step 1.3L11construct

3.1

By [L4] there is a prime $q$ with $q ∣ N$ .

step 2.1L4choose

3.2

The splitting law then gives $Π = (\prod_{i < σ (j)} p_{i}) \cdot (\prod_{l < c} p_{σ (j) + l})$ , and $\prod_{i < σ (j)} p_{i} = (\prod_{i < j} p_{i}) p_{j}$ ; by associativity and commutativity $Π = p_{j} \cdot B$ where $B : = (\prod_{i < j} p_{i}) (\prod_{l < c} p_{σ (j) + l})$ . Hence $p_{j} ∣ Π$ , that is $q ∣ Π$ .

step 2.2L1L2L7L8

4.1

So $q ∣ N$ and $q ∣ Π$ , whence $q ∣ N - Π = 1$ by linearity, forcing $q = 1$ or $q = - 1$ and contradicting $q > 1 > 0 > - 1$ . Therefore $q \neq p_{i}$ for every $i < n$ , which is clause 1.

step 1.1step 1.2step 3.1step 3.2L5L6L7L8L9

5.1

Clause 1 applied to $f$ supplies a prime $q_{0}$ with $q_{0} \neq f (i)$ for every $i < m$ . But $q_{0} \in P$ , so $g (q_{0}) < m$ and $f (g (q_{0})) = q_{0}$ , a contradiction. Hence no such $m$ and $g$ exist and $P$ is not finite, which is clause 2.

step 4.1step 1.3step 2.3L10L11discharge-contradiction∎

Remarks

The theorem does not say $N$ is prime, and reading it that way is a common slip. What is proved is that $N = p_{0} \dots p_{n - 1} + 1$ has a prime divisor, and that this divisor is not on the list. The false reading is refuted on the companion page by FALSE: for every finite list $p_{0}, \dots, p_{n - 1}$ of distinct primes, $p_{0} \dots p_{n - 1} + 1$ is prime ↗, where $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$ .
Clause 1 is the constructive statement and clause 2 is a consequence of it. Clause 1 says nothing about infinite sets and needs no notion of cardinality; it just extends any finite list. Clause 2 turns that into "not finite" in the sense of Finite, countably infinite, countable, uncountable, and the only input it needs is that a bijection $P \to m$ produces a list enumerating every prime.
This is not a statement about where the primes are. Arbitrarily long runs of composite integers exist (For every $n \in N$ there are $n$ consecutive composite integers: with $N : = \prod_{j < n} (j + 2)$ , each of $N + 2, \dots, N + n + 1$ is composite ↗), so the gaps between consecutive primes are unbounded; the two facts are compatible and neither weakens the other.

Depends on

Used by

Dependency tree · two levels

68 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Euclid's theorem (Wikipedia) (standard reference, not scraped)
Inquiry into Advanced Algebra: Division, primes, and factorisation (standard reference, not scraped)

Euclid's theorem: for every n∈Nn∈N and every list p:n→Zp:n→Z of primes there is a prime not among p0,…,pn−1p0​,…,pn−1​; consequently the set of primes is not finite