Indukce

Uvažujme množinu prvků, která je vytvořena postupným přidáváním.
Několik prvních je explicitně vyjmenování a dále jsou daná pravidla, jak z již existujících prvků vytvářet nové.

Dále uvažujme nějakou vlastnost , kterou chceme dokázat pro všechny prvky této množiny. Tu dokážeme indukcí, pokud provedeme 2 kroky:

1. Dokážeme, že všechny prvně vyjmenované prvky vlastnost splňují
2. Pro každý prvek vytvořený později pomocí pravidel dokážeme, že pokud vlastnost měly prvky, ze kterých byl vytvořen, pak ji má i on sám.