Identifier
F:nat-finset-exists-collision
Proof route
kernel-lean
External status
proved
Axiom footprint
Empty

Recorded description

Let s and t be finite sets over the naturals and g a function on the naturals. If the size of t is strictly less than the size of s, and g sends every member of s to a member of t, then there exist two DISTINCT members a and b of s with g a = g b.

Formal statement
theorem Nat.Finset.exists_collision : ((x0 : AxNat.Finset) -> ((x1 : AxNat.Finset) -> ((x2 : ((x2 : AxNat) -> AxNat)) -> ((x3 : AxNat.lt (AxNat.Finset.card x1) (AxNat.Finset.card x0)) -> ((x4 : ((x4 : AxNat) -> ((x5 : Eq.{1} Bool (AxNat.Finset.memB x0 x4) Bool.true) -> Eq.{1} Bool (AxNat.Finset.memB x1 (x2 x4)) Bool.true))) -> Exists.{1} AxNat (fun (x5 : AxNat) => Exists.{1} AxNat (fun (x6 : AxNat) => And (Eq.{1} Bool (AxNat.Finset.memB x0 x5) Bool.true) (And (Eq.{1} Bool (AxNat.Finset.memB x0 x6) Bool.true) (And (Not (Eq.{1} AxNat x5 x6)) (Eq.{1} AxNat (x2 x5) (x2 x6)))))))))))

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. The pigeonhole principle over a A false bounded loop yields an A bounded Boolean universal ref Mathlib v4.30 source propositio [generated] kernel theorem Nat. Membership implies the index is [generated] kernel theorem Nat. Current fact
7 direct dependencies 0 direct dependents

Evidence

kernel-nat-finset-exists-collision

Kind
kernel-term
Status
checked

Supports: Nat.Finset.exists_collision is admitted by the trusted kernel gate with the type recorded in formal.statement.

Checker command
out=$(target/release/examples/kernel_declaration_projection 2>&1) && test "$(printf "%s\n" "$out" | grep -cF -e '(And (Not (Eq.{1} AxNat x5 x6)) (Eq.{1} AxNat (x2 x5) (x2 x6))))')" -ge 1
Evidence notes

The pattern is a DISTINGUISHING substring of the admitted type, not the declaration's name: an existence check would still pass if the statement drifted. Verified to hit ZERO on a perturbed pattern before this row was written -- see the mutation table in ADR-1593. `kernel_declaration_projection` prints every declaration with its footprint size and its rendered type, and the prelude build admits this theorem only through the trusted gate, so a successful build IS the type-check. `grep -cF -e` rather than `grep -cF`: a pattern beginning with `-` is parsed as an OPTION, and five of these seven do. The table in ADR-1593 caught that -- the rows failed as written before `-e` was added, which is why it was run at all.

footprint-nat-finset-exists-collision

Kind
instance-pin
Status
checked

Supports: axiom_footprint: [] -- read from Kernel::axiom_footprint for this declaration, not from a maintained list

Checker command
out=$(target/release/examples/kernel_declaration_projection 2>&1) && test "$(printf "%s\n" "$out" | awk -F'\t' '$3 == "Nat.Finset.exists_collision" && $4 == "0"' | wc -l)" -ge 1
Evidence notes

The pattern pins BOTH the declaration name and the footprint size 0, so a proof that reached for a trusted declaration would fail the check rather than be reported as axiom-free. A one-character name typo hits zero rows, and so does asking for any size other than 0.

statement-nat-finset-exists-collision

Kind
instance-pin
Status
checked

Supports: The statement says what its name says -- checked at a concrete instance with hand-computed numerals and paired with the specific wrong statement it rules out

Checker command
cargo test -q --release -p axeyum-lean-kernel --lib -- nat_prelude::finset_pigeonhole_tests --test-threads=4
Evidence notes

The trusted gate cannot tell a THEOREM's statement is not what its name says: a `card_le_of_injOn` with its two `card`s transposed, an `exists_collision` whose pair need not be DISTINCT, or a `pigeonhole` whose strict inequality points the other way would each be admitted, carry an empty axiom footprint, and pass every other row in this ledger. `nat_prelude/finset_pigeonhole_tests.rs` instantiates each statement at a concrete pair of sets whose cardinalities are computed independently, and pairs every positive with the wrong statement it rules out. Three of its controls are the sharper kind, where a hypothesis cannot be DISCHARGED (`infer` must fail) rather than a conclusion merely being false.

Provenance

{
  "date": "2026-09-03",
  "established_by": "axeyum-lean-kernel build_nat_prelude",
  "source": "declaration name and canonical type read directly from kernel_declaration_projection, which prints render_lean of the admitted type; lane finset-pigeonhole, ADR-1593."
}