AFTD Auto-Formalizing Theoretical Domains

has_contiguous_subtrees

def

An interval family has contiguous subtrees if the identifier image of every subtree is a closed integer interval.

Statement

def has_contiguous_subtrees {T : ColoredRootedTree} {R : ℕ} (F : IntervalFamily T R) : Prop
Defined in
arXiv:2611.03620 Proposition 3.3
Verified
05 Nov 2026
Axioms
none listed
Built on 5
  • 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…
  • colored_tree_subtreeThe subtree rooted at vertex v consists of all descendants of v in the tree.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

Read back from the Lean

Given a colored rooted tree $T$, a natural number $R$, and an interval family $F$ associated with $T$ and $R$, has_contiguous_subtrees F asserts that for every vertex $v \in T.V$, there exist integers $a, b \in \mathbb{Z}$ such that the image under $F.\mathrm{id}$ of the subtree rooted at $v$ (i.e., the set of vertices $w \in T.V$ with $v \le w$) is equal to the closed integer interval $[a, b] = \{x \in \mathbb{Z} \mid a \le x \le b\}$.

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

/-- Contiguous subtree property: each subtree occupies consecutive integer positions. -/
def has_contiguous_subtrees {T : ColoredRootedTree} {R : ℕ} (F : IntervalFamily T R) : Prop := ∀ v : T.V, ∃ a b : ℤ, F.id '' (colored_tree_subtree T v) = Set.Icc a b
See it in the graphDiscuss this resultChallenge it