zero_is_matroid_rank_valuation
The constantly zero set function is a matroid-rank valuation.
Statement
theorem zero_is_matroid_rank_valuation (m : ℕ) : is_matroid_rank_valuation (fun (_ : Finset (Fin m)) => (0 : ℝ))
- Source
- folklore
- 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 every natural number $m$, the constant zero function on the subsets of $\mathrm{Fin}(m)$ (mapping every $S \in \mathrm{Finset}(\mathrm{Fin}(m))$ to $0 \in \mathbb{R}$) is a matroid rank valuation (it evaluates to 0 on the empty set, is submodular, and has binary marginals).
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 a set function that vanishes on the empty set, is submodular, and has binary marginal gains (every element contributes either 0 or 1). For the constant zero function, all values are zero, so it trivially vanishes at the empty set, its marginal gains are everywhere zero (which satisfies submodularity since $0 \le 0$), and each marginal gain is 0 (satisfying the binary marginal condition $0 \in \{0, 1\}$). Expanding these three definitions reduces the claim to trivial identities that the simplifier closes immediately.
The constant zero set function is a matroid-rank valuation.
Unfolding the definitions of a matroid-rank valuation (`is_matroid_rank_valuation`), submodularity (`is_submodular`), and binary marginals (`has_binary_marginals`) reduces the theorem to three conditions on the constant zero function: (1) evaluating at the empty set yields $0 = 0$; (2) submodularity requires $0 - 0 \le 0 - 0$ (i.e., $0 \le 0$) for all sets and elements; and (3) binary marginals require $0 = 0 \lor 0 = 0 + 1$ for all sets and elements, which holds since $0 = 0$. The simplifier expands these definitions and closes the resulting trivial arithmetic goals.
uses
is_matroid_rank_valuation,is_submodular,has_binary_marginalssimp [is_matroid_rank_valuation, is_submodular, has_binary_marginals]
is_matroid_rank_valuation- A set function $v$ is a matroid-rank valuation if $v(\emptyset) = 0$, $v$ is submodular, and $v$ has binary marginals.
is_submodular- A set function $v$ is submodular if for all $S \subseteq T$ and $j \notin T$, the marginal gain $v(T \cup \{j\}) - v(T)$ is at most $v(S \cup \{j\}) - v(S)$.
has_binary_marginals- A set function $v$ has binary marginals if for all $S$ and $j \notin S$, adding $j$ increases the value by either $0$ or $1$, i.e., $v(S \cup \{j\}) = v(S)$ or $v(S \cup \{j\}) = v(S) + 1$.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The zero valuation is a matroid-rank valuation. -/theorem zero_is_matroid_rank_valuation (m : ℕ) : is_matroid_rank_valuation (fun (_ : Finset (Fin m)) => (0 : ℝ)) := by simp [is_matroid_rank_valuation, is_submodular, has_binary_marginals]