Chi vincerà il mondiale del 2014? Una questione di Logica intuizionista? - Appendice 2

Nell'appendice numero uno dicevamo che tra le principali differenze della Logica intuizionista rispetto alla Logica classica c'è sia la non validità del principio del terzo escluso che la non validità dell'equivalenza tra affermazione e doppia negazione (I ↔ ¬¬I).

Usando quindi gli strumenti della Logica intuizionista, non sì potrà ad esempio dedurre la profezia Italia '14 (P="o l'Italia vincerà il mondiale del 2014 oppure l'Italia non vincerà il mondiale del 2014").
Inoltre, usando l'intuito, molti di voi probabilmente direbbero che affermare che l'Italia vincerà il mondiale del 2014 è equivalente a dire che non è vero che l'Italia non vincerà il mondiale del 2014.
O detto in termini simbolici:

I ↔ ¬¬I

Invece nella Logica intuizionista, dal fatto che l'Italia vincerà il mondiale del 2014 si potrà sì dedurre che non è vero che l'Italia non vincerà il mondiale del 2014 ( I → ¬¬I ), ma non vale il viceversa. Cioè dal fatto che non è vero che l'Italia non vincerà il mondiale del 2014 non si potrà dedurre che l'Italia vincerà il mondiale del 2014 (¬¬I → I).

A questo punto risulta sicuramente interessante vedere molto brevemente qualche cenno di semantica per la Logica intuizionista. È infatti grazie ad essa che possono essere verificate le suddette affermazioni.
Il primo a fornire una semantica per la Logica intuizionista fu Heyting, un allievo di Brouwer.
In modo simile alla semantica per la Logica proposizionale classica, in cui l'algebra booleana viene usata per stabilire se una formula sia vera o falsa, Heyting pensò di introdurre un nuovo tipo di algebra, chiamata in seguito algebra di Heyting, per stabilire se una formula sia vera o falsa nell'ambito della Logica intuizionista.

La Logica proposizionale classica, come la maggior parte dei sistemi di Logica matematica, è costituita da una parte sintattica ed una parte semantica.La parte sintattica è quella che si occupa di definire la corretta struttura delle formule; e nella quale si include di solito anche l'apparato deduttivo che definisce gli assiomi e le regole che consentono di dedurre i teoremi a partire dagli assiomi.
Mentre la parte semantica, che risulta di solito più semplice ed intuitiva, è quella che si occupa di definire il significato dei simboli.

Per definire una semantica della Logica proposizionale classica si può partire ad esempio da una funzione di valutazione che va dall'insieme L delle formule all'insieme {V,F} (vero, falso). O detto in termini più semplici, si definisce un meccanismo per determinare in quali casi una formula sia vera o falsa. La funzione la si definisce nel seguente modo:

v : L → {V,F}

tale che per ogni coppia di formule A e B valgano le seguenti condizioni (sse sta per se e solo se):

v(¬A) = V sse v(A) = F  (¬A è vera sse A è falsa)

v(¬A) = F sse v(A) = V  (¬A è falsa sse A è vera)

v(A∧B) = V sse v(A) = V e v(B) = V  (A∧B è vera sse A è vera e B è vera)

v(A∨B) = V sse v(A) = V oppure v(B) = V  (A∨B è vera sse A è vera oppure B è vera)

v(A→B) = V sse v(A) = F oppure v(B) = V  (A→B è vera sse A è falsa oppure B è vera)

Ciò che collega la sintassi con la semantica sono i teoremi di completezza, il cui scopo è dimostrare l'equivalenza tra il concetto di dimostrabilità sintattica ed il concetto di verità semantica. Nel caso particolare della Logica classica (sia proposizionale che predicativa) interviene il Teorema di completezza di Gödel (da non confondere con il Teoremi di incompletezza di Gödel) ad asserire che una formula è dimostrabile sse è vera per ogni funzione di valutazione.

