Garantire l’impossibile

by Massimo Lauria

Introduzione

gli impossibili!

In questo articolo voglio occuparmi del tema dell’impossibilità in un senso molto pratico e “computazionale”: quello legato alla certificazione. Da questo punto di vista possiamo osservare similarità e differenze tra i concetti di impossibilità, necessità, possibilità e falsificabilità.

Questi temi sono fondamentali e possono essere affrontati da moltissimi punti di vista. Per questo ci concentreremo su quello legato alla nozione di “certificato”, che in un certo senso mette insieme i concetti di dimostrazione, calcolo, esempio e controesempio.

Certificare possibilità o impossibilità è l’essenza stessa della computazione e di buona parte della matematica. Oltretutto questo punto di vista apre la strada a considerazioni riguardanti i programmi e l’efficienza computazionale, di cui comunque non tratteremo in questo articolo.

L’articolo non richiede molte nozioni di matematica e non introduce concetti complicati. Spero quindi che sia una gradevole lettura per chiunque che passi da queste parti.

Necessità ed impossibilità

Cosa vuol dire matematicamente che qualcosa è impossibile? Per esempio sappiamo che nella geometria euclidea è impossibile avere un triangolo con due angoli ottusi (i.e. maggiore di 90 gradi). Se denotiamo come P la proprietà di avere due angoli ottusi, possiamo scrivere che

Non esiste triangolo euclideo t per cui P(t) sia vera.

In sostanza stiamo dicendo che nessun membro di un dato insieme di oggetti verifica una certa affermazione. Capire questo tipo di “frasi matematiche” è essenziale per comprendere appieno cosa si intende quando si afferma che qualcosa è possibile/impossibile.

Ora osserviamo le seguenti frasi, stavolta scritte in linguaggio naturale. La prima frase non è altro che una riscrittura dell’esempio precedente.

  1. Nessun triangolo euclideo ha almeno due angoli ottusi;
  2. tutti i triangoli euclidei hanno al massimo un angolo ottuso;
  3. tutti i triangoli euclidei hanno almeno due angoli ottusi;
  4. esiste un triangolo euclideo con almeno due angoli ottusi.

Osserviamo che in queste varianti abbiamo utilizzato i termini esiste, nessuno, tutti. Gli studenti alle prime armi spesso si confondono e superficialmente pensano che dal punto di vista logico l’espressione nessuno sia l’opposto dell’espressione tutti. Niente affatto!

La relazione tra le frasi (1) e (2), e tra le frasi (1) e (3) sono esemplari da questo punto di vista. Le frasi (1) e (2) dicono in effetti la stessa cosa! Il trucco è che nel passaggio dalla frase (1) alla (2) la proprietà da verificare si inverte: se nessun triangolo ha due angoli ottusi allora tutti i triangoli ne hanno al massimo uno. E viceversa. Ma allora qual’è la negazione della frase (1)? Diciamo prima di tutto cosa si intende per negazione logica di una frase matematica.

Consideriamo una frase matematica F(x) che può essere vera o falsa a seconda di cosa sia x. La negazione di F, denotata come \neg F, è quella frase tale che per tutti i valori di x, F(x) è vera se e solo se \neg F(x) è falsa.

Potrebbe essere la (3) la nostra negazione logica? In effetti la frase (3) è falsa, mentre la frase (1) è vera. Tuttavia questo non basta e lo si può vedere con un altro esempio: se dico che un tale ha tutti figli maschi questo fatto diventa falso esattamente quando il tale ha almeno una figlia femmina. Non è necessario che le figlie siano tutte femmine.

E qui finalmente raggiungiamo un punto cruciale. La negazione della frase (1) è infatti la frase (4). La frase (4) non indica una necessità o un’impossibilità, ma indica una possibilità.

Riassumendo, dire che

non “esiste un triangolo con ha due angoli ottusi”,

è quindi equivalente a dire che

tutti i triangoli “non hanno due angoli ottusi”.

Abbiamo visto che la nozione di impossibilità è di fatto è logicamente equivalente a quella di necessità. L’impossibilità di un evento si può esprimere come la necessità della sua negazione.

Confusi? In effetti il modo migliore per visualizzare questi concetti è usare la notazione matematica comunemente adottata. La vedremo insieme più avanti.

Possibilità e falsificabilità

