AFTD Auto-Formalizing Theoretical Domains

op_1429_mirror_symmetric_m_leafy_trees_n_one_unique

theoremverified

For every natural number m ≥ 1, there exists a unique tree t such that t ∈ mirror_symmetric_m_leafy_trees m 1.

Statement

theorem op_1429_mirror_symmetric_m_leafy_trees_n_one_unique (m : ℕ) (hm : 1 ≤ m) :
    ∃! t : PlaneTree, t ∈ mirror_symmetric_m_leafy_trees m 1
Source
arXiv:2611.10154 Sec. 2.3
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
Used by 2
  • plane_tree_subtrees_nodeThe 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…
  • op_1430_involution_group_n_oneFor n = 1 and any m ≥ 1, any two involutions on MLeafyTree m 1 generate a trivial (subsingleton) permutation subgroup.

Read back from the Lean

For every natural number $m$ with $1 \le m$, there exists a unique plane tree $t$ belonging to the set of mirror-symmetric $m$-leafy trees with parameter $n = 1$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

For n = 1 and any m ≥ 1, a tree in mirror_symmetric_m_leafy_trees m 1 must have exactly 1 internal node and m + 1 leaves. A tree with 1 internal node is necessarily a root node whose children all have 0 internal nodes, making every child a leaf. Therefore, any such tree must be the unique root node with m + 1 leaf children. Existence comes from the nonemptiness theorem, and uniqueness follows because any two elements share this identical shape.

  1. A plane tree with 0 internal nodes must be a leaf.

    We proceed by cases on the tree t. If t is a leaf, the claim is trivial. If t is a node, its internal node count is 1 plus the sum of internal nodes of its children, which is at least 1, contradicting that the count is 0.

    lines 4–8

    uses op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node

      cases t with
      | leaf => rfl
      | node cs =>
        rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node] at h
        omega
  2. A list whose elements are all leaves is equal to a replicate of leaves.

    By induction on the list cs. If cs is empty, both sides are empty. In the inductive step, the head is a leaf and every element of the tail is a leaf; rewriting by the induction hypothesis on the tail completes the step.

    lines 13–20

    uses List.mem_cons_self, List.mem_cons_of_mem, List.length_cons, List.replicate_succ

      induction cs with
      | nil => rfl
      | cons head tail ih =>
        have hhead : head = PlaneTree.leaf := h head List.mem_cons_self
        have htail : ∀ c ∈ tail, c = PlaneTree.leaf := fun c hc => h c (List.mem_cons_of_mem head hc)
        rw [hhead, List.length_cons, List.replicate_succ]
        congr 1
        exact ih htail
  3. The total number of leaves across a list of leaves equals the length of the list.

    By induction on the list cs. If cs is empty, both the sum and length are 0. For head :: tail, head contributes 1 leaf and the tail contributes tail.length leaves by the induction hypothesis, so the sum is 1 + tail.length = tail.length + 1.

    lines 25–31

    uses List.mem_cons_self, List.mem_cons_of_mem, List.map_cons, List.sum_cons, plane_tree_num_leaves.eq_1, List.length_cons

      induction cs with
      | nil => rfl
      | cons head tail ih =>
        have hhead : head = PlaneTree.leaf := h head List.mem_cons_self
        have htail : ∀ c ∈ tail, c = PlaneTree.leaf := fun c hc => h c (List.mem_cons_of_mem head hc)
        rw [List.map_cons, List.sum_cons, hhead, plane_tree_num_leaves.eq_1, ih htail, List.length_cons]
        omega
  4. If a list of natural numbers sums to 0, every element in the list is 0.

    By induction on the list l. An empty list has no elements. For head :: tail, head + tail.sum = 0 forces head = 0 and tail.sum = 0; if x is the head then x = 0, and if x is in the tail then x = 0 by the induction hypothesis.

    lines 35–42

    uses List.sum_cons, List.mem_cons.mp

      induction l with
      | nil => contradiction
      | cons head tail ih =>
        rw [List.sum_cons] at h
        have : head = 0 ∧ tail.sum = 0 := by omega
        rcases List.mem_cons.mp hx with rfl | hmem
        · exact this.1
        · exact ih this.2 hmem
  5. A tree with 1 internal node cannot be a leaf.

    A leaf has 0 internal nodes by definition, which contradicts the assumption that it has 1 internal node.

    lines 47–50

    uses plane_tree_num_internal.eq_1

      cases t with
      | leaf =>
        rw [plane_tree_num_internal.eq_1] at hint
        contradiction
  6. A tree with 1 internal node is a node whose children are all leaves, replicated to match the tree's leaf count.

    If t = node cs has 1 internal node, then 1 + ∑ internal(cs) = 1, so the sum of internal nodes of the children is 0. Therefore every child has 0 internal nodes and is a leaf. Thus cs is a list of leaves, which means cs = replicate cs.length leaf. Since each child is a leaf, the number of leaves of t is exactly cs.length.

    lines 51–67

    uses op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node, List.mem_map_of_mem, op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_nat_list_sum_eq_zero, op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_num_internal_eq_zero, op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_eq_replicate_leaf, op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node, op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_leaves_sum

      | node cs =>
        rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node] at hint
        have hsum : (List.map plane_tree_num_internal cs).sum = 0 := by omega
        have hcs_zero : ∀ c ∈ cs, plane_tree_num_internal c = 0 := by
          intro c hc
          have hmem : plane_tree_num_internal c ∈ List.map plane_tree_num_internal cs :=
            List.mem_map_of_mem hc
          exact op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_nat_list_sum_eq_zero _ hsum _ hmem
        have hcs_leaf : ∀ c ∈ cs, c = PlaneTree.leaf := fun c hc =>
          op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_num_internal_eq_zero c (hcs_zero c hc)
        have hcs_eq : cs = List.replicate cs.length PlaneTree.leaf :=
          op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_eq_replicate_leaf cs hcs_leaf
        have hleaves : plane_tree_num_leaves (PlaneTree.node cs) = cs.length := by
          rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node]
          exact op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_leaves_sum cs hcs_leaf
        rw [hleaves]
        congr 1
  7. There exists a witness tree t₀ in mirror_symmetric_m_leafy_trees m 1.

    We invoke the nonemptiness theorem for m ≥ 1 and n = 1 to obtain a witness tree t₀, reducing the goal to showing that any tree in the set must equal t₀.

    lines 72–73

    uses op_1429_mirror_symmetric_m_leafy_trees_nonempty, le_rfl

      rcases op_1429_mirror_symmetric_m_leafy_trees_nonempty m 1 hm le_rfl with ⟨t0, ht0⟩
      refine ⟨t0, ht0, fun y hy => ?_⟩
  8. Any tree in mirror_symmetric_m_leafy_trees m 1 is a node with m + 1 leaf children.

    Any tree t in the set has 1 internal node and m · 1 + 1 = m + 1 leaves. By our earlier lemma, any tree with 1 internal node is a node whose children are leaves equal in number to the tree's leaf count, so t must be a node with m + 1 leaves.

    lines 74–82

    uses op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicate

      have h_eq : ∀ t, t ∈ mirror_symmetric_m_leafy_trees m 1 →
          t = PlaneTree.node (List.replicate (m + 1) PlaneTree.leaf) := by
        intro t ht
        rcases ht with ⟨⟨-, hint, hleaves⟩, -⟩
        have ht_shape := op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicate t hint
        rw [hleaves] at ht_shape
        have : m * 1 + 1 = m + 1 := by omega
        rw [this] at ht_shape
        exact ht_shape
  9. The tree in mirror_symmetric_m_leafy_trees m 1 is unique.

    Both an arbitrary element y and the witness t₀ equal the unique node with m + 1 leaf children, so y = t₀.

    line 83

      rw [h_eq y hy, h_eq t0 ht0]
