(f. St. Louis, Missouri, 8 December 1919; D.Berkeley, Kalifornien, 30 juli 1985), matematik, matematisk logik, talteori, beslutsproblem, definierbarhet.
Robinsons matematiska arbete uppvisar kraft och charm. Hon tacklade svåra problem och strävade efter eleganta lösningar. Hennes liv och arbete kan inte ses ordentligt utan att notera att hon som kvinna i ett mansdominerat fält var något av en pionjär. Hennes m äpplenier var gränssnittet mellan två grenar av matematik, logik och talteori, vanligtvis tros ha lite att göra med varandra. Hon är särskilt känd för sina bidrag till lösningen av det tionde problemet i en berömd lista över tjugotre som föreslagits av matematikern David Hilbert 1900. Hon valdes till National Academy of Sciences och även till ordförandeskapet i American Mathematical Society, i båda fallen den första kvinnliga matematiker att vara så hedrad, och var också en mottagare av en MacArthur Fellowship.
Tidigt liv född Julia Bowman, hon led två katastrofer tidigt i livet. Hon var bara två när hennes mamma dog och lämnade sin far för att klara Julia och hennes äldre syster Constance. Efter hans omgifte, familjen flyttade västerut, slutligen till San Diego, där hennes styvsyster Billie föddes. När Julia var nio genomgick hon en förödande sjukdom: scharlakansfeber följt av reumatisk feber. Hon missade två år i skolan och led mycket allvarliga skador på hennes hjärta. Akademiskt utmärkte hon sig och gjorde snart sin förlorade mark. På gymnasiet var hon den enda tjejen som tog kurser i avancerad vetenskap och matematik och tog examen med ett antal utmärkelser. 1936 gick hon in i San Diego State College, huvudämne i matematik. Söker bredare perspektiv, hon överfördes till University of California i Berkeley för hennes sista år. Bland de fem matematik kurser hon tog det året var en på teorin om siffror undervisas av Raphael Robinson. Imponerad av hennes förmåga övertygade han henne om att fortsätta sina studier som doktorand. Raphael var en matematiker med breda intressen och kunskaper och en idealisk mentor. Men snart blev deras förhållande mer personligt och de gifte sig i December 1941. Deras förhoppningar om att starta en familj slogs när Julia fick missfall och varnade av en läkare att graviditeten på grund av hennes allvarligt skadade hjärta skulle vara extremt farlig. Hans åsikt var att hon sannolikt skulle dö innan hon var fyrtio. I ett försök att hjälpa Julia att övervinna den djupa depression som hon kastades i, Raphael uppmuntrade henne att söka tröst i matematik.
matematisk bakgrund 1930-talet hade sett revolutionerande utveckling i det gamla ämnet logik, drastiskt förändrats från det traditionella fältet som härstammar från Aristoteles. Kurt g Sackudel berömda ofullständighetssats hade pekat på de inneboende begränsningarna i formella logiksystem för att inkapsla matematisk praxis. Arbete av Alonzo Church, Alan Turing och Emil Post såväl som g Sackaridel själv hade visat att frågan om förekomsten av algoritmiska lösningar på specifika matematiska problem kunde ges en exakt formulering. Detta öppnade möjligheten att sådana algoritmiska lösningar i specifika fall kanske inte existerar, och även i sådana fall kan detta bevisas. Alfred Tarski hade förklarat hur man definierar semantiska begrepp om sanning och definierbarhet av formella språk. Dessa var utvecklingen som gav sammanhanget för Julia Robinsons forskning.
varje särskild gren av matematiken kommer att använda symboler för att stå för de särskilda operationer och relationer som är grundläggande för det ämnet. Förutom sådana symboler använder modern matematisk logik specialsymbolerna
tillsammans med det bekanta = tecknet. Man talar om dessa symboler tillsammans med de som motsvarar en viss gren av matematik som utgör ett språk. Julia Robinsons arbete var till stor del i samband med aritmetiska språket som använder de två symbolerna + och exporteras som står för addition respektive multiplikation samt symboler för 0 och 1. Bokstäverna i alfabetet används som variabler, och när det gäller aritmetiska språket förstås de vanligtvis att variera över de välbekanta naturliga siffrorna 0,1,2 …… så till exempel uttrycker ”meningen”
det sanna förslaget att lägga till två udda tal ger ett jämnt tal. Formeln (u) (x = u+u+1)> definierar i sig uppsättningen udda tal, dvs om x ersätts av ett visst naturligt tal, kommer den resulterande meningen att vara sant om och endast om det numret är udda. Frågor om definierbarhet och förekomsten av algoritmer var grundläggande för robinsons arbete.
en uppsättning naturliga tal s kallas beräkningsbar (eller rekursiv) om det finns en algoritm som kan bestämma för ett givet naturligt tal n huruvida n tillhör S. en uppsättning naturliga tal kallas listable (termen föredragen av Julia Robinson) eller rekursivt uppräkningsbar om det finns en algoritm för att systematiskt göra en lista över medlemmarna i S. Alla olösliga resultat kan betraktas som konsekvenser av nyckelsatsen: det finns en listable uppsättning som inte kan beräknas. Dessa frågor var också mycket viktiga i Robinsons arbete.
Julia Robinsons avhandling Det var i ett seminarium som leddes av den karismatiska Alfred Tarski, en av de stora logikerna i det tjugonde århundradet, som Robinson hittade henne M. Tarski hade lämnat sitt hemland Polen i augusti 1939 på vad som skulle ha varit en kort resa för att delta i en konferens i USA, strax före tysk invasion av Polen utlöste andra världskriget. Tarski ställde ett antal olösta frågor om definierbarhet på det aritmetiska språket som Robinson lockades till. Vid 1940-talet var det välkänt att det inte finns någon algoritm för att avgöra om en given mening i aritmetiska språket, med variablerna som sträcker sig över de naturliga siffrorna, är sant. Som man säger är detta ett algoritmiskt olösligt problem. Tarski ville veta om detsamma är sant när på samma språk får variabler sträcka sig över alla rationella tal istället för bara de naturliga siffrorna. (De rationella talen är de uttryckbara som fraktioner m/n eller-m / n där m är ett naturligt tal och n är ett naturligt tal som inte är noll.) Det hade utvecklats tekniker för att” reducera ”ett sådant” beslutsproblem ” till ett annat. I det här fallet skulle man visa att om det fanns en algoritm för att testa för sanning en mening av aritmetiska språket med variablerna begränsade att variera över de rationella siffrorna, skulle en sådan algoritm kunna användas för att tillhandahålla en algoritm för att göra detsamma när variablerna sträcker sig över de naturliga siffrorna. Så, eftersom det inte finns någon sådan algoritm för den senare, skulle det följa att det inte heller kunde finnas en för den förra.
huvudresultatet av Robinsons avhandling var en uttrycklig formel i aritmetiska språket, med variablerna begränsade att variera över de rationella talen, som exakt definierar uppsättningen heltal (det vill säga uppsättningen naturliga tal och deras negativ). Det följde sedan att problemet med att bestämma sanningen i en aritmetisk mening förblir olöslig även när variablerna sträcker sig över de rationella siffrorna. Andra olösliga resultat följde också. Robinsons tillvägagångssätt var invecklat, elegant och genialt med hjälp av några ganska djupa tankar från talteori.
eleganta karakteriseringar Robinson sökte alltid elegans och enkelhet i sitt matematiska arbete. En av hennes tidiga papper visade hur man på ett särskilt enkelt sätt kan karakterisera de algoritmiskt beräkningsbara funktionerna (även kallade rekursiva funktioner) som kartlägger de naturliga siffrorna i sig själva. Hennes vackra karaktärisering innefattar två initiala funktioner och tre operationer för att erhålla nya funktioner från givna funktioner. En av de ursprungliga funktionerna är bara efterträdarfunktionen S (x)= x+1. Den andra, som Robinson kallar E, definieras som skillnaden mellan ett givet tal och den största perfekta torget som inte överstiger det. (Således E(19) = 19 – 16 = 3 och E (25) = 25 -25 = 0.) De tre operationerna är följande: (1) från givna funktioner F och G erhåller funktionen H(x)=F(G (x)); (2) från givna funktioner F och G erhåller funktionen H(x)=F(x) + G (x); och(3) från en given funktion F vars värden inkluderar alla naturliga tal erhåller funktionen H där H(x) är det minsta antalet t för vilket F (t)=x.
det är verkligen anmärkningsvärt att alla beräkningsbara funktioner (från naturliga tal till naturliga tal) kan erhållas genom att börja med de två initiala funktionerna och tillämpa dessa tre operationer om och om igen.
mycket senare visade Robinson samma elegans och verve i att hitta nya karakteriseringar av en domän långt ifrån det beräkningsbara. Förekomsten av en listbar uppsättning K som inte kan beräknas har redan nämnts. Så det finns ingen algoritm för att bestämma medlemskap i K. Genom att överväga uppsättningar som kan listas av algoritmer som har tillgång till medlemsinformation om sådana uppsättningar (metaforiskt via ett ”oracle”) kan ytterligare uppsättningar föras in i veckan, och denna process kan itereras. Genom att tillåta denna iteration att inträffa något begränsat antal gånger, visar sig de erhållna uppsättningarna vara exakt de som kallas aritmetiska, uppsättningarna definierbara på aritmetiska språket med variabler som sträcker sig över de naturliga siffrorna. Men det finns inget behov av att stanna här. Man kan definiera en icke-aritmetisk uppsättning, och sedan använda det som ett ”oracle” för att kunna lista ännu fler uppsättningar. Det finns en naturlig plats där denna process slutar, och de uppsättningar av naturliga tal som erhålls kallas hyperaritmetiska. Det var detta sällsynta rike för vilket Robinson gav en enkel och direkt karaktärisering.
existentiell Definierbarhet och Hilberts tionde Problem det arbete som Julia Robinson är mest ihågkommen för har sitt ursprung i ett till synes enkelt problem som Alfred Tarski ställde. Tarski ville veta vilka uppsättningar av naturliga tal som kan definieras med formler av aritmetiska språk om symbolerna och utesluts. Han kallade sådana uppsättningar existentiellt definierbara och föreslog problemet med att bevisa att uppsättningen {1,2,4,8,16,….} av befogenheter 2 är inte existentiellt definierbara. Detta var precis den typ av problem som Robinson gillade. Begreppet existentiell definierbarhet kan lätt ses som nära besläktat med problem av ett slag som talteoretiker studerar, så kallade Diofantinska problem. Dessa har vanligtvis att göra med en polynomekvation p (a, x, y, z, u, v, w,….) = 0 med heltalskoefficienter där a är en parameter och x, y, z, u, v, w,…. är ” okända.”(Kom ihåg att ett sådant polynom bara är summan av termer som 5a3x2v5 och-7a4x3z6.) För särskilda Diofantinekvationer av detta slag försöker talteoretiker bestämma för vilka naturliga talvärden för parametern a, ekvationen har naturliga tallösningar i de okända. Nu med enkla standardmetoder är det lätt att se att en uppsättning naturliga tal S är existentiellt definierbar om och endast om det finns en polynomekvation av detta slag så att S är exakt den uppsättning värden för parametern för vilken ekvationen har naturliga tallösningar. Av denna anledning kallas existentiellt definierbara uppsättningar också Diofantin, och detta är termen som har antagits i den senare litteraturen.
Robinson började inte överväga möjligheten att Tarskis gissning kunde ha varit fel. För att göra några framsteg var hon tvungen att anta en viss hypotes, obevisad vid den tiden, som kom att kallas Jr; grovt sett Jr. anger att det finns en Diofantin ekvation med två parametrar a,b med egenskapen att paren (a,b) för vilka ekvationen har lösningar är sådana att b växer exponentiellt som en funktion av A. genom att anta Jr och genomföra en komplex och genial analys bevisade hon inte bara att krafterna för 2 är Diofantin, utan också att uppsättningen primtal liksom många andra också är. Det är lätt att se att alla Diofantinuppsättningar är listbara, men nu undrade hon om det motsatta kan vara sant, om alla listbara uppsättningar kan vara Diofantin. Detta visste hon skulle få djupa konsekvenser.
1900, för att hälsa på det nya århundradet, föreslog den stora matematikern David Hilbert en lista med tjugotre problem att stå som en utmaning. Den tionde på hans lista var att tillhandahålla en algoritm för att avgöra om en given polynomdiofantin ekvation har lösningar. Om verkligen alla listbara uppsättningar var Diofantin, insåg hon, då skulle det särskilt finnas en icke-beräkningsbar Diofantinuppsättning, vilket innebär att det inte kunde finnas någon algoritm som Hilbert hade bett om. Detta skulle utgöra en negativ lösning på Hilberts tionde problem.
sommaren 1959 fick Robinson i posten ett förtryck av ett papper av Martin Davis och Hilary Putnam. Papperet innehöll ett bevis på att, förutsatt att Jr, alla listbara uppsättningar verkligen är Diofantin. Beviset hade dock ett viktigt gap. Det använde det faktum att det finns godtyckligt långa sekvenser av primtal med den speciella egenskapen att skillnaden mellan på varandra följande termer av sekvensen är konstant. Även om detta är sant, var det 1959 bara en hypotes, det bevisades först 2004. Robinson kände Davis och Putnams tidigare arbete mycket bra och uttryckte överraskning och nöje över deras prestation. I mycket kort ordning visade hon hur man skulle göra utan den extra hypotesen om primtal och hittade till och med en kort version av beviset. Så för att få den förväntade negativa lösningen av Hilberts tionde problem återstod det bara att bevisa Jr
detta uppnåddes i januari 1970 av den tjugotvååriga Yuri Matiyasevich med den berömda Fibonacci-sekvensen 1,1,2,3,5,8,13,…. Han hittade en Diofantin ekvation med två parametrar a,b som han kunde bevisa har lösningar bara om b är Fibonacci-numret på 2A-platsen i denna sekvens. Eftersom Fibonacci-siffrorna växer exponentiellt utgjorde detta ett bevis på att J. R. Robinson var glad över Matiyasevichs geniala bevis och reste till Leningrad där deras familjer träffades. Deras samarbete var fruktbart; tillsammans kunde de visa att Hilberts tionde problem är olösligt även för ekvationer i 13 okända. (Senare kunde Matiyasevich minska antalet till 9.)
Coda ”nepotism” – reglerna som gäller vid University of California skulle ha gjort en regelbunden fakultetsutnämning för Robinson omöjlig så länge hennes man var på fakulteten. I alla fall kan det vara så att hennes hälsoproblem skulle ha uteslutit en heltidsställning. Hon gjorde ibland undervisa en kurs som adjungerad, och hon fungerade som de facto rådgivare till två utmärkta doktorander, Leonard Adleman och Kenneth Manders. Robinson trotsade doktorns förutsägelse att hon inte skulle leva för att vara fyrtio, men vid hennes fyrtioförsta födelsedag hade hennes skadade hjärta fört henne nära ogiltig status. Hon räddades av ett kirurgiskt ingrepp som nyligen hade blivit tillgängligt och som förbättrade hennes situation avsevärt och gjorde det möjligt för henne att leva ett aktivt liv i ytterligare tjugofem år.
hennes enastående arbete erkändes av hennes val 1975 till National Academy of Sciences, den första kvinnan som valdes till matematiksektionen. Samma år erbjöds hon äntligen en professorutnämning vid University of California i Berkeley.
på hennes begäran var det en kvartstid. En MacArthur Fellowship kom 1983. Hon valdes till president för American Mathematical Society för 1983-1984, den första kvinnan som innehar detta kontor. Tragiskt nog kunde hon inte slutföra sin mandatperiod. Hon befanns lida av leukemi under sommaren 1984. Efter en kort eftergift dog Julia Robinson av sjukdomen den 30 juli 1985.
bibliografi
verk av ROBINSON
”Definierbarhet och beslutsproblem i aritmetik.”Journal of symbolisk logik 14 (1949): 98-114. Detta var Robinsons avhandling. ”Allmänna Rekursiva Funktioner.”Proceedings of the American Mathematical Society 1 (1950): 703-718. Förutom karaktäriseringen av beräkningsbara funktioner för ett argument som beskrivs ovan diskuteras många andra intressanta resultat i detta dokument. ”Existentiell Definierbarhet i aritmetik.”Transaktioner från American Mathematical Society 72 (1952): 437-449. Ett grundläggande papper där det som kom att kallas Jr visade sig innebära existentiell definierbarhet av krafterna i 2, primerna och faktiskt den fullständiga exponentiella funktionen.
med Martin Davis och Hilary Putnam.”Beslutsproblemet för exponentiella Diofantinekvationer.”Annals of Mathematics 74 (1961): 425-436. Det var i detta dokument som det bevisades att J. R. innebär att Hilberts tionde problem inte kan lösas. ”En introduktion till Hyperaritmetiska funktioner.”Journal of symbolisk logik 32 (1967): 325-342. Detta var Robinsons enda utflykt till det mycket oföränderliga.
Med Yuri Matiyasevich. ”Reduktion av en godtycklig Diofantin ekvation till en av 13 okända.”Acta Arithmetica 27 (1975): 521-553. Virtuos talteori! Med Martin Davis och Yuri Matiyasevich. ”Hilberts tionde Problem. Diophantine ekvationer: positiva aspekter av en negativ lösning.”I matematisk utveckling som härrör från Hilbert-problem, redigerad av Felix Browder. Providence, RI: amerikanska matematiska samhället, 1976.
symposier i ren matematik 28 (1976): 323-378. En undersökning av bevis på olöslighet Hilbert tionde problem samt matematiska utvecklingen härrör från det av tre av de fyra matematiker vars arbete ledde till att bevis.
de samlade verk av Julia Robinson. Redigerad av Solomon
Feferman. Providence, RI: amerikanska matematiska samhället, 1996. Alla tjugofem av Robinsons publikationer återges här i sin helhet. Dessutom finns det den fina biografiska uppsatsen om henne skriven av Feferman för National Academy of Sciences.
andra källor
Davis, Martin. ”Hilberts tionde Problem är olösligt.”
American Mathematical Monthly 80 (1973): 233-269; omtryckt som en bilaga I beräkningsbarhet och Olöslighet, redigerad av Martin Davis. New York: Dover, 1983. En Steele-prisvinnande uppsats som ger det fullständiga beviset på Hilberts tionde problem. Dover-omtrycket är en av de första boklängdsbehandlingarna av beräkningsteori.
—, och Reuben Hersh. ”Hilberts tionde Problem.”
Vetenskaplig Amerikansk 229 (November 1973): 84-91. Omtryckt i Chauvenet Papers, Vol. 2, redigerad av J. C. Abbott. Washington, DC: matematisk Förening av Amerika, 1978. En Chauvenet – prisvinnande artikel avsedd för den allmänna utbildade allmänheten.
Matiyasevich, Yuri. ”Mitt samarbete med Julia Robinson.”
Den Matematiska Intelligencer 14 (1992): 38-45. Hans berättelse om hur en ung Rysk och en mycket äldre amerikansk kvinna kom för att producera elegant matematik tillsammans.
———. Hilberts tionde Problem. Cambridge, MA: MIT Press,
1993. En utmärkt introduktion och undersökning lämplig för grundutbildning matematik majors, med en mycket inkluderande bibliografi.
Reid, Constance. Julia, ett liv i matematik. Washington, DC:
matematisk Förening av Amerika, 1996. Av Robinsons syster har den fotografier, Reids användbara biografi med titeln ”Julia Robinsons självbiografi” och en kort anteckning av Martin Davis om hans arbete med Hilary Putnam.
Martin Davis
