AFTD Auto-Formalizing Theoretical Domains

interval_family_member_depth

def

The depth of a member I of an interval family: the number of members of the same color as I (the color of the owner) whose interval contains the interval of I, I itself included.

Statement

noncomputable def interval_family_member_depth {T : ColoredRootedTree} {R : ℕ} (F : IntervalFamily T R)
    (i : F.ι) : ℕ
Defined in
arXiv:2611.03620 (Adjacency Labeling Schemes of Size log n + O(log log* n) for Graphs of Bounded Treewidth), Definition 2.2 (depth of a member of F).
Verified
07 Nov 2026
Axioms
none listed
Built on 2
  • IntervalFamilyAn interval family for a colored tree consists of an injective mapping from vertices to integers and a laminar family of non-empty integer…
  • ColoredRootedTreeA finite rooted tree properly colored with 4 colors, represented by an ancestorship partial order with a root element below all vertices,…
Used by 3

Read back from the Lean

Given an implicit colored rooted tree T, an implicit natural number R, an interval family F over T with parameter R, and an element i : F.ι, interval_family_member_depth F i is defined as the cardinality (as a natural number, via Nat.card) of the subtype of elements j : F.ι such that both: 1. The owner vertex of j has the same color in T as the owner vertex of i (T.color (F.owner j) = T.color (F.owner i)), and 2. The interval associated with i is a subset of the interval associated with j (F.interval i ⊆ F.interval j).

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

noncomputable def interval_family_member_depth {T : ColoredRootedTree} {R : ℕ} (F : IntervalFamily T R)
    (i : F.ι) : ℕ :=
  Nat.card {j : F.ι // T.color (F.owner j) = T.color (F.owner i) ∧ F.interval i ⊆ F.interval j}
See it in the graphDiscuss this resultChallenge it