AFTD Auto-Formalizing Theoretical Domains

k_submod_kernel_proj

theoremverified

The coordinate projection function (fun x _ => x) : ℝ → ℝ → ℝ satisfies is_k_submod_kernel.

Statement

theorem k_submod_kernel_proj : is_k_submod_kernel (fun x _ => x)
Source
arXiv:2610.26677, Lemma 2.1
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_k_submod_kernelA two-variable kernel H : ℝ → ℝ → ℝ satisfies the hidden-label conditions if H(0,0) = 0, H(1,0) > 0, H(x,y) ≤ H(1,0) on [0,1]², H is…
Used by 1
  • c1_k_submod_kernel_projThe first coordinate projection function (fun x _ => x) : ℝ → ℝ → ℝ satisfies is_c1_k_submod_kernel.

Read back from the Lean

The function $H : \mathbb{R} \to \mathbb{R} \to \mathbb{R}$ defined by $H(x, y) = x$ (the projection onto the first argument) satisfies is_k_submod_kernel.

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 coordinate projection function $H(x, y) = x$ is shown to be a $k$-submodular kernel by directly verifying the seven conditions in the definition. Normalization at the origin, strict positivity at $(1, 0)$, boundedness by $H(1, 0)$, and monotonicity in both arguments are either trivial equalities or follow immediately from domain hypotheses and order reflexivity. The two derivative inequalities reduce to $1 \le 1$ and $0 \le 0$, respectively, because the derivative of the identity is identically $1$ and the derivative of a constant is identically $0$.

  1. The definition of `is_k_submod_kernel` expands to seven conditions for the projection function $H(x, y) = x$.

    We simplify the definition of a $k$-submodular kernel applied to $H(x, y) = x$. This reduces the goal to proving seven properties: $0 = 0$, $0 < 1$, $x \le 1$ for all $x \in [0, 1]$, $x_1 \le x_2$ whenever $x_1 \le x_2$, $x \le x$, and two inequalities on partial derivatives.

    line 3

      dsimp [is_k_submod_kernel]
  2. The first five conditions (normalization, positivity, upper bound by $H(1, 0)$, and monotonicity in each argument) hold.

    The equality $0 = 0$ holds by reflexivity (`rfl`). Strict positivity $0 < 1$ is given by `zero_lt_one`. The upper bound $x \le 1$ and monotonicity in the first coordinate $x_1 \le x_2$ follow directly from the corresponding hypotheses on the domain. Monotonicity in the second coordinate $x \le x$ holds by reflexivity of the order (`le_rfl`).

    lines 4–5

    uses zero_lt_one, le_rfl

      refine ⟨rfl, zero_lt_one, fun _ _ _ hx1 _ _ => hx1, fun _ _ _ _ hx12 _ _ _ => hx12,
        fun _ _ _ _ _ _ _ _ => le_rfl,
  3. The derivative inequality with respect to the first argument holds: $\frac{\partial H}{\partial x}(x_2, y_2) \le \frac{\partial H}{\partial x}(x_1, y_1)$.

    For $H(t, y) = t$, the derivative with respect to $t$ is identically $1$ everywhere by `deriv_id''`. The required inequality thus simplifies to $1 \le 1$, which holds by reflexivity (`le_refl`).

    line 6

    uses deriv_id'', le_refl

        fun _ _ _ _ _ _ _ _ _ _ => by simp only [deriv_id'', le_refl],
  4. The derivative inequality with respect to the second argument holds: $\frac{\partial H}{\partial y}(x_2, y_2) \le \frac{\partial H}{\partial y}(x_1, y_1)$.

    For $H(x, t) = x$, which is constant with respect to $t$, the derivative is identically $0$ everywhere by `deriv_const`. The required inequality simplifies to $0 \le 0$, which holds by reflexivity (`le_refl`).

    line 7

    uses deriv_const, le_refl

        fun _ _ _ _ _ _ _ _ _ _ => by simp only [deriv_const, le_refl]⟩
zero_lt_one
In any ordered structure with zero and nonzero one, zero is strictly less than one ($0 < 1$).
le_rfl
The preorder relation $\le$ is reflexive: $a \le a$ for any element $a$.
le_refl
The preorder relation $\le$ is reflexive: $a \le a$ for any element $a$.
deriv_id''
The derivative of the identity function $t \mapsto t$ is the constant function $1$.
deriv_const
The derivative of a constant function at any point is $0$.

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

/-- The coordinate projection function satisfies the kernel conditions. -/theorem k_submod_kernel_proj : is_k_submod_kernel (fun x _ => x) := by  dsimp [is_k_submod_kernel]  refine ⟨rfl, zero_lt_one, fun _ _ _ hx1 _ _ => hx1, fun _ _ _ _ hx12 _ _ _ => hx12,    fun _ _ _ _ _ _ _ _ => le_rfl,    fun _ _ _ _ _ _ _ _ _ _ => by simp only [deriv_id'', le_refl],    fun _ _ _ _ _ _ _ _ _ _ => by simp only [deriv_const, le_refl]⟩
See it in the graphDiscuss this resultChallenge it