is_correct_interval_family
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
- 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,…
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