cycle_greedy_costs_measurable
For every n, the vector of sequential nearest-free greedy costs is a Borel measurable function of the arrival vector.
Statement
theorem cycle_greedy_costs_measurable (n : ℕ) : Measurable (cycle_greedy_costs n)- Source
- Measurability of the process used in OP-894.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- cycle_greedy_costsGiven n facilities placed at integers 0, ..., n-1 on the circle ℝ/nℤ and an arrival sequence x in Fin n -> Real arriving in sequential…
The proof, explained
The sequential nearest-free greedy costs are computed by sequentially processing arrival points, choosing at each step the nearest available index (with index-order tie-breaking) and recording the circular distance. The proof shows that this process is measurable by viewing it as folding a step transition over the arrivals list. First, the circular distance and the tie-breaking choice function are shown to be measurable on each step. Then, using a piecewise measurability lemma on finite partitions, each step preserves the measurability of the remaining free set fibers and the accumulated costs. An induction on the list of arrivals establishes that every entry in the final cost list is a measurable function of the input arrivals.
A piecewise-defined function subordinate to a finite measurable partition is measurable if each piece is measurable.
Equipping the finite partition index type T with the discrete measurable space makes all subsets measurable, so the selector s : X → T is measurable. The composite function x ↦ h(s(x), x) is the composition of the product map x ↦ (x, s(x)) and the slice-measurable map (x, t) ↦ h(t, x), both of which are measurable.
uses
MeasurableSpace.measurableSet_top,measurable_to_countable',measurable_from_prod_countable_lefttheorem cgcm_piecewise {X T Y : Type} [MeasurableSpace X] [MeasurableSpace Y] [Finite T] {s : X → T} (hs : ∀ t, MeasurableSet {x | s x = t}) {h : T → X → Y} (hh : ∀ t, Measurable (h t)) : Measurable fun x => h (s x) x := by let _ : MeasurableSpace T := ⊤ have : MeasurableSingletonClass T := ⟨fun _ => MeasurableSpace.measurableSet_top⟩ have hsm : Measurable s := measurable_to_countable' fun t => hs t exact (measurable_from_prod_countable_left (f := fun p : X × T => h p.2 p.1) hh).comp (measurable_id.prodMk hsm)
The greedy tie-breaking choice function cgcm_pick is well-defined on any nonempty subset of indices.
Given a nonempty finset of available indices and a cost function f, the set of costs achieves a minimum value in ℝ. The preimage of this minimum within the free set is nonempty, so taking its minimum in the linear order of Fin n uniquely specifies a chosen index.
uses
Finset.Nonempty.image,Finset.min'_memnoncomputable def cgcm_pick {n : ℕ} (free : Finset (Fin n)) (h : free.Nonempty) (f : Fin n → ℝ) : Fin n := (free.filter (fun j => f j = (free.image f).min' (Finset.Nonempty.image h _))).min' (by have hmem := Finset.min'_mem (free.image f) (Finset.Nonempty.image h _) rcases Finset.mem_image.mp hmem with ⟨j, hj, heq⟩ exact ⟨j, Finset.mem_filter.mpr ⟨hj, heq⟩⟩)
If cgcm_pick selects an index j, then j is free and minimizes f with tie-breaking by index order.
By definition, the chosen index j minimizes the index among all free elements achieving the minimum cost m. Thus j is in the free set, and for any other free index j', either f(j') > m = f(j), or f(j') = m = f(j) and j ≤ j' by minimality of j in the tie set.
uses
Finset.min'_mem,Finset.min'_le,Finset.mem_image_of_mem,lt_or_eq_of_letheorem cgcm_pick_eq_iff {n : ℕ} (free : Finset (Fin n)) (h : free.Nonempty) (f : Fin n → ℝ) (j : Fin n) : cgcm_pick free h f = j ↔ j ∈ free ∧ ∀ j' ∈ free, f j < f j' ∨ (f j = f j' ∧ j ≤ j') := by unfold cgcm_pick set m := (free.image f).min' (Finset.Nonempty.image h _) with hm constructor · intro hj have hmem := Finset.min'_mem (free.filter (fun j => f j = m)) (by have hmem := Finset.min'_mem (free.image f) (Finset.Nonempty.image h _) rcases Finset.mem_image.mp hmem with ⟨j, hj, heq⟩ exact ⟨j, Finset.mem_filter.mpr ⟨hj, heq⟩⟩) rw [hj] at hmem obtain ⟨hjf, hjm⟩ := Finset.mem_filter.mp hmem refine ⟨hjf, fun j' hj' => ?_⟩ have hle : m ≤ f j' := Finset.min'_le _ _ (Finset.mem_image_of_mem f hj') rcases lt_or_eq_of_le hle with hlt | heq · left; rw [hjm]; exact hlt · right refine ⟨by rw [hjm, heq], ?_⟩ rw [← hj] exact Finset.min'_le _ _ (Finset.mem_filter.mpr ⟨hj', heq.symm⟩)
Conversely, any free index j satisfying the minimal cost and tie-breaking conditions equals cgcm_pick.
If j is free and satisfies the conditions against all other free elements, antisymmetry implies its cost f(j) equals the minimum cost m. Furthermore, any element y achieving cost m cannot have f(j) < f(y), so the condition forces j ≤ y. Therefore j is the minimum index among all minimizers of f.
uses
le_antisymm,Finset.min'_mem,Finset.min'_le,Finset.mem_image_of_mem,Finset.le_min',lt_irrefl· rintro ⟨hjf, hall⟩ have hjm : f j = m := by apply le_antisymm · have hmem := Finset.min'_mem (free.image f) (Finset.Nonempty.image h _) rcases Finset.mem_image.mp hmem with ⟨j0, hj0, heq⟩ rw [← hm] at heq rw [← heq] rcases hall j0 hj0 with hlt | ⟨heq', _⟩ · exact hlt.le · exact heq'.le · exact Finset.min'_le _ _ (Finset.mem_image_of_mem f hjf) apply le_antisymm · exact Finset.min'_le _ _ (Finset.mem_filter.mpr ⟨hjf, hjm⟩) · apply Finset.le_min' intro y hy obtain ⟨hyf, hym⟩ := Finset.mem_filter.mp hy rcases hall y hyf with hlt | ⟨_, hle⟩ · rw [hjm, hym] at hlt; exact absurd hlt (lt_irrefl _) · exact hleThe greedy choice cgcm_pick is a measurable function of the arrival parameter when each cost function is measurable.
Because Fin n is finite, measurability reduces to showing that the preimage of each singleton {j} is measurable. By the exact characterization of cgcm_pick, this preimage is an intersection over j' : Fin n of conditions involving strict inequalities or equalities of measurable real functions, which are measurable sets.
uses
measurable_to_countable',cgcm_pick_eq_iff,MeasurableSet.iInter,measurableSet_lt,measurableSet_eq_funtheorem cgcm_pick_measurable {n : ℕ} (free : Finset (Fin n)) (h : free.Nonempty) (D : ℝ → Fin n → ℝ) (hD : ∀ j, Measurable fun a => D a j) : Measurable fun a => cgcm_pick free h (D a) := by apply measurable_to_countable' intro j change MeasurableSet {a | cgcm_pick free h (D a) = j} simp only [cgcm_pick_eq_iff] by_cases hj : j ∈ free · simp only [hj, true_and] have : {a | ∀ j' ∈ free, D a j < D a j' ∨ (D a j = D a j' ∧ j ≤ j')} = ⋂ j' : Fin n, {a | j' ∈ free → D a j < D a j' ∨ (D a j = D a j' ∧ j ≤ j')} := by ext a; simp rw [this] refine MeasurableSet.iInter fun j' => ?_ by_cases hj' : j' ∈ free · simp only [hj', true_implies] by_cases hle : j ≤ j' · simp only [hle, and_true] exact (measurableSet_lt (hD j) (hD j')).union (measurableSet_eq_fun (hD j) (hD j')) · simp only [hle, and_false, or_false] exact measurableSet_lt (hD j) (hD j') · simp [hj'] · simp [hj]
The cyclic greedy cost function is represented as folding a step transition G over the arrivals list.
We introduce local definitions for the circular distance D(a, j), the single-step state transition ST (which selects the nearest available target and removes it from the free set), and the accumulator step G (which appends the new cost and updates the free set). The function cycle_greedy_costs n is definitionally equal to folding G over List.finRange n starting with empty costs and all indices free.
theorem cycle_greedy_costs_measurable (n : ℕ) : Measurable (cycle_greedy_costs n) := by let D : ℝ → Fin n → ℝ := fun a j => if n = 0 then 0 else let d := a - (j.val : ℝ) let k : ℝ := ((⌊d / (n : ℝ) + 1 / 2⌋ : ℤ) : ℝ) |d - (n : ℝ) * k| let ST : Finset (Fin n) → ℝ → ℝ × Finset (Fin n) := fun τ a => if h : τ.Nonempty then (D a (cgcm_pick τ h (D a)), τ.erase (cgcm_pick τ h (D a))) else (0, τ) let G : (Fin n → ℝ) → (List ℝ × Finset (Fin n)) → Fin n → (List ℝ × Finset (Fin n)) := fun x acc i => (acc.1 ++ [(ST acc.2 (x i)).1], (ST acc.2 (x i)).2) have hdef : cycle_greedy_costs n = fun x i => ((List.finRange n).foldl (G x) ([], Finset.univ)).1.getD i.val 0 := rfl
The circular distance function a ↦ D(a, j) is measurable for every target j.
When n = 0, D is constant 0, hence measurable. When n > 0, D(a, j) = |(a - j) - n ⌊(a - j)/n + 1/2⌋|. The floor term is measurable because the floor maps measurably to ℤ and ℤ embeds countably into ℝ; taking linear combinations and the absolute value preserves measurability.
uses
measurable_const,measurable_of_countablehave hD : ∀ j, Measurable fun a => D a j := by intro j by_cases hn : n = 0 · simp only [D, hn, if_true]; exact measurable_const · simp only [D, hn, if_false] have h1 : Measurable fun a : ℝ => ((⌊(a - (j.val : ℝ)) / (n : ℝ) + 1 / 2⌋ : ℤ) : ℝ) := (measurable_of_countable (fun z : ℤ => (z : ℝ))).comp (((measurable_id.sub_const _).div_const _).add_const _).floor exact continuous_abs.measurable.comp ((measurable_id.sub_const _).sub (h1.const_mul _))
A single step of the algorithm preserves measurability of the fibers of the remaining free set.
Given an accumulator function F whose free set component has measurable fibers, we apply cgcm_piecewise on the finite collection of possible free sets τ. If τ is nonempty, the new free set is obtained by erasing the greedy pick; since erasing is a function from the finite type Fin n and the greedy pick is measurable by cgcm_pick_measurable, the resulting free set fiber is measurable.
uses
cgcm_piecewise,measurable_of_finite,cgcm_pick_measurable,measurable_pi_apply,measurable_consthave hfib : ∀ (F : (Fin n → ℝ) → List ℝ × Finset (Fin n)) (i : Fin n), (∀ σ, MeasurableSet {x | (F x).2 = σ}) → ∀ σ, MeasurableSet {x | (G x (F x) i).2 = σ} := by intro F i hF σ apply measurableSet_setOfPred.mpr refine cgcm_piecewise (s := fun x => (F x).2) hF (h := fun τ x => (ST τ (x i)).2 = σ) (fun τ => ?_) by_cases hτ : τ.Nonempty · simp only [ST, dif_pos hτ] exact (measurable_of_finite (fun j : Fin n => τ.erase j = σ)).comp ((cgcm_pick_measurable τ hτ D hD).comp (measurable_pi_apply i)) · simp only [ST, dif_neg hτ] exact measurable_const
The cost incurred at each step is a measurable function of the arrival vector.
Conditioning on the current free set τ via cgcm_piecewise, when τ is nonempty the cost is D(x(i), j) evaluated at the chosen index j = cgcm_pick τ h (D(x(i))). Conditioning again on j via cgcm_piecewise over the finite set Fin n, for each fixed j the map x ↦ D(x(i), j) is measurable by composing D(·, j) with the coordinate projection.
uses
cgcm_piecewise,cgcm_pick_measurable,measurable_pi_apply,measurableSet_singleton,measurable_consthave hcost : ∀ (F : (Fin n → ℝ) → List ℝ × Finset (Fin n)) (i : Fin n), (∀ σ, MeasurableSet {x | (F x).2 = σ}) → Measurable fun x => (ST (F x).2 (x i)).1 := by intro F i hF refine cgcm_piecewise (s := fun x => (F x).2) hF (h := fun τ x => (ST τ (x i)).1) (fun τ => ?_) by_cases hτ : τ.Nonempty · simp only [ST, dif_pos hτ] have hp := (cgcm_pick_measurable τ hτ D hD).comp (measurable_pi_apply (X := fun _ : Fin n => ℝ) i) exact cgcm_piecewise (s := fun x : Fin n → ℝ => cgcm_pick τ hτ (D (x i))) (fun t => hp (measurableSet_singleton t)) (h := fun j x => D (x i) j) (fun j => (hD j).comp (measurable_pi_apply i)) · simp only [ST, dif_neg hτ] exact measurable_const
By induction on a list of arrivals L, folding G preserves measurability of all accumulated cost entries.
For the empty list, the costs are unchanged and measurable by assumption. For a cons step i :: L, the free set fibers remain measurable by hfib. Appending the step cost yields a list of constant length whose j-th entry is either an existing entry (if j < m), the new step cost (if j = m, measurable by hcost), or 0 (if j > m). Since all cases are measurable, the inductive hypothesis applies to the rest of the list.
uses
List.getD_append,List.getD_append_right,Nat.exists_eq_succ_of_ne_zero,measurable_consthave key : ∀ (L : List (Fin n)) (F : (Fin n → ℝ) → List ℝ × Finset (Fin n)), (∀ σ, MeasurableSet {x | (F x).2 = σ}) → (∀ j, Measurable fun x => (F x).1.getD j 0) → (∀ x y, (F x).1.length = (F y).1.length) → ∀ j, Measurable fun x => (L.foldl (G x) (F x)).1.getD j 0 := by intro L induction L with | nil => intro F _ hget _ j; exact hget j | cons i L ih => intro F hF hget hlen simp only [List.foldl_cons] apply ih (fun x => G x (F x) i) (hfib F i hF) · intro j let m := (F 0).1.length have hc := hcost F i hF have heq : ∀ x, (G x (F x) i).1.getD j 0 = if j < m then (F x).1.getD j 0 else if j = m then (ST (F x).2 (x i)).1 else 0 := by intro x have hl : (F x).1.length = m := hlen x 0 simp only [G] split_ifs with h1 h2 · rw [List.getD_append _ _ _ _ (by omega)] · rw [List.getD_append_right _ _ _ _ (by omega)] simp [h2, hl] · rw [List.getD_append_right _ _ _ _ (by omega)] have : j - (F x).1.length ≠ 0 := by omega obtain ⟨k, hk⟩ := Nat.exists_eq_succ_of_ne_zero this simp [hk] simp only [heq] split_ifs · exact hget j · exact hc · exact measurable_const · intro x y simp [G, hlen x y]
The full vector cycle_greedy_costs n is measurable.
A vector-valued function is measurable if each coordinate is measurable (measurable_pi_lambda). Rewriting by the fold definition and applying the induction lemma key to the list of all indices List.finRange n with the initial state ([], Finset.univ), all base conditions hold trivially, completing the proof.
uses
measurable_pi_lambda,MeasurableSet.const,measurable_constrw [hdef] exact measurable_pi_lambda _ fun i => key (List.finRange n) (fun _ => ([], Finset.univ)) (fun σ => MeasurableSet.const _) (fun j => measurable_const) (fun _ _ => rfl) i.val
MeasurableSpace.measurableSet_top- In the discrete measurable space, every subset is measurable.
measurable_to_countable'- A function into a countable space is measurable if the preimage of every singleton is measurable.
measurable_from_prod_countable_left- A function on a product space X × T with T countable and discrete is measurable if each slice x ↦ f(x, t) is measurable.
Finset.Nonempty.image- The image of a nonempty finite set under any function is nonempty.
Finset.min'_mem- The minimum element of a nonempty finite linear order belongs to the set.
Finset.min'_le- The minimum element of a finite set is less than or equal to any element in the set.
Finset.mem_image_of_mem- If an element belongs to a finite set, its image under f belongs to the image set.
lt_or_eq_of_le- If a ≤ b, then either a < b or a = b.
le_antisymm- If a ≤ b and b ≤ a, then a = b.
Finset.le_min'- If x is a lower bound for a nonempty finite set, then x is less than or equal to its minimum element.
lt_irrefl- Strict inequality is irreflexive: no element is strictly less than itself.
cgcm_pick_eq_iff- The greedy choice function returns j if and only if j is in the free set and is minimal under the lexicographic order comparing cost and then index.
MeasurableSet.iInter- A countable intersection of measurable sets is measurable.
measurableSet_lt- The set where one measurable real function is strictly less than another is measurable.
measurableSet_eq_fun- The set where two measurable functions are equal is measurable.
measurable_const- Any constant function is measurable.
measurable_of_countable- Any function from a countable discrete measurable space is measurable.
cgcm_piecewise- A function defined piecewise according to a measurable partition with finitely many pieces is measurable if each piece is measurable.
measurable_of_finite- Any function from a finite discrete measurable space is measurable.
cgcm_pick_measurable- If the cost function to each target is measurable, then the index chosen by the nearest-free tie-breaking rule is measurable.
measurable_pi_apply- The evaluation map at a point in a product space is measurable.
measurableSet_singleton- In a space with measurable singletons, every singleton set is measurable.
List.getD_append- The n-th element of an appended list l ++ l' equals the n-th element of l when n < l.length.
List.getD_append_right- The n-th element of an appended list l ++ l' equals the (n - l.length)-th element of l' when n ≥ l.length.
Nat.exists_eq_succ_of_ne_zero- Every non-zero natural number is the successor of some natural number.
measurable_pi_lambda- A function into a product space is measurable if each of its coordinate projections is measurable.
MeasurableSet.const- A constant predicate defines a measurable set (either the whole space or the empty set).
- The inductive step in the list traversal (lines 147–160) relies on automated integer arithmetic (`omega`) to verify cases when accessing entries of the concatenated list.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
theorem cgcm_piecewise {X T Y : Type} [MeasurableSpace X] [MeasurableSpace Y] [Finite T] {s : X → T} (hs : ∀ t, MeasurableSet {x | s x = t}) {h : T → X → Y} (hh : ∀ t, Measurable (h t)) : Measurable fun x => h (s x) x := by let _ : MeasurableSpace T := ⊤ have : MeasurableSingletonClass T := ⟨fun _ => MeasurableSpace.measurableSet_top⟩ have hsm : Measurable s := measurable_to_countable' fun t => hs t exact (measurable_from_prod_countable_left (f := fun p : X × T => h p.2 p.1) hh).comp (measurable_id.prodMk hsm)noncomputable def cgcm_pick {n : ℕ} (free : Finset (Fin n)) (h : free.Nonempty) (f : Fin n → ℝ) : Fin n := (free.filter (fun j => f j = (free.image f).min' (Finset.Nonempty.image h _))).min' (by have hmem := Finset.min'_mem (free.image f) (Finset.Nonempty.image h _) rcases Finset.mem_image.mp hmem with ⟨j, hj, heq⟩ exact ⟨j, Finset.mem_filter.mpr ⟨hj, heq⟩⟩)theorem cgcm_pick_eq_iff {n : ℕ} (free : Finset (Fin n)) (h : free.Nonempty) (f : Fin n → ℝ) (j : Fin n) : cgcm_pick free h f = j ↔ j ∈ free ∧ ∀ j' ∈ free, f j < f j' ∨ (f j = f j' ∧ j ≤ j') := by unfold cgcm_pick set m := (free.image f).min' (Finset.Nonempty.image h _) with hm constructor · intro hj have hmem := Finset.min'_mem (free.filter (fun j => f j = m)) (by have hmem := Finset.min'_mem (free.image f) (Finset.Nonempty.image h _) rcases Finset.mem_image.mp hmem with ⟨j, hj, heq⟩ exact ⟨j, Finset.mem_filter.mpr ⟨hj, heq⟩⟩) rw [hj] at hmem obtain ⟨hjf, hjm⟩ := Finset.mem_filter.mp hmem refine ⟨hjf, fun j' hj' => ?_⟩ have hle : m ≤ f j' := Finset.min'_le _ _ (Finset.mem_image_of_mem f hj') rcases lt_or_eq_of_le hle with hlt | heq · left; rw [hjm]; exact hlt · right refine ⟨by rw [hjm, heq], ?_⟩ rw [← hj] exact Finset.min'_le _ _ (Finset.mem_filter.mpr ⟨hj', heq.symm⟩) · rintro ⟨hjf, hall⟩ have hjm : f j = m := by apply le_antisymm · have hmem := Finset.min'_mem (free.image f) (Finset.Nonempty.image h _) rcases Finset.mem_image.mp hmem with ⟨j0, hj0, heq⟩ rw [← hm] at heq rw [← heq] rcases hall j0 hj0 with hlt | ⟨heq', _⟩ · exact hlt.le · exact heq'.le · exact Finset.min'_le _ _ (Finset.mem_image_of_mem f hjf) apply le_antisymm · exact Finset.min'_le _ _ (Finset.mem_filter.mpr ⟨hjf, hjm⟩) · apply Finset.le_min' intro y hy obtain ⟨hyf, hym⟩ := Finset.mem_filter.mp hy rcases hall y hyf with hlt | ⟨_, hle⟩ · rw [hjm, hym] at hlt; exact absurd hlt (lt_irrefl _) · exact hletheorem cgcm_pick_measurable {n : ℕ} (free : Finset (Fin n)) (h : free.Nonempty) (D : ℝ → Fin n → ℝ) (hD : ∀ j, Measurable fun a => D a j) : Measurable fun a => cgcm_pick free h (D a) := by apply measurable_to_countable' intro j change MeasurableSet {a | cgcm_pick free h (D a) = j} simp only [cgcm_pick_eq_iff] by_cases hj : j ∈ free · simp only [hj, true_and] have : {a | ∀ j' ∈ free, D a j < D a j' ∨ (D a j = D a j' ∧ j ≤ j')} = ⋂ j' : Fin n, {a | j' ∈ free → D a j < D a j' ∨ (D a j = D a j' ∧ j ≤ j')} := by ext a; simp rw [this] refine MeasurableSet.iInter fun j' => ?_ by_cases hj' : j' ∈ free · simp only [hj', true_implies] by_cases hle : j ≤ j' · simp only [hle, and_true] exact (measurableSet_lt (hD j) (hD j')).union (measurableSet_eq_fun (hD j) (hD j')) · simp only [hle, and_false, or_false] exact measurableSet_lt (hD j) (hD j') · simp [hj'] · simp [hj]theorem cycle_greedy_costs_measurable (n : ℕ) : Measurable (cycle_greedy_costs n) := by let D : ℝ → Fin n → ℝ := fun a j => if n = 0 then 0 else let d := a - (j.val : ℝ) let k : ℝ := ((⌊d / (n : ℝ) + 1 / 2⌋ : ℤ) : ℝ) |d - (n : ℝ) * k| let ST : Finset (Fin n) → ℝ → ℝ × Finset (Fin n) := fun τ a => if h : τ.Nonempty then (D a (cgcm_pick τ h (D a)), τ.erase (cgcm_pick τ h (D a))) else (0, τ) let G : (Fin n → ℝ) → (List ℝ × Finset (Fin n)) → Fin n → (List ℝ × Finset (Fin n)) := fun x acc i => (acc.1 ++ [(ST acc.2 (x i)).1], (ST acc.2 (x i)).2) have hdef : cycle_greedy_costs n = fun x i => ((List.finRange n).foldl (G x) ([], Finset.univ)).1.getD i.val 0 := rfl have hD : ∀ j, Measurable fun a => D a j := by intro j by_cases hn : n = 0 · simp only [D, hn, if_true]; exact measurable_const · simp only [D, hn, if_false] have h1 : Measurable fun a : ℝ => ((⌊(a - (j.val : ℝ)) / (n : ℝ) + 1 / 2⌋ : ℤ) : ℝ) := (measurable_of_countable (fun z : ℤ => (z : ℝ))).comp (((measurable_id.sub_const _).div_const _).add_const _).floor exact continuous_abs.measurable.comp ((measurable_id.sub_const _).sub (h1.const_mul _)) have hfib : ∀ (F : (Fin n → ℝ) → List ℝ × Finset (Fin n)) (i : Fin n), (∀ σ, MeasurableSet {x | (F x).2 = σ}) → ∀ σ, MeasurableSet {x | (G x (F x) i).2 = σ} := by intro F i hF σ apply measurableSet_setOfPred.mpr refine cgcm_piecewise (s := fun x => (F x).2) hF (h := fun τ x => (ST τ (x i)).2 = σ) (fun τ => ?_) by_cases hτ : τ.Nonempty · simp only [ST, dif_pos hτ] exact (measurable_of_finite (fun j : Fin n => τ.erase j = σ)).comp ((cgcm_pick_measurable τ hτ D hD).comp (measurable_pi_apply i)) · simp only [ST, dif_neg hτ] exact measurable_const have hcost : ∀ (F : (Fin n → ℝ) → List ℝ × Finset (Fin n)) (i : Fin n), (∀ σ, MeasurableSet {x | (F x).2 = σ}) → Measurable fun x => (ST (F x).2 (x i)).1 := by intro F i hF refine cgcm_piecewise (s := fun x => (F x).2) hF (h := fun τ x => (ST τ (x i)).1) (fun τ => ?_) by_cases hτ : τ.Nonempty · simp only [ST, dif_pos hτ] have hp := (cgcm_pick_measurable τ hτ D hD).comp (measurable_pi_apply (X := fun _ : Fin n => ℝ) i) exact cgcm_piecewise (s := fun x : Fin n → ℝ => cgcm_pick τ hτ (D (x i))) (fun t => hp (measurableSet_singleton t)) (h := fun j x => D (x i) j) (fun j => (hD j).comp (measurable_pi_apply i)) · simp only [ST, dif_neg hτ] exact measurable_const have key : ∀ (L : List (Fin n)) (F : (Fin n → ℝ) → List ℝ × Finset (Fin n)), (∀ σ, MeasurableSet {x | (F x).2 = σ}) → (∀ j, Measurable fun x => (F x).1.getD j 0) → (∀ x y, (F x).1.length = (F y).1.length) → ∀ j, Measurable fun x => (L.foldl (G x) (F x)).1.getD j 0 := by intro L induction L with | nil => intro F _ hget _ j; exact hget j | cons i L ih => intro F hF hget hlen simp only [List.foldl_cons] apply ih (fun x => G x (F x) i) (hfib F i hF) · intro j let m := (F 0).1.length have hc := hcost F i hF have heq : ∀ x, (G x (F x) i).1.getD j 0 = if j < m then (F x).1.getD j 0 else if j = m then (ST (F x).2 (x i)).1 else 0 := by intro x have hl : (F x).1.length = m := hlen x 0 simp only [G] split_ifs with h1 h2 · rw [List.getD_append _ _ _ _ (by omega)] · rw [List.getD_append_right _ _ _ _ (by omega)] simp [h2, hl] · rw [List.getD_append_right _ _ _ _ (by omega)] have : j - (F x).1.length ≠ 0 := by omega obtain ⟨k, hk⟩ := Nat.exists_eq_succ_of_ne_zero this simp [hk] simp only [heq] split_ifs · exact hget j · exact hc · exact measurable_const · intro x y simp [G, hlen x y] rw [hdef] exact measurable_pi_lambda _ fun i => key (List.finRange n) (fun _ => ([], Finset.univ)) (fun σ => MeasurableSet.const _) (fun j => measurable_const) (fun _ _ => rfl) i.val