{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,15]],"date-time":"2024-03-15T11:42:58Z","timestamp":1710502978857},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2015,5,11]],"date-time":"2015-05-11T00:00:00Z","timestamp":1431302400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2017,2]]},"abstract":"<jats:p>This paper considers \u2203*\u2200* prenex sentences of pure first-order predicate calculus with equality. This is the set of formulas which Ramsey's treated in a famous article of 1930. We demonstrate that the satisfiability problem and the problem of existence of arbitrarily large models for these formulas can be reduced to the satisfiability problem for \u2203*\u2200* prenex sentences of Set Theory (in the relators \u2208, =).<\/jats:p><jats:p>We present two satisfiability-preserving (in a broad sense) translations \u03a6 \u21a6 <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0960129515000122_inline1\" \/><jats:tex-math>$\\dot{\\Phi}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and \u03a6 \u21a6 \u03a6<jats:sup>\u03c3<\/jats:sup> of \u2203*\u2200* sentences from pure logic to well-founded Set Theory, so that if <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0960129515000122_inline1\" \/><jats:tex-math>$\\dot{\\Phi}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is satisfiable (in the domain of Set Theory) then so is \u03a6, and if \u03a6<jats:sup>\u03c3<\/jats:sup> is satisfiable (again, in the domain of Set Theory) then \u03a6 can be satisfied in arbitrarily large finite structures of pure logic.<\/jats:p><jats:p>It turns out that |<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0960129515000122_inline1\" \/><jats:tex-math>$\\dot{\\Phi}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>| = <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0960129515000122_inline2\" \/><jats:tex-math>$\\mathcal{O}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>(|\u03a6|) and |\u03a6<jats:sup>\u03c3<\/jats:sup>| = <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0960129515000122_inline2\" \/><jats:tex-math>$\\mathcal{O}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>(|\u03a6|<jats:sup>2<\/jats:sup>).<\/jats:p><jats:p>Our main result makes use of the fact that \u2203*\u2200* sentences, even though constituting a decidable fragment of Set Theory, offer ways to describe infinite sets. Such a possibility is exploited to glue together infinitely many models of increasing cardinalities of a given \u2203*\u2200* logical formula, within a single pair of infinite sets.<\/jats:p>","DOI":"10.1017\/s0960129515000122","type":"journal-article","created":{"date-parts":[[2015,5,11]],"date-time":"2015-05-11T07:41:25Z","timestamp":1431330085000},"page":"296-310","source":"Crossref","is-referenced-by-count":9,"title":["Set-syllogistics meet combinatorics"],"prefix":"10.1017","volume":"27","author":[{"given":"EUGENIO G.","family":"OMODEO","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALBERTO","family":"POLICRITI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALEXANDRU I.","family":"TOMESCU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2015,5,11]]},"reference":[{"key":"S0960129515000122_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160340203"},{"key":"S0960129515000122_ref11","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exr020"},{"key":"S0960129515000122_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-012-9272-3"},{"key":"S0960129515000122_ref4","volume-title":"Set Theory for Computing. From Decision Procedures to Declarative Programming with Sets","author":"Cantone","year":"2001"},{"key":"S0960129515000122_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160330503"},{"key":"S0960129515000122_ref13","doi-asserted-by":"publisher","DOI":"10.2307\/2275470"},{"key":"S0960129515000122_ref10","unstructured":"Omodeo E. G. , Policriti A. and Tomescu A. I. (2009). Statements of ill-founded infinity in set theory. In: C\u00e9gielski P. (ed.) Studies in Weak Arithmetics, No. 196 in Lecture Notes, Center for the Study of Language and Information, Stanford University 173\u2013199."},{"key":"S0960129515000122_ref12","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1988-0938682-2"},{"key":"S0960129515000122_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160480908"},{"key":"S0960129515000122_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59207-2"},{"key":"S0960129515000122_ref7","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1268917490"},{"key":"S0960129515000122_ref17","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-30.1.264"},{"key":"S0960129515000122_ref15","volume-title":"Matching Theory","author":"Plummer","year":"1986"},{"key":"S0960129515000122_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-85729-808-9"},{"key":"S0960129515000122_ref3","first-page":"131","volume-title":"From Linear Operators to Computational Biology: Essays in Memory of Jacob T. Schwartz","author":"Cantone","year":"2012"},{"key":"S0960129515000122_ref8","doi-asserted-by":"crossref","first-page":"896","DOI":"10.2178\/jsl\/1344862166","article-title":"The Bernays-Sch\u00f6nfinkel-Ramsey class for set theory: Decidability","volume":"77","author":"Omodeo","year":"2012","journal-title":"Journal of Symbolic Logic"},{"key":"S0960129515000122_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160460104"},{"key":"S0960129515000122_ref16","article-title":"Small Ramsey numbers","volume":"#14","author":"Radziszowski","year":"2014","journal-title":"The Electronic Journal of Combinatorics"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129515000122","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,18]],"date-time":"2019-04-18T04:06:42Z","timestamp":1555560402000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129515000122\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,11]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["S0960129515000122"],"URL":"https:\/\/doi.org\/10.1017\/s0960129515000122","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,11]]}}}