Шаг 1.
Основы языка Haskell. Индуктивные определения операций и предикатов, заданных на множествах слов. Натуральная индукция. Полная индукция
На этом шаге мы дадим определения этих понятий.
Метод математической индукции (от лат. inductio - наведение) - это основной метод доказательства в математике, применяемый для исследования характеристических свойств множеств слов в алфавите.
Натуральная индукция - это разновидность метода математической индукции; более точно, натуральной индукцией называется метод доказательства утверждений в математике, основанный на
использовании принципа (аксиомы) математической индукции.
Пусть R - некоторое свойство натуральных чисел.
- Определение (принцип математической индукции).
- Допустим, что доказаны следующие утверждения:
- Натуральное число 0 обладает свойством R.
- Если какое-нибудь натуральное число n обладает свойством R, то и следующее за ним число n' ⇔ n+1 также обладает свойством R.
Тогда каждое натуральное число обладает свойством R.
- Теорема (полная индукция, возвратная индукция).
-
Пусть свойство R таково, что для любого натурального числа n из того, что этим свойством обладают все натуральные числа, меньшие n, следует, что им обладает и число n.
Тогда свойством R обладают все натуральные числа.
На следующем шаге мы рассмотрим вполне упорядоченное множество.
Содержание
Следующий шаг