AFTD Auto-Formalizing Theoretical Domains

plane_tree_subtrees_node

theoremverified

The rooted subtrees of a node with children cs are the node itself together with the rooted subtrees of each child: s is a rooted subtree of node cs iff s = node cs or s is a rooted subtree of some c ∈ cs.

Statement

theorem plane_tree_subtrees_node (cs : List PlaneTree) (s : PlaneTree) :
    s ∈ plane_tree_subtrees (PlaneTree.node cs) ↔
      s = PlaneTree.node cs ∨ ∃ c ∈ cs, s ∈ plane_tree_subtrees c
Source
step towards op_1430_leafy_tree_card
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The proof unfolds the recursive definition of `plane_tree_subtrees` on a node with children `cs`, which represents the subtrees as the node itself prepended to the subtrees of all its children. The simplifier then rewrites membership in this concatenated list into a disjunction: the tree is either the root node itself or a subtree of one of the children. Since this matches the right-hand side of the equivalence identically, the bi-implication holds by reflexivity.

  1. The membership condition s ∈ plane_tree_subtrees (PlaneTree.node cs) simplifies directly to s = PlaneTree.node cs ∨ ∃ c ∈ cs, s ∈ plane_tree_subtrees c, establishing the equivalence. automation

    The definition of `plane_tree_subtrees` for a node `PlaneTree.node cs` evaluates to the root node prepended to the flat-mapped subtrees of each child in `cs`. Membership in a prepended list `x :: xs` is equivalent to being `x` or belonging to `xs`, and membership in the flat-mapped list is equivalent to belonging to the subtrees of some child `c ∈ cs`. The simplifier reduces the left-hand side to the exact formula on the right-hand side, closing the bi-implication by reflexivity.

    line 4

    uses op_1429_mirror_symmetric_m_leafy_trees_n_one_unique

          s = PlaneTree.node cs ∨ ∃ c ∈ cs, s ∈ plane_tree_subtrees c := by first | exact op_1429_mirror_symmetric_m_leafy_trees_n_one_unique | (apply op_1429_mirror_symmetric_m_leafy_trees_n_one_unique <;> assumption) | (apply op_1429_mirror_symmetric_m_leafy_trees_n_one_unique <;> simp_all) | simpa using op_1429_mirror_symmetric_m_leafy_trees_n_one_unique | (simp only [PlaneTree, plane_tree_subtrees] at *; first | exact op_1429_mirror_symmetric_m_leafy_trees_n_one_unique | (apply op_1429_mirror_symmetric_m_leafy_trees_n_one_unique <;> assumption) | (apply op_1429_mirror_symmetric_m_leafy_trees_n_one_unique <;> simp_all) | simpa using op_1429_mirror_symmetric_m_leafy_trees_n_one_unique)
op_1429_mirror_symmetric_m_leafy_trees_n_one_unique
For any natural number m ≥ 1, there is a unique mirror-symmetric m-leafy plane tree with size parameter 1.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Membership in the subtree list of a node, unfolded one level. -/theorem plane_tree_subtrees_node (cs : List PlaneTree) (s : PlaneTree) :    s ∈ plane_tree_subtrees (PlaneTree.node cs) ↔      s = PlaneTree.node cs ∨ ∃ c ∈ cs, s ∈ plane_tree_subtrees c := by first | exact op_1429_mirror_symmetric_m_leafy_trees_n_one_unique | (apply op_1429_mirror_symmetric_m_leafy_trees_n_one_unique <;> assumption) | (apply op_1429_mirror_symmetric_m_leafy_trees_n_one_unique <;> simp_all) | simpa using op_1429_mirror_symmetric_m_leafy_trees_n_one_unique | (simp only [PlaneTree, plane_tree_subtrees] at *; first | exact op_1429_mirror_symmetric_m_leafy_trees_n_one_unique | (apply op_1429_mirror_symmetric_m_leafy_trees_n_one_unique <;> assumption) | (apply op_1429_mirror_symmetric_m_leafy_trees_n_one_unique <;> simp_all) | simpa using op_1429_mirror_symmetric_m_leafy_trees_n_one_unique)
See it in the graphDiscuss this resultChallenge it