Con ragionamenti simili a quelli visti per impossibilità e necessità si può osservare che anche i concetti di possibilità e di falsificabilità sono legati. Consideriamo le frasi:

  1. esiste un triangolo con due lati uguali (possibilità);
  2. tutti i triangoli hanno lati diversi (necessità);
  3. nessun triangolo ha due lati uguali (impossibilità);
  4. non tutti i triangoli hanno lati diversi (falsificabilità).

La frase (1) esprime la possibilità che un triangolo isoscele esista. Come abbiamo già visto le frasi (2) e (3) esprimono entrambe la negazione di (1), affermando rispettivamente una necessità ed una impossibilità. La frase (4) invece è più interessante, perché esprime direttamente il fatto che una certa proprietà non sia necessaria. Ovvero afferma che questa proprietà può essere falsificata. Quindi

la possibilità di un evento si può esprimere come la falsificabilità del suo opposto.

Quantificatori universali ed esistenziali

Immagino che alcuni dei lettori possano essere confusi da tutto questo circo di cose impossibili, falsificabili e compagnia cantando.

La notazione matematica ci viene in soccorso! Un profano che si avvicini ad un testo matematico spesso viene confuso da simboli strani, pensa che la disciplina sia misteriosa oppure costituita semplicemente da “formule aride” (questa l’ho sentita dire spesso). La notazione in realtà serve per rappresentare in modo schematico dei concetti le cui descrizioni in linguaggio naturale possono risultare prolisse ed imprecise.

In questa sezione introduciamo un minimo di simboli matematici utili a riassumere quanto detto finora. Se però la notazione matematica vi spaventa troppo potete saltare alla prossima sezione, non avrete comunque problemi a leggere il resto.

Predicato: è una formula del tipo P(x) che essenzialmente dice che “l’oggetto x verifica le condizioni espresse da P ”. Un predicato può essere anche costituito dalla composizione di predicati più semplici. Un predicato potrebbe essere “x ha due angoli ottusi”; “x è un numero maggiore di 5”; e così via.

Negazione: se P(x) esprime che x verifica il predicato P, allora \neg P(x) esprime che “x non verifica il predicato P ” oppure che “x verifica il predicato \neg P ”. Se ad esempio P indica “avere almeno due angoli ottusi”, allora \neg  P indica il “non avere almeno due angoli ottusi” o alternativamente “avere al massimo un angolo ottuso”.

Quantificatore universale: \forall x vuol dire “il predicato è vero per ogni x ”. Quindi

\displaystyle      \forall x P(x)

vuol dire che “P è vero per tutti gli x ”.

Quantificatore esistenziale: \exists  x vuol dire “esiste un x per cui il predicato è vero”. Quindi

\displaystyle      \exists x P(x)

vuol dire che “P è vero per almeno un x ”.

Utilizzando questo linguaggio è possibile descrivere facilmente che

  • P è impossibile: \neg \exists x P(x);
  • P è necessario: \forall x P(x);
  • P è possibile: \exists x P(x);
  • P è falsificabile: \neg \forall x P(x).

Abbiamo discusso del fatto che P sia impossibile se e solo se \neg P è necessario. Lo possiamo scrivere così:

\displaystyle      \neg \exists x P(x) \quad \text{ se e solo se } \quad \forall x \neg P(x).

Vale anche che P è falsificabile se e solo se \neg P è possibile. Questo si scrive così:

\displaystyle      \neg \forall x P(x) \quad \text{ se e solo se } \quad \exists x \neg P(x).

Il trucco “sintattico” di questa notazione è che la negazione può essere portata dentro al quantificatore, invertendo il senso del quantificatore stesso (i.e. cambiando \exists in \forall e viceversa).

Dimostrare proprietà universali ed esistenziali

Se non avete letto la parte sulla notazione matematica non fa niente: in sostanza ho ribadito con il linguaggio formale che a noi interessano solo due concetti:

  • Universalità: che cattura sia l’impossibilità che la necessità.
  • Esistenza: che cattura sia la possibilità che la falsificabilità.

Dal punto di vista computazionale e matematico questa distinzione è fondamentale: se si vuole dimostrare una proprietà, il fatto che questa sia universale o esistenziale cambia enormemente le cose.

Come dimostrare che nessun triangolo ha due angoli ottusi? O che un sistema di equazioni non ha soluzione? O addirittura che un programma per computer sia privo di bug? Queste affermazioni non possono essere verificate direttamente perché per farlo si dovrebbe controllare una serie infinita di casi.

