Lemma 4.1, p. 156 — atoms within δ of a binary assignment force |x(G) − x⁰(G)| < γ when δL ≤ γ
ProvedJeroslowMLP.Value.lemma_4_1linear-inequalitiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1propositional-logicrobustness
Let be a propositional formula of length and let with . Let be a truth assignment of the atoms, and write , for the binary values of an atom and of under it. Suppose real values of the atoms satisfy
and that the node values solve the system (3.1) of (with each node value in ). Then
The lemma is a robustness property of : near-binary inputs produce an output near the correct truth value. It is what allows player 1 in to be forced to binary choices.
Formalization Note The atom type is arbitrary, the length is the one of the Formula definition (atom , each connective ), and hypothesis (4.9) is required only on the atoms occurring in .
Preamble
import Mathlib import Definitions.Def_JeroslowMLP_Value_Formula
Formal statement
namespace JeroslowMLP.Value
theorem lemma_4_1 {α : Type} (G : Formula α) (δ γ : ℝ) (hδ : 0 < δ) (hγ : 0 < γ)
(hδγ : δ * (G.length : ℝ) ≤ γ) (x₀ : α → Bool) (xa : α → ℝ) (xn : G.Node → ℝ)
(h49 : ∀ a ∈ G.atoms, |xa a - (if x₀ a then 1 else 0)| < δ)
(hsys : G.LSys xa xn) :
|G.nodeVal xa xn - (if G.eval x₀ then 1 else 0)| < γ := by sorry
end JeroslowMLP.Value
Source
Jeroslow, The polynomial hierarchy and a simple model for competitive analysis, Math. Programming 32 (1985), p. 156, Lemma 4.1, (4.9)–(4.10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.