AFTD Auto-Formalizing Theoretical Domains

nearest_ancestor_of_color

def

Vertex u is the nearest proper ancestor of vertex v having color c if u is an ancestor of v with color c and no intermediate ancestor between u and v has color c.

Statement

def nearest_ancestor_of_color (T : ColoredRootedTree) (v : T.V) (c : Fin 4) (u : T.V) : Prop
Defined in
arXiv:2611.03620 Section 2
Verified
05 Nov 2026
Axioms
none listed
Built on 2
  • ColoredRootedTreeA finite rooted tree properly colored with 4 colors, represented by an ancestorship partial order with a root element below all vertices,…
  • instPartialOrderColoredRootedTreeThe ancestorship relation on the vertices of a colored rooted tree forms a partial order.
Used by 2
  • contiguous_interval_family_depth_lower_boundFor all integers R ≥ 1 and d ≥ 0 there is a finite rooted tree, properly colored with the 4 colors 0..3, with at most 11(2R+1)^d vertices,…
  • is_correct_interval_familyAn interval family is correct if for every vertex x and color c different from that of x, whenever x has a nearest proper ancestor u of…

Read back from the Lean

Given a colored rooted tree $T$, a vertex $v \in T.V$, a color $c \in \mathrm{Fin}\; 4$, and a vertex $u \in T.V$, the predicate nearest_ancestor_of_color T v c u holds if and only if: 1. $u < v$ (in the partial order on $T.V$), 2. the color of $u$ in $T$ is $c$ ($T.\mathrm{color}\; u = c$), and 3. for every vertex $w \in T.V$, if $u < w$ and $w < v$, then $T.\mathrm{color}\; w \neq c$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Nearest proper ancestor of color c. -/
def nearest_ancestor_of_color (T : ColoredRootedTree) (v : T.V) (c : Fin 4) (u : T.V) : Prop := u < v ∧ T.color u = c ∧ ∀ w : T.V, u < w → w < v → T.color w ≠ c
See it in the graphDiscuss this resultChallenge it