AFTD Auto-Formalizing Theoretical Domains

DiagramSlidingTree

inductive

A sliding tree DiagramSlidingTree D on a diagram $D$ is either a leaf diagram with no crossings (∀ u ∈ D, ∀ v ∈ D, ¬ diagram_crossing u v), or an internal node that chooses a consecutive admissible pair $(b_1, b_2)$ of $D$ and branches into a vertical child sliding tree on diagram_vertical_slide D b_1 b_2 and a horizontal child sliding tree on diagram_horizontal_slide D b_1 b_2.

Statement

inductive DiagramSlidingTree : Finset (ℕ × ℕ) → Type where
Defined in
arXiv:2611.07715, Definition 4.12
Verified
06 Nov 2026
Axioms
none listed
Built on 4
  • diagram_crossingTwo cells $u, v \in \mathbb{N} \times \mathbb{N}$ form a crossing (diagram_crossing u v) if…
  • diagram_is_consecutive_admissible_pairAn admissible pair $(b_1, b_2)$ in a diagram $D$ is consecutive (diagram_is_consecutive_admissible_pair D b_1 b_2) if it is admissible…
  • diagram_vertical_slideThe vertical slide of a diagram $D$ with respect to cells $b_1, b_2$ is the diagram diagram_vertical_slide D b_1 b_2 obtained as the…
  • diagram_horizontal_slideThe horizontal slide of a diagram $D$ with respect to cells $b_1, b_2$ is the diagram diagram_horizontal_slide D b_1 b_2 obtained as the…
Used by 4
  • open_problem_1285_partial_no_crossingsFor every finite diagram $D \subseteq \mathbb{N} \times \mathbb{N}$ having no crossings (∀ u ∈ D, ∀ v ∈ D, ¬ diagram_crossing u v), the…
  • terminal_boxesGiven a sliding tree t : DiagramSlidingTree D and a list $l$ of boxes representing a tableau on $D$, terminal_boxes t l transports $l$…
  • diagram_slide_expansion_agrees_with_descentsA sliding tree t on a finite diagram $D$ satisfies diagram_slide_expansion_agrees_with_descents D t if for every list $l$ representing…
  • open_problem_1285_exists_tree_of_no_crossingsFor every finite diagram $D \subseteq \mathbb{N} \times \mathbb{N}$ having no crossings (∀ u ∈ D, ∀ v ∈ D, ¬ diagram_crossing u v),…

Read back from the Lean

An inductive type family DiagramSlidingTree : Finset (ℕ × ℕ) → Type indexed by a finite set of coordinate pairs D : Finset (ℕ × ℕ), defined with two constructors: 1. leaf: for any D : Finset (ℕ × ℕ), given a hypothesis h that no two elements u, v ∈ D form a crossing (that is, ∀ u ∈ D, ∀ v ∈ D, ¬ diagram_crossing u v), produces a DiagramSlidingTree D. 2. node: for any D : Finset (ℕ × ℕ) and points b₁, b₂ : ℕ × ℕ, given: - hcap: a proof that (b₁, b₂) is a consecutive admissible pair in D (diagram_is_consecutive_admissible_pair D b₁ b₂), - left: a DiagramSlidingTree for the vertical slide of D along (b₁, b₂) (diagram_vertical_slide D b₁ b₂), and - right: a DiagramSlidingTree for the horizontal slide of D along (b₁, b₂) (diagram_horizontal_slide D b₁ b₂), produces a DiagramSlidingTree D.

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

/-- A sliding tree for a diagram D is a rooted binary tree whose internal nodes choose consecutive admissible pairs and branch by vertical and horizontal slides, with leaves having no crossings. -/
inductive DiagramSlidingTree : Finset (ℕ × ℕ) → Type where | leaf (D : Finset (ℕ × ℕ)) (h : ∀ u ∈ D, ∀ v ∈ D, ¬ diagram_crossing u v) : DiagramSlidingTree D
  | node (D : Finset (ℕ × ℕ)) (b₁ b₂ : ℕ × ℕ) (hcap : diagram_is_consecutive_admissible_pair D b₁ b₂)
      (left : DiagramSlidingTree (diagram_vertical_slide D b₁ b₂))
      (right : DiagramSlidingTree (diagram_horizontal_slide D b₁ b₂)) : DiagramSlidingTree D
See it in the graphDiscuss this resultChallenge it