(b. St. Louis, Missouri, 8. prosince 1919; D. Berkeley, Kalifornie, 30. července 1985), matematika, matematická logika, teorie čísel, rozhodovací problémy, definovatelnost.
Robinsonova matematická práce vykazuje sílu a kouzlo. Řešila složité problémy a usilovala o elegantní řešení. Její život a dílo nelze správně vidět, aniž bychom si všimli, že jako žena v oblasti ovládané muži, byla něco jako průkopnice. Její métier byl rozhraní mezi dvěma větvemi matematiky, logiky a teorie čísel, obvykle myslel, že mají málo společného s sebou. Je známá zejména svými příspěvky k řešení desátého problému ve slavném seznamu dvaceti tří navržených matematikem Davidem Hilbertem v roce 1900. Byla zvolena do Národní akademie věd a také do předsednictví Americké matematické společnosti, v obou případech první matematička, která byla tak poctěna,a byl také příjemcem MacArthur Fellowship.
raný život Narodila se Julia Bowmanová, brzy v životě utrpěla dvě kalamity. Byly jí jen dva roky, když její matka zemřela, opouštět svého otce, aby se vyrovnal s Julií a její starší sestrou Constance. Po jeho novém sňatku, Rodina se přestěhovala na západ, nakonec do San Diega, kde se narodila její nevlastní sestra Billie. Když bylo Julii devět, podstoupila zničující nemoc: šarla následovaná revmatickou horečkou. Zmeškala dva roky školy a utrpěla velmi vážné poškození srdce. Akademicky vynikala a brzy si vymyslela ztracenou půdu. Na střední škole byla jedinou dívkou, která absolvovala kurzy pokročilé vědy a matematiky a absolvovala řadu vyznamenání. V roce 1936 vstoupila na San Diego State College, obor matematika. Hledání širších výhledů, přestoupila na Kalifornskou univerzitu v Berkeley na svůj poslední rok. Mezi pěti matematických kurzů vzala ten rok byl jeden na teorii čísel učil Raphael Robinson. Ohromen její schopností, přesvědčil ji, aby pokračovala ve studiu jako postgraduální studentka. Raphael byl matematik širokých zájmů a znalostí a ideální mentor. Brzy se však jejich vztah stal osobnějším a v prosinci 1941 se vzali. Jejich naděje na založení rodiny byly přerušeny, když Julia utrpěla potrat a lékař ji varoval, kvůli jejímu vážně poškozenému srdci, těhotenství by bylo extrémně nebezpečné. Jeho názor byl, že pravděpodobně zemře dříve, než jí bude čtyřicet. Ve snaze pomoci Julii překonat hlubokou depresi, do které byla vržena, Raphael ji povzbudil, aby hledala útěchu v matematice.
matematické pozadí 1930s viděl revoluční vývoj ve starověkém předmětu logiky, drasticky změnil od tradičního pole vznikl Aristoteles. Kurt Gödel slavný neúplnost věta poukázal na inherentní omezení formálních systémů logiky v zapouzdření matematické praxe. Práce Alonza Churcha, Alana Turinga a Emila posta i samotného Gödela ukázaly, že otázka existence algoritmických řešení konkrétních matematických problémů může být dána přesnou formulací. Tím se otevřela možnost, že v konkrétních případech nemusí taková algoritmická řešení existovat, a dokonce i to v takových případech může být prokázáno. Alfred Tarski vysvětlil, jak definovat sémantické pojmy pravdy a definovatelnost formálních jazyků. To byl vývoj, který poskytl kontext výzkumu Julie Robinsonové.
každá konkrétní větev matematiky bude používat symboly k označení konkrétních operací a vztahů, které jsou pro tento předmět zásadní. Kromě těchto symbolů používá moderní matematická logika speciální symboly
spolu se znakem familiar =. Jeden mluví o těchto symbolech spolu s těmi, které odpovídají určitému odvětví matematiky, jako o jazyce. Práce Julie Robinsonové byla z velké části v kontextu jazyka aritmetiky, který používá dva symboly + a × stojící pro sčítání a násobení, respektive, stejně jako symboly pro 0 a 1. Písmena abecedy se používají jako proměnné a v případě jazyka aritmetiky se obvykle rozumí, že se liší oproti známým přirozeným číslům 0,1,2…… tak například „věta“
vyjadřuje pravdivý výrok, že přidání dvou lichých čísel dává sudé číslo. Vzorec (u) (x = u+u+1)> sám o sobě definuje sadu lichých čísel, tj. pokud je x nahrazeno určitým přirozeným číslem, výsledná věta bude pravdivá, pokud je toto číslo liché. Otázky definovatelnosti a existence algoritmů byly pro Robinsonovu práci zásadní.
množina přirozených čísel S se nazývá vypočítatelná (nebo rekurzivní), pokud existuje algoritmus, který může určit pro dané přirozené číslo n, zda n patří nebo nepatří do S. množina přirozených čísel se nazývá listable (termín preferovaný Julií Robinsonovou) nebo rekurzivně vyčíslitelná, pokud existuje algoritmus pro systematické vytváření seznamu členů s. všechny výsledky neřešitelnosti lze považovat za důsledky klíčové věty: existuje seznamovatelná množina, která není vypočítatelná. Tyto záležitosti byly také velmi důležité v Robinsonově práci.
Dizertační práce Julie Robinsonové bylo to na semináři vedeném charismatickým Alfredem Tarskim, jedním z velkých logiků dvacátého století, že Robinson našel její métier. Tarski opustil své rodné Polsko v srpnu 1939 na krátké cestě, aby se zúčastnil konference ve Spojených státech, těsně předtím, než německá invaze do Polska urychlila druhou světovou válku. Tarski položil řadu nevyřešených otázek o definovatelnosti v jazyce aritmetiky, ke kterému byl Robinson přitahován. Ve 40. letech 19. století bylo dobře známo, že neexistuje žádný algoritmus, který by určil, zda je daná věta v jazyce aritmetiky s proměnnými v rozmezí přirozených čísel pravdivá. Jak se říká, Jedná se o algoritmicky neřešitelný problém. Tarski chtěl vědět, zda to samé platí, když v tomto stejném jazyce, proměnné se mohou pohybovat nad všemi racionálními čísly místo pouze přirozených čísel. (Racionální čísla jsou vyjádřitelná jako zlomky m / n nebo-m / n, kde m je přirozené číslo a n je nenulové přirozené číslo.) Byly vyvinuty techniky pro „redukci“ jednoho takového „rozhodovacího problému“ na jiný. V tomto případě by se ukázalo, že pokud by existoval algoritmus pro testování pravdy věta jazyka aritmetiky s proměnnými omezenými na kolísání nad racionálními čísly, takový algoritmus by mohl být použit k poskytnutí algoritmu, který by udělal totéž, když se proměnné pohybují nad přirozenými čísly. Tak, protože pro druhý takový algoritmus neexistuje, z toho by vyplynulo, že ani jeden pro první nemůže existovat.
hlavním výsledkem Robinsonovy disertační práce byl explicitní vzorec v jazyce aritmetiky, s proměnnými omezenými na změnu nad racionálními čísly, který přesně definuje množinu celých čísel(tj. množinu přirozených čísel a jejich negativů). Poté následovalo, že problém určení pravdy věty aritmetiky zůstává neřešitelný, i když se proměnné pohybují nad racionálními čísly. Následovaly i další neřešitelné výsledky. Robinsonův přístup byl složitý, elegantní, a důmyslný pomocí některých poměrně hlubokých nápadů z teorie čísel.
elegantní charakterizace Robinson vždy hledal eleganci a jednoduchost ve své matematické práci. Jeden z jejích raných prací ukázal, jak charakterizovat, zvláště jednoduchým způsobem, algoritmicky vypočítatelné funkce (také nazývané rekurzivní funkce), které mapují přirozená čísla do sebe. Její krásná charakterizace zahrnuje dvě počáteční funkce a tři operace pro získání nových funkcí z daných funkcí. Jednou z počátečních funkcí je pouze nástupnická funkce S (x)= x+1. Druhý, který Robinson nazývá E, je definován jako rozdíl mezi daným číslem a největším dokonalým čtvercem, který jej nepřesahuje. (Tedy E (19) = 19-16 = 3 A E (25) = 25 -25 = 0.) Tyto tři operace jsou následující: (1) z daných funkcí F A G získají funkci H (x)=F (G (x)); (2) z daných funkcí F A G získají funkci H(x)=F(x) + G(x); a (3) z dané funkce F, jejíž hodnoty zahrnují všechna přirozená čísla, získají funkci H, kde H(x) je nejmenší číslo t, pro které F(t)=x.
je skutečně pozoruhodné, že všechny vyčíslitelné funkce (od přirozených čísel po přirozená čísla) lze získat začátkem dvou počátečních funkcí a opakovaným použitím těchto tří operací.
mnohem později Robinson ukázal stejnou eleganci a vervu při hledání nových charakteristik domény daleko od vypočítatelné. Již byla zmíněna existence listovatelné množiny K, která není vyčíslitelná. Neexistuje tedy žádný algoritmus pro určení členství v K. Zvažováním sad, které mohou být uvedeny pomocí algoritmů, které mají přístup k informacím o členství o takových sadách (metaforicky prostřednictvím „oracle“), lze do záhybu přenést další sady a tento proces lze iterovat. Tím, že se tato iterace může vyskytnout v jakémkoli konečném počtu, získané množiny se ukáží jako přesně ty, které se nazývají aritmetické, množiny definovatelné v jazyce aritmetiky s proměnnými v rozmezí nad přirozenými čísly. Ale není třeba se zde zastavit. Jeden může definovat non-aritmetické množinu, a pak použít jako „oracle“, aby bylo možné seznam ještě více sad. Existuje přirozené místo, kde tento proces končí, a množiny takto získaných přirozených čísel se nazývají hyperaritmetické. Byla to právě tato vzácná říše, pro kterou Robinson poskytl jednoduchou a přímou charakterizaci.
existenciální definovatelnost a Hilbertův desátý problém dílo, pro které je Julia Robinsonová nejvíce připomínána, vzniklo zdánlivě jednoduchým problémem, který představuje Alfred Tarski. Tarski chtěl vědět, které sady přirozených čísel jsou definovatelné vzorci jazyka aritmetiky, pokud jsou symboly vyloučeny. Takové množiny označil za existenčně definovatelné a navrhl problém prokázat, že množina {1,2,4,8,16,….} mocnin 2 není existenčně definovatelná. To byl přesně ten druh problému, který se Robinsonovi líbil. Pojem existenciální definovatelnosti lze snadno považovat za úzce související s problémy, které teoretici čísel studují, tzv. Obvykle se jedná o polynomiální rovnici p (A,x,y,z, u, v, w,….) = 0 s celočíselnými koeficienty, kde a je parametr a x, y, z, u, v, w,…. jsou “ neznámí.“(Připomeňme, že takový polynom je jen součtem pojmů jako 5a3x2v5 a-7a4x3z6.) Pro konkrétní Diofantické rovnice tohoto druhu se teoretici čísel snaží určit, pro které přirozené číselné hodnoty parametru a má rovnice řešení přirozených čísel v neznámých. Nyní jednoduchými standardními metodami je snadné vidět, že množina přirozených čísel S je existenčně definovatelná, a to pouze tehdy, pokud existuje polynomiální rovnice tohoto druhu taková, že S je přesně sada hodnot parametru, pro který má rovnice řešení přirozených čísel. Z tohoto důvodu se existenciálně definovatelné sady také nazývají Diofantin, a to je termín, který byl přijat v pozdější literatuře.
Robinson neměl žádný úspěch v prokázání Tarskiho domněnky, že soubor SIL 2 není Diofantin, začal zvažovat možnost, že Tarskiho odhad mohl být špatný. Aby mohla udělat nějaký pokrok, musela předpokládat určitou hypotézu, v té době neprokázanou, která se nazývala J. R.; zhruba řečeno J. R. uvádí, že existuje diofantická rovnice se dvěma parametry a, b s vlastností,že páry (a, b), pro které má rovnice řešení, jsou takové, že b roste exponenciálně jako funkce a. předpokládáním J. R. a provedením komplexní a důmyslné analýzy dokázala nejen to, že mocnina 2 je Diofantina, ale také že množina prvočísel, stejně jako mnoho dalších, jsou také. Je snadno vidět, že všechny diofantinové sady jsou seznamovatelné, ale teď přemýšlela, zda by konverzace mohla být pravdivá, zda všechny seznamovatelné sady mohou být Diofantiny. Věděla, že to bude mít hluboké důsledky.
v roce 1900, aby pozdravil nové století, velký matematik David Hilbert navrhl seznam dvaceti tří problémů, které mají stát jako výzva. Desátý na jeho seznamu měl poskytnout algoritmus pro určení, zda daná polynomiální diofantická rovnice má řešení. Pokud by skutečně všechny seznamovatelné sady byly Diofantiny, uvědomila si, pak by zejména existovala nevyčíslitelná diofantinová sada, což by znamenalo, že by nemohl existovat žádný algoritmus, jaký Hilbert požadoval. To by představovalo negativní řešení Hilbertova desátého problému.
v létě 1959 Robinson obdržel poštou předtisk papíru Martina Davise a Hilary Putnamové. Dokument obsahoval důkaz, že za předpokladu, že J. R., jsou všechny seznamovatelné soubory skutečně Diofantinem. Důkaz však měl důležitou mezeru. Používá skutečnost, že existují libovolně dlouhé sekvence prvočísel se speciální vlastností, že rozdíl mezi po sobě jdoucími termíny sekvence je konstantní. I když je to pravda, v roce 1959 to byla pouhá hypotéza; byla prokázána až v roce 2004. Robinson znal předchozí práci Davise a Putnama velmi dobře a vyjádřil překvapení a potěšení z jejich úspěchu. Ve velmi krátkém pořadí ukázala, jak to udělat bez další hypotézy o prvočíslech, a dokonce našla krátkou verzi důkazu. Abychom tedy získali očekávané negativní řešení Hilbertova desátého problému, zbývá jen dokázat J. R.
to bylo dosaženo v lednu 1970 dvaadvacetiletým Jurijem Matijasevičem pomocí slavné Fibonacciho sekvence 1,1,2,3,5,8,13,…. Našel diofantickou rovnici se dvěma parametry a, b, které dokázal dokázat, že má řešení pro případ, že b je Fibonacciho číslo na 2a-tém místě v této sekvenci. Protože Fibonacciho čísla rostou exponenciálně, představovalo to důkaz, že J. R. Robinson byl potěšen matijasevičovým geniálním důkazem a odcestoval do Leningradu, kde se setkaly jejich rodiny. Jejich spolupráce byla plodná; společně dokázali ukázat, že Hilbertův desátý problém je neřešitelný i pro rovnice ve 13 neznámých. (Později byl Matijasevič schopen snížit počet na 9.)
Coda pravidla „protekce“ platná na Kalifornské univerzitě by znemožnila pravidelné jmenování Robinsona na fakultu, pokud by byl její manžel na Fakultě. V každém případě se může stát, že její zdravotní problémy by vyloučily pozici na plný úvazek. Příležitostně vyučovala kurz jako doplněk, a sloužila jako de facto poradkyně dvou vynikajících doktorandů, Leonard Adleman a Kenneth Manders. Robinson se vzepřel doktorově předpovědi, že se nedožije čtyřiceti let, ale do čtyřicátých prvních narozenin ji její poškozené srdce přivedlo blízko k invalidnímu stavu. Byla zachráněna chirurgickým zákrokem, který byl k dispozici teprve nedávno a který výrazně zlepšil její situaci, což jí umožnilo žít aktivní život dalších dvacet pět let.
její vynikající práce byla uznána jejím zvolením v roce 1975 do Národní akademie věd, první žena, která byla zvolena do sekce matematiky. Téhož roku jí bylo nakonec nabídnuto profesorské jmenování na Kalifornské univerzitě v Berkeley.
na její žádost šlo o čtvrtletní jmenování. MacArthur Fellowship přišel v roce 1983. V letech 1983-1984 byla zvolena prezidentkou Americké matematické společnosti, první ženou, která zastávala tento úřad. Tragicky, nemohla dokončit své funkční období. Bylo zjištěno, že trpí leukémií v létě 1984. Po krátké remisi zemřela Julia Robinsonová na nemoc 30. července 1985.
bibliografie
práce Robinsona
“ definovatelnost a rozhodovací problémy v aritmetice.“Journal of Symbolic Logic 14 (1949): 98-114. To byla Robinsonova disertační práce. „Obecné Rekurzivní Funkce.“Proceedings of the American Mathematical Society 1 (1950): 703-718. Kromě charakterizace vyčíslitelných funkcí jednoho výše popsaného argumentu je v tomto článku diskutováno mnoho dalších zajímavých výsledků. „Existenciální definovatelnost v aritmetice.“Transakce Americké matematické společnosti 72 (1952): 437-449. Základní dokument, ve kterém se ukázalo, že to, co se nazývalo J. R., naznačuje existenciální definovatelnost mocnin 2, prvočísel a vlastně plné exponenciální funkce.
s Martinem Davisem a Hilary Putnamovou.“Rozhodovací problém pro exponenciální Diofantické rovnice.“Annals of Mathematics 74 (1961): 425-436. Právě v tomto článku bylo prokázáno, že J. R. znamená neřešitelnost Hilbertova desátého problému. „Úvod do Hyperaritmetických funkcí.“Journal of Symbolic Logic 32 (1967): 325-342. To byla Robinsonova jediná exkurze k velmi nespočetným.
S Jurijem Matijasevičem. „Redukce libovolné Diofantické rovnice na jednu ze 13 neznámých.“Acta Arithmetica 27 (1975): 521-553. Teorie virtuózních čísel! S Martinem Davisem a Jurijem Matijasevičem. „Hilbertův desátý problém. Diofantické rovnice: pozitivní aspekty negativního řešení.“V matematickém vývoji vyplývajícím z Hilbertových problémů, editoval Felix Browder. Providence, RI: Americká Matematická společnost, 1976.
Sborník sympozií v čisté matematice 28 (1976): 323-378. Průzkum důkazu o neřešitelnosti Hilbertova desátého problému, jakož i matematického vývoje vyplývajícího z něj třemi ze čtyř matematiků, jejichž práce vedla k tomuto důkazu.
sebraná díla Julie Robinsonové. Upravil Solomon
Feferman. Providence, RI: Americká Matematická společnost, 1996. Všech dvacet pět Robinsonových publikací je zde přetištěno v plném rozsahu. Kromě toho existuje jemná životopisná esej o ní napsaná Fefermanem pro Národní akademii věd.
jiné zdroje
Davis, Martin. „Hilbertův desátý problém je neřešitelný.“
American Mathematical Monthly 80 (1973): 233-269; přetištěno jako příloha v Computability and Unsolvability, editoval Martin Davis. New York: Dover, 1983. Steele-oceněná esej, která nabízí úplný důkaz neřešitelnosti Hilbertova desátého problému. Doverův dotisk je jedním z prvních knižních ošetření teorie vyčíslitelnosti.
—, a Reuben Hersh. „Hilbertův desátý problém.“
Scientific American 229 (Listopad 1973): 84-91. Přetištěno v novinách Chauvenet, sv. 2, editoval J. C. Abbotte. Washington, DC: Matematická asociace Ameriky, 1978. Chauvenet-oceněný článek určený pro širokou vzdělanou veřejnost.
Matijasevič, Jurij. „Moje spolupráce s Julií Robinsonovou.“
The Mathematical Intelligencer 14 (1992): 38-45. Jeho příběh o tom, jak mladý Rus a mnohem starší americká žena přišli společně vyrábět elegantní matematiku.
———. Hilbertův desátý problém. Cambridge, MA: MIT Press,
1993. Vynikající úvod a průzkum vhodný pro vysokoškolské obory matematiky, s velmi inkluzivní bibliografií.
Reid, Constance. Julie, život v matematice. Washington, DC:
Matematická asociace Ameriky, 1996. Robinsonova sestra má fotografie, reidovu užitečnou biografii nazvanou „Autobiografie Julie Robinsonové“ a krátkou poznámku Martina Davise o jeho práci s Hilary Putnamovou.
Martin Davis
