(b. St. Louis, Missouri, 8 dicembre 1919; d. Berkeley, California, 30 luglio 1985), matematica, logica matematica, teoria dei numeri, problemi decisionali, definibilità.
Il lavoro matematico di Robinson mostra potenza e fascino. Ha affrontato problemi difficili e si è sforzata per soluzioni eleganti. La sua vita e il suo lavoro non possono essere visti correttamente senza notare che come donna in un campo dominato dagli uomini, era una sorta di pioniera. Il suo métier è stato l’interfaccia tra due rami della matematica, la logica e la teoria dei numeri, di solito pensato di avere poco a che fare con l’altro. È particolarmente nota per i suoi contributi alla soluzione del decimo problema in una famosa lista di ventitré proposte dal matematico David Hilbert nel 1900. È stata eletta alla National Academy of Sciences e anche alla presidenza della American Mathematical Society, in entrambi i casi la prima donna matematica ad essere così onorato, ed è stato anche un destinatario di una borsa di studio MacArthur.
Primi anni di vita Nata Julia Bowman, ha subito due calamità presto nella vita. Aveva solo due anni quando sua madre morì, lasciando suo padre a far fronte a Julia e sua sorella maggiore Constance. Dopo il suo nuovo matrimonio, la famiglia si trasferì ad ovest, in ultima analisi, a San Diego, dove la sua sorellastra Billie è nato. Quando Julia aveva nove anni subì una malattia devastante: la scarlattina seguita dalla febbre reumatica. Ha perso due anni di scuola e ha subito danni molto gravi al suo cuore. Accademicamente eccelleva e presto recuperò il terreno perduto. Al liceo è stata l’unica ragazza a prendere la scienza avanzata e corsi di matematica e si è laureato con una serie di onori. Nel 1936 entrò nel San Diego State College, laureandosi in matematica. Alla ricerca di panorami più ampi, si è trasferita all’Università della California a Berkeley per il suo ultimo anno. Tra i cinque corsi di matematica ha preso quell’anno è stato uno sulla teoria dei numeri insegnato da Raphael Robinson. Impressionato dalla sua capacità, la convinse a continuare i suoi studi come studente laureato. Raffaello era un matematico di ampi interessi e conoscenze e un mentore ideale. Ma presto la loro relazione divenne più personale e si sposarono nel dicembre 1941. Le loro speranze di iniziare una famiglia furono infrante quando Julia subì un aborto spontaneo e fu avvertita da un medico che, a causa del suo cuore gravemente danneggiato, la gravidanza sarebbe stata estremamente pericolosa. La sua opinione era che probabilmente sarebbe morta prima dei quarant’anni. Nel tentativo di aiutare Julia a superare la profonda depressione in cui è stata gettata, Raffaello incoraggiata a cercare conforto in matematica.
Background matematico Il 1930 aveva visto sviluppi rivoluzionari nel soggetto antico della logica, drasticamente cambiato dal campo tradizionale originato da Aristotele. Il famoso teorema di incompletezza di Kurt Gödel aveva indicato i limiti intrinseci dei sistemi formali di logica nell’incapsulare la pratica matematica. Il lavoro di Alonzo Church, Alan Turing, Emil Post e Gödel stesso aveva dimostrato che la questione dell’esistenza di soluzioni algoritmiche a specifici problemi matematici poteva essere data una formulazione precisa. Ciò ha aperto la possibilità che in casi specifici, tali soluzioni algoritmiche potrebbero non esistere, e anche che in tali casi, questo potrebbe essere dimostrato. Alfred Tarski aveva spiegato come definire nozioni semantiche di verità e definibilità dei linguaggi formali. Questi sono stati gli sviluppi che hanno fornito il contesto della ricerca di Julia Robinson.
Qualsiasi particolare ramo della matematica userà i simboli per rappresentare le operazioni e le relazioni particolari che sono fondamentali per quell’argomento. Oltre a tali simboli, la logica matematica moderna utilizza i simboli speciali
insieme al segno = familiare. Si parla di questi simboli insieme a quelli corrispondenti a un particolare ramo della matematica come costituenti una lingua. Il lavoro di Julia Robinson è stato in gran parte nel contesto del linguaggio dell’aritmetica che utilizza i due simboli + e × in piedi per addizione e moltiplicazione, rispettivamente, così come i simboli per 0 e 1. Le lettere dell’alfabeto sono usate come variabili e, nel caso del linguaggio dell’aritmetica, di solito si intendono variare rispetto ai numeri naturali familiari 0,1,2 …… Quindi, ad esempio, la “frase”
esprime la proposizione vera che l’aggiunta di due numeri dispari produce un numero pari. La formula (u) (x = u+u+1)> definisce di per sé l’insieme di numeri dispari, cioè se x è sostituito da un particolare numero naturale, la frase risultante sarà vera se e solo se quel numero è dispari. Questioni di definibilità e l’esistenza di algoritmi sono stati fondamentali per il lavoro di Robinson.
Un insieme di numeri naturali S è chiamato computabili (o ricorsiva) se c’è un algoritmo in grado di determinare, per un dato numero naturale n, se non n appartiene a S. Un insieme di numeri naturali è chiamato listable (termine preferito da Julia Robinson) o ricorsivamente enumerabile se c’è un algoritmo per creare sistematicamente un elenco dei membri del S. Tutti unsolvability risultati possono essere considerati come conseguenze della chiave teorema: esiste un listable set che non è quantificabile. Queste questioni erano anche molto importanti nel lavoro di Robinson.
Tesi di Julia Robinson Fu in un seminario guidato dal carismatico Alfred Tarski, uno dei grandi logici del ventesimo secolo, che Robinson trovò il suo métier. Tarski aveva lasciato la sua nativa Polonia nell’agosto del 1939 in quello che sarebbe stato un breve viaggio per partecipare a una conferenza negli Stati Uniti, poco prima che l’invasione tedesca della Polonia precipitasse la seconda guerra mondiale. Tarski ha posto una serie di questioni irrisolte sulla definibilità nel linguaggio dell’aritmetica a cui Robinson è stato attratto. Dal 1940 era ben noto che non esiste un algoritmo per determinare se una data frase nel linguaggio dell’aritmetica, con le variabili che vanno oltre i numeri naturali, è vera. Come si dice, questo è un problema algoritmicamente irrisolvibile. Tarski voleva sapere se lo stesso è vero quando in questa stessa lingua, le variabili sono autorizzate a variare su tutti i numeri razionali invece dei soli numeri naturali. (I numeri razionali sono quelli esprimibili come frazioni m / n o-m / n dove m è un numero naturale e n è un numero naturale diverso da zero.) Erano state sviluppate tecniche per “ridurre” uno di questi “problemi decisionali” ad un altro. In questo caso si mostrerebbe che se ci fosse un algoritmo per testare per la verità una frase del linguaggio dell’aritmetica con le variabili vincolate a variare sui numeri razionali, tale algoritmo potrebbe essere usato per fornire un algoritmo per fare lo stesso quando le variabili variano sui numeri naturali. Quindi, poiché non esiste un tale algoritmo per quest’ultimo, ne deriverebbe che nessuno dei due potrebbe essercene uno per il primo.
Il principale risultato della tesi di Robinson fu una formula esplicita nel linguaggio dell’aritmetica, con le variabili vincolate a variare rispetto ai numeri razionali, che definisce precisamente l’insieme degli interi (cioè l’insieme dei numeri naturali e dei loro negativi). Seguì poi che il problema di determinare la verità di una frase di aritmetica rimane irrisolvibile anche quando le variabili variano sui numeri razionali. Seguirono anche altri risultati di non risolvibilità. L’approccio di Robinson era intricato, elegante e ingegnoso usando alcune idee piuttosto profonde della teoria dei numeri.
Caratterizzazioni eleganti Robinson ha sempre cercato eleganza e semplicità nel suo lavoro matematico. Uno dei suoi primi documenti ha mostrato come caratterizzare, in modo particolarmente semplice, le funzioni algoritmicamente computabili (chiamate anche funzioni ricorsive) che mappano i numeri naturali in se stessi. La sua bella caratterizzazione coinvolge due funzioni iniziali e tre operazioni per ottenere nuove funzioni da funzioni date. Una delle funzioni iniziali è solo la funzione successiva S( x) = x+1. L’altro, che Robinson chiama E, è definito come la differenza tra un dato numero e il quadrato perfetto più grande che non lo supera. (Quindi E(19) = 19 – 16 = 3 ed E (25) = 25 -25 = 0.) Le tre operazioni sono le seguenti: (1) dalle funzioni date F e G ottenere la funzione H(x)=F(G (x)); (2) dalle funzioni date F e G ottenere la funzione H(x)=F(x) + G (x); e(3) da una data funzione F i cui valori includono tutti i numeri naturali ottenere la funzione H dove H(x) è il numero minimo t per cui F (t)=x.
È davvero notevole che tutte le funzioni computabili (dai numeri naturali ai numeri naturali) possono essere ottenute iniziando con le due funzioni iniziali e applicando queste tre operazioni più e più volte.
Molto più tardi Robinson mostrò la stessa eleganza e verve nel trovare nuove caratterizzazioni di un dominio lontano dal computabile. L’esistenza di un set elencabile K che non è computabile è già stata menzionata. Quindi non esiste un algoritmo per determinare l’appartenenza a K. Considerando gli insiemi che possono essere elencati dagli algoritmi che hanno accesso alle informazioni di appartenenza su tali insiemi (metaforicamente tramite un “oracle”), è possibile portare ulteriori set nella piega e questo processo può essere iterato. Consentendo a questa iterazione di verificarsi un numero finito di volte, gli insiemi ottenuti risultano essere esattamente quelli chiamati aritmetici, gli insiemi definibili nel linguaggio dell’aritmetica con variabili che vanno oltre i numeri naturali. Ma non c’è bisogno di fermarsi qui. Si può definire un set non aritmetico e quindi usarlo come “oracle” per poter elencare ancora più set. C’è un luogo naturale in cui questo processo finisce, e gli insiemi di numeri naturali così ottenuti sono chiamati iperaritmetici. Era questo regno rarefatto per il quale Robinson forniva una caratterizzazione semplice e diretta.
Definibilità esistenziale e decimo problema di Hilbert Il lavoro per il quale Julia Robinson è più ricordato ha avuto origine da un problema apparentemente semplice posto da Alfred Tarski. Tarski voleva sapere quali insiemi di numeri naturali sono definibili da formule del linguaggio dell’aritmetica se i simboli e sono esclusi. Chiamò tali insiemi definibili esistenzialmente e propose il problema di dimostrare che l’insieme {1,2,4,8,16,….} di potenze di 2 non è esistenzialmente definibile . Questo era esattamente il tipo di problema che piaceva a Robinson. La nozione di definibilità esistenziale potrebbe facilmente essere vista come strettamente correlata a problemi di un tipo che i teorici dei numeri studiano, i cosiddetti problemi diofantini. Questi in genere hanno a che fare con un’equazione polinomiale p (a, x, y, z, u, v, w,….) = 0 con coefficienti interi dove a è un parametro e x,y,z,u,v,w,…. sono ” incognite.”(Ricordiamo che un tale polinomio è solo la somma di termini come 5a3x2v5 e-7a4x3z6.) Per particolari equazioni diofantee di questo tipo, i teorici dei numeri cercano di determinare per quali valori di numeri naturali del parametro a, l’equazione ha soluzioni di numeri naturali nelle incognite. Ora con semplici metodi standard è facile vedere che un insieme di numeri naturali S è definibile esistenzialmente se e solo se esiste un’equazione polinomiale di questo tipo tale che S è esattamente l’insieme di valori del parametro per il quale l’equazione ha soluzioni di numeri naturali. Per questo motivo, gli insiemi definibili esistenzialmente sono anche chiamati Diofantini, e questo è il termine che è stato adottato nella letteratura successiva.
Non avendo alcun successo nel dimostrare la congettura di Tarski che l’insieme dei poteri di 2 non è Diofantina, Robinson iniziò a considerare la possibilità che l’ipotesi di Tarski potesse essere sbagliata. Al fine di fare qualsiasi progresso, ha dovuto assumere una certa ipotesi, non provata al momento, che è venuto a essere chiamato J. R.; grosso modo J. R. afferma che c’è una equazione Diofantea con due parametri a,b con la proprietà che le coppie (a,b) per cui l’equazione ha soluzioni sono tali che b cresce in modo esponenziale in funzione di un. Ipotizzando di J. R. e la realizzazione di un complesso e ingegnoso analisi, ha dimostrato non solo che le potenze di 2 sono Diofantee, ma anche che l’insieme dei numeri primi, così come molti altri anche. Si vede subito che tutti gli insiemi diofantini sono elencabili, ma ora si chiedeva se il contrario potrebbe essere vero, se tutti gli insiemi elencabili potrebbero essere diofantini. Questo, sapeva che avrebbe avuto profonde conseguenze.
Nel 1900, per salutare il nuovo secolo, il grande matematico David Hilbert propose una lista di ventitré problemi da affrontare. Il decimo della sua lista era quello di fornire un algoritmo per determinare se una data equazione diofantina polinomiale ha soluzioni. Se davvero tutti gli insiemi elencabili fossero diofantini, si rese conto, in particolare ci sarebbe stato un insieme diofantino non computabile, il che implica che non ci potrebbe essere alcun algoritmo come Hilbert aveva chiesto. Ciò costituirebbe una soluzione negativa del decimo problema di Hilbert.
Nell’estate del 1959, Robinson ricevette per posta una preprint di un documento di Martin Davis e Hilary Putnam. Il documento conteneva una prova che, assumendo J. R., tutti i set elencabili sono davvero diofantini. Tuttavia, la prova ha avuto un divario importante. Ha usato il fatto che ci sono sequenze arbitrariamente lunghe di numeri primi con la proprietà speciale che la differenza tra i termini consecutivi della sequenza è costante. Anche se questo è vero, nel 1959 era una mera ipotesi; è stato dimostrato solo nel 2004. Robinson conosceva molto bene il precedente lavoro di Davis e Putnam e ha espresso sorpresa e piacere per la loro realizzazione. In brevissimo tempo, ha mostrato come fare a meno dell’ipotesi extra sui numeri primi e ha persino trovato una versione breve della dimostrazione. Quindi, per ottenere la soluzione negativa anticipata del decimo problema di Hilbert, rimaneva solo da dimostrare J. R.
Ciò fu compiuto nel gennaio 1970 dal ventiduenne Yuri Matiyasevich usando la famosa sequenza di Fibonacci 1,1,2,3,5,8,13,…. Ha trovato un’equazione diofantina con due parametri a, b che è stato in grado di dimostrare ha soluzioni nel caso in cui b è il numero di Fibonacci nel 2a-esimo posto in questa sequenza. Poiché i numeri di Fibonacci crescono esponenzialmente, questo costituì una prova di J. R. Robinson fu deliziato dalla prova ingegnosa di Matiyasevich e viaggiò a Leningrado dove le loro famiglie si incontrarono. La loro collaborazione è stata fruttuosa; insieme sono stati in grado di dimostrare che il decimo problema di Hilbert è irrisolvibile anche per equazioni in 13 incognite. (Più tardi Matiyasevich è stato in grado di ridurre il numero a 9.)
Coda Il” nepotismo ” regole in vigore presso l’Università della California avrebbe fatto un regolare appuntamento facoltà per Robinson impossibile fino a quando il marito era sulla facoltà. In ogni caso può darsi che i suoi problemi di salute le avrebbero precluso un posto a tempo pieno. Ha fatto occasionalmente insegnare un corso come coadiuvante, e ha servito come de facto consigliere di due eccellenti studenti di dottorato, Leonard Adleman e Kenneth Manders. Robinson sfidò la previsione del dottore che non avrebbe vissuto fino a quarant’anni, ma al suo quarantunesimo compleanno il suo cuore danneggiato l’aveva portata vicino allo status di invalida. È stata salvata da un intervento chirurgico che si era reso disponibile solo di recente e che ha notevolmente migliorato la sua situazione, permettendole di vivere una vita attiva per altri venticinque anni.
Il suo lavoro eccezionale è stato riconosciuto dalla sua elezione nel 1975 alla National Academy of Sciences, la prima donna ad essere eletto alla sezione matematica. Nello stesso anno è stata finalmente offerto un appuntamento professorial presso l’Università della California a Berkeley.
Su sua richiesta era un appuntamento di un quarto di volta. Una borsa di studio MacArthur è venuto nel 1983. E ‘ stata eletta presidente della American Mathematical Society per 1983-1984, la prima donna a tenere questa carica. Tragicamente, non è stata in grado di completare il suo mandato. Si scoprì che soffriva di leucemia durante l’estate del 1984. Dopo una breve remissione, Julia Robinson morì di malattia il 30 luglio 1985.
BIBLIOGRAFIA
OPERE DI ROBINSON
“Definability and Decision Problems in Arithmetic.”Journal of Symbolic Logic 14 (1949): 98-114. Questa era la tesi di Robinson. “Funzioni ricorsive generali.”Proceedings of the American Mathematical Society 1 (1950): 703-718. Oltre alla caratterizzazione delle funzioni computabili di un argomento descritto sopra, molti altri risultati interessanti sono discussi in questo articolo. “Definibilità esistenziale in aritmetica.”Transactions of the American Mathematical Society 72 (1952): 437-449. Un documento fondamentale in cui ciò che è stato chiamato J. R. è stato dimostrato di implicare la definibilità esistenziale dei poteri di 2, i numeri primi, e in realtà, la funzione esponenziale completa.
Con Martin Davis e Hilary Putnam.”The Decision Problem for Exponential Diophantine Equations.”Annals of Mathematics 74 (1961): 425-436. Fu in questo documento che fu dimostrato che J. R. implica l’irrisolvibilità del decimo problema di Hilbert. “An Introduction to Hyperarithmetical Functions.”Journal of Symbolic Logic 32 (1967): 325-342. Questa è stata l’unica escursione di Robinson al molto non calcolabile.
Con Yuri Matiyasevich. “Riduzione di un’equazione diofantina arbitraria a una su 13 incognite.”Acta Arithmetica 27 (1975): 521-553. Virtuoso teoria dei numeri! Con Martin Davis e Yuri Matiyasevich. “Decimo problema di Hilbert. Equazioni diofantee: aspetti positivi di una soluzione negativa.”In Mathematical Developments Rising from Hilbert Problems, a cura di Felix Browder. Providence, RI: American Mathematical Society, 1976.
Proceedings of Symposia in Pure Mathematics 28 (1976): 323-378. Un sondaggio della prova della irrisolvibilità del decimo problema di Hilbert, nonché di sviluppi matematici derivanti da esso da tre dei quattro matematici il cui lavoro ha portato a tale prova.
Le opere raccolte di Julia Robinson. A cura di Solomon
Feferman. Providence, RI: American Mathematical Society, 1996. Tutte le venticinque pubblicazioni di Robinson sono ristampate qui per intero. Inoltre, c’è il bel saggio biografico su di lei scritto da Feferman per l’Accademia Nazionale delle Scienze.
ALTRE FONTI
Davis, Martin. “Il decimo problema di Hilbert è irrisolvibile.”
American Mathematical Monthly 80 (1973): 233-269; ristampato come appendice in Computability and Unsolvability, a cura di Martin Davis. New York: Dover, 1983. Un saggio Steele-Prize-winning che offre la prova completa della irrisolvibilità del decimo problema di Hilbert. La ristampa Dover è di uno dei primi trattamenti libro-lunghezza della teoria della computabilità.
—, e Reuben Hersh. “Decimo problema di Hilbert.”
Scientific American 229 (novembre 1973): 84-91. Ristampato in The Chauvenet Papers, Vol. 2, a cura di J. C. Abbott. Washington, DC: Mathematical Association of America, 1978. Un articolo vincitore del premio Chauvenet destinato al pubblico generale istruito.
Matiyasevich, Yuri. “La mia collaborazione con Julia Robinson.”
The Mathematical Intelligencer 14 (1992): 38-45. La sua storia di come un giovane russo e una donna americana molto più anziana è venuto a produrre matematica elegante insieme.
———. Il decimo problema di Hilbert. Cambridge, MA: MIT Press,
1993. Un’eccellente introduzione e indagine adatta per laureandi in matematica, con una bibliografia molto inclusiva.
Reid, Costanza. Julia, una vita in matematica. Washington, DC:
Mathematical Association of America, 1996. Dalla sorella di Robinson, ha fotografie, biografia utile di Reid, dal titolo “L’autobiografia di Julia Robinson,” e una breve nota di Martin Davis sul suo lavoro con Hilary Putnam.
Martin Davis
