Mar 062013
 

Data una teoria basata sul linguaggio elementare definito nel post precedente non è difficile determinare se una data formula ben formata sia o meno dimostrabile: lo è se e solo se essa è interamente scomponibile in una giustapposizione di assiomi, scomposizione che in generale non è unica neanche se gli assiomi sono tra loro indipendenti. Per esempio, nella teoria i cui assiomi (indipendenti) sono ${AA,AAA,AAB,ABA}$ la formula $AAAABAAA$ è dimostrabile perché scomponibile come $(AA)(AAB)(AAA)$ o anche come $(AAA)(ABA)(AA)$. Noto qui che sto implicitamente utilizzando come modello delle teorie elencate l’insieme delle stringhe che corrispondono alle sequenze delle formule ben formate, il che mi permette subdolamente di evitare di parlare di modelli identificando impropriamente le formule del linguaggio con gli oggetti del modello stesso, concetto quest’ultimo che qui non mi interessa (noto letteralmente tra parentesi che i numeri binari citati ieri non sono in grado di fungere da modello per queste teorie).

Una caratteristica peculiare di questa classe di teorie è dunque quella di avere sia una semantica che una sintassi completamente determinate: data una qualunque formula ben formata si può immediatamente stabilirne la verità o la falsità utilizzando la corrispondente metateoria e osservando quale sia la prima lettera della relativa sequenza, e si può anche stabilirne la dimostrabilità, sempre nella metateoria, ma in modo meno immediato, osservando se tale sequenza sia o meno interamente scomponibile in assiomi. In parole povere, sto utilizzando un linguaggio tanto primitivo da essere completamente sotto il controllo del proprio metalinguaggio.

Le teorie standard costruite su questo linguaggio sono per definizione basate su insiemi di assiomi tutti semanticamente veri e per costruzione, data la definizione di verità utilizzata, possono dimostrare soltanto formule che sono semanticamente vere, risultando quindi semanticamente consistenti e a fortiori sintatticamente consistenti.

Quanto precede non vale invece per le teorie non-standard, nelle quali almeno uno degli assiomi è semanticamente falso e sono dunque sempre semanticamente inconsistenti, alcune di esse risultano sintatticamente consistenti, come quella esemplificata nel precedente articolo, mentre altre possono non esserlo. Illustro ora tramite un esempio un caso che ho ignorato a bella posta nell’articolo di ieri: considero la teoria i cui assiomi sono ${A, AB, ABBB}$, in essa la formula $ABB$, che non è scomponibile in assiomi, è indimostrabile, come è parimenti indimostrabile anche la sua negazione $BAA$. Tuttavia, mentre non ci sono problemi nell’aggiungere $ABB$ agli assiomi, aggiungervi invece la formula $BAA$ permette di derivare il teorema ${A,BAA} vdash BAAA$ e dunque di contraddire l’assioma $ABBB$ dimostrando la sua negazione, ciò che rende inconsistente anche dal punto di vista sintattico questa estensione non-standard della teoria. Un linguaggio e delle regole di inferenza più potenti avrebbero potuto permettere di dimostrare la formula $ABB$ a partire dagli assiomi ${A, AB, ABBB}$. In una teoria acconciamente potenziata si potrebbe per esempio assumere che la formula $BAA$ sia vera derivandone la suddetta contraddizione e dimostrando dunque per assurdo la negazione dell’assunzione, che è per l’appunto $ABB$, ma né il linguaggio da me utilizzato prevede esplicitamente il concetto di negazione, che è solo metalinguistico, né tra le regole di inferenza ho incluso la dimostrazione per assurdo.

Con i mezzi limitati a disposizione si verifica invece che la teoria ${A, AB}$ può essere estesa assumendo come assiomi indipendenti sia le formule $ABB$ e $ABBB$, prese sia singolarmente che in coppia, che le loro negazioni $BAA$ e $BAAA$, sempre prese singolarmente o in coppia, oppure ancora con la coppia $ABB$ e $BAAA$, ottenendo teorie sintatticamente consistenti in ogni caso. Come rimarcato sopra la coppia di formule $BAA$ e $ABBB$ porta invece a una teoria inconsistente quando aggiunta agli assiomi di partenza.

