AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_eventual_hidden_shadow

theoremverified

Compatible finite histories whose hidden-choice records eventually do not increase and whose extensions add no hidden choices eventually form one nested history.

Statement

theorem prioritized_borel_eventual_hidden_shadow {A : Type} [LinearOrder (List A)]
    [WellFoundedLT (List A)] (vis : A → Bool) (own : List A → Bool)
    (hidden : List A → Bool → Bool) (policy : List A → A)
    (forced : List A → Bool → A) (histories : ℕ → List A) (actual : ℕ → A)
    (N : ℕ)
    (hcompat : ∀ n, op1385HiddenCompatible vis own hidden policy forced [] (histories n))
    (hdir : ∀ n, (histories (n+1)).map vis = (histories n).map vis ++ [vis (actual n)])
    (hext : ∀ n ≥ N, op1385HiddenCompatible vis own hidden policy forced []
      (histories n ++ [actual n]))
    (hrecord : ∀ n ≥ N, op1385HiddenRecord vis own hidden [] (histories n ++ [actual n]) =
      op1385HiddenRecord vis own hidden [] (histories n))
    (hstep : ∀ n ≥ N, op1385HiddenRecord vis own hidden [] (histories (n+1)) ≤
      op1385HiddenRecord vis own hidden [] (histories n)) :
    ∃ K ≥ N, ∀ n ≥ K, histories (n+1) = histories n ++ [actual n]
Source
Hidden-choice strategy compression related to arXiv:2611.10136, Conjecture 19.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 2

The proof, explained

