AFTD Auto-Formalizing Theoretical Domains

OnlineLearning.finiteUpperImage_nonempty

theoremverifiedimported Lean

Nonemptiness of the finite upper image. Let $X, Y \subseteq \bbr$, let $f : \bbr \to \bbr \to \bbr$ be a payoff function, and let $u$ be a finite sample of columns from $Y$. If $X$ is nonempty, then the finite upper image $U(X,f,u)$ is nonempty; that is, there exists a vector $z : u \to \bbr$ for which some $x \in X$ satisfies $f(x,y) < z_y$ for every $y \in u$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Real Finset BigOperators in
lemma OnlineLearning.finiteUpperImage_nonempty {X Y : Set ℝ} {f : ℝ → ℝ → ℝ}
    (hX : X.Nonempty) (u : Finset Y) :
    (finiteUpperImage X f u).Nonempty
Source
TCSlib, `OnlineLearning.finiteUpperImage_nonempty`
Lean proof
By Karim Abdel Sadek, Mark Bedaywi, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Karim Abdel Sadek and Mark Bedaywi. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • OnlineLearning.finiteUpperImageFor sets $X, Y \subseteq \bbr$, a payoff $f : \bbr \to \bbr \to \bbr$, and a finite sample $u$ of columns from $Y$, the finite upper image…
Used by 2

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Real Finset BigOperators in/-- The upper image of a finite column sample is nonempty when `X` is: pick any row and add `1` to each sampled payoff. -/lemma OnlineLearning.finiteUpperImage_nonempty {X Y : Set ℝ} {f : ℝ → ℝ → ℝ}    (hX : X.Nonempty) (u : Finset Y) :    (finiteUpperImage X f u).Nonempty := by  rcases hX with ⟨x, hx⟩  refine ⟨fun y : u => f x y + 1, x, hx, ?_⟩  intro y  linarith
See it in the graphDiscuss this resultChallenge it