Consider the following inductive definition:
Define the set $\Lambda$ as follows (where the $\langle x, y, z\rangle$ denote ordered triples):
- if $n \in \mathbb{N},$ then $\langle 0, n, n\rangle \in \Lambda \;$;
- if $n \in \mathbb{N}$ and $x \in \Lambda$ then $\langle 1, n, x \rangle \in \Lambda \;$;
- if $x, y \in \Lambda$, then $\langle 2, x, y \rangle \in \Lambda$.
Now define the function $\ell:\Lambda \to \mathbb{N}$ recursively as follows:
- $\ell(\langle 0, n, n \rangle) = 1, \forall \; n \in \mathbb{N}$;
- $\ell(\langle 1, n, x \rangle) = 1 + \ell(x), \forall \; n \in \mathbb{N}$ and $x \in \Lambda$;
- $\ell(\langle 2, x, y \rangle) = \ell(x) + \ell(y), \forall \; x, y \in \Lambda$.
It is obvious that $\ell(x) > 0, \forall \; x \in \Lambda$, but I don't know how to prove it. It looks like a case for proof by induction, but induction on what?
Thanks!