Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-15T13:11:13.720Z Has data issue: false hasContentIssue false

Π11 relations and paths through

Published online by Cambridge University Press:  12 March 2014

Sergey S. Goncharov
Affiliation:
Academy of Sciences, Siberian Branch, Mathematical Institute, 630090 Novosibirsk, Russia, E-mail: gonchar@math.nsc.ru
Valentina S. Harizanov
Affiliation:
Department of Mathematics, The George Washington University, Washington, DC. 20052, U.S.A., E-mail: harizanv@gwu.edu
Julia F. Knight
Affiliation:
Department of Mathematics, University of Notre Dame, Notre Dame, IN 46556, U.S.A., E-mail: julia.f.knight.1@nd.edu
Richard A. Shore
Affiliation:
Department of Mathematics, Cornell University, Ithaca, NY 14853, U.S.A., E-mail: shore@math.cornell.edu

Extract

When bounds on complexity of some aspect of a structure are preserved under isomorphism, we refer to them as intrinsic. Here, building on work of Soskov [34], [33], we give syntactical conditions necessary and sufficient for a relation to be intrinsically on a structure. We consider some examples of computable structures and intrinsically relations R. We also consider a general family of examples of intrinsically relations arising in computable structures of maximum Scott rank.

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 p-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 paths through Kleene's . With this as motivation, we investigate the possible degrees of these paths. We show that there is a path in which ∅′ 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.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2004

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable