TheoremStatement: AI-adaptedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck 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 \mathbb{N}$ and every list $p : n \to \mathbb{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 \mathbb{Z} : x \text{ 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 $(\mathbb{Z},\cdot,1)$ of $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ as in The product $g_0 g_1 \cdots 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 \mathbb{N}$ and every list $p : n \to \mathbb{Z}$ of primes there is a prime $q$ with $q \ne p_i$ for every $i < n$ .
Consequently $P$ is not finite: there is no $m \in \mathbb{N}$ with $P \approx m$ (Finite, countably infinite, countable, uncountable, Equinumerous sets, $A \approx B$ and $A \preceq 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<\sigma(n)} g_i = \bigl(\prod_{i<n} g_i\bigr) \cdot g_n$ ; the value depends only on $g_0,\dots,g_{n-1}$ (The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity, $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ , Semigroup and monoid).

[L2]

Splitting law: $\prod_{i<m+k} g_i = \bigl(\prod_{i<m} g_i\bigr) \cdot \bigl(\prod_{l<k} g_{m+l}\bigr)$ for all $m, k \in \mathbb{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 $\ge 1$ (Every integer $n \ge 1$ is a finite product of primes: there are $r \in \mathbb{N}$ and a list $p : r \to \mathbb{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 \mid 1$ exactly when $u = 1$ or $u = -1$ ( $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ).

[L7]

Divisibility is reflexive and transitive, and is linear: $d \mid a$ and $d \mid b$ give $d \mid ax + by$ , in particular $d \mid a - b$ (Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ , Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ).

[L8]

$\mathbb{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 $\mathbb{Z}$ is total, antisymmetric and transitive and is compatible with addition (The integers form a totally ordered ring, Order on the integers); $\iota : \mathbb{N} \to \mathbb{Z}$ is injective, preserves the order, and has as image the nonnegative integers, with $\iota(0) = 0$ , $\iota(1) = 1$ (The naturals embed in the integers, The natural numbers $\mathbb{N}$ (von Neumann)).

[L10]

On $\mathbb{N}$ : $j < n$ exactly when $\sigma(j) \le n$ (Discreteness: $\sigma(n)$ is the immediate successor); $a \le b$ means $a + c = b$ for some $c \in \mathbb{N}$ (Order on the natural numbers, Addition of natural numbers); and $n = \{\, m : m < n \,\}$ with $j < \sigma(j)$ (On $\mathbb{N}$ the order is membership: $m < n \iff 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 \mathbb{N}$ (Equinumerous sets, $A \approx B$ and $A \preceq B$ , Finite, countably infinite, countable, uncountable).

Proof

technique · contradiction

1.1

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

1.2

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

L1choose

1.3

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

assume-contraL11choose

2.1

$\Pi \ge 1$ by [L3], so $N = \Pi + 1 \ge 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 $\sigma(j) \le n$ , so $n = \sigma(j) + c$ for some $c \in \mathbb{N}$ .

assume-contrastep 1.2L10

2.3

Define $f : m \to \mathbb{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 \mid N$ .

step 2.1L4choose

3.2

The splitting law then gives $\Pi = \bigl(\prod_{i<\sigma(j)} p_i\bigr) \cdot \bigl(\prod_{l<c} p_{\sigma(j)+l}\bigr)$ , and $\prod_{i<\sigma(j)} p_i = \bigl(\prod_{i<j} p_i\bigr) p_j$ ; by associativity and commutativity $\Pi = p_j \cdot B$ where $B := \bigl(\prod_{i<j} p_i\bigr)\bigl(\prod_{l<c} p_{\sigma(j)+l}\bigr)$ . Hence $p_j \mid \Pi$ , that is $q \mid \Pi$ .

step 2.2L1L2L7L8

4.1

So $q \mid N$ and $q \mid \Pi$ , whence $q \mid N - \Pi = 1$ by linearity, forcing $q = 1$ or $q = -1$ and contradicting $q > 1 > 0 > -1$ . Therefore $q \ne 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 \ne 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 \cdots 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 \cdots 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 \mathbb{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

FALSE: for every finite list p₀, …, pₙ₋₁ of distinct primes, p₀ ⋯ pₙ₋₁ + 1 is prime False statement

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 86 results over 29 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click 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 \in \mathbb{N}n∈N and every list p:n→Zp : n \to \mathbb{Z}p:n→Z of primes there is a prime not among p0,…,pn−1p_0, \dots, p_{n-1}p0​,…,pn−1​; consequently the set of primes is not finite