{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T05:17:49Z","timestamp":1774070269400,"version":"3.50.1"},"reference-count":13,"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":15167,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1972,9]]},"abstract":"<jats:p>A relational structure <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079032_inline1\"\/> of cardinality \u2135<jats:sub>0<\/jats:sub> is called <jats:italic>homogeneous<\/jats:italic> by Fraiss\u00e9 [1] if each isomorphism between finite substructures of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079032_inline1\"\/> can be extended to an automorphism of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079032_inline1\"\/>. In \u00a71 of this paper it is shown that there are <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079032_inline2\"\/> isomorphism types of such structures for the first order language <jats:italic>L<jats:sub>0<\/jats:sub><\/jats:italic> with a single (binary) relation symbol, answering a question raised by Fraiss\u00e9. In fact, as is shown in \u00a72, a family of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079032_inline2\"\/> nonisomorphic homogeneous structures for <jats:italic>L<\/jats:italic><jats:sub>0<\/jats:sub> can be constructed, each member <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079032_inline1\"\/> of which satisfies the following conditions (where <jats:italic>U<\/jats:italic> is the homogeneous, \u2135<jats:sub>0<\/jats:sub>-universal graph, the structure of which is considered in [4]):<\/jats:p><jats:p>(i) The relation <jats:italic>R<\/jats:italic> of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079032_inline1\"\/> is asymmetric (<jats:italic>R<\/jats:italic> \u2229 <jats:italic>R<\/jats:italic><jats:sup>\u22121<\/jats:sup> = \u2205);<\/jats:p><jats:p>(ii) If <jats:italic>A<\/jats:italic> is the domain of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079032_inline1\"\/> and <jats:italic>S<\/jats:italic> is the symmetric relation <jats:italic>R<\/jats:italic> \u222a <jats:italic>R<\/jats:italic><jats:sup>\u22121<\/jats:sup>, then (<jats:italic>A, S<\/jats:italic>) is isomorphic to <jats:italic>U<\/jats:italic>. That is, each <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079032_inline1\"\/> may be regarded as the result of assigning a unique direction to each edge of the graph <jats:italic>U<\/jats:italic>.<\/jats:p><jats:p>Let <jats:italic>T<\/jats:italic><jats:sub>0<\/jats:sub> be the first order theory of all homogeneous structures for <jats:italic>L<\/jats:italic><jats:sub>0<\/jats:sub> which have cardinality \u2135<jats:sub>0<\/jats:sub>. In \u00a73 (which can be read independently of \u00a72) it is shown that <jats:italic>T<\/jats:italic><jats:sub>0<\/jats:sub> has <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079032_inline2\"\/> complete extensions (in L<jats:sub>0<\/jats:sub>), each of which is \u2135<jats:sub>0<\/jats:sub>-categorical. Moreover, among the complete extensions of <jats:italic>T<\/jats:italic><jats:sub>0<\/jats:sub> are theories of arbitrary (preassigned) degree of unsolvability. In particular, there exists an undecidable, \u2135<jats:sub>0<\/jats:sub>-categorieal theory in <jats:italic>L<\/jats:italic><jats:sub>0<\/jats:sub>, which answers a question raised by Grzegorczyk [2], [3].<\/jats:p><jats:p>It follows from Theorem 6 of [3] that there are \u2135<jats:sub>0<\/jats:sub>-categorical theories of partial orderings which have arbitrarily high degrees of unsolvability. This is in sharp contrast to the situation for linear orderings, which were the motivation for Fraiss\u00e9's early work. Indeed, as is shown in [10], every \u2135<jats:sub>0<\/jats:sub>-categorical theory of a linear ordering is finitely axiomatizable. (W. Glassmire [12] has independently shown the existence of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079032_inline2\"\/> theories in <jats:italic>L<\/jats:italic><jats:sub>0<\/jats:sub> which are all \u2135<jats:sub>0<\/jats:sub>-categorical, and C. Ash [13] has independently shown that such theories exist with arbitrary degree of unsolvability.)<\/jats:p>","DOI":"10.2307\/2272734","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:17:55Z","timestamp":1146950275000},"page":"494-500","source":"Crossref","is-referenced-by-count":56,"title":["Countable homogeneous relational structures and <i>\u2135<\/i><sub>0<\/sub>-categorical theories"],"prefix":"10.1017","volume":"37","author":[{"given":"C. Ward","family":"Henson","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200079032_ref010","doi-asserted-by":"publisher","DOI":"10.4064\/fm-64-1-1-5"},{"key":"S0022481200079032_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0060626"},{"key":"S0022481200079032_ref002","first-page":"687","article-title":"Logical uniformity by decomposition and categoricity in \u21350","volume":"16","author":"Grzegorczyk","year":"1968","journal-title":"Bulletin de l'Acad\u00e9mie Polonaise des Sciences, S\u00e9rie Sciences, Mathematiques, Astronomiques et Physiques"},{"key":"S0022481200079032_ref004","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1971.38.69"},{"key":"S0022481200079032_ref005","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10468"},{"key":"S0022481200079032_ref006","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10601"},{"key":"S0022481200079032_ref007","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10648"},{"key":"S0022481200079032_ref008","doi-asserted-by":"publisher","DOI":"10.4064\/aa-9-4-331-340"},{"key":"S0022481200079032_ref009","first-page":"83","volume-title":"A seminar in graph theory","author":"Rado","year":"1967"},{"key":"S0022481200079032_ref011","volume-title":"Mathematical logic","author":"Shoenfield","year":"1969"},{"key":"S0022481200079032_ref012","first-page":"295","article-title":"A problem in categoricity","volume":"17","author":"Glassmire","year":"1970","journal-title":"Notices of the American Mathematical Society"},{"key":"S0022481200079032_ref001","doi-asserted-by":"publisher","DOI":"10.24033\/asens.1027"},{"key":"S0022481200079032_ref013","first-page":"423","article-title":"Undecidable \u21350-categorical theories","volume":"18","author":"Ash","year":"1971","journal-title":"Notices of the American Mathematical Society"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200079032","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T20:57:18Z","timestamp":1559249838000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200079032\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1972,9]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1972,9]]}},"alternative-id":["S0022481200079032"],"URL":"https:\/\/doi.org\/10.2307\/2272734","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1972,9]]}}}