Back to search

University of Waterloo

Degree Spectra of Unary relations on ω and ζ

Abstract

dc:description.abstract

Let X be a unary relation on the domain of (ω,<). The degree spectrum of X on (ω,<) is the set of Turing degrees of the image of X in all computable presentations of (ω,<). Many results are known about the types of degree spectra that are possible for relations forming infinite and coinfinite c.e. sets, high c.e. sets and non-high c.e. sets on the standard copy. We show that if the degree spectrum of X contains the computable degree then its degree spectrum is precisely the set of Δ_2 degrees. The structure ζ can be viewed as a copy of ω* followed by a copy of ω and, for this reason, the degree spectrum of X on ζ can be largely understood from the work on ω. A helpful correspondence between the degree spectra on ω and ζ is presented and the known results for degree spectra on the former structure are extended to analogous results for the latter.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2009

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Knoll, Carolyn Alexis

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/4544

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Knoll, Carolyn Alexis. Degree Spectra of Unary relations on ω and ζ. University of Waterloo, 2009. http://hdl.handle.net/10012/4544