{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T05:06:53Z","timestamp":1769836013420,"version":"3.49.0"},"reference-count":8,"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":14437,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1974,9]]},"abstract":"<jats:p>Let <jats:italic>Q<\/jats:italic> be the class of closed quantificational formulas \u2200<jats:italic>x<\/jats:italic>\u2203<jats:italic>u<\/jats:italic>\u2200<jats:italic>yM<\/jats:italic> without identity such that <jats:italic>M<\/jats:italic> is a quantifier-free matrix containing only monadic and dyadic predicate letters and containing no atomic subformula of the form <jats:italic>Pyx<\/jats:italic> or <jats:italic>Puy<\/jats:italic> for any predicate letter <jats:italic>P<\/jats:italic>. In [DKW] Dreben, Kahr, and Wang conjectured that <jats:italic>Q<\/jats:italic> is a solvable class for satisfiability and indeed contains no formula having only infinite models. As evidence for this conjecture they noted the solvability of the subclass of <jats:italic>Q<\/jats:italic> consisting of those formulas whose atomic subformulas are of only the two forms <jats:italic>Pxy, Pyu<\/jats:italic> and the fact that each such formula that has a model has a finite model. Furthermore, it seemed likely that the techniques used to show this subclass solvable could be extended to show the solvability of the full class <jats:italic>Q<\/jats:italic>, while the syntax of <jats:italic>Q<\/jats:italic> is so restricted that it seemed impossible to express in formulas of <jats:italic>Q<\/jats:italic> any unsolvable problem known at that time.<\/jats:p><jats:p>In 1966 Aanderaa refuted this conjecture. He first constructed a very complex formula in <jats:italic>Q<\/jats:italic> having an infinite model but no finite model, and then, by an extremely intricate argument, showed that <jats:italic>Q<\/jats:italic> (in fact, the subclass <jats:italic>Q<\/jats:italic><jats:sub>2<\/jats:sub> defined below) is unsolvable ([Aa1], [Aa2]). In this paper we develop stronger tools in order to simplify and extend the results of [Aa2]. Specifically, we show the unsolvability of an apparently new combinatorial problem, which we shall call the <jats:italic>linear sampling problem<\/jats:italic> (defined in \u00a71.2 and \u00a72.3). From the unsolvability of this problem there follows the unsolvability of two proper subclasses of <jats:italic>Q<\/jats:italic>, which we now define. For each <jats:italic>i<\/jats:italic> \u2265 0, let <jats:italic>P<\/jats:italic><jats:sub>i<\/jats:sub> be a dyadic predicate letter and let R<jats:sub>i<\/jats:sub> be a monadic predicate letter.<\/jats:p>","DOI":"10.2307\/2272894","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:31:33Z","timestamp":1146951093000},"page":"519-548","source":"Crossref","is-referenced-by-count":17,"title":["Linear sampling and the \u2200\u2203\u2200 case of the decision problem"],"prefix":"10.1017","volume":"39","author":[{"given":"St\u00e5l O.","family":"Aanderaa","sequence":"first","affiliation":[]},{"given":"Harry R.","family":"Lewis","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200076672_ref005","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1962-10809-X"},{"key":"S0022481200076672_ref002","unstructured":"Aanderaa S. O. , A new undecidable problem with applications in logic, Doctoral Dissertation, Harvard University, 1966 (unpublished)."},{"key":"S0022481200076672_ref008","first-page":"23\u201355","volume-title":"Proceedings of a Symposium on the Mathematical Theory of Automata","author":"Wang","year":"1962"},{"key":"S0022481200076672_ref006","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.48.3.365"},{"key":"S0022481200076672_ref001","first-page":"509","article-title":"Some recursively undecidable problems in automata theory and quantification theory","volume":"13","author":"Aanderaa","year":"1966","journal-title":"Notices of the American Mathematical Society"},{"key":"S0022481200076672_ref003","volume-title":"Memoirs of the American Mathematical Society","author":"Berger","year":"1966"},{"key":"S0022481200076672_ref004","unstructured":"Dreben B. and Goldfarb W. D. , A systematic treatment of the decision problem (forthcoming)."},{"key":"S0022481200076672_ref007","doi-asserted-by":"publisher","DOI":"10.2307\/2371809"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200076672","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T21:03:36Z","timestamp":1559163816000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200076672\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1974,9]]},"references-count":8,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1974,9]]}},"alternative-id":["S0022481200076672"],"URL":"https:\/\/doi.org\/10.2307\/2272894","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1974,9]]}}}