19/03/10 11:08:35.27 rk/29Zdt.net
>>149
つづき
４）
”As an example, consider the well-founded relation (N, S), where N is the set of all natural numbers, and S is the graph of the successor function x → x + 1.
Then induction on S is the usual mathematical induction, and recursion on S gives primitive recursion.
If we consider the order relation (N, <), we obtain complete induction, and course-of-values recursion.
The statement that (N, <) is well-founded is also known as the well-ordering principle