(St. Louis, Missouri, 8 December 1919; Berkeley, Californië, 30 juli 1985), wiskunde, wiskundige logica, getaltheorie, beslissingsproblemen, definieerbaarheid.Het wiskundige werk van Robinson vertoont kracht en charme. Ze pakte moeilijke problemen aan en streefde naar elegante oplossingen. Haar leven en werk kunnen niet goed worden gezien zonder op te merken dat ze als vrouw in een door mannen gedomineerd veld een soort pionier was. Haar metier was het raakvlak tussen twee takken van de wiskunde, logica en de theorie van de getallen, die gewoonlijk weinig met elkaar te maken hadden. Ze is vooral bekend voor haar bijdragen aan de oplossing van het tiende probleem in een beroemde lijst van drieëntwintig voorgesteld door de wiskundige David Hilbert in 1900. Ze werd verkozen tot de National Academy of Sciences en ook tot het voorzitterschap van de American Mathematical Society, in beide gevallen de eerste vrouwelijke wiskundige die zo geëerd werd, en was ook een ontvanger van een MacArthur Fellowship.Geboren als Julia Bowman, kreeg ze twee calamiteiten op jonge leeftijd. Ze was pas twee toen haar moeder stierf, en liet haar vader achter om met Julia en haar oudere zus Constance om te gaan. Na zijn hertrouwen verhuisde het gezin naar het westen, uiteindelijk naar San Diego, waar haar stiefzus Billie werd geboren. Toen Julia negen was onderging ze een verwoestende ziekte: roodvonk gevolgd door reumatische koorts. Ze miste twee jaar school en leed zeer ernstige schade aan haar hart. Academisch blonk ze uit en maakte al snel haar verloren terrein weer goed. Op de middelbare school was ze het enige meisje om de geavanceerde wetenschap en wiskunde cursussen te nemen en studeerde af met een aantal onderscheidingen. In 1936 ging ze naar San Diego State College, met als hoofdvak wiskunde. Op zoek naar bredere vergezichten, ze overgebracht naar de Universiteit van Californië in Berkeley voor haar laatste jaar. Onder de vijf wiskunde cursussen die ze nam dat jaar was een over de theorie van de getallen onderwezen door Raphael Robinson. Onder de indruk van haar vermogen, overtuigde hij haar om haar studie als afgestudeerde student voort te zetten. Raphael was een wiskundige met brede interesses en kennis en een ideale mentor. Maar al snel werd hun relatie persoonlijker en ze trouwden in december 1941. Hun hoop om een gezin te beginnen werd verpletterd toen Julia leed aan een miskraam en werd gewaarschuwd door een arts dat, vanwege haar ernstig beschadigde hart, zwangerschap zeer gevaarlijk zou zijn. Zijn mening was dat ze waarschijnlijk zou sterven voordat ze veertig was. In een poging om Julia te helpen de diepe depressie te overwinnen waarin ze werd geworpen, moedigde Raphael haar aan om troost te zoeken in de wiskunde.Wiskundige achtergrond in de jaren 1930 waren revolutionaire ontwikkelingen in het oude onderwerp van de logica te zien, drastisch veranderd van het traditionele veld dat door Aristoteles was ontstaan. Kurt Gödel ‘ s beroemde onvolledigheidsstelling had gewezen op de inherente beperkingen van formele systemen van de logica in het inkapselen van de wiskundige praktijk. Werk van Alonzo Church, Alan Turing, Emil Post en Gödel zelf hadden aangetoond dat de vraag van het bestaan van algoritmische oplossingen voor specifieke wiskundige problemen een precieze formulering kon worden gegeven. Dit opende de mogelijkheid dat in specifieke gevallen dergelijke algoritmische oplossingen niet zouden bestaan, en zelfs dat dit in dergelijke gevallen zou kunnen worden bewezen. Alfred Tarski had uitgelegd hoe semantische noties van waarheid en definieerbaarheid van formele talen te definiëren. Dit waren de ontwikkelingen die de context van Julia Robinson ‘ s onderzoek verschaften.
elke specifieke tak van de wiskunde zal symbolen gebruiken om voor de specifieke operaties en relaties te staan die fundamenteel zijn voor dat onderwerp. Naast deze symbolen gebruikt de moderne wiskundige logica de speciale symbolen
samen met het bekende = teken. Men spreekt van deze symbolen samen met die welke overeenkomen met een bepaalde tak van de wiskunde als een taal. Julia Robinson ‘ s werk was grotendeels in de context van de taal van de rekenkunde, die gebruik maakt van de twee symbolen + en × staan voor optellen en vermenigvuldigen, respectievelijk, evenals symbolen voor 0 en 1. Letters van het alfabet worden gebruikt als variabelen, en in het geval van de taal van de rekenkunde, worden ze meestal geacht te variëren over de bekende natuurlijke getallen 0,1,2 …… dus bijvoorbeeld, de “zin”
drukt de ware stelling uit dat het optellen van twee oneven getallen een even getal oplevert. De formule (U) (x = u+u+1)> definieert op zichzelf de verzameling oneven getallen, d.w.z. als x wordt vervangen door een bepaald natuurlijk getal, zal de resulterende zin dan en alleen waar zijn als dat getal oneven is. Vragen over definieerbaarheid en het bestaan van algoritmen waren fundamenteel voor Robinson ‘ s werk.
Een verzameling van natuurlijke getallen heet computable (of recursieve) als er sprake is van een algoritme voor het bepalen van de voor een gegeven natuurlijk getal n of n behoort tot S. Een verzameling van natuurlijke getallen is genoemd listable (de term de voorkeur van Julia Robinson) of recursief aftelbaar als er een algoritme voor het systematisch maken van een lijst van de leden van S. Alle unsolvability resultaten kunnen worden gezien als gevolgen van de belangrijkste stelling: Er bestaat een listable set die is niet berekenbaar. Deze zaken waren ook erg belangrijk in het werk van Robinson.Het was tijdens een seminar onder leiding van de charismatische Alfred Tarski, een van de grote logici van de twintigste eeuw, dat Robinson haar metier vond. Tarski had zijn geboorteland Polen in augustus 1939 verlaten op wat een korte reis zou zijn geweest om een conferentie in de Verenigde Staten bij te wonen, net voordat de Duitse invasie van Polen de Tweede Wereldoorlog inluidde. Tarski stelde een aantal onopgeloste vragen over definieerbaarheid in de taal van de rekenkunde waartoe Robinson werd aangetrokken. Tegen de jaren 1940 was het bekend dat er geen algoritme was om te bepalen of een bepaalde zin in de taal van de rekenkunde, met variabelen die zich uitstrekken over de natuurlijke getallen, waar is. Zoals men zegt, is dit een algoritmisch onoplosbaar probleem. Tarski wilde weten of hetzelfde Waar is als in dezelfde taal, variabelen zijn toegestaan om te variëren over alle rationele getallen in plaats van alleen de natuurlijke getallen. (De rationale getallen zijn de getallen die kunnen worden uitgedrukt als breuken m / n of-m / n waarbij m een natuurlijk getal is en n een niet-nul natuurlijk getal.) Er waren technieken ontwikkeld om een dergelijk” beslissingsprobleem “tot een ander te” reduceren”. In dit geval zou men aantonen dat als er een algoritme voor het testen van waarheid een zin van de taal van de rekenkunde met de variabelen beperkt om te variëren over de rationale getallen, een dergelijk algoritme zou kunnen worden gebruikt om een algoritme om hetzelfde te doen wanneer de variabelen variëren over de natuurlijke getallen. Dus, aangezien er geen dergelijk algoritme voor de laatste, het zou volgen dat noch kon er een voor de eerste.Het belangrijkste resultaat van Robinson ‘ s proefschrift was een expliciete formule in de taal van de rekenkunde, waarbij de variabelen beperkt waren om te variëren over de rationale getallen, die precies de verzameling van gehele getallen definieert (dat wil zeggen, de verzameling van natuurlijke getallen en hun negatieven). Daarna volgde dat het probleem van het bepalen van de waarheid van een zin van de rekenkunde onoplosbaar blijft, zelfs wanneer de variabelen over de rationale getallen variëren. Ook andere onverantwoorde resultaten volgden. Robinson ‘ s aanpak was ingewikkeld, elegant en ingenieus met behulp van een aantal vrij diepe ideeën uit de getaltheorie.
elegante karakteristieken Robinson zocht altijd elegantie en eenvoud in haar wiskundige werk. Een van haar vroege papers liet zien hoe je op een bijzonder eenvoudige manier de algoritmisch berekenbare functies (ook wel de recursieve functies genoemd) kunt karakteriseren die de natuurlijke getallen in zichzelf in kaart brengen. Haar mooie karakterisering omvat twee initiële functies en drie operaties voor het verkrijgen van nieuwe functies uit bepaalde functies. Een van de eerste functies is alleen de opvolger functie S(x)= x+1. De andere, die Robinson E noemt, wordt gedefinieerd als het verschil tussen een gegeven getal en het grootste perfecte kwadraat dat het niet overschrijdt. (Dus E (19) = 19 – 16 = 3 en E(25) = 25 -25 = 0.) De drie bewerkingen zijn als volgt: (1) uit gegeven functies F en G Verkrijg de functie H(x)=F(G(x)); (2) uit gegeven functies F en G Verkrijg de functie H(x)=F(x) + G(x); en (3) uit een gegeven functie F waarvan de waarden alle natuurlijke getallen omvatten Verkrijg de functie h waar H(x) het minste getal t is waarvoor F(t)=x.Het is werkelijk opmerkelijk dat alle berekenbare functies (van de natuurlijke getallen tot de natuurlijke getallen) kunnen worden verkregen door te beginnen met de twee initiële functies en deze drie bewerkingen steeds opnieuw toe te passen.Veel later toonde Robinson dezelfde elegantie en verve in het vinden van nieuwe karakteriseringen van een domein dat ver verwijderd was van het rekenbare. Het bestaan van een listable set K die niet berekenbaar is is al genoemd. Er is dus geen algoritme om het lidmaatschap te bepalen. Door sets te overwegen die kunnen worden weergegeven door algoritmen die toegang hebben tot lidmaatschapsinformatie over dergelijke sets (metaforisch via een “oracle”) kunnen extra sets in de vouw worden gebracht, en dit proces kan worden herhaald. Door deze iteratie een eindig aantal keren toe te staan, blijken de verkregen verzamelingen precies die te zijn die rekenkundig worden genoemd, de Verzamelingen definieerbaar in de taal van de rekenkunde met variabelen die zich over de natuurlijke getallen uitstrekken. Maar het is niet nodig om hier te stoppen. Men kan een niet-rekenkundige verzameling definiëren, en die dan gebruiken als een “oracle” om nog meer Verzamelingen op te kunnen sommen. Er is een natuurlijke plaats waar dit proces tot een einde komt, en de aldus verkregen verzamelingen van natuurlijke getallen worden hyperarithmetisch genoemd. Het was dit verheven rijk waarvoor Robinson een eenvoudige en directe karakterisering gaf.Existentiële Definieerbaarheid en Hilberts tiende probleem het werk waarvoor Julia Robinson het meest wordt herinnerd, is ontstaan met een schijnbaar eenvoudig probleem dat Alfred Tarski stelde. Tarski wilde weten welke verzamelingen van natuurlijke getallen definieerbaar zijn door formules van de rekenkundige taal als de symbolen en zijn uitgesloten. Hij noemde dergelijke verzamelingen existentieel definieerbaar en stelde het probleem voor om aan te tonen dat de verzameling {1,2,4,8,16, … } van de machten van 2 is niet existentieel definieerbaar. Dit was precies het soort probleem dat Robinson leuk vond. De notie van existentiële definieerbaarheid kan gemakkelijk worden gezien als nauw gerelateerd aan problemen van een soort die getaltheoretici bestuderen, zogenaamde diofantische problemen. Deze hebben meestal te maken met een veeltermvergelijking p(a,x,y,z,u,v,w,….) = 0 met gehele coëfficiënten waarbij a een parameter is en x,y,z,u,v,w,…. zijn ” onbekenden.”(Bedenk dat zo ‘ n veelterm gewoon de som is van termen als 5a3x2v5 en-7a4x3z6. Voor bepaalde diofantische vergelijkingen van dit soort proberen getaltheoretici te bepalen voor welke natuurlijke getalwaarden van de parameter a, de vergelijking heeft natuurlijke getaloplossingen in de onbekenden. Nu door eenvoudige standaardmethoden is het gemakkelijk om te zien dat een verzameling natuurlijke getallen S existentieel definieerbaar is dan en alleen als er een veeltermvergelijking van deze soort zodanig is dat S precies de verzameling van waarden is van de parameter waarvoor de vergelijking natuurlijke getaloplossingen heeft. Om deze reden worden existentieel definieerbare verzamelingen ook Diofantisch genoemd, en dit is de term die in de latere literatuur is overgenomen.Omdat hij er niet in slaagde om Tarski ’s vermoeden te bewijzen dat de verzameling van machten van 2 niet Diofantisch is, begon Robinson na te denken over de mogelijkheid dat Tarski’ s gok verkeerd zou zijn geweest. Om enige vooruitgang te boeken, moest ze een bepaalde hypothese aannemen, onbewezen op dat moment, die J. R. werd genoemd; grofweg J. R. stelt dat er een diofantische vergelijking is met twee parameters a, b met de eigenschap dat de paren (a, b) waarvoor de vergelijking oplossingen heeft zo zijn dat b exponentieel groeit als functie van A. door J. R. aan te nemen en een complexe en ingenieuze analyse uit te voeren, bewees ze niet alleen dat de machten van 2 Diofantisch zijn, maar ook dat de verzameling van priemgetallen en vele anderen dat ook zijn. Het is gemakkelijk te zien dat alle diofantische verzamelingen listable zijn, maar nu vroeg ze zich af of het omgekeerde waar zou kunnen zijn, of alle listable verzamelingen misschien Diofantine zijn. Ze wist dat dit ingrijpende gevolgen zou hebben.In 1900, om de nieuwe eeuw te begroeten, stelde de grote wiskundige David Hilbert een lijst van drieëntwintig problemen voor die als een uitdaging moesten worden beschouwd. De tiende op zijn lijst was om een algoritme te leveren om te bepalen of een bepaalde veeltermdiofantische vergelijking oplossingen heeft. Als inderdaad alle lijstbare verzamelingen Diofantisch waren, realiseerde ze zich, dan zou er in het bijzonder een niet-berekenbare diofantische verzameling zijn, wat impliceert dat er geen algoritme kon zijn zoals Hilbert had gevraagd. Dit zou een negatieve oplossing van Hilberts tiende probleem vormen.In de zomer van 1959 ontving Robinson per post een preprint van een paper van Martin Davis en Hilary Putnam. Het artikel bevatte een bewijs dat, aangenomen dat J. R., alle lijstbare verzamelingen inderdaad Diofantisch zijn. Het bewijs had echter een belangrijke leemte. Het gebruikte het feit dat er willekeurig lange reeksen van priemgetallen zijn met de speciale eigenschap dat het verschil tussen opeenvolgende termen van de reeks constant is. Hoewel dit waar is, was het in 1959 slechts een hypothese; het werd pas in 2004 bewezen. Robinson kende het vorige werk van Davis en Putnam heel goed en sprak zijn verbazing en plezier uit over hun prestatie. In zeer korte volgorde liet ze zien hoe ze zonder de extra hypothese over priemgetallen moest, en vond ze zelfs een korte versie van het bewijs. Dus, om de verwachte negatieve oplossing van Hilberts tiende probleem te verkrijgen, bleef het slechts over om J. R.
te bewijzen dat dit in januari 1970 door de tweeëntwintig jaar oude Joeri Matiyasevich werd bereikt met behulp van de beroemde Fibonacci-reeks 1,1,2,3,5,8,13, … Hij vond een diofantische vergelijking met twee parameters a, b die hij kon bewijzen heeft oplossingen voor het geval b is het Fibonacci nummer in de 2a-de plaats in deze reeks. Omdat de Fibonacci nummers exponentieel groeien, vormde dit een bewijs van J. R. Robinson was blij met Matiyasevich ‘ s ingenieuze bewijs en reisde naar Leningrad, waar hun families elkaar ontmoetten. Hun samenwerking was vruchtbaar; samen konden ze aantonen dat Hilberts tiende probleem onoplosbaar is, zelfs voor vergelijkingen in 13 onbekenden. (Later Matiyasevich was in staat om het aantal te verminderen tot 9.)
Coda de “nepotisme” regels die van kracht zijn aan de Universiteit van Californië zouden een regelmatige faculteitsaanstelling voor Robinson onmogelijk hebben gemaakt zolang haar man op de faculteit zat. In ieder geval kan het zijn dat haar gezondheidsproblemen een fulltime baan zouden hebben uitgesloten. Ze doceerde af en toe een cursus als assistent, en ze diende als de facto adviseur van twee uitstekende promovendi, Leonard Adleman en Kenneth Manders. Robinson tartte de voorspelling van de dokter dat ze niet veertig zou worden, maar op haar eenenveertigste verjaardag had haar beschadigde hart haar bijna invalide status gegeven. Ze werd gered door een chirurgische ingreep die pas onlangs beschikbaar was gekomen en die haar situatie sterk verbeterde, waardoor ze nog eens vijfentwintig jaar actief kon leven.Haar uitmuntende werk werd erkend door haar verkiezing in 1975 in de National Academy of Sciences, de eerste vrouw die werd gekozen in de wiskunde sectie. Datzelfde jaar kreeg ze uiteindelijk een aanstelling als hoogleraar aan de Universiteit van Californië in Berkeley.
op haar verzoek was het een kwart-time aanstelling. Een MacArthur Fellowship kwam in 1983. Ze werd verkozen tot president van de American Mathematical Society voor 1983-1984, de eerste vrouw die dit ambt bekleedde. Helaas kon ze haar termijn niet volbrengen. In de zomer van 1984 bleek ze aan leukemie te lijden. Na een korte remissie overleed Julia Robinson op 30 juli 1985 aan de ziekte.
bibliografie
werken van ROBINSON
” Definability and Decision Problems in Arithmetic.”Journal of Symbolic Logic 14 (1949): 98-114. Dit was Robinson ‘ s proefschrift. “Algemene Recursieve Functies.”Proceedings of the American Mathematical Society 1 (1950): 703-718. Naast de karakterisering van berekenbare functies van een hierboven beschreven argument, worden vele andere interessante resultaten besproken in dit artikel. “Existentiële Definieerbaarheid in rekenkunde.”Transactions of the American Mathematical Society 72 (1952): 437-449. Een fundamenteel artikel waarin werd aangetoond dat wat J. R. werd genoemd, de existentiële definieerbaarheid van de krachten van 2, de priemgetallen, en eigenlijk de volledige exponentiële functie impliceerde.
met Martin Davis en Hilary Putnam.”The Decision Problem for Exponential Diophantic Equations.”Annals of Mathematics 74 (1961): 425-436. In dit artikel werd bewezen dat J. R. de onoplosbaarheid van Hilberts tiende probleem impliceert. “An Introduction to Hyperarithmetical Functions.”Journal of Symbolic Logic 32 (1967): 325-342. Dit was Robinson ‘ s enige excursie naar het zeer onoverkomelijke.
Met Joeri Matiyasevich. “Reductie van een willekeurige diofantische vergelijking tot één op de 13 onbekenden.”Acta Arithmetica 27 (1975): 521-553. Virtuoze getaltheorie. Met Martin Davis en Yuri Matiyasevich. “Hilbert’ s tiende probleem. Diofantische vergelijkingen: positieve aspecten van een negatieve oplossing.”In Mathematical Developments Arising from Hilbert Problems, edited by Felix Browder. Providence, RI: American Mathematical Society, 1976.Verslag van Symposia in de zuivere wiskunde 28 (1976): 323-378. Een overzicht van het bewijs van de onoplosbaarheid van Hilberts tiende probleem en van wiskundige ontwikkelingen die daaruit voortvloeien door drie van de vier wiskundigen wiens werk tot dat bewijs leidde.
de verzamelde werken van Julia Robinson. Uitgegeven door Solomon
Feferman. Providence, RI: American Mathematical Society, 1996. Alle vijfentwintig van Robinson ‘ s publicaties worden hier volledig herdrukt. Daarnaast is er het mooie biografische essay over haar geschreven door Feferman voor de National Academy of Sciences.
overige bronnen
Davis, Martin. “Hilberts tiende probleem Is onoplosbaar.”
American Mathematical Monthly 80 (1973): 233-269; reprinted as an appendix in Computability and Unsolvability, edited by Martin Davis. New York: Dover, 1983. Een Steele-prijswinnend essay dat het volledige bewijs biedt van de onoplosbaarheid van Hilberts tiende probleem. De Dover herdruk is van een van de eerste boek-lengte behandelingen van computability theory.
—, en Reuben Hersh. “Hilbert’ s tiende probleem.”
Scientific American 229 (November 1973): 84-91. Herdrukt in the Chauvenet Papers, Vol. 2, uitgegeven door J. C. Abbott. Washington, DC: Mathematical Association of America, 1978. Een Chauvenet-prijswinnend artikel bedoeld voor het algemeen opgeleide publiek.
Matiyasevich, Yuri. “Mijn samenwerking met Julia Robinson.”
The Mathematical Intelligencer 14 (1992): 38-45. Zijn verhaal over hoe een jonge Rus en een veel oudere Amerikaanse vrouw samen elegante wiskunde produceerden.
———. Hilberts tiende probleem. Cambridge, MA: MIT Press,
1993. Een uitstekende introductie en enquête geschikt voor undergraduate wiskunde majors, met een zeer inclusieve bibliografie.
Reid, Constance. Julia, een leven in wiskunde. Washington, DC:
Mathematical Association of America, 1996. Door Robinson ’s zus, het heeft foto’ s, Reids nuttige biografie, getiteld “The Autobiography of Julia Robinson,” en een korte nota van Martin Davis over zijn werk met Hilary Putnam.
Martin Davis
