LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 2026-08-26

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.

Each $T_{n}$ is finite

Statement

For every natural number $n$ , the set

$T_{n} : = {T \in T : size (T) = n}$

of binary trees of size $n$ is finite (Binary trees, defined recursively, and their size).

Facts & Assumptions

Given: a natural number $n$ .

[F1]

The recursion of Binary trees, defined recursively, and their size gives $T_{n + 1} ≅ ∐_{i = 0}^{n} T_{i} \times T_{n - i} .$

[F2]

If $A$ and $B$ are finite and disjoint, then $A \cup B$ is finite; and a finite disjoint union of finite sets is finite (The sum rule: a finite disjoint union is finite with $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ and $∣ ⋃_{i \in I} A_{i} ∣ = \sum_{i \in I} ∣ A_{i} ∣$ , and a sum over a finite index set splits along a partition).

[F3]

If $A$ and $B$ are finite, then $A \times B$ is finite (The product rule: $∣ A \times B ∣ = ∣ A ∣ ∣ B ∣$ , and $∣ \prod_{i < m} A_{i} ∣ = \prod_{i < m} ∣ A_{i} ∣$ ).

Proof

technique · induction

1.1F1

[base] The set $T_{0}$ has the single element ${ε}$ by Binary trees, defined recursively, and their size, so $T_{0}$ is finite.

1.2given

[ih] Assume that every $T_{j}$ with $j \leq n$ is finite.

2.1F3step 1.2

For each index $i$ with $0 \leq i \leq n$ , the sets $T_{i}$ and $T_{n - i}$ are finite by the induction hypothesis, so $T_{i} \times T_{n - i}$ is finite by [F3].

3.1F2step 2.1

The disjoint union $∐_{i = 0}^{n} T_{i} \times T_{n - i}$ is finite by [F2].

4.1F1step 3.1discharge-induction∎

Since $T_{n + 1}$ is in bijection with that finite disjoint union by [F1], the set $T_{n + 1}$ is finite. Therefore every $T_{n}$ is finite.

Remarks

This is the well-definedness step for the next corollaries. The Catalan count of binary trees is a statement about the natural number $∣ T_{n} ∣$ , and that symbol is honest only because this lemma makes the set finite first.

Depends on

Used by

Dependency tree · two levels

27 results within two dependency steps 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

D. Guichard, An Introduction to Combinatorics and Graph Theory, §3.5 (standard reference, not scraped)

Each TnTn​ is finite