EconCSLib.LinearAlgebra.theorem_of_alternative_base
theoremverifiedformalizationimported Lean
EconCSLib.LinearAlgebra.theorem_of_alternative_base
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.theorem_of_alternative_base {I : Type*} [Fintype I] [DecidableEq I] (A : I β Fin 0 β π) (b : I β π) : Β¬ IsFeasible A b β HasCertificate A b
- Formalizes
- EconCSLib, `EconCSLib.LinearAlgebra.theorem_of_alternative_base`
- 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.theorem_of_alternative_base← EconCSLib.LinearAlgebra.theorem_of_alternative_base (EconCSLib/Math/LinearAlgebra/FourierMotzkin.lean:537): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- EconCSLib.LinearAlgebra.HasCertificateExistence of a Farkas certificate.
- EconCSLib.LinearAlgebra.IsFeasiblePrimal feasibility of the system
A x β₯ b. - EconCSLib.LinearAlgebra.rowEval_defEconCSLib.LinearAlgebra.rowEval_def
- EconCSLib.LinearAlgebra.feas_cert_disjointEconCSLib.LinearAlgebra.feas_cert_disjoint
- 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 1
- EconCSLib.LinearAlgebra.theorem_of_alternative_auxEconCSLib.LinearAlgebra.theorem_of_alternative_aux
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 π] invariable {I : Type*} [Fintype I] [DecidableEq I] {n : β} intheorem EconCSLib.LinearAlgebra.theorem_of_alternative_base {I : Type*} [Fintype I] [DecidableEq I] (A : I β Fin 0 β π) (b : I β π) : Β¬ IsFeasible A b β HasCertificate A b := by classical refine β¨?_, fun hcert hfeas => feas_cert_disjoint A b hfeas hcertβ© intro hinf -- `IsFeasible β β i, b i β€ 0`; the negation provides an index with `0 < b i`. have h_pick : β i : I, 0 < b i := by by_contra hall push Not at hall apply hinf refine β¨fun j : Fin 0 => Fin.elim0 j, fun i => ?_β© have h_row_zero : rowEval A i (fun j : Fin 0 => Fin.elim0 j) = 0 := by unfold rowEval apply Finset.sum_eq_zero intro j _ exact Fin.elim0 j rw [h_row_zero] exact hall i obtain β¨iβ, hiββ© := h_pick refine β¨fun i => if iβ = i then 1 else 0, ?_, ?_, ?_β© Β· intro i show 0 β€ if iβ = i then (1 : π) else 0 split_ifs <;> norm_num Β· intro j; exact Fin.elim0 j Β· -- β i, (if iβ = i then 1 else 0) * b i = b iβ > 0 show 0 < β i, (if iβ = i then (1 : π) else 0) * b i simp only [ite_mul, one_mul, zero_mul, Fintype.sum_ite_eq] exact hiβ