AFTD Auto-Formalizing Theoretical Domains

empty_eq_zero_of_matroid_rank_valuation

theoremverified

A matroid-rank valuation evaluates the empty set to 0.

Statement

theorem empty_eq_zero_of_matroid_rank_valuation {m : ℕ} {v : Finset (Fin m) → ℝ}
    (h : is_matroid_rank_valuation v) : v ∅ = 0
Source
arXiv:2012.12710
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • is_matroid_rank_valuationA set function on a finite set of indivisible goods is a matroid-rank valuation if it evaluates the empty set to 0, is submodular, and has…
  • has_binary_marginalsEvery marginal value of the set function is 0 or 1.
  • is_submodularA set function is submodular: for S inside T and j outside T, the marginal value of j over T is at most its marginal value over S.

Read back from the Lean

For any natural number $m$ and any function $v : \mathrm{Finset}(\mathrm{Fin}\ m) \to \mathbb{R}$, if $v$ is a matroid rank valuation, then $v(\emptyset) = 0$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

By definition, a matroid-rank valuation is required to evaluate the empty set to 0 (alongside having submodular and binary marginals). The result holds immediately by taking the first conjunct of the assumption.

  1. v ∅ = 0

    By definition, `is_matroid_rank_valuation v` is a conjunction consisting of `v ∅ = 0`, submodularity, and binary marginals. Projecting the first component (`h.1`) of the hypothesis `h` directly yields `v ∅ = 0`.

    line 4

      h.1

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- A matroid-rank valuation evaluates the empty set to 0. -/theorem empty_eq_zero_of_matroid_rank_valuation {m : ℕ} {v : Finset (Fin m) → ℝ}    (h : is_matroid_rank_valuation v) : v ∅ = 0 :=  h.1
See it in the graphDiscuss this resultChallenge it