AFTD Auto-Formalizing Theoretical Domains

is_polymatroid_rank

def

A set function f on subsets of Fin n is a polymatroid rank function if it is normalized at the empty set (f ∅ = 0), nondecreasing with respect to inclusion, and submodular.

Statement

def is_polymatroid_rank {n : ℕ} (f : Finset (Fin n) → ℝ) : Prop
Defined in
arXiv:2610.35433:156; Edmonds 1970; Schrijver, Combinatorial Optimization, Section 44.1
Verified
31 Oct 2026
Axioms
none listed
Built on 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 a natural number n and a function f from the finite subsets of Fin n to the real numbers, is_polymatroid_rank f defines the property that: 1. f(∅) = 0; 2. f is monotone (i.e., for all subsets A ⊆ B of Fin n, f(A) ≤ f(B)); and 3. f is submodular (satisfies is_submodular f).

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

Lean source view module on GitHub

/-- A polymatroid rank function is normalized at the empty set, monotone, and submodular. -/
def is_polymatroid_rank {n : ℕ} (f : Finset (Fin n) → ℝ) : Prop := f ∅ = 0 ∧ Monotone f ∧ is_submodular f
See it in the graphDiscuss this resultChallenge it