Abstract

Let a trace be a computably enumerable set of natural numbers such that V[m]={n:〈n,m〉∈V}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${V^{[m]} = \{n : \langle n, m\rangle \in V \}}$$\end{document} is finite for all m, where 〈.,.〉\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\langle^{.},^{.}\rangle}$$\end{document} denotes an appropriate pairing function. After looking at some basic properties of traces like that there is no uniform enumeration of all traces, we prove varied results on traceability and variants thereof, where a function f:N→N\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${f : \mathbb{N} \rightarrow \mathbb{N}}$$\end{document} is traceable via a trace V if for all m,〈f(m),m〉∈V.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${m, \langle f(m), m\rangle \in V.}$$\end{document} Then we turn to lattices Ltr(V)=({W:V⊆WandWatrace},⊆),\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textit{\textbf{L}}_{tr}(V) = (\{W : V \subseteq W \, {\rm and} \, W \, {\rm a} \, {\rm trace}\}, \, \subseteq),$$\end{document}V a trace. Here, we study the close relationship to E=({A:A⊆Nc.e.},⊆)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{E} = (\{A : A \subseteq \mathbb{N} \quad c.e.\}, \subseteq)}$$\end{document}, automorphisms, isomorphisms, and isomorphic embeddings.