{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T12:41:40Z","timestamp":1776688900268,"version":"3.51.2"},"reference-count":36,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":3571,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2004,6]]},"abstract":"<jats:p>When bounds on complexity of some aspect of a structure are preserved under isomorphism, we refer to them as <jats:italic>intrinsic<\/jats:italic>. Here, building on work of Soskov [34], [33], we give syntactical conditions necessary and sufficient for a relation to be intrinsically <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S002248120000791X_inline04\"\/> on a structure. We consider some examples of computable structures <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S002248120000791X_inline02\"\/> and intrinsically <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S002248120000791X_inline04\"\/> relations <jats:italic>R.<\/jats:italic> We also consider a general family of examples of intrinsically <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S002248120000791X_inline04\"\/> relations arising in computable structures of maximum Scott rank.<\/jats:p><jats:p>For three of the examples, the maximal well-ordered initial segment in a Harrison ordering, the superatomic part of a Harrison Boolean algebra, and the height-possessing part of a Harrison <jats:italic>p<\/jats:italic>-group, we show that the Turing degrees of images of the relation in computable copies of the structure are the same as the Turing degrees of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S002248120000791X_inline04\"\/> paths through Kleene's <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S002248120000791X_inline01\"\/>. With this as motivation, we investigate the possible degrees of these paths. We show that there is a <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S002248120000791X_inline04\"\/> path in which \u2205\u2032 is not computable. In fact, there is one in which no noncomputable hyperarithmetical set is computable. There are paths that are Turing incomparable, or Turing incomparable over a given hyperarithmetical set. There is a pair of paths whose degrees form a minimal pair. However, there is no path of minimal degree.<\/jats:p>","DOI":"10.2178\/jsl\/1082418544","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T21:38:27Z","timestamp":1109799507000},"page":"585-611","source":"Crossref","is-referenced-by-count":14,"title":["\u03a0<sub>1<\/sub><sup>1<\/sup> relations and paths through"],"prefix":"10.1017","volume":"69","author":[{"given":"Sergey S.","family":"Goncharov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valentina S.","family":"Harizanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julia F.","family":"Knight","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard A.","family":"Shore","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S002248120000791X_ref036","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(78)90026-8"},{"key":"S002248120000791X_ref034","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19960420110"},{"key":"S002248120000791X_ref030","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)70961-3"},{"key":"S002248120000791X_ref027","first-page":"178","article-title":"A note on paths through","volume":"39","author":"Parikh","year":"1973","journal-title":"Proceedings of the American Mathematical Society"},{"key":"S002248120000791X_ref024","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1971-024-7"},{"key":"S002248120000791X_ref022","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)00059-6"},{"key":"S002248120000791X_ref021","volume-title":"Infinite abelian groups","author":"Kaplansky","year":"1954"},{"key":"S002248120000791X_ref020","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1969.30.67"},{"key":"S002248120000791X_ref015","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90097-6"},{"key":"S002248120000791X_ref013","unstructured":"Goncharov S. S. , Harizanov V. S. , Knight J. F. , McCoy C. , Miller R. G. , and Solomon R. , Enumerations in computable structure theory, submited."},{"key":"S002248120000791X_ref011","first-page":"311","article-title":"Recursiveness in  paths through","volume":"54","author":"Friedman","year":"1976","journal-title":"Proceedings of the American Mathematical Society"},{"key":"S002248120000791X_ref017","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0244049-7"},{"key":"S002248120000791X_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(88)90014-0"},{"key":"S002248120000791X_ref035","first-page":"151","volume":"20","author":"Spector","year":"1955","journal-title":"Recursive well-orderings"},{"key":"S002248120000791X_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(89)90015-8"},{"key":"S002248120000791X_ref032","first-page":"329","volume-title":"The theory of models","author":"Scott","year":"1965"},{"key":"S002248120000791X_ref016","unstructured":"Harrington L. , McLaughlin's conjecture, handwritten notes, 1976."},{"key":"S002248120000791X_ref029","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S002248120000791X_ref007","first-page":"226","volume":"34","author":"Barwise","year":"1969","journal-title":"Infinitary logic and admissible sets"},{"key":"S002248120000791X_ref018","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00087-2"},{"key":"S002248120000791X_ref008","first-page":"1168","volume":"55","author":"Chisholm","year":"1990","journal-title":"Effective model theory vs. recursive model theory"},{"key":"S002248120000791X_ref005","first-page":"26","volume-title":"Aspects of effective algebra","author":"Ash","year":"1981"},{"key":"S002248120000791X_ref003","volume-title":"Computable structures and the hyperarithmetical hierarchy","author":"Ash","year":"2000"},{"key":"S002248120000791X_ref014","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021758312697"},{"key":"S002248120000791X_ref009","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511629167.005"},{"key":"S002248120000791X_ref010","first-page":"113","volume":"40","author":"Friedman","year":"1975","journal-title":"One hundred and two problems in mathematical logic"},{"key":"S002248120000791X_ref023","first-page":"103","volume-title":"Infinitistic methods","author":"Kreisel","year":"1959"},{"key":"S002248120000791X_ref028","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(77)90009-2"},{"key":"S002248120000791X_ref012","doi-asserted-by":"publisher","DOI":"10.1007\/BF01669456"},{"key":"S002248120000791X_ref031","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12013-2"},{"key":"S002248120000791X_ref025","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21755-9"},{"key":"S002248120000791X_ref026","unstructured":"Manasse M. S. , Techniques and counterexamples in almost categorical recursive model theory, Ph.D. thesis , University of Wisconsin-Madison, 1982."},{"key":"S002248120000791X_ref033","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19960420139"},{"key":"S002248120000791X_ref019","doi-asserted-by":"publisher","DOI":"10.4064\/fm-87-2-161-167"},{"key":"S002248120000791X_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)00043-3"},{"key":"S002248120000791X_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(96)00026-7"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S002248120000791X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T21:02:45Z","timestamp":1557176565000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S002248120000791X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,6]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2004,6]]}},"alternative-id":["S002248120000791X"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1082418544","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,6]]}}}