AFTD Auto-Formalizing Theoretical Domains

IntervalFamily

structure

An interval family for a colored tree consists of an injective mapping from vertices to integers and a laminar family of non-empty integer intervals, where each vertex owns at most R intervals.

Statement

structure IntervalFamily (T : ColoredRootedTree) (R : ℕ)
Defined in
arXiv:2611.03620 Definition 2.2
Verified
05 Nov 2026
Axioms
none listed
Built on 5
Used by 8

Read back from the Lean

Given a colored rooted tree T and a natural number R, an IntervalFamily T R is a structure consisting of: 1. A type of indices ι, equipped with Fintype ι and DecidableEq ι. 2. A function interval : ι → Set ℤ assigning a set of integers to each index i : ι. 3. A proof interval_icc that for every index i : ι, there exist integers a, b : ℤ with a ≤ b such that interval i equals the closed interval Set.Icc a b (i.e., {x ∈ ℤ | a ≤ x ≤ b}). 4. A function owner : ι → T.V assigning each index to a vertex of T. 5. A proof owner_bound that for every vertex v : T.V, the number of indices i : ι such that owner i = v (the cardinality of the fiber of owner over v) is at most R. 6. A proof laminar that for every pair of indices i, j : ι, at least one of the three conditions holds: - interval i ⊆ interval j, - interval j ⊆ interval i, or - interval i and interval j are disjoint (i.e., interval i ∩ interval j = ∅). 7. A function id : T.V → ℤ. 8. A proof id_inj that id is injective (∀ u v : T.V, id u = id v → u = v).

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

/-- An interval family for a colored tree with at most R intervals per vertex. -/
structure IntervalFamily (T : ColoredRootedTree) (R : ℕ) where
  ι : Type
  [fintype : Fintype ι]
  [decEq : DecidableEq ι]
  interval : ι → Set ℤ
  interval_icc : ∀ i : ι, ∃ a b : ℤ, a ≤ b ∧ interval i = Set.Icc a b
  owner : ι → T.V
  owner_bound : ∀ v : T.V, (Finset.univ.filter (fun i : ι => owner i = v)).card ≤ R
  laminar : ∀ i j : ι, interval i ⊆ interval j ∨ interval j ⊆ interval i ∨ Disjoint (interval i) (interval j)
  id : T.V → ℤ
  id_inj : Function.Injective id
See it in the graphDiscuss this resultChallenge it