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.
If were admitted as a prime, uniqueness would fail: , lists of different lengths that no permutation matches
Statement refuted
Refuted claim. The clause in Prime and composite integers: is prime when and its only positive divisors are and is an arbitrary convention: replacing it by would leave The fundamental theorem of arithmetic: every integer is a product of primes, and the factorisation is unique up to order — if with every and prime, then and for some true as stated.
Write prime for the modified notion — and the only positive divisors of are and — so that is prime and every prime is prime. The claim under refutation is that for lists of primes, still forces and for some (The symmetric group : the bijections of a set under composition, The product of a finite list in a monoid, by recursion, with the empty product () equal to the identity).
Witness. The lists , and , of lengths , and , all consist of primes and all have product . So fails already between the first two, and no permutation can exist because the index sets have different sizes.
Numerals. For the symbol inside means , the embedding of The naturals embed in the integers.
Facts & Assumptions
Given: The integers , , and , and the three lists above.
is prime when and its only positive divisors are and (Prime and composite integers: is prime when and its only positive divisors are and ).
exactly when or ( is a commutative monoid whose group of units is ; equivalently holds exactly for and ); means for some (Divisibility in : when for some integer ).
For and there is exactly one pair with and , and exactly when (Division with remainder in : for and there are unique with and ).
If with then ; equivalently there is no bijection between two distinct natural numbers (The pigeonhole principle on , Equinumerous sets, and , Injection, surjection, bijection).
A permutation of the von Neumann natural is a bijection (The symmetric group : the bijections of a set under composition); (On the order is membership: , The natural numbers (von Neumann)).
is a commutative ring with ; its order is total, antisymmetric and transitive (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals, The integers form a totally ordered ring, Order on the integers); is injective and order preserving with image the nonnegative integers (The naturals embed in the integers, Discreteness: is the immediate successor, Order on the natural numbers).
Every is a finite product of primes (Every integer is a finite product of primes: there are and a list of primes with , the case being the empty product).
Counterexample
, and every integer satisfies : with , so since preserves the order.
All three products are . By [L2], ; ; and .
is prime: , and a positive divisor of satisfies , hence or by [L3], and positivity leaves , which is itself.
and are prime, hence prime. Each exceeds ; a positive divisor of such an satisfies by [L4] and step 1.1, and the intermediate candidate for is settled by , whose remainder is nonzero. For there is no intermediate candidate.
The three lists consist of primes, by steps 2.1 and 2.2, and their lengths are , and , which are pairwise distinct natural numbers.
So the uniqueness clause fails at its very first assertion: taking and gives with , so "" is false.
Nor could the clause be rescued by dropping "" and asking only for a bijection: a permutation in the sense of [L7] is a bijection between index sets, and by [L6] no bijection exists between the distinct naturals and .
Existence, by contrast, survives the change: is still a factorisation into primes, and every still has one by [L9], since every prime is prime. So it is precisely the uniqueness half that forces the convention .
Remarks
-
The failure is not a technicality about lists. Under the modified definition an integer would have infinitely many factorisations, one for each number of padding factors , so no formulation of uniqueness survives: neither "the same length", nor "the same multiset of factors", nor "the same exponent vector", since would carry an arbitrary exponent.
-
Existence is what makes the convention a genuine choice rather than a necessity. Both notions give factorisations of every , and the difference shows up only when one asks whether the factorisation is unique. That is exactly the asymmetry Prime and composite integers: is prime when and its only positive divisors are and appeals to when it excludes .
-
is excluded for a different reason. It is not that would break uniqueness; it is that has every positive integer as a divisor, so it fails the divisor clause outright, and a product containing the factor is rather than the integer being factored.
Depends on
- Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$
- The fundamental theorem of arithmetic: every integer $n \ge 1$ is a product of primes, and the factorisation is unique up to order — if $\prod_{i<r} p_i = \prod_{j<s} q_j$ with every $p_i$ and $q_j$ prime, then $r = s$ and $q_i = p_{\pi(i)}$ for some $\pi \in \operatorname{Sym}(r)$
- 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
- The symmetric group $\operatorname{Sym}(X)$: the bijections of a set $X$ under composition
- The pigeonhole principle on $\mathbb{N}$
- Equinumerous sets, $A \approx B$ and $A \preceq B$
- Injection, surjection, bijection
- 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
- Semigroup and monoid
- $(\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$
- Divisibility in $\mathbb{Z}$: $d \mid a$ when $a = dq$ for some integer $q$
- If $d \mid a$ and $a \ne 0$ then $d \ne 0$ and $|d| \le |a|$; hence the set of divisors of a nonzero integer is bounded above by $|a|$
- Division with remainder in $\mathbb{Z}$: for $a \in \mathbb{Z}$ and $b > 0$ there are unique $q, r \in \mathbb{Z}$ with $a = qb + r$ and $0 \le r < b$
- The integers form a commutative ring
- The integers form a totally ordered ring
- Arithmetic on the integers
- Order on the integers
- The integers as equivalence classes of pairs of naturals
- The natural numbers $\mathbb{N}$ (von Neumann)
- On $\mathbb{N}$ the order is membership: $m < n \iff m \in n$
- The naturals embed in the integers
- Discreteness: $\sigma(n)$ is the immediate successor
- Order on the natural numbers
Used by
Nothing in the library uses this result yet.
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 94 results over 31 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
- Fundamental theorem of arithmetic (Wikipedia) (standard reference, not scraped)
- Prime number (Wikipedia) (standard reference, not scraped)
- Janssen and Lindsey, Rings with Inquiry: Primes and Factorization (standard reference, not scraped)