AFTD Auto-Formalizing Theoretical Domains

is_correct_interval_family

def

An 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 color c, the innermost interval of color c containing id(x) is owned by u.

Statement

def is_correct_interval_family {T : ColoredRootedTree} {R : ℕ} (F : IntervalFamily T R) : Prop
Defined in
arXiv:2611.03620 Definition 2.2
Verified
05 Nov 2026
Axioms
none listed
Built on 3
  • ColoredRootedTreeA finite rooted tree properly colored with 4 colors, represented by an ancestorship partial order with a root element below all vertices,…
  • IntervalFamilyAn interval family for a colored tree consists of an injective mapping from vertices to integers and a laminar family of non-empty integer…
  • nearest_ancestor_of_colorVertex 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…
Used by 1

Read back from the Lean

Given a colored rooted tree T and a natural number R, an interval family F : IntervalFamily T R is said to be correct (is_correct_interval_family F) if: For every vertex x : T.V, every color c : Fin 4, and every vertex u : T.V, if: 1. c ≠ T.color x (the color c is different from the color of x), and 2. u is the nearest ancestor of x of color c (that is, u < x, T.color u = c, and for all w : T.V, if u < w and w < x then T.color w ≠ c), then there exists an index i : F.ι such that: 1. T.color (F.owner i) = c, 2. F.owner i = u, 3. F.id x ∈ F.interval i, and 4. for all indices j : F.ι, if T.color (F.owner j) = c and F.id x ∈ F.interval j, then F.interval i ⊆ F.interval j (i.e., F.interval i is minimal among intervals whose owner has color c and which contain F.id x).

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

/-- Correctness of an interval family. -/
def is_correct_interval_family {T : ColoredRootedTree} {R : ℕ} (F : IntervalFamily T R) : Prop := ∀ (x : T.V) (c : Fin 4) (u : T.V),
    c ≠ T.color x →
    nearest_ancestor_of_color T x c u →
    ∃ i : F.ι,
      T.color (F.owner i) = c ∧
      F.owner i = u ∧
      F.id x ∈ F.interval i ∧
      ∀ j : F.ι, T.color (F.owner j) = c → F.id x ∈ F.interval j → F.interval i ⊆ F.interval j
See it in the graphDiscuss this resultChallenge it