{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,6]],"date-time":"2024-10-06T00:36:58Z","timestamp":1728175018531},"reference-count":6,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":2749,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2006,9]]},"abstract":"<jats:p>It is known that both <jats:italic>S<\/jats:italic>4 and the Intuitionistic prepositional calculus <jats:italic>Int<\/jats:italic> are <jats:italic>P-SPACE<\/jats:italic> complete. This guarantees that there is a polynomial translation from each system into the other.<\/jats:p><jats:p>However, no sound and faithful polynomial translation from <jats:italic>S<\/jats:italic>4 into <jats:italic>Int<\/jats:italic> is commonly known. The problem of finding one was suggested by Dana Scott during a very informal gathering of logicians in February 2005 at UCLA. Grigori Mints then brought it to my attention, and in this paper I present a solution. It is based on Kripke semantics and describes model-checking for <jats:italic>S<\/jats:italic>4 using formulas of <jats:italic>Int<\/jats:italic>.<\/jats:p><jats:p>A simple translation from <jats:italic>Int<\/jats:italic> into <jats:italic>S<\/jats:italic>4, the G\u00f6del-Tarski translation, is wellknown; given a formula \u03c6 of <jats:italic>Int<\/jats:italic>, one obtains <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200006022_inline1\" \/> by prefixing \u25a1 to every subformula. For example,<\/jats:p><jats:p><jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0022481200006022_Uequ1\" \/><\/jats:disp-formula>.<\/jats:p><jats:p>That the translation is sound and faithful can be seen by considering topological semantics, which assign open sets both to \u25a1-formulas of <jats:italic>S<\/jats:italic>4 and arbitrary formulas of <jats:italic>Int<\/jats:italic>; the interpretation of \u03c6 and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200006022_inline1\" \/> turn out to be identical. See Tarski's paper [6] for details. G\u00f6del's original paper can be found in [3].<\/jats:p><jats:p>In [2], Friedman and Flagg present a kind of inverse to G\u00f6del-Tarski. Given a formula \u03c6 of <jats:italic>S<\/jats:italic>4 and a finite set of formulas \u0393 of <jats:italic>Int<\/jats:italic>, for each \u03b5 \u2208 \u0393 one gets an intuitionistic formula <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200006022_inline2\" \/>given recursively by<\/jats:p><jats:p><jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0022481200006022_Uequ2\" \/><\/jats:disp-formula><\/jats:p>","DOI":"10.2178\/jsl\/1154698587","type":"journal-article","created":{"date-parts":[[2007,12,19]],"date-time":"2007-12-19T11:23:20Z","timestamp":1198063400000},"page":"989-1001","source":"Crossref","is-referenced-by-count":5,"title":["A polynomial translation of <i>S<\/i>4 into intuitionistic logic"],"prefix":"10.1017","volume":"71","author":[{"given":"David","family":"Fernandez","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200006022_ref006","doi-asserted-by":"publisher","DOI":"10.4064\/fm-31-1-103-134"},{"key":"S0022481200006022_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71685-9"},{"key":"S0022481200006022_ref003","volume-title":"Collected works","author":"G\u00f6del","year":"1986"},{"key":"S0022481200006022_ref001","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107050884"},{"key":"S0022481200006022_ref005","volume-title":"A short introduction to intuitionistic logic","author":"Mints","year":"2000"},{"key":"S0022481200006022_ref002","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0168-0072(86)90043-6","article-title":"Epistemic and intuitionistic formal systems","volume":"32","author":"Friedman","year":"1986","journal-title":"Annals of Pure and Applied Logic"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200006022","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T15:54:35Z","timestamp":1556812475000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200006022\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9]]},"references-count":6,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,9]]}},"alternative-id":["S0022481200006022"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1154698587","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,9]]}}}