AFTD Auto-Formalizing Theoretical Domains

binary_tree_no_ancestor_descendant_repeat

def

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

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