Similmente, anche nel caso della Logica proposizionale intuzionista si può definire una funzione di valutazione, ma di tipo un po' diverso. Invece di essere correlata ad un'algebra booleana la funzione di valutazione della Logica proposizionale intuzionista è correlata ad un'algebra di Heyting.
Ad esempio si può definire la funzione di valutazione che va dall'insieme L delle formule all'insieme dei sottinsiemi aperti della retta reale:

v : L → {int(S) : S ⊆ R} dove int(S) è la parte interna di S

tale che per ogni coppia di formule A e B valgano le seguenti condizioni:

v(A) = int(v(A))

v(¬A) = int(v(A)^C) dove X^C è il complemento di X

v(A∧B) = v(A) ∩ v(B)

v(A∨B) = v(A) ∪ v(B)

v(A→B) = int(v(A)^C ∪ v(B))

Anche in questo caso intervengono teoremi di completezza a dirci che le formule dimostrabili della Logica intuzionista coincidono con quelle valide e che queste ultime sono esattamente quelle per cui v(A) = R per ogni scelta di v. Cioè quelle a cui la funzione di valutazione associa l'insieme più grande: tutta la retta reale.

Grazie a questi teoremi si può facilmente verificare che la formula ¬(A ∧ ¬A) è valida. Il fatto che questa formula risulti valida è un requisito minimale affinché un sistema di Logica matematica possa destare qualche interesse. Se essa risultasse non valida infatti esisterebbero delle A per cui il sistema potrebbe dimostrare sia A che ¬A. Il sistema risulterebbe quindi contraddittorio.
La validità di ¬(A ∧ ¬A) si può dimostrare in quanto ponendo v(A) = X, indipendentemente dall'insieme X che viene scelto come valore della formula A, il valore di ¬(A ∧ ¬A) sarà sempre uguale all'intera retta reale R. Infatti

v(¬(A ∧ ¬A)) =

int((v(A ∧ ¬A))^C) =

int((v(A) ∩ v(¬A))^C) =

int((X ∩ int((v(A))^C))^C) =

int((X ∩ int(X^C))^C) =

(Siccome int(X^C) è un sottinsieme di X^C allora

X ∩ int(X^C) = ∅)

int((∅)^C)=int(R)=R

Invece si può facilmente mostrare che il principio del terzo escluso (A ∨ ¬A) non è valido. A tal scopo è sufficiente trovare una particolare funzione di valutazione v per cui risulti v(A ∨ ¬A) ≠ R.
Basta scegliere v(A) = {x ∈ R : x > 0 }. Si avrà infatti:

v((A ∨ ¬A)) =

v(A) ∪ v(¬A) =

v(A) ∪ int(v(A)^C) =

{x ∈ R : x > 0 } ∪ int({x ∈ R : x ≤ 0 }) =

{x ∈ R : x > 0 } ∪ {x ∈ R : x < 0 }) =

{x ∈ R : x ≠ 0 } ≠ R che è ciò che si voleva dimostrare

Potremo quindi finalmente concludere che usando gli strumenti della Logica intuizionista, non sì può dedurre la profezia Italia '14.

Ho anche provato a dimostrare che nella Logica intuizionista vale (I → ¬¬I), ma non vale il viceversa (¬¬I → I). Per chi fosse interessato può dare uno sguardo a questo mio tentativo di dimostrazione.

Chi vincerà il mondiale del 2014? Una questione di Logica intuizionista? - Appendice 1

Paolo Rossi e Socrates: storica partita
Italia - Brasile 3 -2 (1982)

Nella precedente discussione dicevamo che prendendo una squadra a caso tra quelle che hanno fatto una pessima figura nella fase finale del mondiale di calcio 2010, come l'Italia ad esempio, potremmo formulare la seguente
profezia Italia '14 (che chiameremo P):


P = "o l'Italia vincerà il mondiale del 2014 oppure l'Italia non vincerà il mondiale del 2014"

O detto in termini simbolici, indicando con I la proposizione Italia '14 ("l'Italia vincerà il mondiale del 2014") potremmo scrivere:

P = (I oppure non-I)

che si può anche scrivere come:

P = (I ∨ ¬I)

