AFTD Auto-Formalizing Theoretical Domains

binary_tree_bounded_child_overlap

def

For any type α with decidable equality and any natural number C, binary_tree_bounded_child_overlap C on BinaryTree α is defined recursively: it holds on nil, and on a node with left child l and right child r, it holds if and only if (binary_tree_labels l ∩ binary_tree_labels r).card ≤ C, and the property holds recursively on both l and r.

Statement

def binary_tree_bounded_child_overlap {α : Type*} [DecidableEq α] (C : ℕ) : BinaryTree α → Prop
Defined in
arXiv:2611.04184 Section 4.2 (Short permutation pattern waves: The complete length-five classification)
Verified
07 Nov 2026
Axioms
none listed
Built on 1
  • binary_tree_labelsFor any type α with decidable equality, and any binary tree t : BinaryTree α, the finite set binary_tree_labels t : Finset α of labels…
Used by 1

Read back from the Lean

Given a type α with decidable equality and a natural number C, binary_tree_bounded_child_overlap C is a predicate on binary trees t : BinaryTree α defined recursively: - If t is nil, it is True. - If t is a node with left subtree l and right subtree r (regardless of the node's label), it asserts that: 1. The cardinality of the intersection of the finite set of labels in l and the finite set of labels in r is at most C ((binary_tree_labels l ∩ binary_tree_labels r).card ≤ C), 2. binary_tree_bounded_child_overlap C l holds, and 3. binary_tree_bounded_child_overlap C r holds. In other words, at every internal node in the tree, the number of distinct labels appearing in both the left subtree and the right subtree is at most C.

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

/-- Predicate stating that every vertex has left-right child subtree label overlap at most C. -/
def binary_tree_bounded_child_overlap {α : Type*} [DecidableEq α] (C : ℕ) : BinaryTree α → Prop
| .nil => True
| .node _ l r => (binary_tree_labels l ∩ binary_tree_labels r).card ≤ C ∧
    binary_tree_bounded_child_overlap C l ∧ binary_tree_bounded_child_overlap C r
See it in the graphDiscuss this resultChallenge it