## Abstract

We propose a framework to study the computational complexity of definable relations on a structure. Many of the notions we discuss are old, but the viewpoint is new. We believe that all the pieces fit together smoothly under this new point of view. We also survey related results in the area. More concretely, we study the space of sequences of relations over a given structure. On this space, we develop notions of c.e.-ness, reducibility, join and jump. These notions are equivalent to other notions studied in other settings. We explain the equivalences and differences between these notions.

## 1. Introduction

The study of the complexity of definable relations over a given structure is a main theme in mathematical logic. In this study, we are interested in using computational ways of measuring the complexity of relations. The key notion of this study is the one of *rice sequence of relations*, where rice stands for *relatively intrinsically computably enumerable*. A rice relation on a structure is one that is always computably enumerable relative to any given presentation of (definition 3.1). Rather than looking at relations (i.e. subsets of *A*^{n} for some *n*), we will look at sequences of relations that can be used, for instance, to code subsets of *A*^{<ω}, and even subsets of . This idea of going beyond subsets of *A*^{n} to develop a better theory of computability is not new, and it appears, for instance, in the work on hereditarily finite extensions or Moschovakis extensions that we will mention later. Once we have a notion of c.e.-ness (namely rice) on the space of sequences of relations over a fixed structure , we can define a notion of relative computability, of join and of jump. This notion of jump of a relation, or of a sequence of relations, can then be extended to the notion of the jump of a structure. Different notions of jump for structures have been developed in recent years by researchers in the computability groups of Novosibirsk and Sofia (see §§5 and 6), and by the present author.

In this study, we survey some of this recent work in the context of the study of sequences of relations. We believe that all the pieces fit together nicely under this new viewpoint, which is even slightly different from the one used by the present author in the past few years [1–3]. Much of the notation introduced in those papers is revisited here. For instance, we remark that what used to be called a jump of in Montalbán [1–3] is now called *a structural jump of * defined in §6, and different from *the* jump of as defined in §5.

The reason why we like the viewpoint developed here is that it is closer, in style, to the notions used by many of the people already working on computable structure theory, particularly in the West, which makes it more approachable. Of course, other researchers might disagree. This study also contains historical information explaining what the other known similar notions are, how they were developed and how they connect to the notions here.

The present author's original motivation in this topic [1,2] was to study relations on a given structure that contain all the structural *Σ*^{c}_{n} information about . In many cases, one can find a nice, small set of relations that, alone, give you everything you need to know about all other *Σ*^{c}_{n} relations. Finding such relations can, of course, be useful for other applications. We will talk about this in the last two sections of this study.

Most of the results in this study are not new, at least not in essence. This is except for the work in §7, where we study finite complete sets of rice relations. The work in that section was carried out during a visit to Sofia, Bulgaria, the week before CiE'11, by J. F. Knight, R. Miller, I. N. Soskov, A. Soskova, M. Soskova, S. VanDenDriessche and S. Vatev and the present author. (The author would like to thank them for allowing him to publish these results here.)

## 2. Background

We consider only relational languages, because functions can be coded as relations without changing the computational complexity of the objects we are interested in. Our languages are always computable. That is, they are countable and we can effectively list all their symbols and their arities. We will always use to denote a language, where is finite or infinite, and where *P*_{i} has arity *p*_{i}. Because is computable, the function *i*↦*p*_{i} is computable. By an *-structure*, we mean a tuple where for all *i*. We allow only countable structures, as we will not deal with larger structures in this study. By a *copy of *, or by a *presentation of *, we mean another structure that is isomorphic to and where . Because all our structures are countable, it does not hurt to assume that the domains are always subsets of . However, the words ‘copy’ or ‘presentation’ emphasize that we are talking about this particular representation of , and not about the isomorphism type of .

Given a structure with , we let be the atomic diagram of . More concretely, let *a*_{0},*a*_{1},… be constant symbols naming the elements of where the number is named by *a*_{i} (if *i*∉*A*, then *a*_{i} does not name anybody). Let be an effective listing of all the atomic formulae. Finally, let be defined by
In particular, we let if uses some constant *a*_{j} for which *j*∉*A*. Notice that computes *A* by looking at the formulae *a*_{i}=*a*_{i}.

When we say that a set *X* is c.e. (computable) in a structure , we mean that *X* is c.e. (computable) in , which of course depends on the given presentation of . The *spectrum* of a structure is
where is the set of Turing degrees. (The spectrum of is often the set of degrees of all copies of . The two definitions are equivalent for non-trivial structures, as proved by Knight [4].)

All throughout we will use the letters , and to denote structures with domains *A*, *B* and *C*, and we will use the letters *X*, *Y* and *Z* for sets of natural numbers. Unless we specify otherwise, is always an -structure where is as mentioned earlier.

We will use *Σ*^{c}_{n} and *Π*^{c}_{n} to denote the set of *computable infinitary* *Σ*_{n} and *Π*_{n} formulae. These are first-order -formulae in which we allow infinitary disjunctions and infinitary conjunctions so long as they are taken over a computable list of formulae, and so long as there are only finitely many different free variables over all the formulae in the list. When we count alternation of quantifiers, infinitary disjunctions count as ∃ and infinitary conjunctions count as ∀. See Ash & Knight [5], ch. 7 for more background on these formulae.

Given a tuple in , we let , the * Σ_{1}-type of in *, be the set of Gödel numbers of all

*Σ*

_{1}formulae true about in .

We use to denote the set of finite subsets of *X*.

## 3. Rice relations

The following well-known notion is central to this study.

### Definition 3.1

A relation *R*⊆*A*^{n} is *rice (relatively intrinsically computably enumerable)* if, for every copy of , we have that is c.e. in .

Notice that the notion of being rice is independent of the presentation of , and depends only on its isomorphism type.

### Example 3.2

Let be a linear ordering. We say that *x* and *y*∈*A* are *adjacent*, and write *Adj*(*x*,*y*), if there is no element in between them. The relation ¬*Adj*(⋅,⋅) is rice in .

We shall call a relation whose complement is rice as *co-rice*.

### Example 3.3

Let be a graph that consists of infinitely many disjoint cycles, one of each size *n* for *n*≥3. Let *R* be the set of vertices *x* in such that *x* belongs to a cycle of size *n*, for some *n*∈0′ (i.e. with {*n*}(*n*)↓). Then, *R* is rice in .

The relations in the above-mentioned examples have quite a different feel to them. The former contain structural information, whereas the latter code ‘Turing-degree information’, namely 0′. We will say more about this later.

The following theorem characterizes rice relations in purely syntactical terms, as opposed to the definition that refers to computations whose oracles are the diagrams of the copies of the given structure.

### Theorem 3.4 (Ash et al. [6]; Chisholm [7])

*Let* *be a structure, and R⊆A*^{n} *a relation on it. The following are equivalent*:

