AFTD Auto-Formalizing Theoretical Domains

prioritized_borel_fork_valid_consistent

theoremverified

Every valid hidden block history expands to an edge history consistent with the actual history-dependent p-owned choice function.

Statement

theorem prioritized_borel_fork_valid_consistent (choice : List PrioritizedBorelForkEdge → Bool)
    {u h : List Bool}
    (hv : PrioritizedBorelForkValid
      (fun v k => choice (prioritized_borel_fork_expand v k ++ prioritized_borel_fork_setup)) u h) :
    prioritized_borel_fork_consistent choice [] (prioritized_borel_fork_expand u h)
Source
arXiv:2611.10136, Section 5.3.2; the three-state fork subarena
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 11
Used by 2

The proof, explained

The theorem is proved by induction on the validity hypothesis for the block histories. The base case of empty histories expands to the empty edge sequence, which is vacuously consistent. In each inductive step, expanding the snoc-extended histories yields the prefix expansion followed by a three-step block; consistency decomposes across this concatenation, where the prefix is consistent by the induction hypothesis, and the block is consistent either vacuously (in the stay case) or by matching the choice function at vertex 2 (in the exit case).

  1. The expanded history is consistent in the base case where both block histories are empty.

    The proof proceeds by induction on the derivation of validity `hv`. In the base case `root`, both block histories `u` and `h` are empty lists. Unfolding `prioritized_borel_fork_expand` on empty lists produces the empty edge list, which is vacuously consistent with `choice` by definition of `prioritized_borel_fork_consistent`.

    lines 6–7

      induction hv with
      | root => simp [prioritized_borel_fork_expand, prioritized_borel_fork_consistent]
  2. Consistency is preserved when extending valid histories with a stay block.

    In the `stay` case, the histories are extended to `u ++ [bit]` and `h ++ [false]`. Since valid histories have equal lengths by `prioritized_borel_fork_valid_lengths`, `prioritized_borel_fork_expand_snoc` expands this into the previous expansion followed by a three-step stay block. By `prioritized_borel_fork_consistent_append`, consistency of the concatenated history reduces to consistency of the prefix and consistency of the stay block after simplifying the empty initial prefix with `List.nil_append`. The prefix is consistent by the induction hypothesis `ih`, and the stay block is consistent by `prioritized_borel_fork_stay_consistent` since it never visits vertex 2.

    lines 8–12

    uses prioritized_borel_fork_expand_snoc, prioritized_borel_fork_valid_lengths, prioritized_borel_fork_consistent_append, List.nil_append, prioritized_borel_fork_stay_consistent

      | @stay u h bit hv ih =>
          rw [prioritized_borel_fork_expand_snoc u h (prioritized_borel_fork_valid_lengths hv),
            prioritized_borel_fork_consistent_append]
          simp only [List.nil_append]
          exact ⟨ih, prioritized_borel_fork_stay_consistent choice _ bit⟩
  3. Consistency is preserved when extending valid histories with an exit block.

    In the `exit` case, the histories are extended to `u ++ [color u h]` and `h ++ [true]`, where `color u h` is defined as `choice` applied to the expansion of `(u, h)` followed by the setup edges. Using `prioritized_borel_fork_valid_lengths` and `prioritized_borel_fork_expand_snoc`, the expansion decomposes into the expansion of the prefix followed by a three-step exit block. Decomposing consistency with `prioritized_borel_fork_consistent_append` and simplifying the prefix with `List.nil_append`, the prefix is consistent by `ih`, and the exit block is consistent by `prioritized_borel_fork_exit_consistent` because its direction at vertex 2 is exactly what the choice function requires.

    lines 13–17

    uses prioritized_borel_fork_expand_snoc, prioritized_borel_fork_valid_lengths, prioritized_borel_fork_consistent_append, List.nil_append, prioritized_borel_fork_exit_consistent

      | @exit u h hv ih =>
          rw [prioritized_borel_fork_expand_snoc u h (prioritized_borel_fork_valid_lengths hv),
            prioritized_borel_fork_consistent_append]
          simp only [List.nil_append]
          exact ⟨ih, prioritized_borel_fork_exit_consistent choice _⟩
prioritized_borel_fork_expand_snoc
Appending elements to equal-length block histories expands to the expansion of the prefixes concatenated with the three-step block corresponding to the new elements.
prioritized_borel_fork_valid_lengths
Any valid pair of block histories has equal lengths.
prioritized_borel_fork_consistent_append
A sequence of edges is consistent after a given prefix if and only if its first part is consistent after the prefix and its second part is consistent after the prefix extended by the first part.
List.nil_append
Prepending an empty list to any list leaves the list unchanged.
prioritized_borel_fork_stay_consistent
A three-step stay block is consistent after any prefix, because none of its edges originate at vertex 2.
prioritized_borel_fork_exit_consistent
A three-step exit block is consistent when its decision bit at vertex 2 matches the value of the choice function on the prefix extended by the setup edges.

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 prioritized_borel_fork_valid_consistent (choice : List PrioritizedBorelForkEdge → Bool)    {u h : List Bool}    (hv : PrioritizedBorelForkValid      (fun v k => choice (prioritized_borel_fork_expand v k ++ prioritized_borel_fork_setup)) u h) :    prioritized_borel_fork_consistent choice [] (prioritized_borel_fork_expand u h) := by  induction hv with  | root => simp [prioritized_borel_fork_expand, prioritized_borel_fork_consistent]  | @stay u h bit hv ih =>      rw [prioritized_borel_fork_expand_snoc u h (prioritized_borel_fork_valid_lengths hv),        prioritized_borel_fork_consistent_append]      simp only [List.nil_append]      exact ⟨ih, prioritized_borel_fork_stay_consistent choice _ bit⟩  | @exit u h hv ih =>      rw [prioritized_borel_fork_expand_snoc u h (prioritized_borel_fork_valid_lengths hv),        prioritized_borel_fork_consistent_append]      simp only [List.nil_append]      exact ⟨ih, prioritized_borel_fork_exit_consistent choice _⟩
See it in the graphDiscuss this resultChallenge it