[TYPES] Statement of structural induction

Xavier Leroy xavier.leroy at inria.fr
Tue Jan 9 11:14:59 EST 2018


On 07/01/2018 17:41, Xavier Leroy wrote:

> As your example shows, the tree can contain infinitely-branching nodes, hence the size can be infinite, but all paths are finite, hence the height is finite.

I was confused.  All paths in this tree are finite indeed, and that's why it induces a well-founded ordering.  But in the presence of infinitely-branching nodes, the height can still be infinite and is not an appropriate justification for structural induction.

Sorry for the noise,

- Xavier Leroy


More information about the Types-list mailing list