Proof,ComputationandAgency SYNTHESE LIBRARY STUDIESINEPISTEMOLOGY, LOGIC,METHODOLOGY,ANDPHILOSOPHYOFSCIENCE Editors-in-Chief: VINCENT F. HENDRICKS, University of Copenhagen, Denmark JOHN SYMONS, University of Texas at El Paso, U.S.A. Honorary Editor: JAAKKO HINTIKKA, Boston University, U.S.A. Editors: DIRK VAN DALEN, University of Utrecht, The Netherlands THEO A.F. KUIPERS, University of Groningen, The Netherlands TEDDY SEIDENFELD, Carnegie Mellon University, U.S.A. PATRICK SUPPES, Stanford University, California, U.S.A. JAN WOLEN´ SKI, Jagiellonian University, Krako´w, Poland VOLUME 352 For further volumes: http://www.springer.com/series/6607 Proof, Computation and Agency Logic at the Crossroads Editedby Johan van Benthem ILLC,UniversityofAmsterdam TheNetherlandsandStanfordUniversity,USA Amitabha Gupta IndianInstituteofTechnologyBombay,India and Rohit Parikh BrooklynCollegeandTheGraduateCenter CityUniversityofNewYork,USA 123 Editors Prof.JohanvanBenthem Prof.AmitabhaGupta UniversityofAmsterdam AdiShankaracharyaMarg InstituteforLogic,Language 503WhisperingWoods andComputation(ILLC) PowaiVihar,Bldg.3 SciencePark,P.O.Box94242 700076Powai,Mumbai 1090GEAmsterdam India TheNetherlands [email protected] [email protected] Prof.RohitParikh CityUniversityofNewYork BrooklynCollegeandtheCUNYGraduateCenter ComputerScience,MathematicsandPhilosophy 365FifthAvenue NewYork,NY10016 USA [email protected] ISBN978-94-007-0079-6 e-ISBN978-94-007-0080-2 SetISBN978-94-007-0920-1 DOI10.1007/978-94-007-0080-2 SpringerDordrechtHeidelbergLondonNewYork LibraryofCongressControlNumber:2011923788 (cid:2)c SpringerScience+BusinessMediaB.V.2011 Nopartofthisworkmaybereproduced,storedinaretrievalsystem,ortransmittedinanyformorby anymeans,electronic,mechanical,photocopying,microfilming,recordingorotherwise,withoutwritten permissionfromthePublisher,withtheexceptionofanymaterialsuppliedspecificallyforthepurpose ofbeingenteredandexecutedonacomputersystem,forexclusiveusebythepurchaserofthework. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Foreword Thisbookisallaboutnewlinksinlogic.The“FirstIndianConferenceonLogicand itsRelationshipwithOtherDisciplines”tookplaceinMumbaiatIITBombay,from January8to12,2005,asaninitiativeoftheMumbailogiccircle,bringingtogether Indianlogiciansfromvariousdisciplinarybackgroundsanddifferentlocationswith agroupofopen-mindedandactiveinternationalcolleagues. Theconferencetookplaceover6days:twoofthemdevotedtotutorialsandfour to advanced talks. Tutorials as well as advanced talks were given by Indian logi- ciansandbyvisitorsfromabroad.ThevisitorsrespondingtotheCallfortheMum- bai event came from Australia, the Czech Republic, Finland, Great Britain, Italy, Israel,Japan,theNetherlands,theUSA,andothernations.Together,theyformeda distinguishedgalaxyseldomfoundevenwithconferencesintheWest.Thepapers emphasized novel approaches and perspectives emanating from research by some ofthemastersoflogicanditsinterfaceswithsurroundingdisciplines. TheConferencevenueweretheoutstandinglogisticalandscenicfacilitiesatIIT Bombay,withsmoothorganizationaleffortsandcrucialsupportprovidedbyfaculty, andespeciallyalsobystudentvolunteers.Thegeese,thepond,andtheviewofthe lakeprovidedmostpeoplewiththeneededinspirationtothinkofdeepermatters. Talksrangedfromreflectionsontherangeofmathematicalproofanddefinability to recent developments in computational logic, as well as new interfaces between logic,informationdynamics,andgames.Inaddition,therewasawiderangeofpre- sentationsonschoolsofIndianlogic.Onetermusednowadaysforthisbroadview of logic is “intelligent interaction”. The Mumbai Conference took this term in the doublesenseofbothinformationexchangeandcommunityformation,andindeed both processes were in evidence. Accordingly, the “Second Indian Conference on LogicanditsRelationshipwithOtherDisciplines”washeldfromJanuary9to11in 2007atIITBombay,Mumbai,withequalsuccess.BesidesthesetwoConferences, afirstIndianWinterSchoolwiththesametopicandtitlewasheldatIITBombay, MumbaifromJanuary1to15,2006,primarilyforstudentsandresearchers. ThecurrentvolumecontainsabroadselectionofmaterialfromthefirstConfer- ence, while further volumes will document the follow-up. We see this publication ventureasprovidinginformation,butalsoasameansofshapingacommunity.Our v vi Foreword aim is to present an Indian audience with what we see as a representative sample of modern logic, in the hands of some of its best practitioners. This volume is not atextbook,however,accessiblethroughouttoabsolutebeginners.Butwedoexpect thatthepaperscollectedherewillgiveasenseofvitality,strengthanddirection,and that,throughthestory-linesandreferences,ourchapterswillopenfurtherdoorsto thefieldasthereadergetsinspired. WealsohopethatthisvolumewillhelptheIndianlogiccommunitytakeshape andflight,andindeed,therearesomeveryencouragingsigns.Sincethisbookwas puttogether,an‘AssociationforLogicinIndia’hasbeenformedthathastakenthe IIT Bombay initiative as well as other congenial events in Kolkata 2007 under its aegis. The website http://ali.cmi.ac.in/ shows its lively past and current activities. Thus the Mumbai founding events have found a natural continuation in a national seriesofconferencesandschools. Finally, on a still larger scale, we hope that the present publication initiative willmaintainthetiesbetweentheIndiancommunityanditsfriendsandcolleagues worldwide.Inparticular,weseethepapersonIndianLogicinthisvolumeasreach- ing out to more classical communities in the field while informing their modern colleagues.Oneday,weenvisionthatlogicwillhaveonehistory,withGotamaand Gangesa along with Aristotle and Boole. Be that as it may be, our book may be a firstgentlepushtowardjoiningforcesbetweenhistoricallydifferent,butmaybein thefinalanalysis,notallthatdifferentstrandsinourfascinatingfield. Theeditorsofthisvolumehavehadaneasytaskinsomeways.Thepositivere- sponseandgenerouscooperationfrombothIndianandinternationalcolleagueshas beenoverwhelming.Editingiseasywithauthorsofthisenergyandquality,whilese- riousrefereeswereeasytofind.Nevertheless,producingthisvolumehasalsomeant solvingahostofnon-triviallogisticproblems,whichcouldonlyhavebeendoneby our Mumbai experts. Special thanks are due to Mr. Abhisekh Sankaran, who has provided vital technical support to our efforts in putting the act together. We must notfailtoregisterhereourappreciationtoAlliedPublishers,especiallyMr.Sharad Gupta,fortheirconcern,persistenceandendurancetoseetheprojectthroughinits firstIndianinstalment.Wearegratefulthatwenowhaveachancetobringthisbook toanevenwideraudiencethroughthemediumofSpringerPublishers. We would like to record here the support and advice given to the organizers of theFirstConferencebyseveralfacultymembersfromvariousdepartmentsandau- thoritiesatIITBombay,Mumbai,aswellastheInstituteofMathematicalSciences, ChennaiandTIFR,Mumbai.Furthermore,generousfinancialsupportwasreceived, for the Conference and this publication, from Infosys Technologies Ltd., the De- partment of Science and Technology, Government of India, the Indian Council of Philosophical Research, New Delhi and Microsoft, India. All this is hereby grate- fullyacknowledged. Mumbai AmitabhaGupta NewYork RohitParikh Amsterdam JohanvanBenthem Preface Logic:AViewfromtheCross-roads Logicstandsatthecross-roadsofmanydisciplinesandcultures.Thediscoverythat humanreasoningandargumentationcontainsstablepatternsthatcanbestudiedas such has been made independently in Antiquity in the Greek, Indian, and Chinese traditions, showing a remarkable unity to human thought. Ever since those days, logichashadaspecialrelationshipwithdisciplineswherepurereasoningisofthe essence,inparticular,philosophyandmathematics. Modern logic as we have today began with developments in the 19th century duetoFrege,Boole,Peirce,Cantorandothersconcernedwithlogicaswellaswith thefoundationsofmathematics.Theywerefollowedbyearly20thcenturyfigures like Russell, Wittgenstein, and Ramsey. A sense of crisis provoked by Russell’s and other paradoxes eventually led to Hilbert’s program and to deep technical re- sults in the first half of the 20th century on provability, computability, truth, and definability found by Hilbert, Herbrand, Go¨del, Gentzen, Skolem, Tarski, Turing, andothers.Sincethattime,mathematicalnotionsandtechniqueshavepervadedthe field,andthisbookcontainsseveralchaptersdevotedtothegreatthemesfromthat mathematics-orientedtradition. Butmodernlogicisalsoameetinggroundofmanyfurtherdisciplines.Thestudy ofdecidabilityandundecidabilityofmathematicalquestionsledtothefoundations of computing and eventually, to the birth of computers. Thus, nowadays, there is a wide family of interfaces between logic and computer science, ranging from the study of programming languages to the design of databases or intelligent multi- agent systems, and sometimes even straight into practical matters of information technology.Thistrend,too,iswell-representedinvariouschaptersofthisvolume, and ‘computational logic’ broadly conceived may indeed be the bulk of all logic researchtoday. Still, this is by no means the complete picture of current developments. Logic is being used extensively in the study of topics beyond narrower proof or compu- tation, with a particular emphasis on the behaviour of rational agents which have knowledge,beliefs,preferences,andobligations,andneedtoadjusttheseinaworld vii viii Preface thatchangesovertime.Allthishastraditionallybeenthedomainof“philosophical logic”attheinterfaceoflogicandphilosophy,withtiestoepistemology,philosophy of action, philosophy of science, and ethics. But over the last decades, this stream of research has started converging with computational logic, as computer systems becomemoreandmoresophisticated,aloneorinnetworkedsocieties,thusbecom- ing more and more like us. This is why AI, in particular, has been a large scale “consumer”oflogic. Finally,logicinthelastcenturyhashadextensivecontactswithlinguistics,since its account of meaning and definability provides intriguing interfaces with natural language in all its facets, from syntax to semantics and pragmatics. Frege, with hisdistinctionbetween“sense”and“reference”alreadygaveusthemorningstar– eveningstarproblemcentraltobothsemanticsandthephilosophyoflanguage.But more recent influences have been those of Lewis with his somewhat controversial notionofcommonknowledge,andGricewithhisnotionofimplicaturewhichhas made pragmatics deeply embedded into semantics. Another important figure has beenSaulKripkewhosesemanticsofmodallogicandwhosenotionofrigiddesig- natorhaveplayedcentralrolesinrecentdevelopments. Right now, it seems fair to say that the discipline of logic also finds itself at a crossroads in the other sense, that of choosing its future directions. This book documentswhatarearguablythemajorones. First, the study of rational agency as a broader goal beyond computation and deduction naturally leads to the logical study of intelligent interaction and social behaviour.Let’snotforgetthatlogicprobablyaroseinthefirstplaceasastudyof legal,philosophicalandpoliticaldebate!Aninspiringparadigmforthisis“Social Software”,thestudyofpatternsofsocialinteractionbymeansoftechniquesfrom logicandcomputerscience.Inthisway,logicalsojoinsforceswiththesocialsci- encessuchasgametheoryineconomics,orsocialchoicetheory,oreventheLaw, asourmostfamoushistoricalexampleofrationalsocialengineering. Next,eventhoughlogichastraditionallyvieweditselfasnormative,andnotasa descriptionofactualbehaviour,connectionsbetweenlogicandempiricalpsychol- ogyandcognitivescienceareontherise,asmorefactsaboutactualbehaviourand even about the human brain are becoming available for inspection. Logical theo- riessuddenlyfindthemselvesattheforefrontoftheorizingabouthumanreasoning skills. In a sense, this was already implicit in earlier studies of logic and natural language,whereactualfactsofmeaningandinferenceinhumanpracticehavelong servedasaconstraintontheory. Finally, the future is sometimes opened up by paying proper attention to one’s past. There is a rising interest in logic in other traditions than the Western one, includingtheindependentoriginsintheIndianandChinesetraditions(afactwhich byitselfshouldsufficeforshakingupsomereceivedculturalstereotypes),butalso, its transformation in the golden age of early medieval Arabic culture. Some first explorationshavealreadyexposedfascinatingvistas. It was in this lively current setting that a group of Indian logicians decided to startaseriesofmeetingsinMumbaidevotedtothefullwidthoflogictoday,andits modernandancientrootsinIndianculturallife.Onepurposeofthesemeetingswas Preface ix torestoreIndiatoitsrightfulplaceinthelogicalworld.WhileIndiahasbeenone ofthetraditionalhomesoflogic,inrecentdays,Indiancontributionsinlogichave remainedasmallpartofIndiancontributionstoscienceoreventomathematicsand philosophy.OnecouldsaythattheIndiangeniushasbeeninadequatelyharnessed inthisimportantarea. Ashasalreadybeenpointedoutthatthecurrentvolumecontainsarepresentative selection of material from the first Conference, while the planned further volumes inthisbookserieswilldocumentthefollow-up. Hereisabriefguidetothechaptersinthisvolume. ThefirsttwochaptersinPartI,entitled“ViewsofLogicToday,”provideagrand settingtowhatistofollow.JohnCrossleygivesamasterfulsurveyofmathematical logic,whichhighlightstheessentialandfar-ranginginsightsthathaveaccumulated bynowintoproof,computation,anddefinabilityviaformalsystems.RohitParikh then follows up with an extended view of logic as a way of studying patterns and proceduresinsocialagency,showinghowtheperspectiveof“socialsoftware”can systematizethisfield,whilebringingoutinterestingaspectsofdifferentcultures. PartIIcomprisingagroupofthreepaperson“LogicandMathematics”demon- stratesthecontinuedvitalityofmathematicallogicandfoundationsofmathematics. JohnCrossleyexamineswhatisamathematicalproof,aquestionwhichcontinuesto inspirenewlogicaltheory.PetrHajekdevelopsarigoroustreatmentoffuzzylogic, once thought to be a “soft” subject, but by now fully respectable mathematically. Finally, Wilfrid Hodges takes us back to the formative years of model theory and recursion theory, and Tarski’s seminal results joining expressive power and com- plexityinarithmeticalsettings. Asacounter-pointtothisgrandtraditioninlogic,wehaveplacedinPartIIIsome papers from another grand tradition providing “Perspectives from Indian Logic”. K. Ramasubramanian presents an overview that will help Western readers under- stand the rich tapestry of this field, while even teaching Indian readers a thing or two.Moreover,thesameauthoraddsaconcretesample,intheformofanexposition ofthesubtletyofaspecificthemeinIndianLogic,viz.theconceptofhetvabhasain theNya¯ya-sastra.Finally,SundarSarukkaipositionsIndianlogicinitsconnections withphilosophicalepistemologyandthephilosophyofscience,showinghowtopics rannaturallyintoeachother.Thisinterfaceseemsespeciallyrelevantinunderstand- inglogic/philosophyinterfacestoday. The next groups of papers spread over three sections document some major streams in contemporary logic. We start with Part IV, viz., “Logic and Computa- tion,”anareawhichisrichlyrepresentedinIndiatoday.JohnCrossleyexaminesthe entangled and complementary notions of “proof” and “program”, and charts their marriage in current theories, including Combinatory Logic and Hoare Logic. Yuri GurevichandAndreasBlassdiscussthestateoftheartconcerningZero-OneLaws, themysteriousstatisticalregularitiesunderlyingtheexpressivepowerofmanylog- icalsystemsthatwerefirstbroughttolightinthe1970s.RonvanderMeydende- velops another strand, the penetration of systems from philosophical logic, such as epistemic and temporal logic, into the study of computational systems and net- worksecurity.DanieleMundiciandandFerdinandoCicalesethentakeupthetopic x Preface ofcodingtheory,anditsdeepandsurprisingconnectionswithmany-valuedlogics which came originally from the Polish School in the early 20th century. Finally, Noson Yanofsky gives a masterful yet light-footed survey of the new paradigm of quantumcomputing,whichbothstudentsandexpertswillfindbothinformativeand delightful. Itmaybesaidwithsomeexaggerationthatmoderncomputingisrationalagency in societies of interacting agents, which pass information, correct themselves, and engageinpurposefulstrategicbehaviour.Thus,connectionsbetweenlogic,philoso- phyofaction,computersciences,andsocialsciencescometothefore.Thenextpart, i.e.PartVon“Logic,Agency,andGames”hassomesamplesofthisrecenttrend. JohanvanBenthempresentsanextensivesurveyofwaysinwhichgameshavebeen usedtomodellogicalcoreactivitiessuchasmodelchecking,modelbuilding,orar- gumentation,andthenrelatesthisinteractiveviewoflogictostandardnotionsfrom gametheorysuchasstrategies,equilibrium,andimperfectinformation.EricPacuit tackles one specific issue in social software, viz. the correctness and scope of the algorithmof“AdjustedWinner”infairdivision,andshowshowlogicaltechniques provide general viewpoints and more reliable conclusions about what such proce- duresachieve.Next,KristerSegerbergdiscussesthemoregeneralphenomenonof beliefrevisioninthelightofdynamiclogicsofcomputationandaction,andshows howthissystematicstancecansolvetheproblemof“iteratedbeliefrevision”which has plagued belief revision theory in AI and philosophy for a long time. Finally, G. Venkatesh develops systems of temporal preference logic which can describe players’ goals and evaluations over time, as different parts of a game tree become availablewhensuccessivemovesareplayed.Thispointsthewaytowardrichlogics ofgamesasaparadigmforintelligentinteractionovertime. Whilesocialphenomenasuggestsomemorecarefulattentiontoempiricalfacts thanwhathasbeenthenormforlogicians,game-theoreticanalysesmaystillbenor- mativeflashesofbrilliance,ratherthantheoutcomeofgenuinepainstakingobser- vationofbehaviour.Ourfinalpart,PartVI,ison“Logic,LanguageandCognition”. Itmovesclosertotherealitiesofatleastonemajorempiricalphenomenon,the“sea ofdiscourse”thatwealllivein,viz.NaturalLanguage.D.B.AcharyaandShalini Joshistartbyexploringthescopeandlimitsofdiscretemathematicalmodels(most logical systems are) for the behavioral, cognitive, and social sciences. Then Wil- fridHodgesgivesamasterfulanalysisofthePrincipleofCompositionalityandthe emergence of meaning from sentence understanding. This theme has been crucial tounderstandingtherecursivelearnabilityoflanguagesince,notjustFregeandthe modernsemanticists,buteven,astheauthorshows,allthewaybackintomedieval ArabicLogic,anotherrelevanthistoricalandculturaltradition. Intheirtotality,thesecontributionsofferaviewofreasoning,computation,and rational agency in awide modern sense, with logicacting as acommon language, andindeed,anintellectualcatalyst. Amsterdam JohanvanBenthem NewYork RohitParikh Mumbai AmitabhaGupta