Prime and search computability, characterized as definability in certain sublanguages of constructible 𝐿_{𝜔}_{1,𝜔}

Gordon, Carl E.

doi:10.1090/S0002-9947-1974-0416882-2

Prime and search computability, characterized as definability in certain sublanguages of constructible $L_{\omega }{}_{1,\omega }$
HTML articles powered by AMS MathViewer

by Carl E. Gordon

Trans. Amer. Math. Soc. 197 (1974), 391-407

DOI: https://doi.org/10.1090/S0002-9947-1974-0416882-2

PDF | Request permission

Abstract:

The prime computable (respectively, search computable) relations of an arbitrary mathematical structure are shown to be those relations R such that both R and its complement are definable by disjunctions of recursively enumerable sets of quantifier free (respectively, existential) formulas of the first order language for the structure. The prime and search computable functions are also characterized in terms of recursive sequences of terms and formulas of this language.

References

Daniel Lacombe, Recursion theoretic structure for relational systems, Logic Colloquium ’69 (Proc. Summer School and Colloq., Manchester, 1969) North-Holland, Amsterdam, 1971, pp. 3–17. MR 0276075
Yiannis N. Moschovakis, Abstract computability and invariant definability, J. Symbolic Logic 34 (1969), 605–633. MR 270908, DOI 10.2307/2270854
Yiannis N. Moschovakis, Abstract first order computability. I, II, Trans. Amer. Math. Soc. 138 (1969), 427–464. MR 244045, DOI 10.1090/S0002-9947-1969-0244045-0
Gaisi Takeuti and Akiko Kino, On predicates with constructive infinitely long expressions, J. Math. Soc. Japan 15 (1963), 176–190. MR 155742, DOI 10.2969/jmsj/01520176