una definizione, in un linguaggio, ha due costituenti:

• definiendum: il termine da definire
• definiens: l'espressione o frase che lo definisce

una definizione è ricorsiva quando il definiendum occorre nel definiens

per l'inerente circolarità, una definizione ricorsiva rischia di essere semanticamente viziosa: inutilizzabile al fine di stabilire il significato dei suoi costituenti; tuttavia ...

... si può impedire la formazione di circoli viziosi se il definiendum è un termine parametrico, con un parametro che assume valori in un insieme ben ordinato

• N.B. il significato esatto di questa qualificazione è specificato più avanti

in tal caso, possiamo rendere costruttiva, anziché viziosa, la circolarità in una definizione ricorsiva assicurando che le occorrenze del definiendum nel definiens siano riferite a valori del parametro più piccoli di quello a cui è riferito il definiendum in quanto tale

• una definizione ricorsiva siffatta è, a tutti gli effetti, una definizione induttiva

esempi di costruzioni induttive di largo impiego nella definizione di linguaggi formali, quali ad es. linguaggi logici, linguaggi di programmazione, etc., si hanno nelle definizioni degli insiemi dei termini, formule o espressioni del linguaggio

• tali universi sintattici hanno definizione induttiva in tutti i casi d'interesse pratico

ecco, ad esempio, la definizione induttiva dell'insieme dei termini generato da una segnatura algebrica, ovvero famiglia di operatori, cioè simboli di operazione, dove ogni operatore ha una arietà: il numero di argomenti dell'operazione che esso designa

• quando l'arietà è 0, l'operatore è un simbolo di costante

per una data interpretazione degli operatori quali operazioni di un'algebra (di quelli di arietà 0 quali costanti dell'algebra), un tale termine, essendo privo di variabili, è la descrizione di un calcolo di un valore nell'algebra, a partire da valori costanti

• l'insieme dei termini di complessità 0 è costituito dai simboli di costante
• se ω è un operatore di arietà k>0, e t₁, ..., t_k sono termini di complessità minore o uguale a n ≥ 0, dei quali almeno uno di complessità n, allora ω(t₁, ..., t_k) è un nuovo termine di complessità n+1
• ogni termine ha una complessità, definita induttivamente dalle clausole precedenti

la costruzione induttiva dei termini ben si presta ad introdurre una tecnica di definizione e di dimostrazione molto utile nei linguaggi di programmazione: l'induzione strutturale

supponiamo di voler definire una nuova funzione, o dimostrare che una certa proprietà valga, per tutti i possibili valori assunti da una struttura dati:

• per applicare l'induzione strutturale occorre che ogni valore sia rappresentabile da (almeno) un termine privo di variabili
• ad esempio, per le pile di interi, ogni pila o è vuota (una costante del tipo di dati in questione) o è rappresentabile da un termine push(n, p), dove n è una costante intera e p è un termine rappresentante una pila allo stesso modo

in tali condizioni, l'induzione strutturale consiste nel

• definire o dimostrare per le strutture più piccole, tipicamente costanti del tipo di dati
• definire o dimostrare per le strutture generate dalle operazioni di costruzione del tipo di dati C(t₁, ..., t_k), assumendo di aver già definito o dimostrato per t₁, ..., t_k (ipotesi di induzione)

il principio di induzione strutturale può essere facilmente dedotto dal principio di induzione naturale di Peano, giacché altro non è che induzione naturale sulla complessità dei termini che rappresentano i valori delle strutture dati in gioco

il seguente principio di induzione, al contrario, è una generalizzazione propria del principio di Peano

una relazione binaria su un insieme è un ordinamento stretto se è irriflessiva (cioè non vale mai per una coppia di elementi identici) e transitiva

• se < designa un ordinamento stretto, > designa la sua relazione conversa, anch'essa un ordinamento stretto

un ordinamento stretto < su un insieme S è detto ben fondato, o che S è ben ordinato da <, se non esistono catene discendenti infinite a₀ > a₁ > ... a_n > ..., cioè ogni catena discendente termina

• tecniche di dimostrazione della terminazione di programmi si basano sulla possibilità di poter ben ordinare l'insieme delle sue possibili computazioni

una proprietà P definita per gli elementi di S, strettamente ordinato da <, è detta ereditaria se vale l'implicazione

• (∀y<x P(y)) → P(x)

il seguente principio di induzione è dovuto a Emmy Noether:

• in un insieme ben ordinato, ogni proprietà ereditaria vale in tutto l'insieme

l'ordinamento dei naturali è ben fondato, dal che discende una forma equivalente dell'induzione di Peano (la cui base deriva dalla validità vacua dell'implicazione di ereditarietà sui naturali quando x=0)

non si può invece ricondurre l'induzione noetheriana a quella naturale: l'ordinamento dei naturali è totale, mentre l'induzione noetheriana si applica alla più ampia classe degli ordinamenti parziali (ben fondati)