Adaptive Boolean read transcripts depend only on earlier seed levels
ProvedKServer.binary_read_trace_nonanticipationLet be any index type for Boolean seeds, and assign each coordinate a natural-number level . An adaptive program starts with an all-false transcript. At step , it chooses a seed coordinate as a function of and the current transcript, reads that coordinate, and records the resulting bit at transcript position .
Suppose that for every and every possible transcript ,
For any , if two seed assignments agree on all coordinates of level below , then their transcripts after reads agree:
This deterministic causality statement supplies freshness for sequential random sampling: changing a coordinate at the current or a later level cannot alter the already produced transcript. It requires no probability distribution, finiteness of the seed index type, or positivity assumptions.
Formalization Note Transcript equality means equality as total Boolean-valued functions on natural indices. The statement includes . The level condition is imposed only before the finite horizon.
import Definitions.Def_KServer_binary_read_trace import Lean.Elab.Tactic.Omega set_option autoImplicit false open KServer
theorem KServer.binary_read_trace_nonanticipation {ι : Type*} (grade : ι → ℕ)
(choose : ℕ → (ℕ → Bool) → ι) (N : ℕ)
(hgrade : ∀ n < N, ∀ history : ℕ → Bool, grade (choose n history) = n)
(n : ℕ) (hn : n ≤ N) (seed seed' : ι → Bool)
(hagree : ∀ i, grade i < n → seed i = seed' i) :
binaryReadTrace choose seed n = binaryReadTrace choose seed' n := by sorry