Definibilita

Enciclopedia della Matematica (2013)

definibilita


definibilità termine che designa uno dei principali oggetti di studio della logica matematica, insieme con la dimostrabilità e la calcolabilità; consiste in una riflessione sul concetto di definizione rigorosa degli enti matematici. Alla fine del xix secolo D. Hilbert aveva proposto una riorganizzazione di tutta la matematica su basi assiomatiche. Ogni teoria matematica doveva essere dotata di un proprio sistema di assiomi, a partire dai quali dimostrare, con le regole di deduzione della logica, ogni proposizione della teoria. In questo contesto nacque lʼopera Fondamenti di geometria (Grundlagen der Geometrie, 1899), in cui Hilbert si proponeva di dare una sistemazione assiomatica alla geometria euclidea; unʼimpresa analoga avevano tentato per lʼaritmetica G. Peano (assiomi di Peano) e R. Dedekind. Il programma hilbertiano prevedeva che ogni teoria fosse intrinsecamente coerente, quindi incapace di generare proposizioni contraddittorie: ciò al fine di fondare la matematica su basi logiche al riparo da ogni contraddizione. La speranza di realizzare tale obiettivo venne meno con la cosiddetta crisi dei fondamenti della matematica e in particolare con la scoperta di molti paradossi e antinomie fra cui lʼantinomia di Russell del 1902, lʼantinomia di Richard del 1905, lʼantinomia di Berry del 1906. Queste ultime due antinomie sono alla base della riflessione sul tema della definibilità.

Lʼantinomia di Richard si basa sul fatto che alcune frasi della lingua naturale designano un numero reale; per esempio, nella lingua italiana la frase «lʼunico numero positivo che elevato al quadrato dà come risultato 2» designa il numero reale √(2). Inoltre tutte le frasi di una lingua, per esempio le frasi italiane, possono essere ordinate nel seguente modo:

• le frasi di n caratteri precedono tutte le frasi che hanno un numero maggiore di caratteri;

• le frasi con lo stesso numero di caratteri possono essere ordinate secondo un ordinamento lessicografico, come in un vocabolario.

In questo modo tutte le frasi che indicano numeri reali vengono ordinate: basta eliminare, dallʼordinamento precedente, tutte quelle che non indicano tali numeri. Il numero n-esimo dellʼelenco così costruito è detto n-esimo numero di Richard. Ora si consideri la frase «il numero reale la cui n-esima cifra decimale è 1, se lʼn-esima cifra decimale dellʼn-esimo numero di Richard non è 1, e la cui n-esima cifra decimale è 2, se lʼn-esima cifra decimale dellʼn-esimo numero di Richard è 1». Questa frase definisce un numero di Richard che non è compreso nellʼelenco precedente. Eppure lʼelenco costruito avrebbe dovuto essere esaustivo, cioè contenere tutti i numeri di Richard. Lʼantinomia di Richard pone, quindi, un problema di definibilità. Tuttavia questo aspetto non venne subito considerato nella sua importanza dalla comunità matematica; in particolare G. Peano ed E. Zermelo rifiutarono il concetto di definibilità come non matematico: Zermelo affermò, infatti, che lʼesempio di Richard non ha un interesse matematico, ma solamente un interesse di tipo linguistico.

Analogamente, lʼantinomia di Berry – dal nome di G.G. Berry (1867-1928), un bibliotecario dellʼuniversità di Oxford, che la formulò in una lettera a B. Russell – si basa sulla considerazione che in una lingua naturale, per esempio la lingua italiana, si possono costruire solo un numero finito di espressioni contenenti meno di sessanta sillabe; fra queste espressioni, alcune definiscono dei numeri interi positivi. Sia k «il più piccolo numero intero positivo che non è definito da unʼespressione della lingua italiana contenente meno di sessanta sillabe». La contraddizione deriva dal fatto che la frase virgolettata contiene meno di sessanta sillabe e definisce il numero k.

La riflessione sul tema della definibilità prende le mosse dalle antinomie riportate e viene estesa ad aree di ricerca contigue, quali per esempio la teoria della calcolabilità, la teoria degli insiemi e lʼinformatica teorica. Per quanto riguarda lʼinformatica teorica, il concetto di definibilità è alla base dello studio matematico dei linguaggi formali e diventa importante nel momento in cui la possibilità di studiare un linguaggio da un punto di vista matematico viene sancita dalla tecnica di gödelizzazione ( Gödel, numero di) tramite la quale è possibile esprimere interamente, in un linguaggio formale, affermazioni riguardanti il linguaggio stesso. Nella teoria degli insiemi, invece, lʼesigenza di definire in maniera rigorosa e non contraddittoria gli enti matematici fondamentali nasce in seguito alla contraddizione rilevata da Russell nel concetto di «insieme» così come esposto da G. Frege nel suo Grundgesetze der Arithmetikbegriffsschriftlich abgeleitet (I principi dellʼaritmetica derivati secondo lʼideografia, 1893). Per evitare i paradossi insiti nella teoria degli insiemi, dovuti allʼadozione del principio di comprensione, vengono proposte teorie quali la teoria dei tipi di Russell e la teoria assiomatica degli insiemi elaborata da Zermelo nel 1908 e poi ulteriormente sviluppata grazie allʼapporto di J. von Neumann, A. Robinson, P. Bernays e K. Gödel ( Zermelo-Fraenkel, teoria di). Vi sono, inoltre, alcune teorie ibride che combinano aspetti della teoria dei tipi con la teoria assiomatica degli insiemi, come il sistema nf (New Foundation) di W.V. Quine.

Vicina al tema della definibilità è anche la riflessione sulla calcolabilità e la ricerca di una definizione rigorosa del concetto di funzione calcolabile; la risposta a questa esigenza è fornita dallʼintroduzione di alcuni modelli di calcolo come la macchina di Turing, le funzioni ricorsive e il λ-calcolo ( lambda-calcolo).

TAG

Teoria della calcolabilità

Antinomia di → russell

Numeri interi positivi

Macchina di → turing

Teoria degli insiemi