Quella che abbiamo appena scritto la si può anche vedere come la formula che descrive in termini simbolici il Principio del terzo escluso. La profezia Italia '14 è quindi un esempio di Principio del terzo escluso. Terzo escluso in quanto la ragione ci porterebbe a dire che non esiste una terza alternativa nell'affermazione "o l'Italia vincerà il mondiale del 2014 oppure l'Italia non vincerà il mondiale del 2014".
Ma è proprio così? Sì può asserire che P = (I ∨ ¬I) è sempre vera? Che non esiste una terza alternativa?

Penso che, a differenza della profezia Maya, nessuno dei membri della comunità scientifica, tranne forse qualche vetero-intuizionista, proverebbe a contraddire la profezia Italia '14...
Certo però che se la profezia Maya dovesse rivelarsi nel frattempo valida....
Bè, in tal caso potremmo forse dire che è vera ¬I, anche se in quel caso nessuno sarà in grado di attestare che l'Italia non ha vinto il mondiale del 2014.
Eppure ci sono stati dei logico-matematici che hanno posto dubbi sulla validità del principio del terzo escluso. L'approccio sostenuto da tali logico-matematici fu definito intuizionismo.
Vediamo quindi con un po' più di precisione che cos'è questo intuizionismo.

Ho già citato il fatto che il mio dialogo immaginario della precedente puntata tra Brouwer e Hilbert è ispirato ad una reale controversia tra i due matematici che va inquadrata tra le appassionanti discussioni di fine '800 primi del '900 relative ai fondamenti della matematica  e che tra le posizioni filosofiche ipegnate nella rifondazione dei fondamenti c'era quella costruttivista con Poincaré e Weyl, all'interno della quale si posizionava la corrente radicale degli intuizionisti con Brouwer.
I costruttivisti, contrapponendosi principalmente al pensiero di Hilbert e dei formalisti, affermavano la necessità di trovare o di costruire un oggetto matematico per poterne dimostrare l'esistenza rifiutando le dimostrazioni per assurdo soprattutto nei casi che coinvolgono l'infinito; inoltre la corrente intuizionista dei costruttivisti, capeggiata da Brouwer (mi sembra quasi di stare a descrivere un partito), si spingeva oltre il costruttivismo rifiutando più in generale le dimostrazioni che implicano l'utilizzo di insiemi infiniti e l'applicazione in questi casi dei ragionamenti basati sul principio del terzo escluso.

Oggi si può probabilmente affermare che l'intuizionismo, come prospettiva filosofica volta a rifondare la matematica, ebbe un successo piuttosto limitato; anche se generò utili e prolifiche discussioni. Tuttavia lo stesso non si può dire per il sistema formale della Logica Intuizionista sviluppato da Arend Heyting, un allievo di Brouwer. Tale sistema formale ha dato luogo infatti ad una serie di sviluppi della Logica e ha trovato inoltre diverse applicazioni nell'informatica, sia teorica che applicata.

Tra le principali differenze della Logica intuizionista rispetto alla Logica classica c'è sia la non validità del principio del terzo escluso che la non validità dell'equivalenza tra affermazione e doppia negazione (I ↔ ¬¬I).
Ovvero, tralasciando per un attimo il rigore matimatico, si può dire che usando gli strumenti della Logica intuizionista, non sì potrà ad esempio dedurre la profezia Italia '14.
Inoltre, usando l'intuito, molti di voi probabilmente direbbero che affermare che l'Italia vincerà il mondiale del 2014 è equivalente a dire che non è vero che l'Italia non vincerà il mondiale del 2014.
O detto in termini simbolici:

I ↔ ¬¬I

Invece nella Logica intuizionista, dal fatto che l'Italia vincerà il mondiale del 2014 si potrà sì dedurre che non è vero che l'Italia non vincerà il mondiale del 2014 ( I → ¬¬I ), ma non vale il viceversa. Cioè dal fatto che non è vero che l'Italia non vincerà il mondiale del 2014 non si potrà dedurre che l'Italia vincerà il mondiale del 2014 ¬(¬¬I → I).

