AFTD Auto-Formalizing Theoretical Domains

binary_tree_labels

def

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

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)
See it in the graphDiscuss this resultChallenge it