Математична індукція - це метод доведення математичних тверджень, який полягає у наступному: твердження , яке залежить від натурального параметра , вважається доведеним, якщо доведено і із припущення, що справедливе , доведено справедливість .
Доведення твердження називається першим кроком індукції (базисом індукції), а доведення за припущення справедливості називається індуктивним переходом. При цьому називається параметром індукції, а припущення при доведенні називається індуктивним припущенням.
Нехай – зчисленна множина і для n ÎN
є множина впорядкованих n-членних ланцюгів. Тоді за твердженням 4 і методом (принципом) математичної індукції є зчисленною множиною .