A questo punto risulterebbe sicuramente interessante dare un breve sguardo alla semantica per la Logica intuizionista. È infatti grazie ad essa che possono essere verificate le suddette affermazioni. Ma questo lo vedremo nell'appendice numero due.

Carnevale della Matematica #27

Oggi è il14 luglio e oltre a commemorare la presa della Bastiglia segnaliamo anche la nuova puntata del Carnevale della Matematica, la n. 27, ospitata dal fondatore del Carnevale della Matematica Maurizio Codogno su il Post, il giornale on-line di Luca Sofri.

Il numero degli articoli stavolta è un po' più ridotto, forse a causa del clima e delle vacanze, ma la qualità continua ad essere ottima.
Il mio contributo viene introdotto in questo modo:

Dionisoo nel suo Blogghetto scomoda nientemeno che Brouwer e Hilbert per fare una previsione sul risultato dell’Italia nei prossimi mondiali di calcio del 2014 (profezia dei Maya permettendo), portando il lettore a capire se e come si possono usare le dimostrazioni per assurdo e con insiemi infiniti.

Il 14 agosto, l'edizione ferragostano-vacanzierissima - la numero 28 - del Carnevale della Matematica sarà ospitata da Zar sul blog Gli studenti di oggi.

Calendario con le date delle prossime edizioni del Carnevale

Pagina fan del Carnevale su Facebook

Il ciclo delle notizie scientifiche

Immagine copiata dal post Il ciclo delle notizie scientifiche su D I S . A M B . I G . U A N D O

Grigorij Perelman rifiuta 1 milione di dollari!? La risposta è sì!

Ne avevo parlato qui.
La decisione è stata finalmente presa qualche giorno fa. Grigorij Perelman ha rifiutato 1 milione di dollari!

Pare che la motivazione principale sia stata il disaccordo con la comunità dei matematici: "I don’t like their decisions; I consider them unjust".

Chi vincerà il mondiale? Una questione di Logica intuizionista?

Scegliamo una squadra a caso tra quelle che hanno fatto una pessima figura nella fase finale del mondiale di calcio 2010. L'Italia ad esempio.
Potremmo già formulare un pronostico sui risultati dell'Italia ai modiali brasiliani del 2014?
Bè, potrei affermare ad esempio che:

o l'Italia vincerà il mondiale del 2014 oppure l'Italia non vincerà il mondiale del 2014

Penso che pochi proverebbero a contraddirmi. Ma siamo proprio sicuri che non ci sia un'altra possibilità? O come direbbe qualcuno, siamo proprio sicuri che tertium non datur?

