Strukturální indukce

Uvažujme množinu definovanou induktivně pomocí nějakých základních pravidel a induktivních pravidel.
Uvažujme vlastnost , která má smysl pro všechny prvky z množiny .
Předpokládejme, že následující předpoklady jsou splněny:

1. Základní krok (ZK): je splněna pro všechny prvky, které jsou do dodány základními pravidly.
2. Indukční krok (IK): Pro každé induktivní pravidlo platí "Jestliže je splněna pro prvky z jeho předpokladu, pak je splněna i pro prvek z jeho závěru."

Potom dle strukturální indukce platí pro všechny prvky množiny .