Supponete che qualcuno vi voglia convincere che non ci sono triangoli con due angoli ottusi mostrandovi una serie di esempi. Quanti esempi servono per convincervi? Per quanti triangoli vi vengano mostrati nulla esclude che ce ne siano altri con due angoli ottusi che invece vi vengono nascosti. Al contrario per convincersi che un triangolo isoscele esista basta unire i punti (0,1), (1,0) e (0,0) del piano cartesiano.

L’affermazione di una proprietà universale è al di là delle possibilità umane di verifica, perché di norma questa verifica riguarda infiniti casi. Una proprietà esistenziale è invece dimostrabile tramite un singolo esempio.

La possibilità e la falsificabilità di un evento sono certificabili.

L’impossibilità e la necessità di un evento non sono (in generale) certificabili.

Questo per altro è il problema fondamentale delle teorie scientifiche. Nessuna teoria riguardante le scienze naturali può essere dimostrata vera al 100%, tuttavia anche le teorie più robuste o in voga possono essere falsificate da una singola osservazione contraria. È proprio la possibilità di falsificare le affermazioni scientifiche a qualificarle come tali. Per chi fosse interessato a questo problema rimando alla lettura di Karl Popper, che della questione si è occupato approfonditamente.

Universali che possono essere certificati

A volte un universale può essere certificato. Ci sono intere aree di ricerca che poggiano le loro basi sulla possibilita di certificare proprietà universali di certi oggetti matematici.

La stessa matematica (o larga parte di essa) è in un certo senso una serie di certificati di proprietà necessarie o impossibili. Un teorema matematico non è altro che la dimostrazione formale di una di queste proprietà.

Nella maggior parte dei casi un matematico vuole mostrare che ogni oggetto che soddisfa alcuni postulati ha necessariamente determinate caratteristiche. Ovviamente i possibili oggetti che soddisfano questi postulati sono infiniti, quindi la dimostrazione non può essere certo un lungo elenco di verifiche. L’idea è quindi che si utilizzino operazioni di deduzione logica che producano l’affermazione desiderata a partire dai postulati.

Sappiamo che i postulati sono veri per ipotesi. Le operazioni di deduzione sono necessariamente corrette, cioè da ipotesi vere deducono sempre conseguenze vere. Un’affermazione matematica necessaria può essere quindi certificata se viene dimostrata in un sistema logico. La dimostrazione stessa è il certificato, ed è esattamente così che la matematica fa progressi. Leggere una dimostrazione di un teorema è sufficiente per convincersi della sua verità anche se il lettore non è in grado di dimostrare il teorema egli stesso.

La dimostrazione di un teorema matematico è quasi sempre un
certificato per un universale.

La geometria e dall’algebra ci forniscono esempi concreti di proprietà universali certificabili:

  • soluzione di equazioni polinomiali;
  • la programmazione lineare.

Certificati per sistemi di equazioni polinomiali.

Partiamo con delle equazioni polinomiali. Queste hanno la forma

\displaystyle     p(x_{1},x_{2},\ldots,x_{n}) = 0

dove p è un polinomio nelle variabili x_{1},x_{2},\ldots,x_{n}. Ad esempio x_{1}^{2}-2x_{1}x_{2}+x_{2}^{2}=0 è un’equazione polinomiale nelle variabili x_{1} e x_{2}.

È naturale chiedersi: esiste una soluzione per una data equazione? Esistono numeri da sostituire alle variabili in modo che il polinomio valga 0 come richiesto dal’equazione? È chiaro che si sta chiedendo se la proprietà “x è una soluzione” è soddisfacibile.

Più in generale si possono avere tante equazioni polinomiali

\displaystyle     p(x_{1},x_{2},\ldots,x_{n})=0

\displaystyle     q(x_{1},x_{2},\ldots,x_{n})=0

\displaystyle     r(x_{1},x_{2},\ldots,x_{n})=0

sulle variabili x_{1},x_{2},\ldots x_{n}. In questo caso ci si può chiedere se esiste una soluzione comune per queste equazioni, ovvero una sequenza di n numeri che, sostituiti alle variabili, facciano valere zero tutti i polinomi p,q,r,\ldots

In questo caso un certificato di soddisfacibilità è semplicemente una soluzione del’insieme di equazioni. Quello che sorprende è che in effetti esiste anche un metodo per fornire un certificato di insoddisfacibilità!

