{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:55:00Z","timestamp":1759146900104},"reference-count":24,"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":1653,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2009,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A cylindric algebra atom structure is said to be <jats:italic>strongly representable<\/jats:italic> if all atomic cylindric algebras with that atom structure are representable. This is equivalent to saying that the full complex algebra of the atom structure is a representable cylindric algebra. We show that for any finite <jats:italic>n<\/jats:italic> \u2265 3, the class of all strongly representable <jats:italic>n<\/jats:italic>-dimensional cylindric algebra atom structures is not closed under ultraproducts and is therefore not elementary.<\/jats:p><jats:p>Our proof is based on the following construction. From an arbitrary undirected, loop-free graph \u0393, we construct an <jats:italic>n<\/jats:italic>-dimensional atom structure <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200003315_inline1\" \/>, and prove, for infinite \u0393, that <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200003315_inline1\" \/> is a strongly representable cylindric algebra atom structure if and only if the chromatic number of \u0393 is infinite. A construction of Erd\u0151s shows that there are graphs \u0393<jats:sub><jats:italic>k<\/jats:italic><\/jats:sub>(<jats:italic>k<\/jats:italic> &lt; <jats:italic>\u03c9<\/jats:italic>) with infinite chromatic number, but having a non-principal ultraproduct \u03a0<jats:sub><jats:italic>D<\/jats:italic><\/jats:sub>\u0393<jats:sub><jats:italic>k<\/jats:italic><\/jats:sub> whose chromatic number is just two. It follows that <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200003315_inline2\" \/> is strongly representable (each <jats:italic>k<\/jats:italic> &lt; <jats:italic>\u03c9<\/jats:italic>) but <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200003315_inline3\" \/> is not.<\/jats:p>","DOI":"10.2178\/jsl\/1245158086","type":"journal-article","created":{"date-parts":[[2009,6,16]],"date-time":"2009-06-16T13:16:09Z","timestamp":1245158169000},"page":"811-828","source":"Crossref","is-referenced-by-count":7,"title":["Strongly representable atom structures of cylindric algebras"],"prefix":"10.1017","volume":"74","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"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200003315_ref002","first-page":"65","volume":"73","author":"Andr\u00e9ka","year":"2008","journal-title":"Omitting types for finite variable fragments and complete representations of algebras"},{"key":"S0022481200003315_ref024","doi-asserted-by":"publisher","DOI":"10.1007\/s000120050047"},{"key":"S0022481200003315_ref019","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/8.4.451"},{"key":"S0022481200003315_ref016","doi-asserted-by":"publisher","DOI":"10.2307\/2372123"},{"key":"S0022481200003315_ref010","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0095613"},{"key":"S0022481200003315_ref009","volume-title":"Cylindric algebras part II","author":"Henkin","year":"1985"},{"key":"S0022481200003315_ref007","doi-asserted-by":"publisher","DOI":"10.1007\/BF01181878"},{"key":"S0022481200003315_ref021","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021368713305"},{"key":"S0022481200003315_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(89)90032-8"},{"key":"S0022481200003315_ref004","volume-title":"Graduate Texts in Mathematics","volume":"173","author":"Diestel","year":"1997"},{"key":"S0022481200003315_ref003","volume-title":"Model theory","author":"Chang","year":"1990"},{"key":"S0022481200003315_ref011","first-page":"816","volume":"62","author":"Hirsch","year":"1997","journal-title":"Complete representations in algebraic logic"},{"key":"S0022481200003315_ref023","first-page":"291","volume-title":"Advances in modal logic '96","author":"Venema","year":"1997"},{"key":"S0022481200003315_ref015","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-04-03743-2"},{"key":"S0022481200003315_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)00015-8"},{"key":"S0022481200003315_ref022","first-page":"56","article-title":"Contributions to the theory of models, III","volume":"58","author":"Tarski","year":"1955","journal-title":"Koninklijke Nederlandse Akademie van Wetenschappen. Indagationes Mathematicae"},{"key":"S0022481200003315_ref013","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-01-06232-3"},{"key":"S0022481200003315_ref020","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-30.1.264"},{"key":"S0022481200003315_ref017","first-page":"331","volume":"34","author":"Monk","year":"1969","journal-title":"Nonfinitizability of classes of representable cylindric algebras"},{"key":"S0022481200003315_ref008","volume-title":"Cylindric algebras part I","author":"Henkin","year":"1971"},{"key":"S0022481200003315_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)00027-4"},{"key":"S0022481200003315_ref018","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19700460105"},{"key":"S0022481200003315_ref005","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1959-003-9"},{"key":"S0022481200003315_ref012","volume-title":"Relation algebras by games","volume":"147","author":"Hirsch","year":"2002"}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200003315","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T11:24:13Z","timestamp":1556623453000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200003315\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["S0022481200003315"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1245158086","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9]]}}}