The theorem shows that an eventually non-increasing sequence of compatible histories whose extensions add no hidden choices eventually becomes a nested history chain. To prove this, each history is assigned a rank given by its record of hidden choices; because the order on records is well-founded and the ranks are eventually non-increasing, the rank sequence stabilizes past some index K ≥ N. For all n ≥ K, the next history histories(n + 1) and the candidate extension histories(n) ++ [actual n] have the exact same visible observations and the exact same hidden record. Since execution replay uniquely reconstructs compatible histories from visible observations and hidden choices, this commonality forces the two histories to coincide.

  1. The empty execution is correctly replayed from the empty observation and empty hidden record. automation

    For the base case xs = [], the hidden record and visible observation sequences are both empty. Replaying on an empty visible sequence immediately returns the initial history and empty record, matching the claim by definition.

    lines 49–50

    uses op1385HiddenRecord, op1385HiddenReplay

      induction xs generalizing hist with
      | nil => simp [op1385HiddenRecord, op1385HiddenReplay]
  2. Any compatible execution step is correctly replayed, inductively recovering the full history.

    In the inductive step for a :: xs, we analyze whether the history is owned (own hist) and whether the visible signal is hidden (hidden hist (vis a)). If owned, the single-step rule forces a = policy hist, and replay follows the policy without consuming from the record. If not owned and hidden, a is pushed to the hidden record, and replay consumes a from the head of the record. If not owned and unhidden, the step forces a = forced hist (vis a), which replay reproduces from the visible observation alone. In all branches, applying the induction hypothesis to hist ++ [a] recovers the remaining history.

    lines 51–67

    uses op1385HiddenCompatible, op1385HiddenStep, op1385HiddenRecord, op1385HiddenReplay, List.append_assoc

      | cons a xs ih =>
        simp only [op1385HiddenCompatible] at h
        cases ho : own hist <;> cases hb : hidden hist (vis a)
        · have ha' : a = forced hist (vis a) := by simpa [op1385HiddenStep, ho, hb] using h.1
          have ha : forced hist (vis a) = a := ha'.symm
          simpa [op1385HiddenRecord, op1385HiddenReplay, ho, hb, ha, List.append_assoc] using
            ih (hist ++ [a]) h.2
        · simpa [op1385HiddenRecord, op1385HiddenReplay, ho, hb, List.append_assoc] using
            ih (hist ++ [a]) h.2
        · have ha : a = policy hist := by simpa [op1385HiddenStep, ho, hb] using h.1
          subst a
          simpa [op1385HiddenRecord, op1385HiddenReplay, ho, hb, List.append_assoc] using
            ih (hist ++ [policy hist]) h.2
        · have ha : a = policy hist := by simpa [op1385HiddenStep, ho, hb] using h.1
          subst a
          simpa [op1385HiddenRecord, op1385HiddenReplay, ho, hb, List.append_assoc] using
            ih (hist ++ [policy hist]) h.2
  3. Compatible executions with identical visible observations and identical hidden records are equal.

    Replaying both compatible sequences xs and ys with their common visible traces and hidden records yields some (hist ++ xs, []) and some (hist ++ ys, []). Equating these two outputs gives hist ++ xs = hist ++ ys, from which left cancellation of hist gives xs = ys.

    lines 77–81

    uses op1385_hidden_replay_recovers, congrArg, Prod.fst, Option.some.inj, List.append_cancel_left

      have hx' := op1385_hidden_replay_recovers vis own hidden policy forced hist xs hx
      have hy' := op1385_hidden_replay_recovers vis own hidden policy forced hist ys hy
      rw [hvis, hrecord] at hx'
      have h := hx'.symm.trans hy'
      exact List.append_cancel_left (congrArg Prod.fst (Option.some.inj h))
  4. Compatibility of an extended sequence xs ++ [a] is equivalent to compatibility of xs followed by a valid step for a. automation

    Proved by induction on xs. The base case follows directly from the definition of op1385HiddenCompatible. For the inductive step x :: xs, expanding the definition, rewriting with the inductive hypothesis, and reassociating conjunctions closes the equivalence.

    lines 89–93

    uses op1385HiddenCompatible, List.append_assoc, and_assoc

      induction xs generalizing hist with
      | nil => simp [op1385HiddenCompatible]
      | cons x xs ih =>
        simp [op1385HiddenCompatible, ih, List.append_assoc, and_assoc]
    
  5. The hidden record of an extended sequence xs ++ [a] appends [a] if and only if the final step was an unforced hidden choice. automation

    Proved by induction on xs. The base case holds by definition. For the inductive step x :: xs, case analysis on whether the head step was an unforced hidden choice followed by simplification and associativity of list append closes the goal.

    lines 99–103

    uses op1385HiddenRecord, List.append_assoc

      induction xs generalizing hist with
      | nil => simp [op1385HiddenRecord]
      | cons x xs ih =>
        cases hb : (!own hist && hidden hist (vis x)) <;>
          simp [op1385HiddenRecord, hb, ih, List.append_assoc]
  6. The shifted sequence f(n) = r(N + n) is antitone on all of ℕ.

    Because r is non-increasing past N, we have r(N + n + 1) ≤ r(N + n) for all n ≥ 0. By antitone_nat_of_succ_le, an ordering between every consecutive pair implies that the shifted sequence f is antitone.

    lines 109–114

    uses antitone_nat_of_succ_le, Nat.add_assoc

      let f : ℕ → α := fun n => r (N+n)
      have hmono : Antitone f := by
        apply antitone_nat_of_succ_le
        intro n
        have h := hstep (N+n) (by omega)
        simpa [f, Nat.add_assoc] using h
  7. An eventually antitone sequence in a well-founded partial order eventually stabilizes.

    By the antitone chain condition for well-founded orders (WellFoundedLT.antitone_chain_condition), the antitone sequence f stabilizes at some K, meaning f(m) = f(K) for all m ≥ K. Setting the cutoff to N + K ≥ N, for any n ≥ N + K we have n - N ≥ K, so r(n) = f(n - N) = f(K) = r(N + K).

    lines 115–122

    uses WellFoundedLT.antitone_chain_condition, Nat.add_sub_of_le

      obtain ⟨K, hK⟩ := WellFoundedLT.antitone_chain_condition hmono
      refine ⟨N+K, by omega, ?_⟩
      intro n hn
      have hstart : N ≤ n := by omega
      have hi : K ≤ n-N := by omega
      have h := hK (n-N) hi
      change r (N+K) = r (N+(n-N)) at h
      simpa only [Nat.add_sub_of_le hstart] using h.symm
  8. The hidden records rank n = op1385HiddenRecord [] (histories n) eventually stabilize at some K ≥ N.

    The rank sequence is non-increasing for n ≥ N by hypothesis hstep. Since the order on List A is well-founded, the stabilization lemma op1385_eventually_antitone_well_order_stabilizes yields an index K ≥ N such that rank n = rank K for all n ≥ K.

    lines 138–142

    uses op1385_eventually_antitone_well_order_stabilizes, le_trans

      let rank : ℕ → List A := fun n => op1385HiddenRecord vis own hidden [] (histories n)
      obtain ⟨K, hKN, hstable⟩ := op1385_eventually_antitone_well_order_stabilizes rank N hstep
      refine ⟨K, hKN, ?_⟩
      intro n hn
      have hnN : N ≤ n := le_trans hKN hn
  9. For all n ≥ K, histories (n + 1) and histories n ++ [actual n] have identical hidden records.

    By hypothesis hrecord, appending actual n does not change the hidden record of histories n for n ≥ N. Since n ≥ K ≥ N, stabilization gives rank (n + 1) = rank K = rank n, so the hidden record of histories (n + 1) equals that of histories n ++ [actual n].

    lines 143–146

      have hrec : op1385HiddenRecord vis own hidden [] (histories (n+1)) =
          op1385HiddenRecord vis own hidden [] (histories n ++ [actual n]) := by
        rw [hrecord n hnN]
        exact (hstable (n+1) (by omega)).trans (hstable n hn).symm
  10. For all n ≥ K, histories (n + 1) = histories n ++ [actual n].

    Both histories (n + 1) and histories n ++ [actual n] are compatible executions extending the empty history. Their visible traces coincide by hdir, and their hidden records coincide by the previous step. Injectivity of the hidden record (op1385_hidden_record_injective) implies they are identical.

    lines 147–150

    uses op1385_hidden_record_injective

      apply op1385_hidden_record_injective vis own hidden policy forced []
        (histories (n+1)) (histories n ++ [actual n]) (hcompat (n+1)) (hext n hnN)
      · simpa using hdir n
      · exact hrec