Se questo certificato non ci fosse, si dovrebbero verificare tutti i possibili (infiniti) modi di sostituire le n variabili con dei numeri. Invece la basta la sequente osservazione: se tutti i polinomi valgono 0 simultaneamente, allora sommandoli o moltiplicandoli per qualche altro polinomio si ottiene sempre un polinomio che vale 0. In particolare sono accettabili combinazioni algebriche del tipo:

\displaystyle     h_{1} \cdot p + h_{2} \cdot q + h_{3} \cdot r,

dove h_{1}, h_{2}, h_{3} sono dei polinomi. Queste combinazioni algebriche preservano tutte le soluzioni comuni di p,q,r

Ma se il polinomio risultante fosse il polinomio costante 1? Questo polinomio non ha soluzione e quindi neppure p,q,r possono avere soluzioni in comune. Visto che h_{1},  h_{2}, h_{3} sono oggetti matematici finiti, questi possono essere descritti e quindi forniscono il certificato di insoddisfacibilità desiderato.

Un famoso teorema detto Hilbert Nullstellensatz (più o meno impropriamente traducibile come “teorema degli zeri”) afferma che

un insieme di polinomiali non ha zeri in comune se e solo se è il polinomio 1 può essere scritto come combinazione algebrica degli stessi.

In sostanza questa combinazioni algebrica può essere facilmente vista come una “deduzione logica” del fatto che da p=0, q=0, r=0 derivi 1=0, ovvero una contraddizione logica.

Esempio: 2x^{2}+x+1=0 e x+1 = 0 non hanno soluzione comune, perché

\displaystyle  -\frac{1}{2} \cdot (2x^{2}+x+1) + \frac{2x-1}{2} \cdot (x+1) = 1

Certificati per sistemi di disuguaglianze lineari

Un discorso simile vale per le disuguaglianze lineari, ovvero delle disuguaglianze della forma

\displaystyle     a_{1} x_{1} + a_{2} x_{2} + \ldots a_{n} x_{n} \leq b

dove a_{i} sono coefficienti noti e x_{i} sono le variabili. In sostanza la soluzione deve essere tale che la somma delle variabili pesata dai coefficienti a_{i} non sia maggiore di b. Qui ci si chiede se una serie di queste disuguaglianze lineari abbiano una soluzione in comune.

Per rispondere a questa domanda osserviamo che si possono effettuare delle operazioni tra disuguaglianze che preservato tutte le soluzioni. Ad esempio sommando uno ad uno i coefficienti di due di esse, se ne ottiene una che ha almeno le stesse soluzioni. Ad esempio una soluzione comune di

\displaystyle     3x + 2y + 5z \leq 10

\displaystyle     5x + y - 2z \leq -3

è anche una soluzione di

\displaystyle     8x+3y+3z \leq 7.

Questo vale anche se si moltiplica una disuguaglianza per un numero positivo (esercizio: perché se si moltiplica per un numero negativo le soluzioni non sono preservate?)

\displaystyle     3x + 2y + 5z \leq 10

implica

\displaystyle     6x + 4y + 10z \leq 20

Per costruzione queste combinazioni positive di disuguaglianze sono soddisfatte dalle soluzioni delle disuguaglianze iniziali. Quindi se si riesce a costruire una disuguaglianza “falsa” come 0\leq -1, si dimostra che il sistema iniziale è impossibile da soddisfare. La cosa grandiosa è che questa “tecnica” può essere applicata a tutti gli insiemi di disuguaglianze insoddisfacibili!

Lemma di Farkas (parafrasi): delle disuguaglianze lineari sono collettivamente insoddisfacibili se e solo se esiste una loro combinazione positiva che produce 0 \leq -1.

Certificati impossibili

I certificati per proprietà universali a volte esistono. Questo è grandioso, specialmente per quelle proprietà che si possono codificare in un programma per computer.

In questo caso fortunato si possono eseguire in parallelo due programmi che cerchino:

  1. un certificato per mostrare che la proprietà è necessaria;
  2. un certificato per mostrare che la proprietà è falsificabile.

Alla fine uno dei due deve per forza terminare dimostrando o falsificando “automaticamente” un teorema. È evidente quindi che la presenza di certificati di impossibilità sia fondamentale nella matematica ma soprattutto nell’informatica e nella logica.

Se il programma (1) trovasse sempre un certificato per ogni proprietà necessaria allora (1) e (2) potrebbero collettivamente automatizzare la matematica. Questo era il sogno dei matematici (e principalmente dei logici) tra la fine del 19° e l’inizio del 20° secolo.

