AFTD Auto-Formalizing Theoretical Domains

all_cube_func_one_is_submodular

theoremverified

On the 1-dimensional Boolean hypercube, every function f : {0, 1}^1 → {0, ..., k} is submodular.

Statement

theorem all_cube_func_one_is_submodular (k : ℕ) (f : CubeFunc 1 k) :
    is_submodular_cube f
Source
arXiv:2611.02374, Sec. 2
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • CubeFuncThe type of functions from the n-dimensional Boolean hypercube {0, 1}^n into {0, 1, ..., k}, represented by Fin (k + 1).
  • is_submodular_cubeA function f from the Boolean hypercube to {0, ..., k} is submodular if f(x ∨ y) + f(x ∧ y) ≤ f(x) + f(y) for all x, y in {0, 1}^n when…

Read back from the Lean

For every natural number $k$ and every function $f : (\mathrm{Fin}\ 1 \to \mathrm{Bool}) \to \mathrm{Fin}(k + 1)$, $f$ is a submodular cube function (is_submodular_cube f).

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

The proof proceeds by case analysis on the relative order of the single coordinates of any two vertices x, y in {0, 1}¹. Because the hypercube has dimension 1, its elements are totally ordered: either x ≤ y or y ≤ x. In either case, the two vertices are comparable, so their join and meet are simply the vertices themselves in some order (that is, {x ⊔ y, x ⊓ y} = {x, y}). The submodularity inequality f(x ⊔ y) + f(x ⊓ y) ≤ f(x) + f(y) then reduces to an equality f(x) + f(y) = f(x) + f(y), which holds trivially.

  1. To prove f is submodular, it suffices to consider arbitrary vertices x, y ∈ {0, 1}¹, which satisfy either x(0) ≤ y(0) or y(0) ≤ x(0).

    Unfolding the definition of submodularity introduces two arbitrary hypercube vertices x and y. Because `Bool` is linearly ordered, its values at the coordinate 0 are comparable by totality (`le_total`), giving two cases: x(0) ≤ y(0) or y(0) ≤ x(0).

    lines 4–5

    uses le_total

      intro x y
      rcases le_total (x 0) (y 0) with h | h
  2. The submodularity inequality holds in the case where x(0) ≤ y(0).

    Because the index set Fin 1 has a unique element (any index i equals 0 by `Subsingleton.elim`), x(0) ≤ y(0) implies x ≤ y coordinatewise. For comparable elements with x ≤ y, their join is y (`sup_eq_right.mpr`) and their meet is x (`inf_eq_left.mpr`). Rewriting the submodularity goal with these equalities gives f(y) + f(x) ≤ f(x) + f(y), which holds by commutativity of real addition.

    lines 6–11

    uses Subsingleton.elim, sup_eq_right.mpr, inf_eq_left.mpr

      · have hle : x ≤ y := by
          intro i
          rw [Subsingleton.elim i 0]
          exact h
        rw [sup_eq_right.mpr hle, inf_eq_left.mpr hle]
        linarith
  3. The submodularity inequality holds in the case where y(0) ≤ x(0).

    Symmetrically, since any index i in Fin 1 equals 0 (`Subsingleton.elim`), y(0) ≤ x(0) implies y ≤ x coordinatewise. Hence the join x ⊔ y is x (`sup_eq_left.mpr`) and the meet x ⊓ y is y (`inf_eq_right.mpr`). Rewriting with these identities simplifies the inequality to f(x) + f(y) ≤ f(x) + f(y), which holds identically by reflexivity.

    lines 12–16

    uses Subsingleton.elim, sup_eq_left.mpr, inf_eq_right.mpr

      · have hle : y ≤ x := by
          intro i
          rw [Subsingleton.elim i 0]
          exact h
        rw [sup_eq_left.mpr hle, inf_eq_right.mpr hle]
le_total
Any two elements in a linear order are comparable: a ≤ b or b ≤ a.
Subsingleton.elim
Any two elements of a subsingleton type (a type with at most one element) are equal.
sup_eq_right.mpr
If a ≤ b, then the least upper bound (join) a ⊔ b equals b.
inf_eq_left.mpr
If a ≤ b, then the greatest lower bound (meet) a ⊓ b equals a.
sup_eq_left.mpr
If b ≤ a, then the least upper bound (join) a ⊔ b equals a.
inf_eq_right.mpr
If b ≤ a, then the greatest lower bound (meet) a ⊓ b equals b.

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

/-- Every function on the 1-dimensional Boolean hypercube is submodular. -/theorem all_cube_func_one_is_submodular (k : ℕ) (f : CubeFunc 1 k) :    is_submodular_cube f := by  intro x y  rcases le_total (x 0) (y 0) with h | h  · have hle : x ≤ y := by      intro i      rw [Subsingleton.elim i 0]      exact h    rw [sup_eq_right.mpr hle, inf_eq_left.mpr hle]    linarith  · have hle : y ≤ x := by      intro i      rw [Subsingleton.elim i 0]      exact h    rw [sup_eq_left.mpr hle, inf_eq_right.mpr hle]
See it in the graphDiscuss this resultChallenge it