import Determinize.Proof.FiniteModel.Boundaryimport Determinize.Proof.FiniteModel.Pathsnamespace Determinize.Proof.FiniteModelopen Spec.FiniteModel MeasureTheory/-- The value equations of a finite model: a returned state's value is its reward, a rejectedstate's is zero, and a transient state's is the expected value of its successors. They need notdetermine the expected reward. -/def ValueEquations (model : Model) (values : Fin model.size → Rat) : Prop := ∀ state, values state = match model.kind state with | .returned reward => reward | .rejected => 0 | .transient => ∑ next, model.transition state next * values nextinstance (model : Model) (values : Fin model.size → Rat) : Decidable (ValueEquations model values) := inferInstanceAs (Decidable (∀ _, _))/-- Change only the observable assigned to a successful return. -/abbrev rewards (model : Model) (f : Rat → Rat) : Model := {model with kind := fun state ↦ match model.kind state with | .returned r => .returned (f r) | other => other}theorem query_sound (model : Model) (f : Rat → Rat) (g : ℝ → ℝ) (agree : ∀ r : Rat, g (r : ℝ) = (f r : ℝ)) (values : Fin model.size → Rat) (equations : ValueEquations (rewards model f) values) (paths : Paths (rewards model f)) (valid : paths.Valid (rewards model f)) : (∫ x, g x ∂model.outputMeasure) = (values model.initial : ℝ) := by have unique := paths_unique (rewards model f) paths valid (fun state ↦ (∫ x, g x ∂outputAt model state) - (values state : ℝ)) have zero := unique (by intro state rw [outputAt_equations model state g] have eqs := equations state cases h : model.kind state with | returned reward => simp [h] at eqs; simp [h, agree, eqs] | rejected => simp [h] at eqs; simp [h, eqs] | transient => simp only [rewards, h] at eqs ⊢ rw [eqs] simp [Rat.cast_sum, Rat.cast_mul, Finset.sum_sub_distrib, mul_sub]) model.initial exact sub_eq_zero.mp zeroend Determinize.Proof.FiniteModel