Position of an element in a filtered list
ProvedDirKECC1549.Asm.filter_atIf the -th entry of a list satisfies the predicate , then it is the entry of the filtered list at position equal to the number of entries satisfying among the first .
Context. This lemma belongs to the machine-checked word-RAM implementation of Lemma 1 (p.11): Algorithm 1 refining by small -out sets, with the deterministic local search of [GKK+26, Proposition 6] (FindOutPaths and recursive path reversals). The program is written in the structured language Stmt compiled to the published word-RAM; Run E s mem Q states that the statement s, started on mem, reaches its end in a state satisfying Q t mem' within t ticks. The input cells double as registers; they are saved at SV and read through the image ImgAt. All definitions are in the Definitions.Def_DirKECC1549_Impl_* modules.
import Definitions.Def_DirKECC1549_Impl_L1Base
set_option autoImplicit false
open Classical Finset
open DirKECC1549 DirKECC1549.Asm
variable {α : Type}theorem DirKECC1549.Asm.filter_at (p : α → Bool) (l : List α) (j : ℕ) (hj : j < l.length) (hp : p l[j] = true) :
∃ h : (l.take j).countP p < (l.filter p).length, (l.filter p)[(l.take j).countP p] = l[j] := by sorry