indukcija

indùkcija (lot. inductio – paskatinimas, įvedimas), samprotavimas, kuriame nuo pavienių faktų einama prie bendresnių. Κai faktų skaičius begalinis, taikoma pilnoji matematinė indukcija: jeigu savybė (predikatas) S yra teisinga, kai skaičius n = 0, ir iš prielaidos, kad S yra teisinga natūraliajam skaičiui n, išplaukia, kad S teisinga natūraliajam skaičiui n + 1, tai savybė S yra teisinga visiems natūraliesiems skaičiams. Ji užrašoma taip: (S(0) & $\forall$n(S(n) → S(n + 1))) → $\forall$nS(n). n vadinamas indukcijos parametru, o jo kitimo aibė šiuo atveju yra natūraliųjų skaičių aibė. Yra ir kitokie matematinės indukcijos variantai, pvz., sustiprintoji indukcija, kuri formuluojama taip: jeigu savybė S teisinga, kai n = 0, ir iš prielaidos, kad S teisinga visiems natūraliesiems skaičiams, ne didesniems už n (n > 0), išplaukia, kad S teisinga skaičiui n + 1, tai savybė S yra teisinga visiems natūraliesiems skaičiams. Jei parametrų kitimo aibėje apibrėžta visiška tvarka ir bet kuriame jos netuščiame poaibyje yra mažiausias nagrinėjamos tvarkos atžvilgiu elementas, tai sustiprintoji indukcija su tokia parametrų kitimo aibe vadinama transfiničiąja. Ją taikant gautas Peano aritmetikos neprieštaringumas, pjūvio taisyklės pašalinamumas klasikiniame sekvenciniame skaičiavime. Ja remiantis t. p. įrodyta, kad primityviai rekursyviųjų funkcijų aibė yra griežtas bendrųjų rekursyviųjų funkcijų poaibis.

35