plane_tree_subtrees_node
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
- plane_tree_subtreesThe collection of all rooted subtrees T_v of a plane tree T.
- PlaneTreeA finite plane tree is either a leaf or an internal node with a list of child plane trees.
- op_1429_mirror_symmetric_m_leafy_trees_n_one_uniqueFor every natural number m ≥ 1, there exists a unique tree t such that t ∈ mirror_symmetric_m_leafy_trees m 1.
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.
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.
uses
op_1429_mirror_symmetric_m_leafy_trees_n_one_uniques = 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.
- The proof script is generated by an automated search pattern that attempts several tactic combinations using the lemma `op_1429_mirror_symmetric_m_leafy_trees_n_one_unique`. That lemma concerns mirror-symmetric leafy trees and is completely irrelevant to this result; `simpa` closes the goal solely through standard list membership simplification rules and reflexivity after unfolding `plane_tree_subtrees`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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)