{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,18]],"date-time":"2022-05-18T04:49:41Z","timestamp":1652849381291},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,1,15]],"date-time":"2014-01-15T00:00:00Z","timestamp":1389744000000},"content-version":"unspecified","delay-in-days":4154,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. symb. log."],"published-print":{"date-parts":[[2002,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>For every finite <jats:italic>n<\/jats:italic> \u2265 4 there is a logically valid sentence \u03c6<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> with the following properties: \u03c6<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> contains only 3 variables (each of which occurs many times); \u03c6<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> contains exactly one nonlogical binary relation symbol (no function symbols, no constants, and no equality symbol); \u03c6<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> has a proof in first-order logic with equality that contains exactly <jats:italic>n<\/jats:italic> variables, but no proof containing only <jats:italic>n<\/jats:italic> \u2212 1 variables. This result was first proved using the machinery of algebraic logic developed in several research monographs and papers. Here we replicate the result and its proof entirely within the realm of (elementary) first-order binary predicate logic with equality. We need the usual syntax, axioms, and rules of inference to show that \u03c6<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> has a proof with only <jats:italic>n<\/jats:italic> variables. To show that \u03c6<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> has no proof with only <jats:italic>n<\/jats:italic> \u2212 1 variables we use alternative semantics in place of the usual, standard, set-theoretical semantics of first-order logic.<\/jats:p>","DOI":"10.2178\/bsl\/1182353893","type":"journal-article","created":{"date-parts":[[2008,4,3]],"date-time":"2008-04-03T17:09:54Z","timestamp":1207242594000},"page":"348-379","source":"Crossref","is-referenced-by-count":9,"title":["Provability with Finitely Many Variables"],"prefix":"10.1017","volume":"8","author":[{"given":"Robin","family":"Hirsch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ian","family":"Hodkinson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roger D.","family":"Maddux","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,1,15]]},"reference":[{"key":"S1079898600004856_ref012","doi-asserted-by":"publisher","DOI":"10.1007\/BF01458217"},{"key":"S1079898600004856_ref010","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1190150037"},{"key":"S1079898600004856_ref005","first-page":"95","volume-title":"RelMiCS 2000","author":"Gordeev","year":"2000"},{"key":"S1079898600004856_ref024","doi-asserted-by":"publisher","DOI":"10.1037\/12811-000"},{"key":"S1079898600004856_ref006","doi-asserted-by":"publisher","DOI":"10.1090\/cbms\/045"},{"key":"S1079898600004856_ref018","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1307\/mmj\/1029000477","article-title":"Representations of integral relation algebras","volume":"17","author":"McKenzie","year":"1970","journal-title":"The Michigan Mathematical Journal"},{"key":"S1079898600004856_ref003","first-page":"231","article-title":"Color schemes forbidding monochrome triangles","volume":"39","author":"Comer","year":"1983","journal-title":"Proceedings of the Fourteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1983)"},{"key":"S1079898600004856_ref021","doi-asserted-by":"crossref","first-page":"331","DOI":"10.2307\/2270900","article-title":"Nonfinitizability of classes of representable cylindric algebras","volume":"34","author":"Maddux","year":"1969","journal-title":"The Journal of Symbolic Logic"},{"key":"S1079898600004856_ref022","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1090\/S0002-9939-1971-0276063-5","article-title":"Provability with finitely many variables","volume":"27","author":"Maddux","year":"1971","journal-title":"Proceedings of the American Mathematical Society"},{"key":"S1079898600004856_ref008","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1955-001-4"},{"key":"S1079898600004856_ref001","doi-asserted-by":"publisher","DOI":"10.2307\/2048576"},{"key":"S1079898600004856_ref019","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1307\/mmj\/1028999131","article-title":"On representable relation algebras","volume":"11","author":"Monk","year":"1964","journal-title":"The Michigan Mathematical Journal"},{"key":"S1079898600004856_ref009","first-page":"111","volume-title":"Truth, syntax and modality (Proc. Conf. Alternative Semantics, Temple Univ., Philadelphia, Pa., 1970)","volume":"68","author":"Henkin","year":"1973"},{"key":"S1079898600004856_ref002","doi-asserted-by":"crossref","DOI":"10.1016\/S0924-6509(09)70330-7","volume-title":"Graphs and hypergraphs","volume":"6","author":"Berge","year":"1973"},{"key":"S1079898600004856_ref007","volume-title":"Ramsey theory","author":"Graham","year":"1980"},{"key":"S1079898600004856_ref011","doi-asserted-by":"publisher","DOI":"10.2307\/2270901"},{"key":"S1079898600004856_ref014","unstructured":"Maddux R. D. , Topics in relation algebras, Ph.D. thesis , University of California, Berkeley, 1978, pp. iii + 241."},{"key":"S1079898600004856_ref004","first-page":"189","volume-title":"Algebraic Logic (Budapest, 1988)","volume":"54","author":"Givant","year":"1991"},{"key":"S1079898600004856_ref017","doi-asserted-by":"publisher","DOI":"10.2307\/2274756"},{"key":"S1079898600004856_ref027","doi-asserted-by":"publisher","DOI":"10.1007\/BF01972461"},{"key":"S1079898600004856_ref013","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1307\/mmj\/1028998510","article-title":"Relation algebras and projective geometries","volume":"8","author":"Lyndon","year":"1961","journal-title":"The Michigan Mathematical Journal"},{"key":"S1079898600004856_ref020","first-page":"238","volume-title":"The Theory of Models (Proc. 1963 Internat. Sympos. Berkeley)","author":"Maddux","year":"1965"},{"key":"S1079898600004856_ref026","doi-asserted-by":"publisher","DOI":"10.2307\/2268577"},{"key":"S1079898600004856_ref016","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90055-6"},{"key":"S1079898600004856_ref015","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1982-0662049-7"},{"key":"S1079898600004856_ref023","first-page":"727","volume-title":"Algebraic Logic (Budapest, 1988)","volume":"54","author":"Andr\u00e9ka","year":"1991"},{"key":"S1079898600004856_ref025","volume-title":"Vorlesungen \u00fcber die Algebra der Logik (exacte Logik), Volume 3, \u201cAlgebra und Logik der Relative\u201d Part I","author":"Schr\u00f6der","year":"1966"},{"key":"S1079898600004856_ref028","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/041"}],"container-title":["Bulletin of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1079898600004856","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,7]],"date-time":"2019-05-07T00:43:01Z","timestamp":1557189781000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1079898600004856\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,9]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2002,9]]}},"alternative-id":["S1079898600004856"],"URL":"https:\/\/doi.org\/10.2178\/bsl\/1182353893","relation":{},"ISSN":["1079-8986","1943-5894"],"issn-type":[{"value":"1079-8986","type":"print"},{"value":"1943-5894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,9]]}}}