op1385HiddenRecord
Extracts the list of actions corresponding to unowned, hidden choice steps in an execution sequence.
op1385HiddenReplay
Deterministically reconstructs an execution from an initial history, a sequence of visible observations, and a record of hidden choices.
op1385HiddenCompatible
States that a sequence of actions is valid starting from a given history, with each action satisfying the single-step rules.
op1385HiddenStep
Defines a valid single action from a history: governed by policy if owned, unconstrained if hidden, or forced by the visible signal otherwise.
List.append_assoc
List concatenation is associative: (as ++ bs) ++ cs = as ++ (bs ++ cs).
op1385_hidden_replay_recovers
Replaying a compatible execution using its visible trace and hidden record successfully reconstructs the complete history and completely consumes the record.
Option.some.inj
The some constructor of Option is injective: some x = some y implies x = y.
congrArg
Applying a function to equal arguments yields equal values: x = y implies f(x) = f(y).
Prod.fst
The first projection of a pair: Prod.fst (a, b) = a.
List.append_cancel_left
Left cancellation for list concatenation: as ++ bs = as ++ cs implies bs = cs.
and_assoc
Conjunction is associative: (a ∧ b) ∧ c ↔ a ∧ b ∧ c.
antitone_nat_of_succ_le
A function on ℕ is antitone (order-reversing) if f(n + 1) ≤ f(n) for every n.
Nat.add_assoc
Addition of natural numbers is associative: (n + m) + k = n + (m + k).
WellFoundedLT.antitone_chain_condition
Every antitone sequence in a well-founded partially ordered set eventually stabilizes.
Nat.add_sub_of_le
For natural numbers with a ≤ b, a + (b - a) = b.
op1385_eventually_antitone_well_order_stabilizes
Any sequence in a well-founded partial order that is non-increasing beyond an index N eventually becomes constant at some K ≥ N.
le_trans
Transitivity of the order relation: a ≤ b and b ≤ c imply a ≤ c.
op1385_hidden_record_injective
Two compatible executions that produce identical visible sequences and identical hidden records are equal.

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

