binary_tree_no_ancestor_descendant_repeat
For any type α with decidable equality, binary_tree_no_ancestor_descendant_repeat on BinaryTree α is defined recursively: it holds on nil, and on a node with label a, left subtree l, and right subtree r, it holds if and only if a ∉ binary_tree_labels l, a ∉ binary_tree_labels r, and the property holds recursively on both l and r.
Statement
def binary_tree_no_ancestor_descendant_repeat {α : Type*} [DecidableEq α] : 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
- extremal_tree_vertex_bound_sharpFor any natural numbers C and q, there exists a binary tree t : BinaryTree ℕ such that (binary_tree_labels t).card ≤ q,…
Read back from the Lean
Given a type α with decidable equality ([DecidableEq α]), binary_tree_no_ancestor_descendant_repeat defines a predicate on a binary tree (BinaryTree α → Prop) recursively:
- On .nil, it is True.
- On a node .node a l r, it is the conjunction of four conditions:
1. a ∉ binary_tree_labels l
2. a ∉ binary_tree_labels r
3. binary_tree_no_ancestor_descendant_repeat l
4. binary_tree_no_ancestor_descendant_repeat r
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 no class is repeated on an ancestor-descendant pair in a binary tree. -/ def binary_tree_no_ancestor_descendant_repeat {α : Type*} [DecidableEq α] : BinaryTree α → Prop | .nil => True | .node a l r => a ∉ binary_tree_labels l ∧ a ∉ binary_tree_labels r ∧ binary_tree_no_ancestor_descendant_repeat l ∧ binary_tree_no_ancestor_descendant_repeat r