*R is rice*.*R is definable by a**formula with parameters from*.

Recall that a formula is nothing more than an infinitary disjunction of a computable list of finitary *Σ*_{1} -formulae.

Once we have a notion of c.e.-ness among relations on , we can develop a notion of computability.

### Definition 3.5

Let *R* and *Q* be relations on . We say that R is relatively intrinsically computable in *Q*, and we write
if *R* is both rice and co-rice in .

**Historic remark 3.6.** The notion of rice relation has appeared already in Ash *et al*. [6]—see also Ash & Knight [5], ch. 10. The equivalent notion of *Σ*-definable relation on was used by Ershov as part of the study of admissibility over abstract structures, and is still used in Russia quite a bit. We will say more about *Σ*-definability in §4*a*. Moschovakis [8] defined an equivalent notion called a *semi-search computable relation*, which is also defined on an extended domain (of the sort of ), and appears often in the work of Soskov *et al.* The equivalence between these notions is due to Gordon [9].

### (a) Sequences of relations

The space of relations on a structure is not rich enough to develop a good theory of computability because, for instance, it does not always have a universal rice relation. There are various approaches to solve this issue. One is to consider relations defined on extensions of the structure like the hereditarily finite extension (see §4*a*), or the Moschovakis extension [8]. Here, we take a different approach that is probably friendlier for the audience accustomed to the style of Ash & Knight's book [5].

### Definition 3.7

Let be the set of all sequences of relations ** R**=(

*R*

_{0},

*R*

_{1},…), where

*R*

_{i}⊂

*A*

^{ri}and the arity function

*i*↦

*r*

_{i}is computable.

We say that ** R** is

*rice in*if, for every copy of , we have that is uniformly c.e. in , that is, the set is c.e. in .

Given ** R** and , we say that

**is**

*R**r.i. computable in*, and write if both

*Q***and ¬**

*R***are rice in , where ¬**

*R***is the sequence of complements of the relations in**

*R***, and is a new structure whose language is augmented with infinitely many new relations symbols**

*R**Q*

_{i}, one for each , interpreted in the obvious way according to

**.**

*Q*

### Example 3.8

Let be a -vector space. Then, ** LD**=(

*LD*

_{2},

*LD*

_{3},…), given by are linearly dependent}, is rice in .

### Example 3.9

Let be a ring. Then, ** R**=(

*R*

_{1},

*R*

_{2},…), given by

*R*

_{i}={(

*a*

_{0},…,

*a*

_{i})∈

*A*

^{i+1}:

*a*

_{i}

*x*

^{i}+⋯+

*a*

_{1}

*x*+

*a*

_{0}is a reducible polynomial}, is rice in .

### Remark 3.10

Note that we can represent not only subsets of *A*^{<ω} as sequences of relations, but also subsets of , for instance, by considering sequences where *R*_{i,j} has arity *i*. Furthermore, restricting ourselves to work just with subsets of would be essentially equivalent to working with .

**Historic remark 3.11.** An equivalent notion of computability on subsets of , for the structure on an empty language, has already been considered by Baleva [10] and Soskov [11].

#### (i) Information sequences

We can also use sequences of relations to code subsets of in a natural way. We will allow ourselves to consider relations *R*⊆*A*^{r}, where *r*=0. Recall that *A*^{0}={〈〉}, where 〈〉 is the empty tuple, and hence either or *R*={〈〉}. In the former case, we say that *R*=⊥, and that *R*=⊤ in the latter. (The reader who is uncomfortable with 0-ary relations can work with 1-ary relations *R* instead, where either or *R*=*A*.)

### Definition 3.12

If ** R** is a sequence of relations, all of arity 0, we say that

**is an**

*R**information sequence*. Given , let be the information sequence

**=(**

*X**X*

_{0},

*X*

_{1},…) where

We observe that ** X** is c.e. in an oracle

*Z*if and only if

*X*is c.e. in

*Z*. Thus,

**is rice in if and only if**

*X**X*is c.e. in the diagrams of all the copies of . In particular, for every c.e. set

*X*,

**is rice in . The set of all such that**

*X***is rice in , called the**

*X**co-spectrum of*(see Soskov [11]), forms an ideal in the enumeration degrees. This ideal is characterized by a theorem of Knight (corollary 3.16) given later.

Also note that, for , we have

#### (ii) Join of sequences

We also have a least-upper-bound operation on .

### Definition 3.13

Given ** R**=(

*R*

_{0},

*R*

_{1},…) and

**=(**

*Q**Q*

_{0},

*Q*

_{1},…) in , let

It is not hard to see that ** R**⊕

**is the least upper bound of**

*Q***and**

*R***in the -ordering.**

*Q*We will sometimes abuse notation and write *R*⊕** Q**, or

*R*

_{1}⊕

*R*

_{2}, even when

*R*,

*R*

_{1},

*R*

_{2}are relations, rather than sequences of relations, interpreting a single relation

*R*by the sequence .

#### (iii) The Ash–Knight–Manasse–Slaman–Chisholm theorem, revisited

This well-known theorem extends from relations to sequences of relations in a straightforward way. We include the proof here for completeness. The original proofs, which proved the result for r.i. -relations, used forcing, but the rice case can be proved in a much simpler way. An interesting fact about this extended version is that it also extends two other well-known theorems, one of Knight's and one of Selman's. We will see how they follow as particular cases (corollaries 3.16 and 3.17).

### Theorem 3.14 (Ash et al. [6]; Chisholm [7])

*Let* *R**=(R*_{0}*,R*_{1}*,…) be a sequence of relations in* . *The following are equivalent*:

*R**is rice*.*There is a tuple**∈A*^{<ω}*and a computable list ϕ*_{0}*,ϕ*_{1}*,… of Σ*^{c}_{1}*-formulae such that, for all**and all*(where r_{i}is the arity of R_{i}),

### Proof.

It is easy to see that (A2) implies (A1) because deciding *Σ*_{1} formulae about is c.e. in . We prove the other direction. We will attempt to build a copy of where is not uniformly c.e. in . By (A1), this attempt is bound to fail, and we will use this failure to find the list of formulae *ϕ*_{0},*ϕ*_{1},… that we need.

Let *A*^{☆} be the set of finite tuples from *A*, all of whose entries are different. At stage *s*, we will define such that (where inclusion here is as strings). At the end of stages, we will obtain . Along the way, we will make sure that every element of *A* is in some , and hence that *G* is a bijection between and *A*. We can then let be the pull-back of via *G*. That is, has domain , and, if *P* is a relation symbol of , holds if and only if holds. By (A1), we know that, for some index *e*,
Given , we let be the initial segment of of length , which is determined by , assuming we have that . More formally, let {*b*_{0},*b*_{1},…} be a list of constant symbols where *b*_{i} is interpreted as *i* in , and let be a list of all atomic -sentences, and assume that only uses constants *b*_{j} for *j*≤*i*. Given , let be such that if and only if . This way we have that
For *σ*∈2^{<ω}, we let be the step |*σ*| approximation to for any , noticing that cannot read the oracle *S* beyond position |*σ*| in less than |*σ*| steps. So we have that . We also notice that for *σ*∈2^{k} there is an atomic formula *ψ*_{σ} such that .