Esprimendo la stessa costruzione in modo diverso, quando aggiungo alla teoria consistente i cui assiomi sono ${A, AB, ABBB}$ la negazione $BAA$ della formula in essa indecidibile $ABB$ ottengo una teoria sintatticamente inconsistente invece di una teoria non-standard sintatticamente consistente..

Mi pongo ora come problema se sia possibile costruire un insieme di assiomi tale per cui la teoria sia semanticamente consistente e completa, senza tuttavia modificarne l’unica regola di inferenza e senza aggiungerne altre. Consistenza semantica significa che la teoria dimostra soltanto formule vere, mentre la completezza semantica significa che la teoria è in grado di dimostrarle tutte. Aggiungo che completezza sintattica significa che la teoria è in grado di dimostrare ogni formula ben formata o la relativa negazione, cioè che in essa non vi sono formule indecidibili, nessuna delle teorie fin qui elencate è completa dal punto di vista semantico, e neppure da quello sintattico.

È immediatamente chiaro che una tale teoria non può essere costruita utilizzando un insieme finito di assiomi. Pena l’inconsistenza semantica della teoria ogni assioma deve essere vero e dunque iniziare con la lettera $A$, mentre d’altro canto esistono formule vere le cui sequenze contengono un qualunque numero arbitrario di lettere $B$ consecutive. L’unico modo per cui tali sequenze siano dimostrabili, cioè interamente scomponibili in sequenze di assiomi, è che in corrispondenza di ogni numero naturale esista almeno un assioma che contenga dopo la $A$ iniziale il corrispondente numero di $B$ consecutive.

Non è difficile vedere come la teoria che chiameremo $cal{N}$ costruita sullo schema di assiomi ${A, AB, ABB, ABBB, …} = {AB*}$, dove la notazione $B*$ indica una sequenza arbitrariamente lunga di simboli $B$, permetta davvero di dimostrare tutte e sole le formule vere, cioè che essa non è sottoposta ai limiti del teorema di Gödel. Cosa di cui non c’è da stupirsi, dato che tale teoria non è certo in grado di esprimere l’aritmetica ordinaria, che è una delle ipotesi del teorema.

Omettendo uno tra gli infiniti assiomi della teoria un’intera classe di formule vere risulta non dimostrabile, precisamente quella delle formule vere che contengono almeno una sottosequenza che conti esattamente tante $B$ consecutive quante ne sono contenute nell’assioma soppresso e che sia delimitata da un simbolo $A$ a sinistra e dal medesimo simbolo $A$ oppure dal termine della stringa a destra. In particolare omettendo il primo assioma risultano indimostrabili tutte le formule che non contengono il simbolo $B$.

Prendo per esempio in considerazione la teoria in cui venga omesso il terzo assioma $ABB$, in questa teoria tutte le formule vere la cui sequenza contiene esattamente due simboli $B$ consecutivi in almeno una posizione risultano vere e indimostrabili, per esempio $ABABB$, $ABBA$. Nel primo caso non risulta possibile introdurre la negazione della formula tra gli assiomi pena la comparsa di contraddizioni; per esempio da ${cal{N}} cup BABAA – ABB$ si possono dimostrare sia $(BABAA)(A)$ che la sua negazione $(AB)(ABBB)$, mentre nel secondo caso la teoria non-standard ${cal{N}} cup BAAB – ABB$ rimane consistente, per esempio $ABBA$ non vi è dimostrabile.

In tutti i casi in cui viene omesso un insieme di assiomi che non comprende il primo, non è possibile assumere tra gli assiomi la negazione di uno di quelli omessi, pena l’inconsistenza. Sostituendo l’assioma $A$ con $B$, invece, si ottiene comunque una teoria sintatticamente consistente.

Si potrebbe continuare, ma per il momento chiudo qui.

Sorry, the comment form is closed at this time.