Indukce

Co je to indukce?

Indukce je zobecnění speciálních případů. Při indukci z opakovaného pozorování, že A a B se vyskytují současně, odvozujeme, že je mezi nimi implikace. Na indukci (generalizaci z příkladů) je založena většina metod strojového učení; tyto metody lze použít pro automatizované získávání znalostí z dat.

Definice principu matematické indukce:

Buď M množina, která má tyto dvě vlastnosti:

1. 1 M,

2. pro každé přirozené číslo p platí: jestliže p M, potom je též p+1 M.

Potom množina M obsahuje všechna přirozená čísla.

Příklad

Zadání: Dokažte, že číslo 2^3k + 3^4k  není pro žádné přirozené číslo k dělitelné číslem 73.

Řešení: pro k=1 věta platí, neboť 2³ + 3⁴ = 89 a  to není dělitelné číslem 73. Pomocná věta (1) je dokázána. Přístupme k důkazu pomocné věty (2). Buď p přirozené číslo a předpokládejme, že 2^3p + 3^4p není dělitelné číslem 73. Vyšetřme číslo 2^3(p+1) + 3^4(p+1). To je rovno

2^3p+3 + 3^4p+4 = 2³ * 2^3p + 3⁴ * 3^4p  = 8 * 2^3p + 81 * 3^4p = 

= 8 * (2^{3p +} 3^4p) + 73 * 3^4p.

 

 První z obou sčítanců není podle indukčního předpokladu dělitelný číslem 73 a druhý je. Součet tedy číslem 73 dělitelný není. 

Při zavedení dobře uspořádaných množin můžeme rozšířit pojem indukce.

Definice dobře uspořádané množiny:

Množina M se nazývá dobře uspořádaná, jestliže každá její neprázdná podmnožina má nejmenší prvek (M množina, a M se nazývá nejmenší prvek, jestliže pro všechna x M:    a x).

Definice principu transfinitní indukce:

Nechť M je dobře uspořádaná množina, V(x) je vlastnost prvků z M. Dále nechť platí:

1. V(x) platí pro nejmenší prvek v M (a₀ nejmenší prvek v M, V(a₀) = 1),

2. z platnosti V(x) pro každé xA(y), kde yM libovolné, plyne i platnost V(y).

Pak V(x) platí pro každé xM.

Podrobnější informace lze nalézt v [1, 18, 4].