EconCSLib.LinearAlgebra.feas_cert_disjoint
theoremverifiedformalizationimported Lean
EconCSLib.LinearAlgebra.feas_cert_disjoint
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 theorem EconCSLib.LinearAlgebra.feas_cert_disjoint {I : Type*} {n : โ} [Fintype I] (A : I โ Fin n โ ๐) (b : I โ ๐) (hfeas : IsFeasible A b) (hcert : HasCertificate A b) : False
- Formalizes
- EconCSLib, `EconCSLib.LinearAlgebra.feas_cert_disjoint`
- 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.EconCSLib.LinearAlgebra.feas_cert_disjoint← EconCSLib.LinearAlgebra.feas_cert_disjoint (EconCSLib/Math/LinearAlgebra/FourierMotzkin.lean:80): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- EconCSLib.LinearAlgebra.HasCertificateExistence of a Farkas certificate.
- EconCSLib.LinearAlgebra.IsFeasiblePrimal feasibility of the system
A x โฅ b. - EconCSLib.LinearAlgebra.rowEvalEvaluate the LHS of row
iof the matrixA : I โ Fin n โ ๐at the pointx : Fin n โ ๐. - EconCSLib.LinearAlgebra.IsCertificate
u : I โ ๐is a Farkas certificate of infeasibility ofA x โฅ b.
- Used by 2
- EconCSLib.LinearAlgebra.theorem_of_alternative_auxEconCSLib.LinearAlgebra.theorem_of_alternative_aux
- EconCSLib.LinearAlgebra.theorem_of_alternative_baseEconCSLib.LinearAlgebra.theorem_of_alternative_base
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Finset BigOperators inset_option linter.unusedSectionVars false invariable {๐ : Type*} [Field ๐] [LinearOrder ๐] [IsStrictOrderedRing ๐] intheorem EconCSLib.LinearAlgebra.feas_cert_disjoint {I : Type*} {n : โ} [Fintype I] (A : I โ Fin n โ ๐) (b : I โ ๐) (hfeas : IsFeasible A b) (hcert : HasCertificate A b) : False := by obtain โจx, hxโฉ := hfeas obtain โจu, hu_nn, hu_zero, hu_posโฉ := hcert -- โจu, bโฉ โค โจu, Axโฉ = โจuแตA, xโฉ = โจ0, xโฉ = 0 < โจu, bโฉ. have hweighted : โ i, u i * b i โค โ i, u i * rowEval A i x := by apply Finset.sum_le_sum intro i _ exact mul_le_mul_of_nonneg_left (hx i) (hu_nn i) have hzero : โ i, u i * rowEval A i x = 0 := by have h1 : โ i, u i * rowEval A i x = โ i, โ j, u i * (A i j * x j) := by simp only [rowEval, Finset.mul_sum] have h2 : (โ i, โ j, u i * (A i j * x j)) = โ j, โ i, u i * A i j * x j := by rw [Finset.sum_comm] refine Finset.sum_congr rfl ?_ intro j _ refine Finset.sum_congr rfl ?_ intro i _ ring have h3 : (โ j, โ i, u i * A i j * x j) = โ j, (โ i, u i * A i j) * x j := by refine Finset.sum_congr rfl ?_ intro j _ rw [โ Finset.sum_mul] rw [h1, h2, h3] apply Finset.sum_eq_zero intro j _ rw [hu_zero j, zero_mul] linarith