AFTD Auto-Formalizing Theoretical Domains

cycle_greedy_costs_measurable

theoremverified

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.

  1. 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.

    lines 1–9

    uses MeasurableSpace.measurableSet_top, measurable_to_countable', measurable_from_prod_countable_left

    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)
    
  2. 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.

    lines 10–16

    uses Finset.Nonempty.image, Finset.min'_mem

    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⟩⟩)
    
  3. 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.

    lines 17–37

    uses Finset.min'_mem, Finset.min'_le, Finset.mem_image_of_mem, lt_or_eq_of_le

    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⟩)
  4. 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.

    lines 38–57

    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 hle
    
  5. The 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.

    lines 58–81

    uses measurable_to_countable', cgcm_pick_eq_iff, MeasurableSet.iInter, measurableSet_lt, measurableSet_eq_fun

    theorem 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]
    
  6. 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.

    lines 82–95

    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
  7. 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.

    lines 96–104

    uses measurable_const, measurable_of_countable

      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 _))
  8. 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.

    lines 105–117

    uses cgcm_piecewise, measurable_of_finite, cgcm_pick_measurable, measurable_pi_apply, measurable_const

      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
  9. 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.

    lines 118–131

    uses cgcm_piecewise, cgcm_pick_measurable, measurable_pi_apply, measurableSet_singleton, 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
  10. 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.

    lines 132–166

    uses List.getD_append, List.getD_append_right, Nat.exists_eq_succ_of_ne_zero, 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]
  11. 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.

    lines 167–170

    uses measurable_pi_lambda, MeasurableSet.const, measurable_const

      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
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).

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

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
See it in the graphDiscuss this resultChallenge it