def op1385HiddenStep {A : Type} (vis : A → Bool) (own : List A → Bool)    (hidden : List A → Bool → Bool) (policy : List A → A)    (forced : List A → Bool → A) (hist : List A) (a : A) : Prop :=  if own hist then a = policy hist  else if hidden hist (vis a) then True else a = forced hist (vis a)def op1385HiddenCompatible {A : Type} (vis : A → Bool) (own : List A → Bool)    (hidden : List A → Bool → Bool) (policy : List A → A)    (forced : List A → Bool → A) : List A → List A → Prop  | _, [] => True  | hist, a :: rest =>    op1385HiddenStep vis own hidden policy forced hist a ∧      op1385HiddenCompatible vis own hidden policy forced (hist ++ [a]) restdef op1385HiddenRecord {A : Type} (vis : A → Bool) (own : List A → Bool)    (hidden : List A → Bool → Bool) : List A → List A → List A  | _, [] => []  | hist, a :: rest =>    if !own hist && hidden hist (vis a) then      a :: op1385HiddenRecord vis own hidden (hist ++ [a]) rest    else op1385HiddenRecord vis own hidden (hist ++ [a]) restdef op1385HiddenReplay {A : Type} (vis : A → Bool) (own : List A → Bool)    (hidden : List A → Bool → Bool) (policy : List A → A)    (forced : List A → Bool → A) : List A → List Bool → List A → Option (List A × List A)  | hist, [], record => some (hist, record)  | hist, b :: bs, record =>    if own hist then      let a := policy hist      if vis a = b then op1385HiddenReplay vis own hidden policy forced (hist ++ [a]) bs record      else none    else if hidden hist b then      match record with      | [] => none      | a :: tail =>        if vis a = b then op1385HiddenReplay vis own hidden policy forced (hist ++ [a]) bs tail        else none    else      let a := forced hist b      if vis a = b then op1385HiddenReplay vis own hidden policy forced (hist ++ [a]) bs record      else nonetheorem op1385_hidden_replay_recovers {A : Type} (vis : A → Bool) (own : List A → Bool)    (hidden : List A → Bool → Bool) (policy : List A → A)    (forced : List A → Bool → A) (hist xs : List A)    (h : op1385HiddenCompatible vis own hidden policy forced hist xs) :    op1385HiddenReplay vis own hidden policy forced hist (xs.map vis)      (op1385HiddenRecord vis own hidden hist xs) = some (hist ++ xs, []) := by  induction xs generalizing hist with  | nil => simp [op1385HiddenRecord, op1385HiddenReplay]  | cons a xs ih =>    simp only [op1385HiddenCompatible] at h    cases ho : own hist <;> cases hb : hidden hist (vis a)    · have ha' : a = forced hist (vis a) := by simpa [op1385HiddenStep, ho, hb] using h.1      have ha : forced hist (vis a) = a := ha'.symm      simpa [op1385HiddenRecord, op1385HiddenReplay, ho, hb, ha, List.append_assoc] using        ih (hist ++ [a]) h.2    · simpa [op1385HiddenRecord, op1385HiddenReplay, ho, hb, List.append_assoc] using        ih (hist ++ [a]) h.2    · have ha : a = policy hist := by simpa [op1385HiddenStep, ho, hb] using h.1      subst a      simpa [op1385HiddenRecord, op1385HiddenReplay, ho, hb, List.append_assoc] using        ih (hist ++ [policy hist]) h.2    · have ha : a = policy hist := by simpa [op1385HiddenStep, ho, hb] using h.1      subst a      simpa [op1385HiddenRecord, op1385HiddenReplay, ho, hb, List.append_assoc] using        ih (hist ++ [policy hist]) h.2theorem op1385_hidden_record_injective {A : Type} (vis : A → Bool) (own : List A → Bool)    (hidden : List A → Bool → Bool) (policy : List A → A)    (forced : List A → Bool → A) (hist xs ys : List A)    (hx : op1385HiddenCompatible vis own hidden policy forced hist xs)    (hy : op1385HiddenCompatible vis own hidden policy forced hist ys)    (hvis : xs.map vis = ys.map vis)    (hrecord : op1385HiddenRecord vis own hidden hist xs =      op1385HiddenRecord vis own hidden hist ys) : xs = ys := by  have hx' := op1385_hidden_replay_recovers vis own hidden policy forced hist xs hx  have hy' := op1385_hidden_replay_recovers vis own hidden policy forced hist ys hy  rw [hvis, hrecord] at hx'  have h := hx'.symm.trans hy'  exact List.append_cancel_left (congrArg Prod.fst (Option.some.inj h))theorem op1385_hidden_compatible_snoc {A : Type} (vis : A → Bool) (own : List A → Bool)    (hidden : List A → Bool → Bool) (policy : List A → A)    (forced : List A → Bool → A) (hist xs : List A) (a : A) :    op1385HiddenCompatible vis own hidden policy forced hist (xs ++ [a]) ↔      op1385HiddenCompatible vis own hidden policy forced hist xs ∧      op1385HiddenStep vis own hidden policy forced (hist ++ xs) a := by  induction xs generalizing hist with  | nil => simp [op1385HiddenCompatible]  | cons x xs ih =>    simp [op1385HiddenCompatible, ih, List.append_assoc, and_assoc]theorem op1385_hidden_record_snoc {A : Type} (vis : A → Bool) (own : List A → Bool)    (hidden : List A → Bool → Bool) (hist xs : List A) (a : A) :    op1385HiddenRecord vis own hidden hist (xs ++ [a]) =      op1385HiddenRecord vis own hidden hist xs ++        (if !own (hist ++ xs) && hidden (hist ++ xs) (vis a) then [a] else []) := by  induction xs generalizing hist with  | nil => simp [op1385HiddenRecord]  | cons x xs ih =>    cases hb : (!own hist && hidden hist (vis x)) <;>      simp [op1385HiddenRecord, hb, ih, List.append_assoc]theorem op1385_eventually_antitone_well_order_stabilizes    {α : Type} [PartialOrder α] [WellFoundedLT α] (r : ℕ → α) (N : ℕ)    (hstep : ∀ n ≥ N, r (n+1) ≤ r n) :    ∃ K ≥ N, ∀ n ≥ K, r n = r K := by  let f : ℕ → α := fun n => r (N+n)  have hmono : Antitone f := by    apply antitone_nat_of_succ_le    intro n    have h := hstep (N+n) (by omega)    simpa [f, Nat.add_assoc] using h  obtain ⟨K, hK⟩ := WellFoundedLT.antitone_chain_condition hmono  refine ⟨N+K, by omega, ?_⟩  intro n hn  have hstart : N ≤ n := by omega  have hi : K ≤ n-N := by omega  have h := hK (n-N) hi  change r (N+K) = r (N+(n-N)) at h  simpa only [Nat.add_sub_of_le hstart] using h.symmtheorem prioritized_borel_eventual_hidden_shadow {A : Type} [LinearOrder (List A)]    [WellFoundedLT (List A)] (vis : A → Bool) (own : List A → Bool)    (hidden : List A → Bool → Bool) (policy : List A → A)    (forced : List A → Bool → A) (histories : ℕ → List A) (actual : ℕ → A)    (N : ℕ)    (hcompat : ∀ n, op1385HiddenCompatible vis own hidden policy forced [] (histories n))    (hdir : ∀ n, (histories (n+1)).map vis = (histories n).map vis ++ [vis (actual n)])    (hext : ∀ n ≥ N, op1385HiddenCompatible vis own hidden policy forced []      (histories n ++ [actual n]))    (hrecord : ∀ n ≥ N, op1385HiddenRecord vis own hidden [] (histories n ++ [actual n]) =      op1385HiddenRecord vis own hidden [] (histories n))    (hstep : ∀ n ≥ N, op1385HiddenRecord vis own hidden [] (histories (n+1)) ≤      op1385HiddenRecord vis own hidden [] (histories n)) :    ∃ K ≥ N, ∀ n ≥ K, histories (n+1) = histories n ++ [actual n] := by  let rank : ℕ → List A := fun n => op1385HiddenRecord vis own hidden [] (histories n)  obtain ⟨K, hKN, hstable⟩ := op1385_eventually_antitone_well_order_stabilizes rank N hstep  refine ⟨K, hKN, ?_⟩  intro n hn  have hnN : N ≤ n := le_trans hKN hn  have hrec : op1385HiddenRecord vis own hidden [] (histories (n+1)) =      op1385HiddenRecord vis own hidden [] (histories n ++ [actual n]) := by    rw [hrecord n hnN]    exact (hstable (n+1) (by omega)).trans (hstable n hn).symm  apply op1385_hidden_record_injective vis own hidden policy forced []    (histories (n+1)) (histories n ++ [actual n]) (hcompat (n+1)) (hext n hnN)  · simpa using hdir n  · exact hrec
See it in the graphDiscuss this resultChallenge it