List.length_cons
Prepending an element to a list increases its length by 1.
List.map_cons
Mapping a function over a non-empty list applies the function to the head and maps over the tail.
List.mem_map_of_mem
If an element belongs to a list, its image under a function belongs to the mapped list.
List.mem_cons.mp
If an element belongs to a prepended list, it either equals the head or belongs to the tail.
List.mem_cons_of_mem
An element belonging to a list also belongs to that list prepended with any head.
List.mem_cons_self
An element is always a member of any list of which it is the head.
List.replicate_succ
Replicating an element n + 1 times equals prepending the element to its n-fold replication.
List.sum_cons
The sum of a non-empty list is its head plus the sum of its tail.
le_rfl
The relation ≤ is reflexive on any preorder.
op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node
The number of internal nodes in a node tree is 1 plus the sum of the internal nodes of its children.
op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node
The number of leaves of a node tree is the sum of the leaves of its children.
op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_eq_replicate_leaf
A list in which every tree is a leaf is equal to replicating a leaf as many times as the list's length.
op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_leaves_sum
If every tree in a list is a leaf, the sum of their leaf counts equals the length of the list.
op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_nat_list_sum_eq_zero
If the sum of a list of natural numbers is 0, every element in the list is 0.
op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_num_internal_eq_zero
A plane tree with 0 internal nodes must be a leaf.
op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicate
A tree with exactly 1 internal node is a node whose children are all leaves, with count equal to the number of leaves of the tree.
op_1429_mirror_symmetric_m_leafy_trees_nonempty
For any m ≥ 1 and n ≥ 1, the set of mirror-symmetric m-leafy trees with parameter n is nonempty.
plane_tree_num_internal.eq_1
A leaf tree has 0 internal nodes.
plane_tree_num_leaves.eq_1
A leaf tree has 1 leaf.

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

