{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,14]],"date-time":"2023-09-14T00:40:17Z","timestamp":1694652017862},"reference-count":17,"publisher":"Wiley","issue":"5","license":[{"start":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T00:00:00Z","timestamp":1219795200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2008,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In [5] (1982) it has been shown that for first\u2010order definability over the reals there exists an effective procedure which by a finite formula with equality defining an open set produces a finite formula without equality that defines the same set. In this paper we prove that there exists no such procedure for \u03a3\u2010definability over the reals. We also show that there exists even no uniform effective transformation of the definitions of \u03a3\u2010definable sets (i. e., \u03a3\u2010formulas) into new definitions of \u03a3\u2010definable sets in such a way that the results will define open sets, and if a definition defines an open set, then the result of this transformation will define the same set. These results highlight the important differences between \u03a3\u2010definability with equality and \u03a3\u2010definability without equality. (\u00a9 2008 WILEY\u2010VCH Verlag GmbH &amp; Co. KGaA, Weinheim)<\/jats:p>","DOI":"10.1002\/malq.200710064","type":"journal-article","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T09:57:26Z","timestamp":1219831046000},"page":"535-544","source":"Crossref","is-referenced-by-count":4,"title":["On \u03a3\u2010definability without equality over the real numbers"],"prefix":"10.1002","volume":"54","author":[{"given":"Andrei S.","family":"Morozov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Margarita V.","family":"Korovina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2008,8,27]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"J.Barwise Admissible Sets and Structures (Springer\u2010Verlag 1975).","DOI":"10.1007\/978-3-662-11035-5"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"L.Blum F.Cucker M.Shub andS.Smale Complexity and Real Computation (Springer\u2010Verlag 1998).","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1998.0475"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00283-7"},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"C. N.Delzell A finiteness theorem for open semi\u2010algebraic sets with application to Hilbert's 17th problem. In: Ordered Fields and Real Algebraic Geometry. Contemporary Mathematics 8 pp. 79\u201397 (AMS 1982).","DOI":"10.1090\/conm\/008\/653176"},{"key":"e_1_2_1_7_2","unstructured":"Y. L.Ershov The Theory of Enumerations (Nauka 1977)."},{"key":"e_1_2_1_8_2","unstructured":"Y. L.Ershov Definability and Computability (Plenum 1996)."},{"key":"e_1_2_1_9_2","unstructured":"W.Hodges The meaning of specifications II: Set\u2010theoretical specification. In: Semantics of Programming Languages and Model Theory. Algebra Logic and Applications Series 5 pp. 43\u201368 (Gordon and Breach Science Publishers 1993)."},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"M. V.Korovina andO. V.Kudinov Semantic characterisations of second\u2010order computability over the real numbers. In: Proceedings of CSL'01 (L. Fribourg ed.). Lecture Notes in Computer Science 2142 pp. 160\u2013172 (Springer\u2010Verlag 2001).","DOI":"10.1007\/3-540-44802-0_12"},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","unstructured":"M. V.Korovina Computational aspects of \u03a3\u2010definability over the real numbers without the equality test. In: Proceedings of CSL'03 (M. Baaz and J. A. Makowsky eds.). Lecture Notes in Computer Science 2803 pp. 330\u2013344 (Springer\u2010Verlag 2003).","DOI":"10.1007\/978-3-540-45220-1_27"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"M. V.Korovina Recent advances in \u03a3\u2010definability over continuous data types. In: Proceedings of PSI'03 (M. Broy and A. V. Zamulin eds.). Lecture Notes in Computer Science 2890 pp. 238\u2013247 (Springer\u2010Verlag 2004).","DOI":"10.1007\/978-3-540-39866-0_25"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"M. V.Korovina andO. V.Kudinov The uniformity principle for \u03a3\u2010definability with applications to computable analysis. In: Proceedings of CiE'07 (S. B. Cooper B. L\u00f6we and A. Sorbi eds.). Lecture Notes in Computer Science 4497 pp. 416\u2013425 (Springer\u2010Verlag 2007).","DOI":"10.1007\/978-3-540-73001-9_43"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.2307\/1994926"},{"key":"e_1_2_1_15_2","doi-asserted-by":"crossref","unstructured":"A.Tarski A Decision Method for Elementary Algebra and Geometry 2nd edition (Berkeley 1951).","DOI":"10.1525\/9780520348097"},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"J. V.Tucker andJ. I.Zucker Computable functions and semicomputable sets on many\u2010sorted algebras. In: Handbook of Logic in Computer Science (S. Abramsky D. M. Gabbay and T. S. E. Maibaum eds.) pp. 317\u2013523 (Oxford University Press 2000).","DOI":"10.1093\/oso\/9780198537816.003.0008"},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","unstructured":"K.Weihrauch Computable Analysis (Springer Verlag 2000).","DOI":"10.1007\/978-3-642-56999-9"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00008-X"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200710064","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.200710064","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,14]],"date-time":"2023-09-14T00:05:26Z","timestamp":1694649926000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.200710064"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8,27]]},"references-count":17,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2008,9]]}},"alternative-id":["10.1002\/malq.200710064"],"URL":"https:\/\/doi.org\/10.1002\/malq.200710064","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8,27]]}}}