Vai al contenuto
Topos Uranos
Italiano

Induzione sui numeri naturali e sulle formule

Riepilogo

Le formule della logica proposizionale sono infinite, e ogni affermazione su tutte esige un metodo che non consista nell’esaminarle una per una. Questa lezione lo costruisce in due piani. Il primo è l’induzione sui numeri naturali, nella sua forma semplice e nella sua forma forte, che si deduce dalla semplice; il secondo è l’induzione sulla complessità delle formule, o induzione strutturale, che si giustifica per induzione forte sulla lunghezza. Con essa si dimostra il lemma del peso della lingua dei cerchi e dei dischi (ogni formula pesa +1+1 e ogni prefisso per parole proprio e non vuoto pesa al più 00), e da esso si deduce che nessuna formula è prefisso proprio di un’altra e, da ciò, la leggibilità unica: ogni formula composta si scompone in un solo modo nel suo disco iniziale e nelle sue due componenti. La leggibilità unica legittima, infine, le definizioni ricorsive sulle formule (lunghezza, numero di variabili e di dischi connettivi, sottoformule, profondità) e la sostituzione di una sottoformula con un’altra.

Obiettivi di apprendimento

  1. Dimostrare per induzione semplice e per induzione forte proprietà dei numeri naturali, verificando il caso base e individuando il difetto di un’induzione scorretta.
  2. Dimostrare che tutte le formule hanno una proprietà per induzione sulla loro complessità, trattando le variabili e l’unica regola di formazione come gli unici casi.
  3. Dimostrare il lemma del peso e dedurne che nessuna formula è prefisso proprio di un’altra e che ogni formula composta è univocamente leggibile.
  4. Definire funzioni sulle formule per ricorsione (lunghezza, profondità, sottoformule, sostituzione) e dimostrare per induzione relazioni tra di esse.

Affermazioni su tutte le formule

Nella lezione sul linguaggio della logica proposizionale si sono costruite le formule a partire da due simboli, ∘\sigO e ∙\sigI, che chiamiamo cerchio e disco, e da una sola regola di formazione. Le formule sono infinite, e molte delle affermazioni che contano si riferiscono a tutte: che ogni formula termina con un disco, che nessuna formula si legge in due modi, che in ogni formula c’è una variabile in più dei dischi connettivi. Tali affermazioni non sono formule del linguaggio che studiamo, ma enunciati su di esso, formulati nel metalinguaggio (l’italiano, aiutato dalla notazione matematica); la loro dimostrazione non è, quindi, una deduzione all’interno di un sistema formale, ma un ragionamento matematico ordinario il cui oggetto è il sistema formale. Per questo si chiamano dimostrazioni metateoriche o esterne.

Ora, nessuna quantità di esempi verificati dimostra un’affermazione su infiniti oggetti. Ne segue che occorre un principio che permetta di concludere, da un numero finito di verifiche, che una proprietà vale in infiniti casi. Questo principio è l’induzione. Si presenta prima sui numeri naturali, dove è più familiare, e poi sulle formule, dove si appoggia sulla precedente. Lo stesso strumento dimostrerà, nell’unità di metateoria, la correttezza e la completezza del sistema deduttivo.