Qualche notte fa dopo una cena a base di insalata di farro annaffiata da un paio di bicchieri di Regaleali me ne sono andato a letto con un certa sensazione di completezza e soddisfazione. In piena notte vengo però svegliato dall'impressione di un lamento profondo. In piedi accanto al mio letto scorgo una tenebrosa figura antropomorfa. Mi pietrifico all'istante. Dalla figura proviene una voce: quasi un infrasuono.
B: (rabbioso tormentato) Perché non vuole ammetterlo!! L'intuzione e la costruzione sono alla base di tutto!
Eppure in gioventù lo ammiravo così tanto.... E anche lui mi stimava molto.
D: (ripresosi dal trauma riesce timidamente a profferire parola) Scusi, ma lei chi è?
B: (austero e marziale) Molto lieto! Luitzen Egbertus Jan Brouwer. Ma lei può chiamarmi semplicemente professor Brouwer.
D: (reverenziale un po' più animato) E di chi sta parlando professor Brouwer?
B: (spazientito) Come di chi!? Ma del professor David Hilbert naturalmente.

Una seconda figura si materializza nella stanza.

H: (con voce tuonante) Ho sentito pronunziare il mio nome!
B: (con enfasi accigliata) Stavo per l'appunto cercando di dire che la nostra aspirazione deve essere la ricerca della verità, non un arido formalismo alieno da essa.
H: (con sufficienza?) Ma con il mio formalismo saremo in grado di svelare e rivelare la verità in modo automatico e univoco. Potremmo anche giungere ad un punto in cui le presenza umana sarà superflua nel processo di disvelamento delle verità ignote.
B: (categorico) Ma voi, caro Hilbert, partite da premesse sbagliate! Per dimostrare l'esistenza di un oggetto io dovrò mostrare quell'oggetto o almeno mostrare di saperlo costruire.
H: (contraddittoriamente) No! Non è affatto vero! La costruzione appesantisce e complica inutilmente le cose. Brevità ed economia di pensiero! Sono queste le ragioni d'essere delle dimostrazioni d'esistenza. L'oggetto o esiste o non esiste. Tertium non datur! E se assumendo la sua non esistenza giungo ad una contraddizione allora vorrà dire che l'oggetto dovrà necessariamente esistere!
B: (quasi con soddisfazione) Ed ecco che abbiamo introdotto anche le più fallaci tra le vostre assunzioni: le dimostrazioni per assurdo e peggio ancora il principio del Terzo escluso. L'accettazione acritica di tali strumenti solo perché riconducibili a Pitagora e Aristotele è inammissibile!
H: (con scoraggiato scherno) Ma proibire ad un matematico l'uso del principio del terzo escluso sarebbe come proibire a un pugile di usare i pugni o proibire ad un astronomo di usare il telescopio. 
B: (in un crescendo di impeto) La matematica non è un giochino enigmistico privo di significato! I suoi oggetti non sono scorrelati dalla realtà!! Le sue regole formali non possono prescindere dall'intuito!!! La scelta dei suoi assiomi deve essere guidata dall'esperienza!!!!

Le figure svaniscono dissolvendosi lentamente.

Ma allora è vero che o l'Italia vincerà il mondiale del 2014 oppure l'Italia non vincerà il mondiale del 2014? O detto in termini simbolici, indicando con I la proposizione "l'Italia vincerà il mondiale del 2014", è vero che (I ∨ ¬I)?

Forse per il caso di questo enunciato la risposta è sì. (A patto che la profezia Maya non non si riveli nel frattempo valida, ma in tal caso potremmo dire che è vera ¬I, anche se probabilmente nessuno sarà in grado di verificarlo.) Nella matematica tuttavia esistono degli enunciati che non possono essere né provati né refutati, e cioè, approssimando un po', non può essere stabilito né che siano veri né che siano falsi, e sono per questo detti indecidibili. Esempi ne sono l'assioma della scelta e l'ipotesi del continuo, che sono entrambi indecidibili nell'assiomatizzazione tradizionale della teoria degli insiemi.

Il mio dialogo immaginario tra Brouwer e Hilbert è ispirato ad una reale controversia tra i due matematici che va inquadrata tra le appassionanti discussioni relative ai fondamenti della matematica avvenute tra la fine dell'800 e i primi decenni del '900. In questo contesto le posizioni filosofiche che si contendevano il primato erano essenzialmente tre: quella logicista con Frege e Russell; quella formalista con Hilbert; e infine quella costruttivista con Poincaré e Weyl, all'interno della quale si posizionava la corrente radicale degli intuizionisti con Brouwer. I logicisti volevano rifondare la matematica a partire dalla Logica, i formalisti volevan formalizzare la matemitica entro un sistema assimoatico capace di dimostrare o refutare un qualsiasi enunciato, mentre i costruttivisti affermavano la necessità di trovare o di costruire un oggetto matematico per poterne dimostrare l'esistenza rifiutando le dimostrazioni per assurdo soprattutto nei casi che coinvolgono l'infinito; infine l'intuizionismo di Brouwer si spingeva oltre il costruttivismo rifiutando più in generale le dimostrazioni che implicano l'utilizzo di insiemi infiniti e l'applicazione in questi casi dei ragionamenti basati sul principio del terzo escluso.

In seguito un allievo di Brouwer, Arend Heyting, sviluppò l'intuizionismo come un vero e proprio sistema formale: la Logica Intuizionista. Ma questo lo vedremo nell'appendice.