lemma op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_num_internal_eq_zero (t : PlaneTree)    (h : plane_tree_num_internal t = 0) :    t = PlaneTree.leaf := by  cases t with  | leaf => rfl  | node cs =>    rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node] at h    omegalemma op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_eq_replicate_leaf (cs : List PlaneTree)    (h : ∀ c ∈ cs, c = PlaneTree.leaf) :    cs = List.replicate cs.length PlaneTree.leaf := by  induction cs with  | nil => rfl  | cons head tail ih =>    have hhead : head = PlaneTree.leaf := h head List.mem_cons_self    have htail : ∀ c ∈ tail, c = PlaneTree.leaf := fun c hc => h c (List.mem_cons_of_mem head hc)    rw [hhead, List.length_cons, List.replicate_succ]    congr 1    exact ih htaillemma op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_leaves_sum (cs : List PlaneTree)    (h : ∀ c ∈ cs, c = PlaneTree.leaf) :    (List.map plane_tree_num_leaves cs).sum = cs.length := by  induction cs with  | nil => rfl  | cons head tail ih =>    have hhead : head = PlaneTree.leaf := h head List.mem_cons_self    have htail : ∀ c ∈ tail, c = PlaneTree.leaf := fun c hc => h c (List.mem_cons_of_mem head hc)    rw [List.map_cons, List.sum_cons, hhead, plane_tree_num_leaves.eq_1, ih htail, List.length_cons]    omegalemma op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_nat_list_sum_eq_zero (l : List ℕ)    (h : l.sum = 0) (x : ℕ) (hx : x ∈ l) : x = 0 := by  induction l with  | nil => contradiction  | cons head tail ih =>    rw [List.sum_cons] at h    have : head = 0 ∧ tail.sum = 0 := by omega    rcases List.mem_cons.mp hx with rfl | hmem    · exact this.1    · exact ih this.2 hmemlemma op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicate (t : PlaneTree)    (hint : plane_tree_num_internal t = 1) :    t = PlaneTree.node (List.replicate (plane_tree_num_leaves t) PlaneTree.leaf) := by  cases t with  | leaf =>    rw [plane_tree_num_internal.eq_1] at hint    contradiction  | node cs =>    rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node] at hint    have hsum : (List.map plane_tree_num_internal cs).sum = 0 := by omega    have hcs_zero : ∀ c ∈ cs, plane_tree_num_internal c = 0 := by      intro c hc      have hmem : plane_tree_num_internal c ∈ List.map plane_tree_num_internal cs :=        List.mem_map_of_mem hc      exact op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_nat_list_sum_eq_zero _ hsum _ hmem    have hcs_leaf : ∀ c ∈ cs, c = PlaneTree.leaf := fun c hc =>      op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_num_internal_eq_zero c (hcs_zero c hc)    have hcs_eq : cs = List.replicate cs.length PlaneTree.leaf :=      op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_eq_replicate_leaf cs hcs_leaf    have hleaves : plane_tree_num_leaves (PlaneTree.node cs) = cs.length := by      rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node]      exact op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_leaves_sum cs hcs_leaf    rw [hleaves]    congr 1/-- For n = 1 and any m ≥ 1, there exists a unique tree in mirror_symmetric_m_leafy_trees m 1. -/theorem op_1429_mirror_symmetric_m_leafy_trees_n_one_unique (m : ℕ) (hm : 1 ≤ m) :    ∃! t : PlaneTree, t ∈ mirror_symmetric_m_leafy_trees m 1 := by  rcases op_1429_mirror_symmetric_m_leafy_trees_nonempty m 1 hm le_rfl with ⟨t0, ht0⟩  refine ⟨t0, ht0, fun y hy => ?_⟩  have h_eq : ∀ t, t ∈ mirror_symmetric_m_leafy_trees m 1 →      t = PlaneTree.node (List.replicate (m + 1) PlaneTree.leaf) := by    intro t ht    rcases ht with ⟨⟨-, hint, hleaves⟩, -⟩    have ht_shape := op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicate t hint    rw [hleaves] at ht_shape    have : m * 1 + 1 = m + 1 := by omega    rw [this] at ht_shape    exact ht_shape  rw [h_eq y hy, h_eq t0 ht0]
See it in the graphDiscuss this resultChallenge it