Recursive structures
Content coded into the structures
Degree spectra

Primitive recursive degree spectra of structures

Kalimullin I.Sh.
Kazan Federal University
e-mail:ikalimul@gmail.com

Computability in Europe
Batumi, July 25, 2023

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Computable structures

I A structure A is computable if the domain |A| ⊆ N iscomputable and all relations and operations from A are
computable.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Computable structures

I A structure A is computable if the domain |A| ⊆ N iscomputable and all relations and operations from A are
computable.

I A computable presentation of a countable structure A is
any computable isomorphic copy of A.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Computable structures

I A structure A is computable if the domain |A| ⊆ N iscomputable and all relations and operations from A are
computable.

I A computable presentation of a countable structure A is
any computable isomorphic copy of A.
I (N, +1, P) has a computable copy i P is computable.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Computable structures

I A structure A is computable if the domain |A| ⊆ N iscomputable and all relations and operations from A are
computable.

I A computable presentation of a countable structure A is
any computable isomorphic copy of A.
I (N, +1, P) has a computable copy i P is computable.
I All operations can be equivalently transformed into
ralations, e.g., +1 can be replaced by the successor relation.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Primitive recursive structures

I A structure A is primitive recursive if the domain |A| isprimitive recursive and all relations and operations in A are
primitive recursive.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Primitive recursive structures

I A structure A is primitive recursive if the domain |A| isprimitive recursive and all relations and operations in A are
primitive recursive.

I A primitive recursive presentation of a countable structure
A is any primitive recursive isomorphic copy of A.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Primitive recursive structures

I A structure A is primitive recursive if the domain |A| isprimitive recursive and all relations and operations in A are
primitive recursive.

