Шаг 1.
Основы языка Haskell. Индуктивные определения операций и предикатов, заданных на множествах слов. Натуральная индукция. Полная индукция

    На этом шаге мы дадим определения этих понятий.

    Метод математической индукции (от лат.  inductio -  наведение) - это основной метод доказательства в математике, применяемый для исследования характеристических свойств множеств слов в алфавите.

    Натуральная индукция  - это разновидность метода математической индукции; более точно,  натуральной индукцией называется метод доказательства утверждений в математике, основанный на использовании принципа  (аксиомы) математической индукции.

    Пусть R - некоторое свойство натуральных чисел.

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

    На следующем шаге мы рассмотрим вполне упорядоченное множество.




Содержание Следующий шаг