Proof of `Exact rational certificates exist for all linear-programming outcomes`
groundedproofs/Lax109476Proofs/CertificateExistence.lean · lax-109476
What this proof establishes
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
Split on real feasibility and boundedness. An infeasible rational system has rational Farkas multipliers by rational elimination. In the bounded feasible case, strong duality makes the combined primal–dual system with equal objectives real feasible; rational feasibility gives a rational matching pair. In the unbounded case, rationalize both a feasible base point and a recession direction normalized to objective increase at least one. No solver theorem or complexity assumption is used.