Now that we have got the background notation out of the way, here is the construction. Let be the empty sequence. At stage *s*+1=2*e*, we try to force as follows. Ask if there exist , and such that but (where *q*_{<inline−image4>}=(*q*_{j1},…,*q*_{jrn})). If so, let be such , and otherwise let . Notice that in the former case we have succeeded in making because we are forcing and . At stage *s*+1=2*e*+1, we take care of making *G* onto: if the *e*th element of is not already in , add it to the range of ; otherwise let .

Because we are assuming (A1), for some *e* we do get . Thus, at stage *s*+1=2*e*, there were no *n*, and as we wanted, as otherwise we would have acted. Let . We now claim that, for all and all , we have that
if and only if for some , with and with for some , we have that .

Note that this can be written as the disjunction over all *σ*∈2^{<ω} and all with , of the formulae that say that there exists such that, if we let , we get , and . So, the claim gives us a *Σ*^{c}_{1} definition of , with parameters and which is uniform on *n*. To prove the claim, notice that the left-to-right direction follows from by taking to be a long enough segment of *G*. For the other direction, notice that if such and existed, but , we would have chosen them and acted at step *s*+1. Contradicting the fact that we did not act. ■

For the next corollaries, we recall the definition of *enumeration reducibility*.

### Definition 3.15

A set is *e-reducible to* if there exists a c.e. set (called an *enumeration operator*) such that, for all , *n*∈*X* if and only if there exists such that (*n*,*D*)∈*Φ* and *D*⊆*Y* .

### Corollary 3.16 (Knight; see Ash & Knight [5], theorem 10.17)

*Let* . *The following are equivalent*:

*X**is c.e. in every copy of*.*X**is e-reducible to**Σ*_{1}-*tp**for some*∈*A*^{<ω}.

### Proof.

It is not hard to show that (B2) implies (B1) using that all *Σ*_{1}-types are c.e. in every copy of . We prove the other direction.

As we mentioned earlier, *X* is c.e. in every copy of if and only if ** X** is rice in . So, we have that (A1), and hence (A2), of theorem 3.14 hold for

**=**

*R***. Let be a computable sequence of -sentences with parameters witnessing (A2). Each**

*X**ϕ*

_{n}is of the form , where is the

*i*th

*Σ*

_{1}-formula. Let , so that if and only if, for some , , which happens if and only if

*ϕ*

_{n}holds. So, . ■

### Corollary 3.15 (Selman [12])

*Let* . *The following are equivalent*:

*Every enumeration of**Y**computes an enumeration of**X*.*X**is e-reducible to**Y*.

(*By* *enumeration of Y*,

*we mean a function*

*with range*

*Y*.)

### Proof.

It is not hard to show that (C2) implies (C1). We prove the other direction.

Assume *Y* is infinite; otherwise both statements are trivially equivalent to *X* being c.e. Consider a language with constants *c*_{0},*c*_{1},… and a binary relation *Q*. Let be the structure with domain , where *c*_{i} is interpreted as 2*i*, and no constants are assigned to the odd numbers, and where *Q* is a bijection between the odd numbers and the set {*c*_{i}:*i*∈*Y* }.

Now, it is clear that every presentation of computes an enumeration of the set *Y* . Hence, (C1) implies that *X* is c.e. in every presentation of , and thus that ** X** is rice in . So, we have that (B1), and hence (B2), of the previous corollary hold, that is, that

*X*is e-reducible to

*Σ*

_{1}-tp for some ∈

*A*

^{<ω}. Now, every

*Σ*

_{1}-type in is e-reducible to the set

*Y*: it is not hard to show, using disjunctive normal forms in a standard way, that every

*Σ*

_{1}formula about is equivalent to a finite disjunction of formulae of the form ∃

*x*

*Q*(

*x*,

*c*

_{i}) (which holds if and only if

*i*∈

*Y*). So we have that

*X*is e-reducible to

*Y*. ■

### (b) The jump of a sequence of relations

So far, on we have defined a notion of c.e.-ness, of computability and of join. Now, as the central notion of this study, we define a notion of jump. We start by defining the *universal rice sequence of relations*.

Let be an effective listing of all *Σ*^{c}_{1} -formulae, where has arity *k*_{i}.

### Definition 3.18

Let be defined by
is nothing more than the *Σ*^{c}_{1}-diagram of .

It should be clear that is rice.

### Observation 3.19

is *universal among rice sequences of relations* in in the following sense. If ** Q** is rice, there is and a computable such that
where

*q*

_{i}is the arity of

*Q*

_{i}, and the arity of is . To prove this, we use the extended Ash–Knight–Manasse–Slaman–Chisholm theorem 3.14: just let and be as given by the theorem, and let

*f*be the computable function such that

*ϕ*

_{i}is .

### Definition 3.20

Given , let be the structure augmented with infinitely many new relations interpreting *Q*_{i} for . Let *the jump of Q in * be . We denote it by

*.*

*Q*^{′}We can also define *Q*^{′′} as , etc.

### Remark 3.21

Let us use to denote the sequence of empty (unary) relations . Let us emphasize the difference between and **0**′. The former is as in definition 3.18 where the relations in the sequence have all possible arities, each arity appearing infinitely often. The latter is the information sequence coding 0′; so it consists of only 0-ary relations and contains no structural information about . We have that always holds just because **0**′ is rice. However, in most cases, has structural information about that **0**′ alone does not. The last two sections of this paper are dedicated to studying this structural information.

### Example 3.22

Let be a *linear ordering*. Then
This proof is given in Montalbán [2], theorem 2.1 using different notation.

### Example 3.23

Let be a -vector space. Then
This is because we can use ** LD** to compute an isomorphism between and the standard computable presentation of , where , and then we can use 0

^{(n)}to decide

*Σ*

^{c}

_{n}-relations on .

#### (i) Diagonalization

We now prove that, on the space of sequences of relations, the jump is actually a jump in the sense that is strictly increasing.

### Theorem 3.24 (Vatev [13]; Stukachev)

*For every* *.*

### Proof .

It is easy to see that because the *Σ*^{c}_{1} diagram of clearly computes the atomic diagram of . We now show that ** Q**′ is not r.i. computable in

**. It is enough to show that is not r.i. computable in for any given .**

*Q*We start by re-indexing so that the arity of each relation is reflected in the index. Let where is the *i*th *Σ*^{c}_{1} formula with arity *j*. Suppose, towards a contradiction, that is co-rice. For each , let
where {*e*} is the *e*th Turing functional. Note that, under the assumption that is co-rice, ** R** is rice. By the universality of (observation 3.19), there is an , an , and an index

