AFTD Auto-Formalizing Theoretical Domains

boolean_influence_le_one

lemmaverified

For any finite type $U$ with decidable equality, monotone Boolean function $f : (U \to \mathrm{Bool}) \to \mathrm{Bool}$, coordinate $i \in U$, and parameter $p$ in unitInterval, boolean_influence U f i p is at most 1.

Statement

lemma boolean_influence_le_one (U : Type*) [Fintype U] [DecidableEq U]
    (f : (U → Bool) → Bool) (hf : Monotone f) (i : U) (p : unitInterval) :
    boolean_influence U f i p ≤ 1
Source
arXiv:2610.30730 Lemma 2.1
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • boolean_influenceGiven a finite type $U$ with decidable equality, a Boolean function $f : (U \to \mathrm{Bool}) \to \mathrm{Bool}$, coordinate $i \in U$,…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • boolean_product_bernoulliGiven a finite type $U$ and a parameter $p$ in the unit interval unitInterval (the closed interval $[0, 1]$),…
  • boolean_product_bernoulli_isProbabilityMeasureFor any finite type $U$ and parameter $p \in [0, 1]$ in unitInterval, the product Bernoulli measure boolean_product_bernoulli U p on…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1
  • discrete_poincare_monotone_booleanLet $U$ be a finite non-empty type with decidable equality, and let $f : (U \to \mathrm{Bool}) \to \mathrm{Bool}$ be a monotone function.…

Read back from the Lean

For any finite type U with decidable equality, any monotone function f : (U → Bool) → Bool (with respect to the pointwise ordering on U → Bool and the standard order on Bool), any coordinate i : U, and any probability parameter p : unitInterval, the Boolean influence of coordinate i on f with parameter p is at most 1.

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

/-- The influence of any coordinate on a monotone Boolean function is at most 1. -/
lemma boolean_influence_le_one (U : Type*) [Fintype U] [DecidableEq U]
    (f : (U → Bool) → Bool) (hf : Monotone f) (i : U) (p : unitInterval) :
    boolean_influence U f i p ≤ 1 := by
  have hpt : ∀ x : U → Bool,
      (if f (Function.update x i true) then (1:ℝ) else 0) -
        (if f (Function.update x i false) then 1 else 0) ≤ 1 := by
    intro x
    have hle : Function.update x i false ≤ Function.update x i true := by
      intro j
      by_cases h : j = i
      · subst h; simp [Function.update]
      · simp [Function.update, h]
    have hmono : f (Function.update x i false) ≤ f (Function.update x i true) := hf hle
    cases h1 : f (Function.update x i true)
    · have h2 : f (Function.update x i false) = false := by
        have hle' : f (Function.update x i false) ≤ false := by rw [h1] at hmono; exact hmono
        exact le_antisymm hle' (Bool.false_le _)
      simp [h2]
    · cases h2 : f (Function.update x i false)
      · simp
      · simp
  have hint1 : MeasureTheory.Integrable
      (fun x : U → Bool =>
        (if f (Function.update x i true) then (1:ℝ) else 0) -
          (if f (Function.update x i false) then 1 else 0))
      (boolean_product_bernoulli U p) := MeasureTheory.Integrable.of_finite
  have hint2 : MeasureTheory.Integrable (fun _ : U → Bool => (1:ℝ))
      (boolean_product_bernoulli U p) := MeasureTheory.Integrable.of_finite
  have hmono_int := MeasureTheory.integral_mono hint1 hint2 hpt
  have hconst : ∫ (_ : U → Bool), (1:ℝ) ∂boolean_product_bernoulli U p = 1 := by
    rw [MeasureTheory.integral_const]; simp
  unfold boolean_influence
  rw [hconst] at hmono_int
  exact hmono_int
See it in the graphDiscuss this resultChallenge it