TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Weakest-link pruning terminates at the root

Statement

Let $T_{0}$ be a finite empirical binary tree with $L_{0} \geq 1$ terminal nodes and nonempty sample set at every leaf. The weakest-link pruning procedure that repeatedly collapses a current nonterminal node minimizing $g (t)$ terminates at the root leaf after at most $L_{0} - 1$ collapses. This is a termination statement only; it does not assert global cost-complexity optimality.

Statement references

Hastie, Tibshirani, and Friedman, The Elements of Statistical Learning, §9.2.2, printed p. 308

Facts & Assumptions

Given: A finite empirical binary tree $T_{0}$ whose internal nodes each have two nonempty child sample sets.

[F1]

Empirical axis-aligned binary decision trees: Every internal node splits its sample set into two nonempty child sets, and the terminal sample sets partition the original sample.

[F2]

Cost-complexity criteria for subtrees: For a current nonterminal node $t$ , $g (t) = [R (t) - R (T_{t})] / (∣ T_{t} ∣ - 1)$ , where $T_{t}$ is its current descendant subtree.

[F3]

Weakest-link pruning of a finite tree: At each iteration the algorithm chooses a current nonterminal node minimizing $g (t)$ , collapses its descendant subtree to a leaf, and stops when the current tree is the root leaf.

Proof

1.1givenF1F2constructalgebra

If the current tree has more than one leaf, its root is nonterminal. Every nonterminal node $t$ has two finite child subtrees. Starting at either child and following descendants must reach a leaf because the tree is finite, so $∣ T_{t} ∣ \geq 2$ and every denominator in [F2] is positive. The tree has finitely many nonterminal nodes, and every loss in [F2] is a finite real number because the sample and chosen impurity formulas are finite. Hence the candidate quotients form a finite nonempty set of real numbers, which has a minimum by repeated pairwise comparison.

2.1F2F3step 1.1algebrachoose

By [F3], the algorithm selects a minimizing candidate, using its fixed tie rule. If that node has $k = ∣ T_{t} ∣ \geq 2$ descendant leaves, collapsing it replaces those $k$ leaves by one, reducing the current leaf count by $k - 1 \geq 1$ . The resulting tree is still a finite subtree of $T_{0}$ .

3.1F1F3step 1.1step 2.1algebra∎

Starting from $L_{0}$ leaves, each collapse strictly decreases the positive integer leaf count, so there are at most $L_{0} - 1$ collapses. If more than one leaf remains, the root is nonterminal and is among the available candidates by step 1.1; therefore the algorithm cannot stop early. A nonterminal root has at least two descendant leaves by step 1.1, so a tree with one leaf is the root leaf.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · one level

3 results within one dependency step of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, 2nd ed., §9.2.2 (standard reference, not scraped)