Identifier
F:nat-finset-card-le-of-injon
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 g is injective on the members of s and sends every member of s to a member of t, then the size of s is at most the size of t.

Formal statement
theorem Nat.Finset.card_le_of_injOn : ((x0 : AxNat.Finset) -> ((x1 : AxNat.Finset) -> ((x2 : ((x2 : AxNat) -> AxNat)) -> ((x3 : ((x3 : AxNat) -> ((x4 : AxNat) -> ((x5 : Eq.{1} Bool (AxNat.Finset.memB x0 x3) Bool.true) -> ((x6 : Eq.{1} Bool (AxNat.Finset.memB x0 x4) Bool.true) -> ((x7 : Eq.{1} AxNat (x2 x3) (x2 x4)) -> Eq.{1} AxNat x3 x4)))))) -> ((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))) -> AxNat.le (AxNat.Finset.card x0) (AxNat.Finset.card x1))))))

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. Cardinality of an injection, at Membership implies the index is Current fact Two systems of distinct represe The pigeonhole principle over a
2 direct dependencies 2 direct dependents

Evidence

kernel-nat-finset-card-le-of-injon

Kind
kernel-term
Status
checked

Supports: Nat.Finset.card_le_of_injOn 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 '-> AxNat.le (AxNat.Finset.card x0) (AxNat.Finset.card x1))))))')" -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-card-le-of-injon

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.card_le_of_injOn" && $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-card-le-of-injon

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."
}