AFTD Auto-Formalizing Theoretical Domains

EconCSLib.LinearAlgebra.feasible_of_fm_feasible

theoremverifiedformalizationimported Lean

EconCSLib.LinearAlgebra.feasible_of_fm_feasible

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Finset BigOperators in
set_option linter.unusedSectionVars false in
variable {π•œ : Type*} [Field π•œ] [LinearOrder π•œ] [IsStrictOrderedRing π•œ] in
variable {I : Type*} [Fintype I] [DecidableEq I] {n : β„•} in
theorem EconCSLib.LinearAlgebra.feasible_of_fm_feasible (A : I β†’ Fin (n+1) β†’ π•œ) (b : I β†’ π•œ)
    (hred : IsFeasible (fmA A) (fmB A b)) : IsFeasible A b
Formalizes
EconCSLib, `EconCSLib.LinearAlgebra.feasible_of_fm_feasible`
Lean proof
By xbei (from the file's git history), from github.com/gametheoryinlean/EconCSLib at 1a88f809b538 (Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 14
Used by 1

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Finset BigOperators inset_option linter.unusedSectionVars false invariable {π•œ : Type*} [Field π•œ] [LinearOrder π•œ] [IsStrictOrderedRing π•œ] invariable {I : Type*} [Fintype I] [DecidableEq I] {n : β„•} intheorem EconCSLib.LinearAlgebra.feasible_of_fm_feasible (A : I β†’ Fin (n+1) β†’ π•œ) (b : I β†’ π•œ)    (hred : IsFeasible (fmA A) (fmB A b)) : IsFeasible A b := by  obtain ⟨x', hx'⟩ := hred  classical  -- Per-row lower/upper bounds (defined on subtypes).  let L : PosRows A β†’ π•œ := fun p =>    (b p.val - βˆ‘ j : Fin n, A p.val j.castSucc * x' j) / A p.val (Fin.last n)  let U : NegRows A β†’ π•œ := fun q =>    (b q.val - βˆ‘ j : Fin n, A q.val j.castSucc * x' j) / A q.val (Fin.last n)  -- Choose x_last by case-split on emptiness of PosRows / NegRows.  let x_last : π•œ :=    if hPos : (Finset.univ : Finset (PosRows A)).Nonempty then      Finset.univ.sup' hPos L    else if hNeg : (Finset.univ : Finset (NegRows A)).Nonempty then      Finset.univ.inf' hNeg U    else (0 : π•œ)  refine ⟨Fin.snoc x' x_last, ?_⟩  intro i  -- Decompose original row evaluation: first n + last entry.  have hsplit : rowEval A i (Fin.snoc x' x_last)      = (βˆ‘ j : Fin n, A i j.castSucc * x' j)        + A i (Fin.last n) * x_last := by    rw [rowEval_def, Fin.sum_univ_castSucc]    simp [Fin.snoc_castSucc, Fin.snoc_last]  rcases lt_trichotomy (A i (Fin.last n)) 0 with hlt | heq | hgt  Β· -- Negative last-column coefficient: i ∈ NegRows.    let hiN : NegRows A := ⟨i, hlt⟩    have hUbound : x_last ≀ U hiN := by      by_cases hPos : (Finset.univ : Finset (PosRows A)).Nonempty      Β· -- x_last = sup' L; need sup' L ≀ U(hiN), i.e., βˆ€ p, L p ≀ U hiN.        change (if h : _ then Finset.univ.sup' h L                else if h' : _ then Finset.univ.inf' h' U else 0) ≀ U hiN        rw [dif_pos hPos]        apply Finset.sup'_le        intro p _        exact reduced_pair_ineq hx' p hiN      Β· -- x_last = inf' U (NegRows nonempty since hiN exists).        have hNeg : (Finset.univ : Finset (NegRows A)).Nonempty :=          ⟨hiN, Finset.mem_univ _⟩        change (if h : _ then Finset.univ.sup' h L                else if h' : _ then Finset.univ.inf' h' U else 0) ≀ U hiN        rw [dif_neg hPos, dif_pos hNeg]        exact Finset.inf'_le _ (Finset.mem_univ hiN)    have hUval : A i (Fin.last n) * U hiN        = b i - βˆ‘ j : Fin n, A i j.castSucc * x' j := by      show A i (Fin.last n)          * ((b i - βˆ‘ j : Fin n, A i j.castSucc * x' j) / A i (Fin.last n)) = _      have : A i (Fin.last n) β‰  0 := ne_of_lt hlt      field_simp    have hmul : A i (Fin.last n) * U hiN ≀ A i (Fin.last n) * x_last :=      mul_le_mul_of_nonpos_left hUbound hlt.le    rw [hsplit]    linarith  Β· -- Zero last-column coefficient: i ∈ ZeroRows.    let hiZ : ZeroRows A := ⟨i, heq⟩    have h := hx' (Sum.inl hiZ)    simp only [fmB_inl, rowEval_def, fmA_inl] at h    rw [hsplit, heq, zero_mul, add_zero]    exact h  Β· -- Positive last-column coefficient: i ∈ PosRows.    let hiP : PosRows A := ⟨i, hgt⟩    have hPos : (Finset.univ : Finset (PosRows A)).Nonempty :=      ⟨hiP, Finset.mem_univ _⟩    have hLbound : L hiP ≀ x_last := by      change L hiP ≀ (if h : _ then Finset.univ.sup' h L                       else if h' : _ then Finset.univ.inf' h' U else 0)      rw [dif_pos hPos]      exact Finset.le_sup' _ (Finset.mem_univ hiP)    have hLval : A i (Fin.last n) * L hiP        = b i - βˆ‘ j : Fin n, A i j.castSucc * x' j := by      show A i (Fin.last n)          * ((b i - βˆ‘ j : Fin n, A i j.castSucc * x' j) / A i (Fin.last n)) = _      have : A i (Fin.last n) β‰  0 := ne_of_gt hgt      field_simp    have hmul : A i (Fin.last n) * L hiP ≀ A i (Fin.last n) * x_last :=      mul_le_mul_of_nonneg_left hLbound hgt.le    rw [hsplit]    linarith
See it in the graphDiscuss this resultChallenge it