*k*for a total computable function {

*k*} such that We then get the following contradiction: ■

**Historic Remark 3.25**. The proof given earlier is new, although it is clearly similar to the standard proof of the incomputability of the Halting problem. Theorem 3.24 had been previously proved for a different, yet equivalent, notion of jump (notion J2; see below) by Vatev [13]. Vatev's proof, restated in our terms, goes by showing that if is a generic copy of , then has degree (which, of course, is not computable in ), and hence is not r.i. computable in . Stukachev (A. I. Stukachev 2011, personal communication) has another proof that has not been translated into English yet.

## 4. Superstructures

We mentioned in §1 that the notion of rice sequences of relations is equivalent to other notions that were known many decades ago. In this section, we briefly sketch two of these other notions: the study of *Σ*-definable subsets of the hereditarily finite superstructures, and the study of semi-search computable subsets of the Moschovakis superstructure.

The reader can skip this section without affecting the understanding of the rest of the paper.

### (a) The hereditarily finite superstructure

As we mentioned earlier, another approach to the study of rice relations is using *Σ*-definability on admissible structures. We will not use admissible structures in general but just the hereditarily finite extension of an abstract structure , which we define subsequently. We will see how this is essentially equivalent to studying rice sequences of relations. For more background, see Barwise's book [14], ch. II or Stukachev's survey paper [15].

### Definition 4.1

Let denote the collection of finite subsets of *X*. Given a set *A*, we define:

,

and

.

Now, given an -structure , we define the -structure whose domain has two sorts, *A* and , and where the symbols of are interpreted in the *A*-sort as in , ‘∈’ is interpreted in the obvious way, and *D* is a unary relation coding the atomic diagram of , as we explain later.

A quantifier of the form ∀*x*∈*y*… and ∃*x*∈*y*… is called a *bounded quantifier*. A * Σ-formula* is one that is built out of atomic and negation of atomic formulae using disjunction, conjunction, bounded quantifiers and existential unbounded quantifiers. A subset of is

*Δ-definable*if it and its complement are

*Σ*-definable.

Clearly, on , we have the usual pairing function 〈*x*,*y*〉={{*x*},{*x*,*y*}}, and, of course, we can also encode *n*-tuples, strings, etc. Notice, also, that includes the finite ordinals (denoted by ** n**, where and

**+**

*n***1**={

**}∪**

*n***). We use**

*n**ω*to denote the Δ-definable set of finite ordinals of . Well-known arguments in admissibility theory show that every c.e. subset of

*ω*is

*Σ*-definable in , and every computable function is Δ-definable (see, for instance, Barwise [14], theorem II.2.3).

We let be the *satisfaction relation for atomic formulae*, that is, , where is an effective enumeration of all the atomic formulae of . Notice that, if the language of is finite, this is a finite list. So, when the language of is finite, is Δ-definable in , without using of course, and hence it does not need to be added to the definition of .

Now, given any , we can encode it by

Another set we will use is the *satisfaction relation for Σ_{1} formulae*, that is,
where is an enumeration of all the

*Σ*

_{1}formulae of . Using recursion on the size of the formulae, it is not hard to prove that is

*Σ*-definable in .

### Theorem 4.2

*Let* . *The following are equivalent*:

*R**is rice in*.*h*()*R**is Σ-definable in**with parameters*.

**Historic remark 4.3**. This theorem is credited to Vatsenavichyus [16] in Stukachev [15] and appears in some form in Beljaeve & Ta-clin [17].

### Sketch of the proof.

We start by proving that is *Σ*-definable in , where is as in definition 3.18. Let *hK*_{0} be the satisfaction relation for finitary *Σ*_{1} formulae in , that is,
where is an enumeration of all the *Σ*_{1} formulae of . As with , it is not hard to prove that is *Σ*-definable in . Each *Σ*^{c}_{1} formula is a disjunction over some c.e. set *W*_{e} of formulae for *i*∈*W*_{e}. Using the *Σ*-definitions of and of , we get a *Σ*-definition of .

Assume now that ** R** is rice. Thus, there is and a computable function such that, for all and all , holds in if and only if holds. Using the

*Σ*-definition of , we get a

*Σ*-definition of

*h*(

**) with parameters .**

*R*Suppose now that *h*(** R**) is

*Σ*-definable in with parameters; we want to prove that

**is rice. Let be a copy of . Computably in build a copy of and then use the**

*R**Σ*-definition of

*h*(

**) to enumerate . We end up with a computable enumeration of relative to ). ■**

*R*There is also a natural way of going the other way around: from relations in to sequences of relations on . Let *X*={*x*_{0},*x*_{1},…}, where the *x*_{i}s are variable symbols. Every is essentially a term, and we write to show the variables that appear in *t*. Observe that . Let be an effective enumeration of , and let *q*_{i} be the number of different variables in *t*_{i}. Now, given , we define
With a bit of effort, one can show that the relation is Δ-definable in . This can be used to prove the following theorem.

### Theorem 4.4

*Given* *the following are equivalent*:

*s(Q) is rice in*.*Q is Σ-definable in**with parameters*.

### Proof.

Assume *s*(*Q*) is rice in . Then, *h*(*s*(*Q*)) is *Σ*-definable. Now, *a*∈*Q* if and only if there exist and such that and . This gives a *Σ*-definition of *Q* from the one of *h*(*s*(*Q*)).

Suppose now that *Q* is *Σ*-definable. As in the proof of the previous theorem, it is not hard to show that, for every copy of , is c.e. in . ■

### (b) The Moschovakis enrichment

The Moschovakis extension of a structure is not too far from .

### Definition 4.5 (Moschovakis [8])

Let 0 be a new constant symbol. Given a set *A*, we define *A*^{0}=*A*∪{0}, and we let *A** be the closure of *A*^{0} under a pairing operation *x*,*y*↦(*x*,*y*).

Moschovakis [8] then defines a class of partial multi-valued functions from (*A**)^{n} to *A** which he calls *search computable functions*. This class is defined as the least class closed under certain primitive operations, much in the style of Kleene's definition of primitive recursive and partial recursive functions, where, instead of Kleene's least-element operator *μ*, we have a multi-valued search operator *ν*. A subset of *A** is *search computable* if its characteristic function is, and it is *semi-search computable* if it has a definition of the form ∃*y*(*f*(*x*,*y*)=1), where *f* is search computable.

The definition of search computable allows us to add a list of new primitive functions to our starting list (so long as they are given in an effective list, with computable arities), obtaining a sort of *relativized version* of search computability. If we have a structure , we would add to the list of primitive functions the characteristic functions of the relations in to obtain a notion of partial, multi-valued, *search computable function in *.

