binary_tree_labels
For any type α with decidable equality, and any binary tree t : BinaryTree α, the finite set binary_tree_labels t : Finset α of labels occurring in t is defined recursively: the empty tree nil has empty label set ∅, and a node with label a, left child l, and right child r has label set given by inserting a into the union of the label sets of l and r (insert a (binary_tree_labels l ∪ binary_tree_labels r)).
Statement
def binary_tree_labels {α : Type*} [DecidableEq α] : BinaryTree α → Finset α
- Defined in
- arXiv:2611.04184 Section 4.2 (Short permutation pattern waves: The complete length-five classification)
- Verified
- 07 Nov 2026
- Axioms
- none listed
- Used by 3
- binary_tree_bounded_child_overlapFor any type α with decidable equality and any natural number C, binary_tree_bounded_child_overlap C on BinaryTree α is defined…
- binary_tree_no_ancestor_descendant_repeatFor any type α with decidable equality, binary_tree_no_ancestor_descendant_repeat on BinaryTree α is defined recursively: it holds on nil,…
- 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
For any type α with decidable equality ([DecidableEq α]), binary_tree_labels is defined by recursion on a binary tree of type BinaryTree α to produce a Finset α:
- The empty tree .nil maps to the empty set ∅.
- A node .node a l r (with value a : α and subtrees l, r) maps to {a} ∪ (binary_tree_labels l ∪ binary_tree_labels r), i.e., the label a inserted into the union of the label sets of the left and right subtrees.
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
/-- The finite set of class labels occurring in a binary tree. -/ def binary_tree_labels {α : Type*} [DecidableEq α] : BinaryTree α → Finset α | .nil => ∅ | .node a l r => insert a (binary_tree_labels l ∪ binary_tree_labels r)