×

Permutations and implicit definability. (Russian) Zbl 0649.03024

For any Turing degree d, \(G_ d\) is the group of all permutations of \({\mathbb{N}}\) (the set of natural numbers) whose Turing degrees are less or equal to d. A family A of subsets of \({\mathbb{N}}\) is implicitly definable if there is an arithmetical formula \(\phi\) (P), with a unary predicate symbol P, such that for every set of natural numbers \(X: <{\mathbb{N}},+,\cdot,S,<,0,X>\) satisfies \(\phi\) (P) iff X is in A. Main results are the following: If A is implicitly definable then there is a sentence \(\psi\) in the language of groups such that for every degree d, \(G_ d\) satisfies \(\psi\) iff A contains a set of degree d; for every sentence \(\psi\) the set of degrees d such that \(G_ d\) satisfies \(\psi\) is implicitly definable. It follows that the set of Turing degrees of sets in an implicitly definable family is implicitly definable (a family D of degrees is implicitly definable if \(\cup D\) is), in particular every arithmetical degree is implicitly definable. The degree of a model M is the least degree c such that there exists a model M’ recursive in c which is isomorphic to M. It is shown that for every d the degree of \(G_ d\) exists and is equal to d.
Reviewer: R.Kossak

MSC:

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20B99 Permutation groups
PDFBibTeX XMLCite
Full Text: EuDML