Much in the same way as we did for earlier, we have a natural way of encoding sequences by subsets of , and vice versa. Perhaps even more directly, one can go from subsets of *A** to subsets of and back. Gordon [9] proved that the notions of search computable in and semi-search computable in for subsets of *A** coincide with the notions of Δ-definable and *Σ*-definable for subsets of . And hence, when you add parameters, they also coincide with the notions of r.i. computable and rice for sequences of relations in .

## 5. The jump of a structure

In this section, we look at the jump as a map from abstract structures to abstract structures, rather than from to .

### Definition 5.1

Given an -structure , we let where is as in definition 3.18, and is now an -structure, where .

Notice that the isomorphism type of does not depend on the presentation of . However it does depend, in a non-essential way, on the Gödel numbering of the *Σ*^{c}_{1} -formulae, in the same way as the Turing jump of a set depends on the numbering of the partial computable functions. Also notice that the extended language is still a computable relational language. is now infinite, even if was finite, and this can be viewed as a disadvantage of this definition. That is the price to pay if we want and to have the same domain.

We note that the above-mentioned definition also works for uncountable structures. However, we will still assume that all our structures are countable throughout this paper.

**Historic remark 5.2.** The jump of structures has been independently defined various times in the last few years. We have four different definitions of maps from abstract structures to abstract structures that we call jump. All these definitions are equivalent up to *Σ*-equivalence (see definition 5.5).

The first appearance in print of such a definition for all countable abstract structures is due to Baleva [10], as part of her PhD thesis under the supervision of Ivan Soskov. That definition uses, as the domain for the jump of , the Moschovakis extension of (see §4

*b*). Baleva's jump of adds to a universal*Σ*^{c}_{1}set, very similar to the set mentioned in §4*a*. Baleva sets up her definition in the semi-lattice of countable structures over a fixed domain ordered by**SC**-reducibility. This reducibility is essentially as defined in definition 3.7, where is the countable structure on the empty language, and all other structures are viewed as having the same domain as .Soskova and co-workers [18,19] worked with another map from structures to structures, which they did not call the jump of the structure until later papers. There, the domain of is the Moschovakis extension

*A** of*A*, and the added relation is one that codes (the negation of) the forcing relation on*Π*_{1}formulae, which is essentially following the notation of the proof of theorem 3.14.Stukachev [20,21], who was working on the semi-lattice of structures of any size below an arbitrary cardinal, ordered under

*Σ*-reducibility, provided a new definition of the jump of a structure in that setting. Stukachev was the first one to work with uncountable structures of any size. For him, the domain of is , and the added relation is the satisfaction relation for*Σ*_{1}-formulae, namely . The importance of the role of*Σ*-reducibility in this context was previously shown by Stukachev [22,23].Another independent definition of the jump is due to Puzarenko [24]. However, he defines only the jump of an admissible structure, and does not deal with structures in general. The definition is almost the same as that of Stukachev when one considers the jump of the admissible structure ; although they only realized this afterwards. Puzarenko's definition generalized an earlier definition of jump by Morozov [25] that works only for

*recursively listed admissible structures*, which are the admissible structures when there is a*Σ*-definable bijection between the whole domain and the class of ordinals.Montalbán [2], independently of all this previous work, introduced yet another definition. The original definition in Montalbán [2] is not completely equivalent to the above-mentioned definitions; it is what we call the

*structural jump*in §6. In that definition, the domain of the jump of a structure is the same as the domain of , and the language is extended with finitely or infinitely many new relations that, altogether, form a complete set of*Π*^{c}_{1}-relations.

### (a) Comparing structures

Working with structures as objects, we need to have a way of comparing the computational complexity of different structures. There is more than one way to do this. A measurement that is widely accepted is to say that a structure is more complicated than another if it is harder to compute, in the sense that it takes smarter oracles to produce a presentation of it. This reduction is more commonly used implicitly than explicitly as in the following definition.

### Definition 5.3

Given two structures and , we say that is *Muchnik reducible* to , and write , if
or equivalently, if . The ‘*w*’ stands for ‘weak’, where the strong reduction is the Medvedev reduction that asks for a uniform way of computing a copy of from a copy of .

This reduction defines a pre-ordering on the class of all countable structures, and hence an equivalence, ≡_{w}, as usual.

In some cases, this equivalence may not be appropriate, as it does not look too deeply into the model-theoretical aspects of a structure. For example, any two computable structures are equivalent under ≡_{w}, even if the structures are model-theoretically very different. The following reduction is nothing more than an effective version of the notion of interpretability used in model theory.

### Definition 5.4

Let be an -structure, and be any structure, where and *P*_{i} has arity *p*_{i}.

