(f. St. Louis, Missouri, 8. December 1919; D.Berkeley, Californien, 30. juli 1985), matematik, matematisk logik, talteori, beslutningsproblemer, definerbarhed.
Robinsons matematiske arbejde udviser magt og charme. Hun tacklede vanskelige problemer og stræbte efter elegante løsninger. Hendes liv og arbejde kan ikke ses ordentligt uden at bemærke det som en kvinde i et mandsdomineret felt, hun var noget af en pioner. Hendes m pristier var grænsefladen mellem to grene af matematik, logik og teorien om tal, normalt menes at have lidt at gøre med hinanden. Hun er især kendt for sine bidrag til løsningen af det tiende problem i en berømt liste over treogtyve foreslået af matematikeren David Hilbert i 1900. Hun blev valgt til National Academy of Sciences og også til formandskabet for American Mathematical Society, i begge tilfælde den første kvindelige matematiker at være så beæret, og var også en modtager af en MacArthur fællesskab.
Tidligt liv født Julia bueskytte, hun led to ulykker tidligt i livet. Hun var kun to, da hendes mor døde og efterlod sin far til at klare Julia og hendes ældre søster Constance. Efter hans gifte igen, familien flyttede vestpå, i sidste ende til San Diego, hvor hendes stedsøster Billie blev født. Da Julia var ni, gennemgik hun en ødelæggende sygdom: skarlagensfeber efterfulgt af gigtfeber. Hun savnede to års skole og led meget alvorlig skade på hendes hjerte. Akademisk udmærkede hun sig og udgjorde snart sin tabte grund. I gymnasiet var hun den eneste pige til at tage de avancerede videnskab og matematik kurser og dimitterede med en række udmærkelser. I 1936 hun trådte San Diego State College, hovedfag i matematik. Søger bredere udsigter, hun overført til University of California i Berkeley for hendes senior år. Blandt de fem matematik kurser hun tog det år var en på teorien om tal undervist af Raphael Robinson. Imponeret over hendes evne overbeviste han hende om at fortsætte sine studier som kandidatstuderende. Raphael var en matematiker af brede interesser og viden og en ideel mentor. Men snart blev deres forhold mere personligt, og de blev gift i December 1941. Deres håb om at starte en familie blev knust, da Julia fik en spontanabort og blev advaret af en læge om det, på grund af hendes alvorligt beskadigede hjerte, graviditet ville være ekstremt farlig. Hans mening var, at hun sandsynligvis ville dø, før hun var fyrre. I et forsøg på at hjælpe Julia overvinde den dybe depression, som hun blev kastet, Raphael opfordrede hende til at søge trøst i matematik.
matematisk baggrund 1930 ‘ erne havde set revolutionerende udvikling i det gamle emne for logik, drastisk ændret fra det traditionelle felt, der stammer fra Aristoteles. Kurt g Kurtdel ‘ s berømte ufuldstændighed sætning havde peget på de iboende begrænsninger af formelle logiksystemer i indkapsling af matematisk praksis. Hans arbejde, Alan Turing, og Emil Post samt G. K. selv havde vist, at spørgsmålet om eksistensen af algoritmiske løsninger på specifikke matematiske problemer kunne gives en præcis formulering. Dette åbnede muligheden for, at sådanne algoritmiske løsninger i specifikke tilfælde muligvis ikke findes, og endda at dette i sådanne tilfælde kan bevises. Alfred Tarski havde forklaret, hvordan man definerer semantiske forestillinger om sandhed og definerbarhed af formelle sprog. Dette var den udvikling, der gav sammenhængen med Julia Robinsons forskning.
enhver bestemt gren af matematik vil bruge symboler til at stå for de særlige operationer og relationer, der er grundlæggende for dette emne. Ud over sådanne symboler bruger moderne matematisk logik de specielle symboler
sammen med det velkendte = tegn. Man taler om disse symboler sammen med dem, der svarer til en bestemt gren af matematik som udgør et sprog. Julia Robinsons arbejde var stort set i sammenhæng med det aritmetiske sprog, der bruger de to symboler + og kr.stående til henholdsvis Tilføjelse og multiplikation samt symboler for 0 og 1. Bogstaver i alfabetet bruges som variabler, og i tilfælde af aritmetisk sprog forstås de normalt at variere over de velkendte naturlige tal 0,1,2 …… så for eksempel udtrykker “sætningen”
Det sande forslag om, at tilføjelse af to ulige tal giver et lige tal. Formlen(u) (h = u+u+1)> definerer i sig selv sættet med ulige tal, dvs.hvis h erstattes af et bestemt naturligt tal, vil den resulterende sætning være sand, hvis og kun hvis dette tal er ulige. Spørgsmål om definerbarhed og eksistensen af algoritmer var grundlæggende for robinsons arbejde.
et sæt naturlige tal S kaldes beregnelig (eller rekursiv), hvis der er en algoritme, der kan bestemme for et givet naturligt tal n, om n tilhører S. Et sæt naturlige tal kaldes listelig (udtrykket foretrukket af Julia Robinson) eller rekursivt tællelig, hvis der er en algoritme til systematisk at lave en liste over medlemmerne af S. Alle resultater, der ikke kan løses, kan betragtes som konsekvenser af nøglesætningen: der findes et listbart sæt, der ikke kan beregnes. Disse spørgsmål var også meget vigtige i Robinsons arbejde.
Julia Robinsons afhandling det var på et seminar ledet af den karismatiske Alfred Tarski, en af de store logikere i det tyvende århundrede, at Robinson fandt hende M mere. Tarski havde forladt sit hjemland Polen i August 1939 om, hvad der skulle have været en kort tur for at deltage i en konference i USA, lige før den tyske invasion af Polen udfældede anden verdenskrig. Tarski stillede en række uløste spørgsmål om definerbarhed på det aritmetiske sprog, som Robinson blev tiltrukket af. I 1940 ‘ erne var det velkendt, at der ikke er nogen algoritme til at bestemme, om en given sætning på aritmetisk sprog, med variablerne, der spænder over de naturlige tal, er sandt. Som man siger, er dette et algoritmisk uløseligt problem. Tarski ønskede at vide, om det samme er tilfældet, når det er på samme sprog, variabler har lov til at variere over alle rationelle tal i stedet for kun de naturlige tal. (De rationelle tal er dem, der kan udtrykkes som fraktioner m/n eller-m / n hvor m er et naturligt tal og n er et ikke-nul naturligt tal.) Der var udviklet teknikker til at” reducere “et sådant” beslutningsproblem ” til et andet. I dette tilfælde ville man vise, at hvis der var en algoritme til test for sandhed, en sætning af aritmetisk sprog med variablerne begrænset til at variere over de rationelle tal, kunne en sådan algoritme bruges til at tilvejebringe en algoritme til at gøre det samme, når variablerne spænder over de naturlige tal. Så da der ikke findes en sådan algoritme for sidstnævnte, ville det følge, at der heller ikke kunne være en for førstnævnte.
hovedresultatet af Robinsons afhandling var en eksplicit formel på aritmetisk sprog, med variablerne begrænset til at variere over de rationelle tal, der præcist definerer sæt af heltal (det vil sige sæt af naturlige tal og deres negativer). Det fulgte derefter, at problemet med at bestemme sandheden i en sætning af aritmetik forbliver uløselig, selv når variablerne spænder over de rationelle tal. Andre uløselige resultater fulgte også. Robinsons tilgang var indviklet, elegant og genial ved hjælp af nogle ret dybe ideer fra talteori.
elegante karakteriseringer Robinson søgte altid elegance og enkelhed i sit matematiske arbejde. Et af hendes tidlige papirer viste, hvordan man på en særlig enkel måde karakteriserer de algoritmisk beregnelige funktioner (også kaldet de rekursive funktioner), der kortlægger de naturlige tal i sig selv. Hendes smukke karakterisering involverer to indledende funktioner og tre operationer til opnåelse af nye funktioner fra givne funktioner. En af de oprindelige funktioner er kun efterfølgerfunktionen S (H)= H + 1. Den anden, som Robinson kalder E, defineres som forskellen mellem et givet tal og det største perfekte firkant, der ikke overstiger det. (Således E(19) = 19 – 16 = 3 og E (25) = 25 -25 = 0.) De tre operationer er som følger: (1) fra givne funktioner f og G opnår funktionen H(H)=F(G(H)); (2) fra givne funktioner f og G opnår funktionen H(H)=F(H) + G(H); og (3) Fra en given funktion F, hvis værdier inkluderer alle naturlige tal, opnår funktionen H, hvor H(H) er det mindste tal t, for hvilket F(t)=h.
Det er virkelig bemærkelsesværdigt, at alle beregnelige funktioner (fra de naturlige tal til de naturlige tal) kan opnås ved at begynde med de to indledende funktioner og anvende disse tre operationer igen og igen.
meget senere viste Robinson den samme elegance og verve i at finde nye karakteriseringer af et domæne langt væk fra det beregnelige. Eksistensen af et listbart sæt K, der ikke kan beregnes, er allerede nævnt. Så der er ingen algoritme til bestemmelse af medlemskab i K. Ved at overveje sæt, der kan vises ved hjælp af algoritmer, der har adgang til medlemsoplysninger om sådanne sæt (metaforisk via et “orakel”), kan yderligere sæt bringes ind i folden, og denne proces kan gentages. Ved at tillade denne iteration at forekomme et endeligt antal gange, viser de opnåede sæt sig at være nøjagtigt dem, der kaldes aritmetiske, sætene, der kan defineres på aritmetisk sprog med variabler, der spænder over de naturlige tal. Men der er ingen grund til at stoppe her. Man kan definere et ikke-aritmetisk sæt og derefter bruge det som et “orakel” for at kunne liste endnu flere sæt. Der er et naturligt sted, hvor denne proces kommer til en ende, og sæt af naturlige tal, der er opnået, kaldes hyperaritmetisk. Det var dette sjældne rige, for hvilket Robinson gav en enkel og direkte karakterisering.
eksistentiel Definerbarhed og Hilberts tiende Problem det arbejde, som Julia Robinson huskes mest for, stammer fra et tilsyneladende simpelt problem stillet af Alfred Tarski. Tarski ønskede at vide, hvilke sæt naturlige tal der kan defineres ved formler af aritmetisk sprog, hvis symbolerne og er udelukket. Han kaldte sådanne sæt eksistentielt definerbare og foreslog problemet med at bevise, at Sættet {1,2,4,8,16,….} af beføjelser på 2 er ikke eksistentielt definerbar. Dette var netop den slags problem, som Robinson kunne lide. Begrebet eksistentiel definerbarhed kunne let ses at være tæt knyttet til problemer af en art, som talteoretikere studerer, såkaldte Diophantine problemer. Disse har typisk at gøre med en polynomligning p (A, H, y, å, u, v, v,….) = 0 med heltalskoefficienter, hvor A er en parameter og H,y,å,u,v, h,…. er ” ukendte.”(Husk at et sådant polynom er bare summen af udtryk som 5a3h2v5 og-7a4h3s6.) For særlige Diophantine ligninger af denne art forsøger talteoretikere at bestemme for hvilke naturlige talværdier af parameteren a, ligningen har naturlige talløsninger i de ukendte. Nu ved enkle standardmetoder er det let at se, at et sæt naturlige tal S er eksistentielt definerbart, hvis og kun hvis der er en polynomligning af denne art, således at S er nøjagtigt det sæt værdier for den parameter, for hvilken ligningen har naturlige talløsninger. Af denne grund kaldes eksistentielt definerbare sæt også Diofantin, og dette er det udtryk, der er blevet vedtaget i den senere litteratur.
da Robinson ikke havde nogen succes med at bevise Tarskis formodning om, at sæt af kræfter på 2 ikke er Diofantin, begyndte han at overveje muligheden for, at Tarskis gæt kunne have været forkert. For at gøre fremskridt måtte hun antage en bestemt hypotese, uprøvet på det tidspunkt, der kom til at blive kaldt J. R.; groft sagt J. R. siger, at der er en Diophantin ligning med to parametre A,b med den egenskab,at parene (A, b), som ligningen har løsninger på, er sådan, at b vokser eksponentielt som en funktion af A. ved at antage J. R. og udføre en kompleks og genial analyse beviste hun ikke kun, at kræfterne i 2 er Diophantin, men også at sættet med primtal såvel som mange andre også er. Det ses let, at alle Diophantine sæt er listable, men nu spekulerede hun på, om det omvendte kunne være sandt, om alle listable sæt kunne være Diophantine. Dette vidste hun ville have dybe konsekvenser.
i 1900 for at hilse på det nye århundrede foreslog den store matematiker David Hilbert en liste over treogtyve problemer, der skulle stå som en udfordring. Den tiende på hans liste var at tilvejebringe en algoritme til at bestemme, om en given polynomisk Diofantinligning har løsninger. Hvis alle listbare sæt faktisk var Diophantin, indså hun, at der især ville være et ikke-beregneligt Diophantinsæt, hvilket antyder, at der ikke kunne være nogen algoritme, som Hilbert havde bedt om. Dette ville udgøre en negativ løsning på Hilberts tiende problem.
i sommeren 1959 modtog Robinson i posten et preprint af et papir af Martin Davis og Hilary Putnam. Papiret indeholdt et bevis på, at alle listable sæt, forudsat at Jr, faktisk er Diofantin. Beviset havde imidlertid et vigtigt hul. Det brugte det faktum, at der er vilkårligt lange sekvenser af primtal med den specielle egenskab, at forskellen mellem på hinanden følgende udtryk for sekvensen er konstant. Selvom dette er sandt, var det i 1959 en ren hypotese; det blev først bevist i 2004. Robinson kendte Davis og Putnams tidligere arbejde meget godt og udtrykte overraskelse og glæde over deres præstation. I meget kort rækkefølge viste hun, hvordan man kunne undvære den ekstra hypotese om primtal, og fandt endda en kort version af beviset. Så for at opnå den forventede negative løsning af Hilberts tiende problem forblev det kun at bevise J. R.
dette blev opnået i januar 1970 af den toogtyve år gamle Yuri Matiyasevich ved hjælp af den berømte Fibonacci-sekvens 1,1,2,3,5,8,13,…. Han fandt en Diophantin ligning med to parametre a,b at han var i stand til at bevise har løsninger bare i tilfælde b er Fibonacci nummer i 2A-th sted i denne rækkefølge. Fordi Fibonacci-tallene vokser eksponentielt, udgjorde dette et bevis på J. R. Robinson var glad for Matiyasevichs geniale bevis og rejste til Leningrad, hvor deres familier mødtes. Deres samarbejde var frugtbart; sammen var de i stand til at vise, at Hilberts tiende problem er uløseligt, selv for ligninger i 13 ukendte. (Senere var Matiyasevich i stand til at reducere antallet til 9.)
Coda de “nepotisme” – regler, der gælder ved University of California, ville have gjort en regelmæssig fakultetsudnævnelse for Robinson umulig, så længe hendes mand var på fakultetet. Under alle omstændigheder kan det godt være, at hendes sundhedsmæssige problemer ville have udelukket en fuldtidsstilling. Hun underviste lejlighedsvis i et kursus som supplement, og hun fungerede som de facto rådgiver for to fremragende ph.d. – studerende, Leonard Adleman og Kenneth Manders. Robinson trodsede lægens forudsigelse om, at hun ikke ville leve for at være fyrre, men ved sin fyrreogtreds fødselsdag havde hendes beskadigede hjerte bragt hende tæt på ugyldig status. Hun blev reddet af en kirurgisk procedure, der først for nylig var blevet tilgængelig, og som i høj grad forbedrede hendes situation, gør det muligt for hende at leve et aktivt liv i yderligere femogtyve år.
hendes fremragende arbejde blev anerkendt af hendes valg i 1975 til National Academy of Sciences, den første kvinde til at blive valgt til matematik sektion. Samme år blev hun endelig tilbudt en professoraftale ved University of California i Berkeley.
på hendes anmodning var det en kvart tid aftale. Et MacArthur-fællesskab kom i 1983. Hun blev valgt til formand for American Mathematical Society for 1983-1984, den første kvinde til at holde dette kontor. Tragisk, hun var ude af stand til at fuldføre sin periode. Hun blev fundet at lide af leukæmi i løbet af sommeren 1984. Efter en kort remission døde Julia Robinson af sygdommen den 30. juli 1985.
bibliografi
værker af ROBINSON
“Definerbarhed og beslutningsproblemer i aritmetik.”Tidsskrift for symbolsk logik 14 (1949): 98-114. Dette var Robinsons afhandling. “Generelle Rekursive Funktioner.”Proceedings of the American Mathematical Society 1 (1950): 703-718. Ud over karakteriseringen af beregnelige funktioner af et argument beskrevet ovenfor, mange andre interessante resultater diskuteres i dette papir. “Eksistentiel Definerbarhed i aritmetik.”Transaktioner af American Mathematical Society 72 (1952): 437-449. Et grundlæggende papir, hvor det, der blev kaldt J. R., viste sig at antyde den eksistentielle definerbarhed af kræfterne i 2, primerne og faktisk den fulde eksponentielle funktion.
med Martin Davis og Hilary Putnam.”Beslutningen Problem for eksponentielle Diophantine ligninger.”Annaler for Matematik 74 (1961): 425-436. Det var i dette papir, at det blev bevist, at J. R. indebærer uopløseligheden af Hilberts tiende problem. “En introduktion til Hyperaritmetiske funktioner.”Tidsskrift for symbolsk logik 32 (1967): 325-342. Dette var Robinsons ene udflugt til det meget ukomputable.
Med Yuri Matiyasevich. “Reduktion af en vilkårlig Diofantinligning til en ud af 13 ukendte.”Acta Arithmetica 27 (1975): 521-553. Virtuos talteori! Med Martin Davis og Yuri Matiyasevich. “Hilberts tiende Problem. Diophantine ligninger: Positive aspekter af en negativ løsning.”I matematiske udvikling som følge af Hilbert problemer, redigeret af Feliks Bruder. Providence, RI: American Mathematical Society, 1976.
Proceedings of Symposies in Pure Mathematics 28 (1976): 323-378. En undersøgelse af bevis for uløseligheden af Hilbert ‘ s tiende problem samt af matematiske udvikling stammer fra det af tre af de fire matematikere, hvis arbejde førte til dette bevis.
De Samlede Værker af Julia Robinson. Redigeret af Solomon
Feferman. Providence, RI: American Mathematical Society, 1996. Alle femogtyve af Robinsons publikationer genoptrykkes her fuldt ud. Derudover er der det fine biografiske essay om hende skrevet af Feferman til National Academy of Sciences.
andre kilder
Davis, Martin. “Hilberts tiende Problem er uløseligt.”
American Mathematical Monthly 80 (1973): 233-269; genoptrykt som et tillæg I beregningsevne og uopløselighed, redigeret af Martin Davis. Dover, 1983. Et Steele-prisvindende essay, der giver det komplette bevis på uopløseligheden af Hilberts tiende problem. Dover-genoptrykket er af en af de første boglængdebehandlinger af beregningsteori.
—, og Reuben Hersh. “Hilberts tiende Problem.”
Scientific American 229 (November 1973): 84-91. Genoptrykt i Chauvenet Papers, Vol. 2, redigeret af J. C. Abbott. Den matematiske sammenslutning af Amerika, 1978. En Chauvenet-prisvindende artikel beregnet til den almindeligt uddannede offentlighed.
Matiyasevich, Yuri. “Mit samarbejde med Julia Robinson.”
Den Matematiske Intelligencer 14 (1992): 38-45. Hans historie om, hvordan en ung russer og en meget ældre amerikansk kvinde kom til at producere elegant matematik sammen.
———. Hilberts tiende Problem. Cambridge, MA: MIT Press,
1993. En fremragende introduktion og undersøgelse egnet til bachelor matematik majors, med en meget inkluderende bibliografi.
Reid, Constance. Julia, et liv i matematik. USA:
matematisk forening af Amerika, 1996. Af Robinsons søster har den fotografier, Reids nyttige biografi med titlen” Julia Robinsons selvbiografi ” og en kort note af Martin Davis om hans arbejde med Hilary Putnam.
Martin Davis