I A primitive recursive presentation of a countable structure
A is any primitive recursive isomorphic copy of A.
I (from Kleene's Normal Form). Every computable structure
in a relational language has a primitive recursive
presentation.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Primitive recursive structures

I A structure A is primitive recursive if the domain |A| isprimitive recursive and all relations and operations in A are
primitive recursive.

I A primitive recursive presentation of a countable structure
A is any primitive recursive isomorphic copy of A.
I (from Kleene's Normal Form). Every computable structure
in a relational language has a primitive recursive
presentation.

I (Alaev, 2016). Every computable locally nite structure ina relational language has a primitive recursive presentation.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Primitive recursive structures

I A structure A is primitive recursive if the domain |A| isprimitive recursive and all relations and operations in A are
primitive recursive.

I A primitive recursive presentation of a countable structure
A is any primitive recursive isomorphic copy of A.
I (from Kleene's Normal Form). Every computable structure
in a relational language has a primitive recursive
presentation.

I (Alaev, 2016). Every computable locally nite structure ina relational language has a primitive recursive presentation.

I (N, +1, P) has a primitive recursive presentation i P isprimitive recursive.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Punctual structures

I A structure A is punctual if A is nite or |A| = N and all
relations and operations in A are primitive recursive.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Punctual structures

I A structure A is punctual if A is nite or |A| = N and all
relations and operations in A are primitive recursive.
I A punctual presentation of a countable structure A is any
punctual isomorphic copy of A.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Punctual structures

I A structure A is punctual if A is nite or |A| = N and all
relations and operations in A are primitive recursive.
I A punctual presentation of a countable structure A is any
punctual isomorphic copy of A.
I Every primitive recursive structure which is not locallynite has a punctual recursive presentation.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Punctual structures

I A structure A is punctual if A is nite or |A| = N and all
relations and operations in A are primitive recursive.
I A punctual presentation of a countable structure A is any
punctual isomorphic copy of A.
I Every primitive recursive structure which is not locallynite has a punctual recursive presentation.

I (KMN, 2017). There is a computable graph without apunctual presentation

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Punctual structures

I A structure A is punctual if A is nite or |A| = N and all
relations and operations in A are primitive recursive.
I A punctual presentation of a countable structure A is any
punctual isomorphic copy of A.
I Every primitive recursive structure which is not locallynite has a punctual recursive presentation.

I (KMN, 2017). There is a computable graph without apunctual presentation, while it has a primitive recursiveone.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Punctual structures

I A structure A is punctual if A is nite or |A| = N and all
relations and operations in A are primitive recursive.
I A punctual presentation of a countable structure A is any
punctual isomorphic copy of A.
I Every primitive recursive structure which is not locallynite has a punctual recursive presentation.

I (KMN, 2017). There is a computable graph without apunctual presentation, while it has a primitive recursiveone.

I (N, +1, P) has a punctual presentation i P is primitive
recursive.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Sets coded into the structures
Let P is arbitrary, and X is a Turing oracle.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Sets coded into the structures
Let P is arbitrary, and X is a Turing oracle.

I (N, +1, P) has an X -computable copy i P ≤T X .

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Sets coded into the structures
Let P is arbitrary, and X is a Turing oracle.

I (N, +1, P) has an X -computable copy i P ≤T X .
I The same is true if we replace +1 by the successor relation.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Sets coded into the structures
Let P is arbitrary, and X is a Turing oracle.

I (N, +1, P) has an X -computable copy i P ≤T X .
I The same is true if we replace +1 by the successor relation.
I (Ash, Knight, 2000). Suppose
A has an X -computable copy =⇒ P ≤T X
for every X .

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Sets coded into the structures
Let P is arbitrary, and X is a Turing oracle.

I (N, +1, P) has an X -computable copy i P ≤T X .
I The same is true if we replace +1 by the successor relation.
I (Ash, Knight, 2000). Suppose
A has an X -computable copy =⇒ P ≤T X
for every X . Then for some xed parameters ~a ∈ A there
are computable mappings into quantier-free formulaen 7→ Φn and n 7→ Ψn such thatn ∈ P ⇐⇒ A |= (∃~x )Φn (~x , ~a);n∈
/ P ⇐⇒ A |= (∃~x )Ψn (~x , ~a).
Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -reducibilityn
I We write g ≤PR f if g can be obtained from o(x), s(x), Im
and f by composition and primitive recursion.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -reducibilityn
I We write g ≤PR f if g can be obtained from o(x), s(x), Im
and f by composition and primitive recursion. We writef ≡PR g if f ≤PR g and g ≤PR f .

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -reducibilityn
I We write g ≤PR f if g can be obtained from o(x), s(x), Im
and f by composition and primitive recursion. We writef ≡PR g if f ≤PR g and g ≤PR f .
I In general, f 6≡PR graph(f ).

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -reducibilityn
I We write g ≤PR f if g can be obtained from o(x), s(x), Im
and f by composition and primitive recursion. We writef ≡PR g if f ≤PR g and g ≤PR f .
I In general, f 6≡PR graph(f ). But if f ≤PR X for a set X thenf is dominated by a primitive recursive function, so thatf ≡PR graph(f ).

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -reducibilityn
I We write g ≤PR f if g can be obtained from o(x), s(x), Im
and f by composition and primitive recursion. We writef ≡PR g if f ≤PR g and g ≤PR f .
I In general, f 6≡PR graph(f ). But if f ≤PR X for a set X thenf is dominated by a primitive recursive function, so thatf ≡PR graph(f ). Thus, the sets form a proper ideal in the
PR -degrees of functions.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -reducibilityn
I We write g ≤PR f if g can be obtained from o(x), s(x), Im
and f by composition and primitive recursion. We writef ≡PR g if f ≤PR g and g ≤PR f .
I In general, f 6≡PR graph(f ). But if f ≤PR X for a set X thenf is dominated by a primitive recursive function, so thatf ≡PR graph(f ). Thus, the sets form a proper ideal in the
PR -degrees of functions.
I A structure A is f -punctual if A is nite or |A| = N and all
relations and operations in A are ≤PR f .

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -reducibilityn
I We write g ≤PR f if g can be obtained from o(x), s(x), Im
and f by composition and primitive recursion. We writef ≡PR g if f ≤PR g and g ≤PR f .
I In general, f 6≡PR graph(f ). But if f ≤PR X for a set X thenf is dominated by a primitive recursive function, so thatf ≡PR graph(f ). Thus, the sets form a proper ideal in the
PR -degrees of functions.
I A structure A is f -punctual if A is nite or |A| = N and all
relations and operations in A are ≤PR f . An f -punctual
presentation of a countable structure A is any f -punctual
isomorphic copy of A.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectraSets

PR -coded into the structures

Let P is arbitrary, and f is a PR -oracle.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectraSets

PR -coded into the structures

Let P is arbitrary, and f is a PR -oracle.

I (N, +1, P) has an f -punctual copy i P ≤PR f .

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectraSets

PR -coded into the structures

Let P is arbitrary, and f is a PR -oracle.

I (N, +1, P) has an f -punctual copy i P ≤PR f .
I The same is true if we consider the locally nite structure(N, ◦, P), where x ◦ y = max(x + 1, y ).

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectraSets

PR -coded into the structures

Let P is arbitrary, and f is a PR -oracle.

I (N, +1, P) has an f -punctual copy i P ≤PR f .
I The same is true if we consider the locally nite structure(N, ◦, P), where x ◦ y = max(x + 1, y ).
I (KMM, 2021). Suppose
A has an f -punctual copy =⇒ P ≤PR f
for every f . Then for some xed parameters ~a ∈ A there areprimitive recursive mappings into quantier-free formulaen 7→ Φn and n 7→ Ψn such that for every tuple ~x ofpairwisely distinct elementsn ∈ P ⇐⇒ A |= Φn (~x , ~a);n∈
/ P ⇐⇒ A |= Ψn (~x , ~a).
Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Questions arised

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Questions arised

1. Are there examples among relational structures?

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Questions arised

1. Are there examples among relational structures?
2. Can we code arbitrary functions, not only the sets?

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Question 1

I Are there examples among relational structures?

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Question 1

I Are there examples among relational structures?
I No.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Question 1

I Are there examples among relational structures?
I No.
I Because Ramsey's Theorem says that every innite
relational structure contains an innite substructure
isomorphic to a quantier-free interpretation in (N, <)Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Question 1

I Are there examples among relational structures?
I No.
I Because Ramsey's Theorem says that every innite
relational structure contains an innite substructure
isomorphic to a quantier-free interpretation in (N, <)(which is obviously primitive recursive).

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Question 2

I Can we code arbitrary functions, not only the sets?

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Question 2

I Can we code arbitrary functions, not only the sets?
I No.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Question 2

I Can we code arbitrary functions, not only the sets?
I No.
I Because every f -punctual structure can be isomorphicallytransformed into an f -punctual structure whose operations
are primitively recursively bounded

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Question 2

I Can we code arbitrary functions, not only the sets?
I No.
I Because every f -punctual structure can be isomorphicallytransformed into an f -punctual structure whose operations
are primitively recursively bounded , i.e., there is a set

X ≤PR f such that the structure has an X -punctual
presentation.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Turing degree spectra

I The Turing degree spectrum SpT (A) is the collection of allsets X such that A has an X -computable presentation.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Turing degree spectra

I The Turing degree spectrum SpT (A) is the collection of allsets X such that A has an X -computable presentation.
I SpT (N, +1, P) = {X : P ≤T X }.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Turing degree spectra

I The Turing degree spectrum SpT (A) is the collection of allsets X such that A has an X -computable presentation.
I SpT (N, +1, P) = {X : P ≤T X }.
I (Folklore). If P |T Q then the collection{X : P ≤T X } ∪ {X : Q ≤T X } is not a Turing degree
spectrum.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Spectra of Slaman-Wehner typeI (Slaman, Wehner, 1998). The collection {X : X 6≤T ∅} is theTuring degree spectrum of a structure.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Spectra of Slaman-Wehner typeI (Slaman, Wehner, 1998). The collection {X : X 6≤T ∅} is theTuring degree spectrum of a structure.

I (K, 2008). If A is c.e. then the collection {X : X 6≤T A} isthe Turing degree spectrum of a structure.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Spectra of Slaman-Wehner typeI (Slaman, Wehner, 1998). The collection {X : X 6≤T ∅} is theTuring degree spectrum of a structure.

I (K, 2008). If A is c.e. then the collection {X : X 6≤T A} isthe Turing degree spectrum of a structure. Unions ofnitely many such collections again form degree spectra.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Spectra of Slaman-Wehner typeI (Slaman, Wehner, 1998). The collection {X : X 6≤T ∅} is theTuring degree spectrum of a structure.

I (K, 2008). If A is c.e. then the collection {X : X 6≤T A} isthe Turing degree spectrum of a structure. Unions ofnitely many such collections again form degree spectra.

I (AKKLMM, 2016). The collection {X : X 6≤T ∅00 } is not a
Turing degree spectra.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

The idea of the Wehner's proof

I We can code into a structure the family of nite sets
W = {{n} ⊕ F : F 6= ϕn },where ϕn is the n-th partially computable function.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

The idea of the Wehner's proof

I We can code into a structure the family of nite sets
W = {{n} ⊕ F : F 6= ϕn },where ϕn is the n-th partially computable function.

I The family W has an X -computable enumeration if andonly if X 6≤T ∅.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

The idea of the Wehner's proof

I We can code into a structure the family of nite sets
W = {{n} ⊕ F : F 6= ϕn },where ϕn is the n-th partially computable function.

I The family W has an X -computable enumeration if andonly if X 6≤T ∅.
I Indeed, W has no computable enumeration by Recursion
Theorem.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

The idea of the Wehner's proof

I We can code into a structure the family of nite sets
W = {{n} ⊕ F : F 6= ϕn },where ϕn is the n-th partially computable function.

I The family W has an X -computable enumeration if andonly if X 6≤T ∅.
I Indeed, W has no computable enumeration by Recursion
Theorem. If X 6≤T ∅ we can use X as a sample to extend
every unsucessfull guess F 6= ϕn .

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

The idea of the Wehner's proof

I We can code into a structure the family of nite sets
W = {{n} ⊕ F : F 6= ϕn },where ϕn is the n-th partially computable function.

I The family W has an X -computable enumeration if andonly if X 6≤T ∅.
I Indeed, W has no computable enumeration by Recursion
Theorem. If X 6≤T ∅ we can use X as a sample to extend
every unsucessfull guess F 6= ϕn .
I Some modication of the family gives the degree spectrumof the hyperimmune degrees (CK, 2010).

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -degree spectra

I The PR -degree spectrum SpPR (A) is the collection of all
functions f such that A has an f -punctual presentation.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -degree spectra

I The PR -degree spectrum SpPR (A) is the collection of all
functions f such that A has an f -punctual presentation.
I SpPR (N, +1, P) = {f : P ≤PR f }.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -degree spectra

I The PR -degree spectrum SpPR (A) is the collection of all
functions f such that A has an f -punctual presentation.
I SpPR (N, +1, P) = {f : P ≤PR f }.
I (Folklore). If P |PR Q then the collection{f : P ≤PR f } ∪ {f : Q ≤PR f } is not a PR -degree spectrum.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -degree spectra

I The PR -degree spectrum SpPR (A) is the collection of all
functions f such that A has an f -punctual presentation.
I SpPR (N, +1, P) = {f : P ≤PR f }.
I (Folklore). If P |PR Q then the collection{f : P ≤PR f } ∪ {f : Q ≤PR f } is not a PR -degree spectrum.
I (Set Basis Property). If f ∈ SpPR (A) then X ∈ SpPR (A) forsome X ≤PR f .

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Set Basis Property for{f : f 6≤PR ∅}I (Kristiansen, 1996). If f 6≤PR ∅ then X 6≤PR ∅ for someX ≤PR f .

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Set Basis Property for{f : f 6≤PR ∅}I (Kristiansen, 1996). If f 6≤PR ∅ then X 6≤PR ∅ for someX ≤PR f .
I Indeed, if graph(f ) 6≤PR ∅ we are done.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Set Basis Property for{f : f 6≤PR ∅}I (Kristiansen, 1996). If f 6≤PR ∅ then X 6≤PR ∅ for someX ≤PR f .
I Indeed, if graph(f ) 6≤PR ∅ we are done. If graph(f ) ≤PR ∅then f is not dominated by primitive recursive functions, sothat we can use a hyperimmune-permitting-like argument.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Set Basis Property for{f : f 6≤PR ∅}I (Kristiansen, 1996). If f 6≤PR ∅ then X 6≤PR ∅ for someX ≤PR f .
I Indeed, if graph(f ) 6≤PR ∅ we are done. If graph(f ) ≤PR ∅then f is not dominated by primitive recursive functions, sothat we can use a hyperimmune-permitting-like argument.

I Note that the proof can be made uniform.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Punctual families

I A countable family F ⊆ 2N is punctual if there is a{0, 1}-valued primitive recursive function p such thatX ∈ F ⇐⇒ (∃i)(∀x)[x ∈ X ↔ phi, xi = 1]
for all X .

I For a function f a countable family F ⊆ 2N is f -punctual if
there is a {0, 1}-valued function p ≤PR f such thatX ∈ F ⇐⇒ (∃i)(∀x)[x ∈ X ↔ phi, xi = 1]
for all X .

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Coding families

I For a countable family F ⊆ 2N dene the algebraic
structure A(F) in the language {r , s, I} on the domain
F × N × N such that the unary operations r and s aredened byr (X , x, y) = (X , 0, y);s(X , x, y) = (X , x + 1, y );and the unary predicate I is dened by

I(X , x, y) ↔ x ∈ X .
I A countable family F ⊆ 2N is f -punctual if and only if
f ∈ SpPR (A(F)).
Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

An analogue of the Wehner's family

I Let pn is the n-th primive recursive function.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

An analogue of the Wehner's family

I Let pn is the n-th primive recursive function. Then thefamily of nite sets

V = {{n} ⊕ F : F 6= pn }Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

An analogue of the Wehner's family

I Let pn is the n-th primive recursive function. Then thefamily of nite sets

V = {{n} ⊕ F : F 6= pn }is punctual.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

An analogue of the Wehner's family

I Let pn is the n-th primive recursive function. Then thefamily of nite sets

V = {{n} ⊕ F : F 6= pn }is punctual.

I Just because we can start to enumerate the sets {n} ⊕ Fwith F (i) 6= pn (i) after the value pn (i) become computed.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

The correct analogue of the Wehner's family

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

The correct analogue of the Wehner's family

I The family of nite sets
V = {{n} ⊕ F : F 6= pϕn (n) }Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

The correct analogue of the Wehner's family

I The family of nite sets
V = {{n} ⊕ F : F 6= pϕn (n) }is f -punctual if and only if f 6≤PR ∅.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

The correct analogue of the Wehner's family

I The family of nite sets
V = {{n} ⊕ F : F 6= pϕn (n) }is f -punctual if and only if f 6≤PR ∅.

I Indeed, if V is punctual then for every n we cancomputably nd an s(n) such that ps(n) 6= pϕn (n) . But thens(n) 6= ϕn (n). A contradiction.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

The correct analogue of the Wehner's family

I The family of nite sets
V = {{n} ⊕ F : F 6= pϕn (n) }is f -punctual if and only if f 6≤PR ∅.

I Indeed, if V is punctual then for every n we cancomputably nd an s(n) such that ps(n) 6= pϕn (n) . But thens(n) 6= ϕn (n). A contradiction.
I If X 6≤PR ∅ we can use X as a sample to extend every
unsucessfull guess F 6= pϕn (n) .

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

The correct analogue of the Wehner's family

I The family of nite sets
V = {{n} ⊕ F : F 6= pϕn (n) }is f -punctual if and only if f 6≤PR ∅.

I Indeed, if V is punctual then for every n we cancomputably nd an s(n) such that ps(n) 6= pϕn (n) . But thens(n) 6= ϕn (n). A contradiction.
I If X 6≤PR ∅ we can use X as a sample to extend every
unsucessfull guess F 6= pϕn (n) .
I Now it is enough to apply Set Basis Property for{f : f 6≤PR ∅}.
Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -Spectra of Slaman-Wehner type

I The collection {f : f 6≤PR ∅} is the PR -degree spectra of astructure.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -Spectra of Slaman-Wehner type

I The collection {f : f 6≤PR ∅} is the PR -degree spectra of astructure.

I If graph(g) is primitive recursive then the collection{f : f 6≤PR g} is also a PR -degree spectra.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -Spectra of Slaman-Wehner type

I The collection {f : f 6≤PR ∅} is the PR -degree spectra of astructure.

I If graph(g) is primitive recursive then the collection{f : f 6≤PR g} is also a PR -degree spectra.
I Let h be the Ackerman's function,

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -Spectra of Slaman-Wehner type

I The collection {f : f 6≤PR ∅} is the PR -degree spectra of astructure.

I If graph(g) is primitive recursive then the collection{f : f 6≤PR g} is also a PR -degree spectra.
I Let h be the Ackerman's function, Pnh be the n-th set≤PR h,

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -Spectra of Slaman-Wehner type

I The collection {f : f 6≤PR ∅} is the PR -degree spectra of astructure.

I If graph(g) is primitive recursive then the collection{f : f 6≤PR g} is also a PR -degree spectra.
I Let h be the Ackerman's function, Pnh be the n-th set≤PR h, P h = ⊕n Pnh .

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -Spectra of Slaman-Wehner type

I The collection {f : f 6≤PR ∅} is the PR -degree spectra of astructure.

I If graph(g) is primitive recursive then the collection{f : f 6≤PR g} is also a PR -degree spectra.
I Let h be the Ackerman's function, Pnh be the n-th set≤PR h, P h = ⊕n Pnh . Then the collection {f : f 6≤PR P h } has
no Set Basis Property

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

PR -Spectra of Slaman-Wehner type

I The collection {f : f 6≤PR ∅} is the PR -degree spectra of astructure.

I If graph(g) is primitive recursive then the collection{f : f 6≤PR g} is also a PR -degree spectra.
I Let h be the Ackerman's function, Pnh be the n-th set≤PR h, P h = ⊕n Pnh . Then the collection {f : f 6≤PR P h } has
no Set Basis Property, and so is not a PR -degree spectra.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Open questions

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Open questions

I For which g the collection {f : f 6≤PR g} is a PR -degree
spectra?

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Open questions

I For which g the collection {f : f 6≤PR g} is a PR -degree
spectra? E.g, the collection {f : f 6≤PR P}, where P = ⊕n Pn .

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Open questions

I For which g the collection {f : f 6≤PR g} is a PR -degree
spectra? E.g, the collection {f : f 6≤PR P}, where P = ⊕n Pn .
I If graph(g) is primitive recursive then the collection{f : f 6≤PR g} is also a PR -degree spectra.

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Open questions

I For which g the collection {f : f 6≤PR g} is a PR -degree
spectra? E.g, the collection {f : f 6≤PR P}, where P = ⊕n Pn .
I If graph(g) is primitive recursive then the collection{f : f 6≤PR g} is also a PR -degree spectra.
I The T -degree spectra are closed under jumps andjump-inversions, so we have collections of the high degrees{X : ∅00 ≤T X 0 } and of the non-low degrees {X : X 0 6≤T ∅0 }.
Are there PR -analogues of these?

Kalimullin I.Sh.

Primitive recursive degree spectra of structures

Recursive structures
Content coded into the structures
Degree spectra

Thank you!

Kalimullin I.Sh.

Primitive recursive degree spectra of structures