We say that is *effectively interpretable* in , and write , if, for some , in , there is a rice set *D*⊆*B*^{n}, a r.i. computable subset *η*⊆*B*^{n}×*B*^{n} which is an equivalence relation on *D*, and a r.i. computable sequence of sets *R*_{i}⊆*B*^{n⋅pi}, closed under the equivalence *η* within *D*, such that
The sets *R*_{i} do not need to be subsets of *D*^{pi}, and when we refer to the structure (*D*/*η*;*R*_{0},*R*_{1},…) we, of course, mean (*D*/*η*;(*R*_{0}∩*D*^{p0})/*η*,(*R*_{1}∩*D*^{p1})/*η*,…).

Being ≡_{I} is a very strong notion of equivalence, which reflects both effective and model-theoretical aspects of the structure. However, in some cases, the restriction of *D* to being a subset of *B*^{n} can be too strong. We already argued that, when studying rice relations, one needs to go beyond the study of subsets *D*⊆*B*^{n}. The following notion fixes this problem.

### Definition 5.5

Consider structures and as mentioned already. We say that is * Σ-reducible to* if there is an effective interpretation of in as in the previous definition, but allowing

*D*to be a rice subset of , and

*η*and

**to be r.i. computable relations on , of course viewed as elements of .**

*R*

### Observation 5.6

Consider structures and as above. Then

### Theorem 5.7

*For any structures* *and*

*implies*and*implies*.

*None of the implications above reverses.*

### Proof.

None of the implications is hard to prove. To see that the first implication does not reverse consider , and the countable infinite structure over the empty language. Then, because can be effectively interpreted in arithmetic, and hence is ≤_{Σ}-reducible to any structure. On the other hand, it is not hard to prove that , because the only rice subsets of *B*^{n} in are either finite or co-finite.

There are various proofs that does not imply ; see, for instance, Stukachev [22] and Kalimullin [26,27]. For one such example: let be the structure coding the family of the graphs of all computable functions, i.e. it is a family of sets of pairs, each set being the graph of a computable function. Let be the family of all c.e. sets. Then, it is proved in Kalimullin & Puzarenko [27] that but . ■

**Historic remark 5.8.** The notion of *Σ*-reducibility between abstract structures was introduced independently by Khisamiev [28] and Stukachev [22], and it is based on the notion of *Σ*-definability of a structure inside an admissible set by Ershov. Stukachev [22,23] and Puzarenko and co-workers [24,27] showed the importance of this reducibility and compared it with various other reducibilities between structures (including ≤_{w}). The definitions of earlier studies [22,28] used, of course, the notions of *Σ*-definability rather than rice. The equivalence with the definition given here follows from theorems 4.2 and 4.4.

### (b) The three main theorems about the jump

We now state the three main results about the jump of structures.

#### (i) The first jump inversion theorem

This theorem is a generalization of the Friedberg jump inversion theorem to the semi-lattice of structures under ≤_{Σ}-reducibility.

### Theorem 5.9

*For every structure* *which codes 0′ (i.e.* *is r.i. computable in* *there is a structure* *such that* *.*

**Historic remark 5.10**. For the case of Muchnik equivalence, this theorem was proved independently in two occasions. One is due to Goncharov *et al.* [29], lemma 5.5 for *α*=2. They do not state their result in terms of the jump of a structure, and they prove only the theorem for graphs, but any degree spectrum can be realized as the degree spectrum of a graph. They prove inversion, not only for a single jump, but also for the *α*th jump, for every . They proved this result as a tool to get other results about categoricity and intrinsic relations. Their *α*-jump inversion theorem was used on other occasions, for instance by Greenberg *et al.* [30] to build a structure whose spectrum is exactly the non-hyperarithmetic degrees.

The other proof of theorem 5.9 for ≡_{w} is due to Soskova and co-workers [18,19]. Her construction is quite different and uses Marker extensions. The inspiration to use a Marker extension in this context came from Goncharov & Khusainov [31]. Furthermore, she proved a relativized version of the theorem, where the relativization is to structures. That is, she proved that if , then there is a structure such that .

Stukachev [15,21] then proved this theorem for the stronger notion of *Σ*-equivalence, as in the statement of the above-mentioned theorem, and for structures of arbitrary cardinality. Stukachev used the same structure that Soskova used, although the proof that it works for *Σ*-equivalence is completely different and more model theoretical.

#### (ii) The second jump inversion theorem

This second jump inversion theorem is not a generalization of the usual jump inversion theorem to a more general class of degrees, but a generalization in the sense that, given , it gives with *Y* ′≡_{T}*X* and some extra properties.

### Theorem 5.11

*If X computes a copy of* *then there is a set Y, with Y ′≡*_{T}*X, which computes a copy of* *. Equivalently, this says that
*

This theorem is proved by showing that any copy of can compute a one-generic copy of , and that, for such a copy, .

The equivalent formulation in the second sentence of the theorem can be viewed as a *correctness* statement: it reaffirms that our definition of the jump is an analogue of the usual definition of the Turing jump on sets of numbers.

### Corollary 5.12 (Montalbán [2], theorem 3.5)

*The following are equivalent*:

*has the**low property*:*if**X*′≡_{T}*Y*′*and**X**computes a copy of**then so does**Y*.*admits strong jump inversion*:*if**X*′*computes a copy of**then**X**computes a copy of*.

**Historic remark 5.13.** Theorem 5.11 was first introduced by Soskov at a talk during the LC'02 in Münster, Germany; a full proof then appeared in Soskova & Soskov [19]. That proof just shows the existence of a structure with ; this structure was only later called the jump of , and it is notion J2 (see above). Theorem 5.11 was first stated in print in Baleva [10], theorem 5, but the proof there is not complete (lemma 4 is not correct).

Another proof of the theorem then appeared independently in Montalbán [2]. Both proofs are essentially the same, although the great differences in the underlying setting make them look quite different.

#### (iii) The fixed point theorem

The third theorem says that the jump operation on structures does not always jump.

**Historic remark 5.15**. Puzarenko's and Montalbán's proofs were found independently . Montalbán uses the existence of 0^{♯}, and is a paragraph long, once the definition of 0^{♯} is understood. Puzarenko's proof works inside *ZFC*, but is much more complicated. Both proofs work by building an ill-founded *ω*-model of *V* =*L* where, for some ordinal *α* of the model, .

More surprising than the theorem itself is the complexity necessary for its proof.

### Theorem 5.16 (Montalbán [33])

*Higher order arithmetic cannot prove that there exists a structure* *with* *(i.e.* *. Higher order arithmetic refers to the union of nth-order arithmetic for all* *.*

One of the main steps to prove this theorem is to show that if , then the co-spectrum of (i.e. ) is the second-order part of an *ω*-model of full second-order arithmetic. Generalizing this to higher orders, the author proves that the *ω*-jump of any presentation of computes a countably coded *ω*-model of higher order arithmetic.

Puzarenko's proof of theorem 5.14 uses *KP* plus iterations of the power-set axiom. So there is still a gap as to what is actually needed to prove the fixed point theorem.

## 6. The structural jump

The present author's original definition of the jump of a structure [2], which is different from the one we give here, uses a complete set of *Π*^{c}_{1}-relations. Complete sets of *Π*^{c}_{1}-relations or, by taking complements, of rice relations provide the link between the formal definition of the jump of a relation and its applications on concrete natural structures.

### (a) Complete sets of rice relations

The author's original definition [2], definition 1.1 is given as part (2) of lemma 6.3. The following definition is equivalent.

### Definition 6.1

A sequence of relations ** R** is

*structurally rice complete*if it is rice and More generally,

**is**

*R**structurally*if it is

*Σ*^{c}_{n}(*Π*^{c}_{n}) complete*Σ*

^{c}

_{n}(

*Π*

^{c}

_{n}) and

In Montalbán [2], definition 1.1, instead of saying that ** R** is structurally rice complete, we said that

**is a complete set of rice relations. The new notation is more accurate, but, as an abuse of notation, we will still use the old notation sometimes. The word ‘structurally’ reflects that**

*R***is complete in the sense that it has all the structural information of , but it may need to borrow other information from**

*R***0**′ to be actually equivalent to . In addition, it is important that

**is a sequence and not just a set, because the -equivalence asks for uniform reductions between sequences.**

*R*

### Example 6.2

From examples 3.22 and 3.23, we get that ¬*Adj* alone and ** LD** are structurally rice complete for linear orderings and vector spaces, respectively. More examples are given in §7.

The following lemma shows how having a simple complete set of rice relations on a structure can be very useful: first because it gives a simple characterization of all the r.i. relations in , and second because it can be used to build copies of .

### Lemma 6.3

Let ** R** be a finite or infinite

*Σ*

^{c}

_{n}sequence of relations on . The following are equivalent:

is structurally*R**Σ*^{c}_{n}complete.Every

*Σ*^{c}_{n+1}formula about is equivalent to a 0^{(n)}-computable disjunction of finitary*Σ*_{1}formulae about and this equivalent disjunction can be found uniformly in*ψ*.If

*X*≥_{T}0^{(n)}computes a copy of then there exists*Y*with*Y*^{(n)}≡_{T}*X*that computes a copy of and, furthermore,*X*computes an isomorphism between and its copy.

### Sketch of the proof.

That (2) implies (1) follows from the fact that both and are *Σ*^{c}_{n+1} definable. To prove that (1) implies (2), one needs to use, first, that every *Σ*^{c}_{n+1} formula about is equivalent to a *Σ*^{c}_{1} formula about , and, second, that is both *Σ*^{c}_{1}- and *Π*^{c}_{1}-definable in , to get that every *Σ*^{c}_{n+1} formula is equivalent to a *Σ*^{c}_{1} formula about . Such a *Σ*^{c}_{1} formula is equivalent to a 0^{(n)}-computable disjunction of finitary *Σ*_{1} formulae about .

That (1) implies (3) follows from theorem 5.11 iterated *n* times.

Let us now assume that (3). To show that (1) holds, we need to show that, for every copy of , computes . Let *X* compute . By (3), there exists *Y* , with *Y* ^{(n)}≡_{T}*X*, which computes a copy of and *X* computes the isomorphism. Then, *X* computes , and, through the isomorphism, it computes . ■

The following particular case of the previous lemma was independently proved by Frolov.

### Corollary 6.4 (Frolov [34], theorem 6)

*If* *is a linear ordering and* *has a 0′-computable copy, then* *has a low copy*.

It is not always the case that there is a nice complete set of rice relations. Conditions for when this is the case, under a certain interpretation of ‘nice’, are given in Montalbán [1]. There, the author studies sequences of *Π*^{c}_{n} *formulae* that define complete sets of *Π*_{n} relations for all the structures inside a class , and that, furthermore, are complete relative to any oracle. It is proved in Montalbán [1] that such a set of formulae exists if and only if the number of *n*-back-and-forth types of tuples in structures in is countable, and some mild effectiveness conditions hold on these types.

### (b) The author's original definition of jump

The definition given in this paper is better than the one in Montalbán [2] in the sense that it matches the other definitions of jump. However, the definition from Montalbán [2] has the advantage that it is more practical, and aesthetic, when looking at particular examples of jumps.

### Definition 6.5

A *structural jump* of is a structure of the form where is structurally rice complete.

Notice that , as defined in definition 5.1, is a structural jump of , and that the only essential difference between and any other structural jump of is that codes the information sequence **0**′ while might not. This difference is not *structural*; it just involves information unrelated to the structure .

The following examples show how simple the structural jump of a structure can be. More examples are given in the next section.

### Example 6.6

If is a linear ordering, then is a structural jump of . If is a -vector space, is a structural jump of . If is a Boolean algebra, is a structural jump of , and is a structural double-jump of .

## 7. Finite complete sets of rice relations

In this section, we look at the following question: for which structures, and , is there a finite structurally *Σ*^{c}_{n} complete set of relations? We do not have a general answer for this question, but we have some interesting examples.

### (a) Linear orderings

As we have said a few times already, for linear orderings we have a finite complete set of rice relations, namely the singleton {¬*Adj*}, and a proof of this can be found in Montalbán [2]. Linear orderings also enjoy a nice structural double jump. The following is a complete set of *Π*^{c}_{2} relations for linear orderings with endpoints:

*Adj*(*x*,*y*).*limleft*(*x*); where*limleft*(*x*) holds if*x*is a limit from the left, that is, if ∃*y*<*x*& ∀*y*<*x*∃*z*(*y*<*z*<*x*).*limright*(*x*); where*limright*(*x*) holds if*x*is a limit from the right, that is, if ∃*y*>*x*& ∀*y*>*x*∃*z*(*x*<*z*<*y*).*D*_{n}(*x*,*y*) for*n*≥1; where*D*_{n}(*x*,*y*) holds if there is no string of*n*+1 adjacent elements somewhere between*x*and*y*, that is, if .

That these form a complete set of *Π*^{c}_{2} relations follows from the work of Frolov [34], theorem 7, who proved that part (3) of lemma 6.3 holds for these relations. In the case when the linear ordering has no endpoints, the situation is not much different; we just need to consider extra relations and , which are like *D*_{n}(⋅,⋅) but look at the end and initial segments, and , respectively.

This is a nice set of relations, but it is not finite.

### Theorem 7.1 (J. F. Knight, R. Miller, A. Montalbán, I. N. Soskov, A. Soskova, M. Soskova, S. VanDenDriessche & S. Vatev 2011, unpublished data)

*There is a finite complete set of Π*^{c}_{2} relations for linear orderings with endpoints. These relations are:

*Adj(x,y);**limleft(x);**limright(x); and**where Succ*^{n}*(z)=w is a shorthand for*.

The theorem also holds for linear orderings without endpoints, although one needs to consider a couple of added relations.

### Proof.

Let be a presentation of linear orderings with endpoints. We need to show that the relations *D*_{n} are uniformly computable in the relations above. Fix *n*. If *n*=1, then *D*_{1}(*x*,*y*)≡*P*(*x*,*y*,*x*,*x*). Suppose now that *n*>1, and consider *x*,*y*∈*A*. Suppose that, recursively, we know whether or not *D*_{n}(*x*,*y*) holds, and we want to check if *D*_{n+1}(*x*,*y*) holds. If *D*_{n}(*x*,*y*) holds, then we know that *D*_{n+1}(*x*,*y*) holds too. Suppose now that ¬*D*_{n}(*x*,*y*) holds. Then, we can search for *z*,*w* such that *Succ*^{n}(*z*)=*w* and we have that *P*(*x*,*y*,*z*,*w*)⇔*D*_{n+1}(*x*,*y*). ■

### (b) Boolean algebras

Harris & Montalbán [35] proved that, for all , there is a finite structurally *Π*^{c}_{n}-complete set of relations. They describe a recursive procedure to build these sets of relations, but the construction is too involved to give here. Up to Boolean combination, and for the cases *n*= 1–4, relations that are structurally *Π*^{c}_{n} complete for Boolean algebras were considered by Downey & Jockusch [36] for *n*=1, Thurber [37] for *n*=2, and Knight & Stob [38] for *n*=3,4. They did not mention their completeness, but they proved that (3) of lemma 6.3 holds. Moreover, they showed that Boolean algebras have the low_{4} property by showing that they admit strong fourth jump inversion (see corollary 5.12).

### (c) Vector spaces

As we mentioned before, ** LD** is structurally rice complete for -vector spaces. This is again a very nice sequence of relations that is not finite.

### Theorem 7.2 (J. F. Knight, R. Miller, A. Montalbán, I. N. Soskov, A. Soskova, M. Soskova, S. VanDenDriessche & S. Vatev 2011, unpublished data)

*Let* *be the infinite dimensional countable* *-vector space. There is no finite complete set of rice relations in* *.*

### Sketch of the proof.

The proof has two parts. First, we give a different, more hands on, proof that ** LD** is structurally rice complete. A proof that lets us observe that every rice relation is -reducible to 0′ and finitely many instances of

**. Let**

*LD**n*be the arity of

*R*and let . Then, using (

*LD*

_{2},…,

*LD*

_{n}) we can find out all the linear dependencies among the vectors

*v*

_{1},…,

*v*

_{n}. So we can find a linearly independent subset of

*v*

_{1},…,

*v*

_{n}which generates the rest, and then we can search for the equations witnessing these dependencies. Let us now assume that the

*v*

_{i}s are all linearly independent, as otherwise we can reduce the problem to a smaller set. By standard arguments using disjunctive normal forms, one can show that every finitary

*Σ*

_{1}formula about

*v*

_{1},…,

*v*

_{n}can be effectively decided by solving systems of linear equations and inequations, and hence 0′ can then decide infinitary

*Σ*

^{c}

_{1}formulae about

*v*

_{1},…,

*v*

_{n}in a uniform way.

Second, we show that no finite sequence (*LD*_{2},…,*LD*_{n−1}) can -compute the whole sequence ** LD**. We build a copy of where (

*LD*

_{2},…,

*LD*

_{n−1}) is computable, but

**is not. We will define a computable subspace**

*LD**W*of and then let be the quotient . Let

*b*

_{0},

*b*

_{1},… be the standard basis of . To make sure

*LD*

_{n}is not computable, we will let

*LD*

_{n}(

*b*

_{kn},…,

*b*

_{k(n+1)−1}) hold in if and only if

*k*∈0′. Given , let

*A*

_{s}be the set of all which are linear combinations of

*b*

_{0},…,

*b*

_{s}using coefficients among the first

*s*rational numbers. At stage

*s*of the construction, if we see that

*k*enters 0′ we enumerate a non-trivial linear combination of

*b*

_{kn},…,

*b*

_{k(n+1)−1}to

*W*without adding to

*W*any vector of

*A*

_{s}that was not in

*W*already, and without adding any new dependence between any set of vectors of

*A*

_{s}of size less than

*n*. Proving that this can be done requires a little linear algebra, and proving that

*W*and

*LD*

_{2},…,

*LD*

_{n−1}end up being computable is a rather standard argument (for a fully spelled out argument of a similar kind, see Downey

*et al*. [39]).

Relativizing this proof to 0′, we get a 0′-computable copy of , where (*LD*_{2},…,*LD*_{n−1})⊕**0**′ is 0′-computable, but ** LD** computes 0

^{′′}. Thus

**is not r.i. computable in (**

*LD**LD*

_{2},…,

*LD*

_{n−1})⊕

**0**′.

Finally, if *R*_{1},…,*R*_{m} were structurally rice complete, then by the first part of the argument we would have that finitely many of the *LD*_{i} would also be rice complete, but the second part shows that this is not the case. ■

### (d) Equivalence structures

An *equivalence structure* is a structure with a binary relation *E* which is an equivalence relation. For equivalence structures, the following is a complete set of rice relations:

*F*_{k}(*x*) for , where*F*_{k}(*x*) holds if there are ≥*k*elements equivalent to*x*, andthe information sequence

(called the*G**character*of*E*), where there are ≥*n*equivalence classes with ≥*k*elements}.

Fix an equivalence structure , and a rice relation *R* of arity *n*. We will show how we can uniformly compute using , and 0′. Let . Using (*F*_{2},…,*F*_{n}), find which of the *v*_{i}s are equivalent to which. Let us assume that they are all non-equivalent, as otherwise we can reduce the problem to a maximal subset of non-equivalent *v*_{i}s. Given , let . A standard argument shows that every finitary *Σ*_{1} formula about *v*_{1},…,*v*_{n} is equivalent to a disjunction of formulae of the form in conjunction with some formulae of the form ‘(*m*,*k*)∈*G*’. So, using *G*, we can effectively transform every *Σ*^{c}_{1} formula into a disjunction of formulae for in some computable set . Define the following ordering on : if for all *i*=1,…,*n*, *k*_{i}≤*l*_{i}. Note that if , then . It is not hard to show (by induction on *n*) that is a well-quasi ordering, that is, for every sequence , there is *i*<*j* with . Well-quasi orderings have the property that for every set of there is a finite subset *C*_{0}⊆*C* such that every element of *C* is -above some element of *C*_{0}. It follows that . Let us note that 0′ is necessary to find *C*_{0} from *C*. So, we have shown that every *Σ*^{c}_{1} formula can be re-written, with the help of 0′ and *G*, as a finite disjunction of the form .

### Theorem 7.3 (J. F. Knight, R. Miller, A. Montalbán, I. N. Soskov, A. Soskova, M. Soskova, S. VanDenDriessche & S. Vatev 2011, unpublished data)

*Let* *be an equivalence structure that has one equivalence class of each finite size. There is no finite complete set of rice relations in* *.*

### Sketch of the proof.

First, observe that every rice relation is -reducible to 0′ and finitely many instances of ** F**, noting that

*G*is computable in this case.

Second, we show that no finite sequence (*F*_{2},…,*F*_{n−1}) can -compute the whole sequence ** F**. We build a copy of where (

*F*

_{2},…,

*F*

_{n−1}) are computable, but

**is not. Suppose**

*F**n*is even; if not take

*n*+1 as

*n*. Start by building a structure with equivalence classes of all even sizes and all sizes less than

*n*; we will build the odd size classes beyond

*n*by stages. Let

*b*

_{k}be a fixed element in a class of size 2

*k*+

*n*. If

*k*enters 0′, we will make

*b*

_{k}'s equivalence class bigger, so asking whether

*F*

_{2k+n+1}(

*b*

_{k}) holds will tell us if

*k*∈0′. At each stage, build one new odd size equivalence class. If

*k*enters 0′ add elements to

*b*

_{k}'s equivalence class to make it have some large odd size not considered yet, and also make a new equivalence class of size 2

*k*+

*n*. Notice that the value of

*F*

_{i}for

*i*<

*n*is never changed during the construction, and hence these relations are all computable.

Relativize this proof to 0′ to obtain a 0′-computable copy of where (*F*_{2},…,*F*_{n−1})⊕**0**′ is 0′-computable but ** F** computes 0

^{′′}.

Finally, if there was a finite complete set of rice relations, we would get that a finite set of the *F*_{k}s would also make a complete set, but we just proved that this cannot be the case. ■

## Acknowledgements

The author was partially supported by NSF grant no. DMS-0901169 and the Packard Fellowship. The author thanks Asher Kach for helpful comments throughout the paper.

## Footnotes

One contribution of 18 to a Theme Issue ‘The foundations of computation, physics and mentality: the Turing legacy’.

- This journal is © 2012 The Royal Society