English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We show that for any arithmetical m-degree d there is a first order decision problem P such that P has m-degree d for the free 2-step nilpotent group of rank 2. This implies a conjecture of Sacerdote. Let So(v) be a formula of the first order language of group theory L and 7r a finite group presentation in an alphabet X. The first order decision problem (?v)p(v) for G, the group defined by xr, is the problem of deciding for arbitrary tuple of words u in X whether or not the sentence po(u) holds in Go. For example, (?v)v =1 is the word problem and (?xy)(3z)xz = y is the conjugacy problem. It is easy to see that for a finitely presented group G the type of recursive isomorphism of the problem (?v)(o(v) is independent of which finite presentation of G one chooses. Sacerdote [S1] posed the following problem: which Turing degrees of unsolvability are the degrees of first order decision problems for finitely presented groups? For any atomic formula ~p(v) the problem (?v)p(v) is recursively enumerable; therefore any first order decision problem for any finitely presented group is arithmetical. Boone suggested that all first order decision problems for finitely presented groups have recursively enumerable Turing degrees. Sacerdote [S2] showed that it is not so. He constructed an ad hoc rather complicated example of a finitely presented group G and a formula p(v) with four free variables such that the problem (?v)fO(v) has degree 0" for G. He suggested the following Conjecture. Let D be an arithmetical degree of unsolvability. Then there exist a first order decision problem P and a finitely presented group G such that P has degree D for G. The aim of the present note is to prove this conjecture in a stronger form. Theorem. Let F be the free 2-step nilpotent group of rank 2. Then for any arithmetical m-degree d there is an L-formula Pod(v) with one free variable such that the problem (?v)pd(v) has m-degree d for F. Note that F is finitely presented: if a, and a2 freely generate F, then the relations [a,,a2,al] =1 and [ai,a2,a2] = 1 define F. Received by the editors August 19, 1994. 1991 Mathematics Subject Classification. Primary 03D40, 03D30, 20F10, 20F18.

Degrees of unsolvability of first order decision problems for finitely presented groups