Il principio di induzione è un metodo dimostrativo che si basa sulle proprietà dell'insieme dei numeri naturali, in particolare il fatto che abbia un numero iniziale che è lo zero e tutti i numeri hanno un successivo .
Teorema
Sia un numero naturale e per ogni maggiore o uguale a sia un predicato (cioè una formula), se è vera e è vera, allora si può affermare che è vera per ogni numero naturale: