31 marzo 2018

Grundlagenstreit, parte I. Formalismo e intuizionismo.

Nessuno potrà cacciarci dal paradiso che Cantor ha creato per noi
(D. Hilbert)

Nel 1899, D. Hilbert aveva pubblicato il suo fortunato libro sui fondamenti della Geometria [H99]. In esso, oltre a dare un risistemazione logica al contenuto degli Elementi di Euclide che ne correggeva le imprecisioni, egli presentava la sua visione della materia, che poteva essere racchiusa in una parola: formalismo.

Ogni teoria può essere applicata a infiniti sistemi di enti fondamentali”, spiegava Hilbert illustrando il carattere assiomatico della nuova matematica. Per la geometria usava una battuta fortunata: “Invece di punti, rette, piani dobbiamo ugualmente poter dire tavoli, sedie, boccali di birra[L16]. In altre parole, e in aperto contrasto con la visione platonista della disciplina, ciò che definisce una teoria non è l'"essenza" degli oggetti matematici, ma solo gli assiomi che essi soddisfano.

L'impostazione filosofica di Hilbert era ben chiara fin dai suoi primi lavori sulla teoria degli invarianti (1888), nei quali aveva dimostrato l'esistenza di un sistema finito di generatori per l'anello degli invarianti delle forme $n$-arie in un qualsiasi numero di variabili per mezzo di un procedimento puramente esistenziale e non costruttivo, che aveva incontrato (almeno all'inizio) l'opposizione dei matematici più tradizionalisti come P. Gordan e L. Kronecker. Quest'ultimo era anche un acerrimo avversario della teoria degli insiemi di Cantor e un propugnatore di una filosofia costruttivista, opposta a quella formalista di Hilbert, che era sintetizzata dalla sua famosa frase "Dio ha creato i numeri naturali, tutto il resto è opera dell'uomo". Per Kronecker, la dimostrazione per assurdo con cui Cantor aveva dimostrato che $\mathbb{R}$ non è equipotente a $\mathbb{N}$ era pura eresia.

Kronecker morì nel 1891, dunque il suo ruolo diretto nelle vicende che seguono fu marginale; tuttavia, le sua posizioni vennero adottate e sistematizzate dalla scuola intuizionista, il cui fondatore e principale apostolo fu il famoso matematico olandese L. E. J. Brouwer (1881-1966).


L.E.J. Brouwer
Giovanissimo, Brouwer aveva ottenuto fama internazionale per i suoi profondi risultati in Topologia, fra i quali il Teorema di Punto Fisso che oggi porta il suo nome, il Teorema di Invarianza della Dimensione e quello di Invarianza del Grado Topologico, che gli avevano permesso a soli 31 anni di essere eletto membro della Royal Netherlands Academy of Arts and Sciences.

Brouwer raccolse il testimone di Kronecker e, con la sua filosofia intuizionista, si oppose fermamente al formalismo di Hilbert e dei suoi collaboratori P. Bernays, W. Ackermann e J. von Neumann. Semplificando al massimo, si può dire che l'intuizionismo si opponeva all'uso del principio del terzo escluso in logica ("non è possibile che due proposizioni contraddittorie siano entrambe non vere") in ogni ragionamento che coinvolgesse insiemi infiniti. In particolare, la scuola intuizionista considerava non valide le dimostrazioni non costruttive che sfruttavano la tecnica per assurdo, come ad esempio il procedimento diagonale di Cantor e la dimostrazione di Hilbert del suo Teorema della Base.

Come ci si può aspettare, le posizioni filosofiche di Brouwer vennero accolte con irritazione da Hilbert e dalla sua scuola (a parte H. Weyl, che ne fu invece affascinato, con sdegno del suo maestro). Hilbert affermò con veemenza che "impedire ad un matematico di usare il principio del terzo escluso è come impedire ad un pugile di usare i pugni", e che l'intuizionismo rischiava di privare la matematica di molti dei suoi risultati più importanti e di farla precipitare nella barbarie.

Un aneddoto famoso narra di Brouwer che, invitato a tenere un seminario a Gottinga, affermò (per dare un esempio delle posizioni intuizioniste) che non si può sapere se esiste una stringa di dieci $9$ consecutivi nello sviluppo decimale di pi greco, finché tale stringa non venga effettivamente trovata mediante il calcolo dello sviluppo stesso. Qualcuno del giro di Hilbert obiettò "Magari noi non lo possiamo sapere, ma Dio si!", al che Brouwer replicò seccamente "Non dispongo di una linea diretta con Dio" [R70].

Sia Hilbert che Brouwer avevano una forte e carismatica personalità, ed entrambi erano sinceramente convinti che dalla vittoria della loro posizione dipendessero il destino e la salvezza della Matematica. La guerra esplose nel 1928, quando Hilbert portò il conflitto sul piano personale, decidendo che le loro differenze erano tali che non potevano più lavorare insieme. Pertanto si adoperò per estromettere Brouwer dall'Editorial Board dei Mathematische Annalen, di cui lui era Managing Editor. Era il culmine della cosiddetta Grundlagenstreit, la "disputa sui fondamenti" [continua].

Riferimenti:

[H99] D. Hilbert: Grundlagen der Geometrie (1899)
[L16] G. Lolli: Tavoli, sedie, boccali di birra (David Hilbert e la matematica del '900), Cortina editore (2016).
[R70] C. Reid: Hilbert, Springer (1970)

20 marzo 2018

Il teorema dei Quattro Colori

Immaginiamo di avere una mappa piana costituita da un numero finito di regioni. Quanti colori sono al massimo necessari per colorarla in modo che due regioni adiacenti (cioè, con un confine in comune) non abbiano lo stesso colore?

Non è difficile costruire una mappa che necessita di quattro colori: si pensi ad una mappa costituita da un cerchio centrale e una corona circolare divisa in tre parti uguali intorno ad esso, come nella figura sotto: 


Una mappa che necessita di quattro colori (a sinistra) e il corrispondente grafo duale (a destra)

Sorge dunque naturale il seguente
Problema dei quattro colori. E' sempre possibile colorare una mappa piana con quattro colori, in modo che due regioni adiacenti abbiano colore differente? Oppure esiste una mappa che necessita di almeno $5$ colori? Equivalentemente, è vero che il numero cromatico del grafo duale di una mappa piana è sempre minore o uguale a $4$?
Si potrebbe pensare che l'origine del problema risalga allo studio della cartografia, ma in realtà le carte geografiche che necessitano di quattro colori sono piuttosto rare (tre colori bastano quasi sempre), e non si è trovata traccia di esso in nessun libro antico sull'argomento. L'origine del Problema dei Quattro Colori sembra in realtà risalire a F. Guthrie, uno studente ad Edimburgo che lo enunciò nel 1852. Guthrie ne parlò al suo insegnante A. De Morgan, il quale ne scrisse a sua volta come segue:

"A student of mine [Guthrie] asked me to day to give him a reason for a fact which I did not know was a fact—and do not yet. He says that if a figure be any how divided and the compartments differently colored so that figures with any portion of common boundary line are differently colored—four colors may be wanted but not more—the following is his case in which four colors are wanted. Query cannot a necessity for five or more be invented…"

Nel 1879, A. Kempe pubblicò una dimostrazione del Teorema dei Quattro Colori [K1879]. L'argomento di Kempe venne ritenuto corretto fino al 1890, quando P. J. Heawood scoprì al suo interno un errore fatale. I tentativi di Heawood di riparare la dimostrazione di Kempe non ebbero successo, tuttavia egli riuscì ad adattarne le tecniche per far vedere che cinque colori sono sempre sufficienti [H1890].

Dopodiché, molti matematici famosi si cimentarono nella dimostrazione del Teorema dei Quattro Colori, ma tutti i loro tentativi furono votati al fallimento. Nella sua biografia di D. Hilbert, C. Reid narra di H. Minkowski che (in un raro moto di arroganza) sostenne durante il suo corso di topologia a Goettingen che per un matematico di prim'ordine come lui ci sarebbe voluto ben poco per produrre una dimostrazione, salvo ritrattare poche settimane dopo spiegando che il suo argomento era fallace e che "il Cielo aveva punito la sua boria". Analogamente, nella sua autobiografia "Ex-prodigy", il pioniere della cibernetica N. Wiener descrive il suo sgomento nel vedere la dimostrazione da lui fornita "sbriciolarsi davanti ai suoi occhi" [Gard3].

La cosa era resa ancora più frustrante dal fatto che, paradossalmente, si conosceva la risposta per mappe disegnate per superfici in apparenza più complicate del piano, come il toro (dove sette colori sono necessari e sufficienti per colorare ogni mappa), la bottiglia di Klein, il nastro di Moebius o il piano proiettivo (dove sei colori sono necessari e sufficienti).

La dimostrazione del Teorema dei Quattro Colori arrivò nel 1976, ad opera di K. Appell e W. Haken [AH77]. Oltre che per il risultato in sé, la dimostrazione di Appell e Haken è storicamente importante in quanto si tratta del primo enunciato di rilievo dimostrato con l'ausilio del computer. La strategia della prova, infatti, consiste dapprima in un lungo e difficile procedimento di riduzione del problema originario ad un problema finito, che coinvolge $1936$ mappe. Tali mappe vengono poi analizzate una per una con l'aiuto del calcolatore, facendo vedere che ognuna di esse può essere colorata con quattro colori e deducendo da ciò che ogni mappa piana ha la stessa proprietà.

Siccome era impossibile verificare a mano i calcoli di Appell e Haken, molti matematici avanzarono dubbi sulla validità del metodo usato, o per lo meno lo trovarono insoddisfacente dal punto di vista epistemologico. Addirittura, il New York Times rifiutò di pubblicare un articolo sulla dimostrazione, temendo che potesse essere sbagliata come molte altre annunciate in precedenza.

Nel 1996, N. Robertson, P. Sanders, P. Seymour e R. Thomas diedero una nuova dimostrazione, basata sulle stesse idee di quella di Appell e Haken ma più efficiente, in quanto richiedeva l'analisi di "sole" 633 configurazioni. Ancora una volta, però, risultò impossibile verificare con carta e penna tutti i passaggi, e si dovette ricorrere al computer [RSST97].

Infine, nel 2005, B. Werner and G. Gonthier hanno implementato la dimostrazione del Teorema dei Quattro Colori nel linguaggio di programmazione (o, meglio, "theorem proving software") Coq, verificando la validità di ciascuno dei passi che la compongono [Gon08].

Riferimenti:

https://en.wikipedia.org/wiki/Four_color_theorem

http://mathworld.wolfram.com/Four-ColorTheorem.html

[AH77]
K. Appel; W. Haken: Solution of the Four Color Map Problem, Scientific American, 237 (4), pp. 108–121 (1977)
[Gard3] M. Gardner: Enigmi e giochi matematici, vol 3.
[Gon08] G. Gonthier: Formal Proof—The Four-Color Theorem, Notices of the American Mathematical Society 55 (11), pp. 1382-1393 (2008).
[H1890] P. J. Heawood: Map-Colour Theorem, Quarterly Journal of Mathematics 24, 332–338 (1890).
[K1879] A. B. Kempe (1879): On the Geographical Problem of the Four Colours, American Journal of Mathematics  2 (3): 193–220.
[RSST97] N. Robertson; D. Sanders; P. Seymour; R. Thomas: The Four-Colour Theorem, J. Combin. Theory Ser. B 70 (1), pp. 2–44 (1977)doi:10.1006/jctb.1997.1750,

10 marzo 2018

Harald Bohr: teoria dei numeri e nazionale di calcio

Harald Bohr (Copenhagen, 1887 - Gentofte, 1951) era il fratello minore del fisico teorico Niels Bohr, Premio Nobel 1922 per i suoi fondamentali contributi alla Meccanica Quantistica.

Anche se meno conosciuto rispetto al celeberrimo fratello, Harald ebbe una carriera scientifica di tutto rispetto. Infatti fu un famoso matematico, professore all'Università di Copenhagen e noto per le sue ricerche in Teoria Analitica dei Numeri (funzioni quasi-periodiche, distribuzione degli zeri della funzione zeta di Riemann), che portarono a collaborazioni con mostri sacri del campo come E. Landau e G. Hardy. Uno dei suoi risultati più famosi è il
Teorema di Bohr-Mullerup: La funzione Gamma di Eulero può essere caratterizzata come l'unica funzione analitica $f$ definita su $x>0$ e avente le seguenti proprietà:
$\bullet$  $f(1)=1$
$\bullet$ $f(x+1)=xf(x)$
$\bullet$ $f$ è logaritmicamente convessa (cioè, $\log(f(x))$ è convessa).
Un altro suo importante contributo è il Teorema di Bohr-Landau, una versione debole dell'Ipotesi di Riemann che afferma che "quasi tutti" gli zeri della funzione Zeta sono contenuti in una piccola striscia verticale centrata sulla retta critica $\mathrm{Re}(z)=1/2$.

Ciò che rende peculiare la carriera di H. Bohr è tuttavia il fatto che è stato l'unico matematico professionista a vincere una medaglia alle Olimpiadi come membro della nazionale di calcio del suo paese. Infatti Bohr era un eccellente attaccante, che debuttò in prima divisione danese nel 1903, a soli 16 anni (per un breve periodo giocò insieme al fratello Niels, che era un buon portiere). Nell'era di Sky e del calcio miliardario è una cosa impensabile, ma all'epoca si potevano ottenere risultati sportivi di rilievo limitandosi a giocare a pallone nel proprio tempo libero.

Nel 1908, venne selezionato per la nazionale olimpica che doveva partecipare ai Giochi di Londra dello stesso anno. In semifinale la Danimarca battè la Francia per 17-1, punteggio che costituisce ancora oggi un record olimpico. In finale la Danimarca perse 2-0 con l'Inghilterra, ottenendo quindi la medaglia d'argento.

L'ultima partita giocata da Bohr in nazionale fu nel 1910. Nello stesso anno discusse la sua tesi di dottorato: le cronache dell'epoca narrano che la sua popolarità come calciatore era tale che in aula si contavano più tifosi che matematici.

Oltre che come matematico e atleta, H. Bohr si distinse anche per il suo impegno a favore di diritti umani. Egli stesso di origine ebraica da parte di madre, fu profondamente disgustato dalle politiche antisemite del regime hitleriano e si adoperò per aiutare i matematici ebrei tedeschi a fuggire dalla Germania. Nel 1934 uscì un articolo a sua firma, pubblicato sul giornale danese Berlingske Aften, che criticava le posizioni filo-naziste del matematico L. Bieberbach.

H. Bohr univa a grandi qualità scientifiche notevoli capacità didattiche, che lo rendevano molto amato dai suoi studenti. Ancora oggi, in suo onore, il premio annuale per l'eccellenza nell'insegnamento attribuito dall'Università di Copenhagen è chiamato "The Harald".

Ulteriori particolari sulla vita e l'opera di Bohr si possono trovare nella sua biografia sull'archivio MacTutor.

Harald Bohr (a sinistra) col fratello Niels (a destra) in una foto giovanile.

05 marzo 2018

L'Ipotesi del Continuo

Nel 1874, G. Cantor aveva introdotto la sua celebre nozione di cardinalità, definendo due insiemi "equipotenti" quando è possibile stabilire una corrispondenza biunivoca fra essi. Era l'inizio di un modo radicalmente nuovo di pensare l'infinito, che avrebbe rivoluzionato i fondamenti della Matematica.

Due insiemi finiti sono equipotenti se e solo se contengono lo stesso numero di elementi, in particolare nessun insieme finito è equipotente ad un suo sottoinsieme proprio. Per insiemi infiniti, invece, la cosa è molto più sottile. Ad esempio, è immediato verificare che l'insieme $\mathbb{N}$ dei naturali è equipotente al sottoinsieme $2 \mathbb{N}$ dei numeri pari, tramite la funzione che associa ad ogni numero il suo doppio. Non è inoltre difficile dimostrare che $\mathbb{N}$ è anche equipotente a $\mathbb{Q}_+$, l'insieme dei numeri razionali positivi: basta enumerare questi ultimi ordinandoli in base alla somma del numeratore e denominatore come segue: $$\frac{1}{1}, \, \frac{1}{2}, \, \frac{2}{1}, \, \frac{1}{3}, \, \frac{2}{2}, \, \frac{3}{1}, \, \frac{1}{4}, \,   \frac{2}{3}, \frac{3}{2}, \, \frac{4}{1}, \cdots$$ Una semplice modifica di questa procedura mostra inoltre che $\mathbb{N}$ è equipotente a $\mathbb{Q}$, l'insieme di tutti i numeri razionali.

Al contrario, non è possibile mettere in corrispondenza biunivoca $\mathbb{N}$ con $\mathbb{R}$, l'insieme dei numeri reali. Per dimostrare questo fatto, Cantor utilizzò un metodo di dimostrazione per assurdo noto come procedimento diagonale. L'idea è quella di associare ad ogni numero reale il suo sviluppo decimale: allora, se i reali potessero essere numerati in una lista, potremmo scegliere un numero reale $r$ la cui prima cifra decimale è diversa dalla prima cifra del primo numero della lista, la seconda cifra decimale è diversa dalla seconda cifra del secondo numero e così via. Ciò implica che $r$ non è contenuto nella lista, contraddizione.

La domanda che ora sorge naturale, e che è il contenuto del primo problema presentato da D. Hilbert al congresso di Parigi del 1900, è la seguente:
Esiste un insieme la cui cardinalità sia strettamente compresa fra quella di $\mathbb{N}$ e quella di $\mathbb{R}$, cioè fra il "numerabile" e il "continuo"?
Il problema (o meglio la congettura che tale insieme non esistesse) divenne noto come Ipotesi del Continuo, e si guadagnò subito lo status di fondamentale questione aperta della Teoria degli Insiemi. Lo stesso Cantor comprese la sua importanza e vi lavorò a lungo, senza risultati.

La prima risposta parziale venne ottenuta nel 1940 da K. Gödel, il logico viennese che sette anni prima aveva stupito la comunità matematica con i suoi celebri Teoremi di Incompletezza. Egli dimostrò che, restringendosi ad una particolare classe di insiemi noti come "insiemi costruibili", si ottiene una teoria che verifica gli assiomi di Zermelo-Fraenkel e l'Assioma di Scelta (ZFC) e nella quale è anche valida l'Ipotesi del Continuo, deducendo che quest'ultima è consistente con ZFC. In altre parole, l'Ipotesi del Continuo non può essere confutata in ZFC, che è l'assiomatizzazione "standard" della teoria degli insiemi.

Il (difficile) passo successivo venne compiuto nel 1963 da P. Cohen. Quest'ultimo sviluppò una particolare tecnica dimostrativa, detta forcing, che permette di allargare la classe degli insiemi costruibili ad una classe più ampia, verificante ZFC ma non l'Ipotesi del Continuo. Come conseguenza, segue che
L'Ipotesi del Continuo non è dimostrabile in ZFC, e utilizzando il precedente risultato di Gödel si deduce quindi che essa è indecidibile in ZFC.


P. Cohen (fonte: Wikipedia)

Per questa sua spettacolare scoperta, Cohen ottenne la medaglia Fields al Congresso Internazionale di Mosca del 1966. Nel 2006, poco prima della sua morte, egli tenne una conferenza a Vienna in occasione dei cento anni dalla nascita di Gödel, nella quale descrisse la sua soluzione al problema del continuo. Il video della conferenza è disponibile online su YouTube.

Riferimenti:


https://en.wikipedia.org/wiki/Continuum_hypothesis


http://mathworld.wolfram.com/ContinuumHypothesis.html

P. J. Cohen: The Independence of the Continuum Hypothesis, Proc. Nat. Acad. Sci. USA. 50, 1143-1148, 1963.

K. Gödel: The Consistency of the Continuum-Hypothesis. Princeton, NJ: Princeton University Press, 1940.

P. Odifreddi: La matematica del Novecento. Einaudi, 2000