Sappiamo come è andata a finire… i lavori di Gödel e Turing hanno messo una pietra tombale su questa speranza: anche i loro risultati più famosi possono essere visti nell’ottica della non certificabilità di universali.

  • (Gödel) In generale non si può certificare che un’affermazione matematica sia indimostrabile.
  • (Turing) In generale non si può certificare che un programma sia corretto per tutti gli input.

Certificati “impossibili”

Prima di concludere vorrei parlare di una questione che trovo particolarmente interessante. Parlarne in maniera approfondita renderebbe l’articolo estremamente lungo, e perciò evito di farlo. Tuttavia voglio lasciarvi con la curiosità, dandovi eventualmente appuntamento ad un articolo successivo.

Esiste una nozione “quantitativa” di impossibilità.

Che cosa intendo dire con questo? Ritorniamo all’esempio dei sistemi di equazioni polinomiali. Diciamo che ho bisogno utilizzare le soluzioni di un sistema polinomiale in un computer: sicuramente ho bisogno di soluzioni che possano essere rappresentate come numeri di precisione finita, oppure con rappresentazioni compatte; il computer non ha memoria infinita e quindi non può rappresentare numeri arbitrari!

Cosa cambia rispetto a quanto visto finora? Il certificato di insoddisfacibilità per sistemi polinomiali dovuto al Nullstellensatz esclude qualunque soluzione. Se il sistema non ha soluzione tra quelle rappresentabili dal computer ma ne ha altre, questo certificato non esiste. Un certificato banale però esiste sempre:

se lo spazio di potenziali soluzioni è finito, il certificato è semplicemente la verifica delle soluzioni una per una.

Questo tipo di certificazione però non sembra soddisfacente… c’è una bella differenza tra mostrare una specifica soluzione e una verifica esaustiva dello spazio delle soluzioni.

È necessario tener conto dell’efficienza di questi certificati: una soluzione specifica può essere verificata in fretta, e in un certo senso cattura la nostra intuizione per cui un certificato deve essere breve e facile da controllare.

Facciamo un altro esempio. Diciamo che qualcuno afferma di avere scritto il cruciverba più difficile del mondo. Voi sospettate che abbia messo definizioni non completamente coerenti per rendere il cruciverba irrisolvibile. Se volete verificare che il soggetto dica il vero (per esempio in una causa civile) avete due modi per farlo: provare a riempire le caselle in tutti i modi possibili, oppure chiedere a lui di darvi la soluzione. Nessun dubbio su quale sia la soluzione più veloce.

Lo studio della complessità computazionale si occupa anche di questo. Ci sono certificati efficienti e certificati non efficienti (troppo lunghi da ottenere o verificare). Anche qui i concetti di universale e di esistenziale si comportano in maniera duale.

Va detto che trattandosi di calcoli informatici, si è sempre nell’ambito di situazioni finite, che quindi possono sempre essere certificate. Tuttavia certificare una proprietà universale in questo contesto può essere “impossibile” in pratica.

Di questo ne parlerò in un intervento successivo, dove introdurrò lo studio della lunghezza delle dimostrazioni logiche, ed il legame molto diretto con il famoso problema “P vs NP”.

Conclusione

Congratulazioni a chi mi ha seguito/sopportato fino a qui. Spero che la lettura sia stata piacevole e spero che la lezione da imparare sia stata chiara. Riassumendo:

  • l’impossibilità e la necessità non sono altro che due modi di descrivere proprietà universali, mentre la possibilità e la falsificabilità sono proprietà esistenziali.
  • la differenza fondamentale tra i due concetti è la certificabilità. Un universale non sempre è certificabile, al contrario di un esistenziale che è certificabile per definizione.
  • nei casi in cui si può certificare un universale, si ottengono strumenti potenti per il calcolo e per la soluzione di problemi matematici ed informatici.
  • se vogliamo applicare questi concetti a problemi più concreti e applicativi, è necessario ragionare quantitativamente: la lunghezza del certificato, il tempo necessario a verificarlo o a trovarlo sono questioni decisive.

Questo ultimo punto richiede una prospettiva più “informatica” che ci porta direttamente nel mondo della Complessità Computazionale e che ci mette di fronte al problema “coNP vs NP”, che sarebbe un cugino del famoso problema “P vs NP”. Per ora lo lasciamo stare, ce ne occuperemo la prossima volta.

Advertisements