“归纳”这个词在不同领域里意思不一样，需要先分清楚． 在经验科学和日常推理里，归纳推理是从有限次观察得出普遍结论： 见过的天鹅都是白的，于是推断“所有天鹅都是白的”． 与它相对的是演绎推理：从前提出发，按逻辑规则推出结论，前提为真则结论必真． 归纳推理的结论可能出错（澳大利亚有黑天鹅）； David Hume 在 18 世纪指出，归纳推理缺乏逻辑上的必然保证， 这就是归纳问题． 数学里的数学归纳法虽然名字里带“归纳”，却属于严格的演绎： 证明 $𝑃\left(0\right)$，再证明“$𝑃\left(𝑛\right)$ 蕴涵 $𝑃\left(𝑛+1\right)$”，就能断定所有自然数都满足 $𝑃$． 结构归纳原理 与 规则归纳法 使用的也是这种演绎证明方法．

数学归纳法的历史很长． 古希腊的 Euclid 证明素数有无穷多个时，已经有了它的影子； 16 世纪的 Francesco Maurolico、17 世纪的 Blaise Pascal 在讨论二项式系数时比较明确地用了它； “数学归纳法”这个名字是 19 世纪 Augustus De Morgan 起的． 19 世纪末，Richard Dedekind 由自然数的最小性推导出归纳原理， Giuseppe Peano 则把归纳列入自然数公理． 结构归纳原理 把这个想法从自然数推广到由规则搭起来的有限树．

词项的集合 的有限项 与 一步规约 的有限推导，采用的是归纳定义： 由这些有限前提的规则生成最小集合，每个对象都有有限的构造或推导．

余归纳则可用相应单调算子的最大不动点刻画对象或行为，并据此证明性质． 它可以描述无限展开，例如无穷数据流或无限运行，但不意味着其中只有无限对象： 带空构造子的余归纳列表就可以同时包含有限和无限列表． 共递归侧重怎样按观察结构逐步产生这样的对象； 要定义可用的无限数据，还须保证每次索取有限的可观察部分都能在有限计算后得到， 这称为生产性． 非结构递归不自动就是共递归，也不自动具有生产性． 列表与受保护共递归的例子见 A Tutorial on [Co-]Inductive Types in Coq §7．