Identifier
F:nat-is-prime-eq-true-of-prime
Proof route
kernel-lean
External status
proved
Axiom footprint
Empty

Recorded description

If n is prime -- 2 <= n and every divisor of n is 1 or n -- then the Bool predicate Nat.isPrime, which decides primality by counting the divisors of n among 1..n and comparing that count to 2, answers true at n.

Formal statement
theorem Nat.isPrime_eq_true_of_prime : ((x0 : AxNat) -> ((x1 : And (AxNat.le (AxNat.succ (AxNat.succ AxNat.zero)) x0) (((x1 : AxNat) -> ((x2 : AxNat.dvd x1 x0) -> Or (Eq.{1} AxNat x1 (AxNat.succ AxNat.zero)) (Eq.{1} AxNat x1 x0))))) -> Eq.{1} Bool (AxNat.isPrime x0) Bool.true))

Dependencies

The graph shows direct ledger edges. Follow a node to open its artifact page.

Direct dependencies appear to the left. The current fact is in the center. Facts that depend directly on it appear to the right. Mathlib v4.30 source propositio Mathlib v4.30 source propositio Mathlib v4.30 source propositio [generated] kernel theorem Nat. [generated] kernel theorem Nat. A countRange over a predicate f [generated] kernel theorem Nat. [generated] kernel theorem Nat. Current fact The prime-counting function is
16 direct dependencies 1 direct dependents Graph shows the first 8 on each side.

Evidence

kernel-Nat.isPrime_eq_true_of_prime

Kind
kernel-term
Status
checked

Supports: prime_condition n implies Nat.isPrime n = true

Checker command
test "$(cargo run -q -p axeyum-lean-kernel --example nat_theorem_inventory -- 'Nat.isPrime_eq_true_of_prime' 2>/dev/null | grep -xFc 'Nat.isPrime_eq_true_of_prime	4	((x0 : AxNat) -> ((x1 : And (AxNat.le (AxNat.succ (AxNat.succ AxNat.zero)) x0) (((x1 : AxNat) -> ((x2 : AxNat.dvd x1 x0) -> Or (Eq.{1} AxNat x1 (AxNat.succ AxNat.zero)) (Eq.{1} AxNat x1 x0))))) -> Eq.{1} Bool (AxNat.isPrime x0) Bool.true))')" -ge 1
Evidence notes

`Nat.isPrime n` unfolds to `beq (countRange (fun j => beq (n % (j+1)) 0) n) 2` -- a divisor COUNT, not a trial division. The proof shows that count is exactly two for a prime: `1 | n` supplies the index 0, `Nat.mod_self` supplies the index n-1, and every index between is refuted by primality's own divisor clause (`c = 1` by `succ_ne_zero`, `c = n` by `lt_irrefl` against the range hypothesis). The count is assembled by peeling the last index with `countRange_succ_of_true` and the first with `countRange_split` at 1, leaving `countRange_eq_zero_of_all_false` for the middle: 2 = 1 + 0 + 1. The rendered type is matched in full because the weakening that matters here is invisible to a name check: `Nat.isPrime` is universe- and argument-compatible with any `AxNat -> Bool`, so a checker that read only the name would be satisfied by a theorem about a different predicate entirely.

footprint-Nat.isPrime_eq_true_of_prime

Kind
exhaustive-enumeration
Status
checked

Supports: axiom_footprint: [] -- the Nat prelude's trusted surface is empty

Checker command
cargo run -q -p axeyum-lean-kernel --example nat_axiom_inventory -- --require-axiom-free nat
Evidence notes

`nat_axiom_inventory` bounds the footprint by enumerating the whole trusted surface: a theorem cannot depend on a trusted declaration the environment does not contain. All three kinds are covered -- counting `Declaration::Axiom` alone would not suffice, because `Opaque` has no proof body and `Quotient` admits `Quot.sound`. The module's own test `the_prime_counting_shelf_is_admitted_and_axiom_free` additionally asserts `Environment::contains` BEFORE reading the footprint, because `axiom_footprint` returns an empty set for a name that was never declared.

Provenance

{
  "date": "2026-09-06",
  "established_by": "lane chebyshev-pi-bounds (ADR-1655), roadmap W3-11",
  "source": "statement authored here against this kernel's own vocabulary; nothing copied"
}