Direct Constructionof Scott Ideals
Russell Miller
Queens College & CUNY Graduate Center

Computability in Europe
25 July 2023
Batumi Shota Rustaveli State UniversityBatumi, Georgia

Russell Miller (CUNY)

Direct Construction of Scott Ideals

CiE 2023

1 / 13

Scott ideals
Definition
In the upper semi-lattice D of Turing degrees under Turing reducibility≤, a Turing ideal T is a set closed under join and downwards under ≤.
Examples: the principal Turing ideals Tb = {d ∈ D : d ≤ b}.
A degree d is PA relative to c if every infinite c-computable subtree of2<ω has a d-computable (infinite) path. (The PA-degrees relative to 0
are precisely the degrees of complete extensions of Peano Arithmetic.)
Definition
A Turing ideal T is a Scott ideal if, for every c ∈ T , T also contains adegree d that is PA relative to c.
No principal Turing ideal is a Scott ideal, but by closing under thePA-requirement, one can readily extend a principal Turing ideal to acountable Scott ideal – if you have a reason to want to do so.
Russell Miller (CUNY)

Direct Construction of Scott Ideals

CiE 2023

2 / 13

Why Scott ideals?
My current project involves computability on Aut(Q), the absolute
Galois group of Q. We view automorphisms of (a computable copy of)
the algebraic closure Q as paths through a computable tree TQ :
√4
√
√

6 7→

3 7→

√4..
.

√
−466

√
i 46..
.

√
4−i 6..
. √√44
i 6 −i 6HH
H

@@
√3PPP
P

2 7→

1 7→@@
√

√
− 3P
√


√
46

√
−46@
@√

− 33PPPP√−22``..
.

P``````

1Given paths f and g, one can uniformly compute g ◦ f and f −1 using
Turing functionals. So this is a very nice tree presentation of Aut(Q).
Russell Miller (CUNY)

Direct Construction of Scott Ideals

CiE 2023

3 / 13

Computable automorphisms of Q
The subgroup Aut0 (Q) of all computable automorphisms is dense inAut(Q), and seems like a fairly good “effectively profinite” version ofAut(Q). But is it an elementary subgroup of Aut(Q)?
Specifically for Σ1 formulas: if f ∈ Aut0 (Q) andAut(Q) |= (∃G) G ◦ G = f ,must Aut0 (Q) contain some g with g ◦ g = f ?
To try to find such a g, one considers the subtree T of all nodesγ ∈ Aut(F ) such that γ ◦ γ = f↾ F , for finite Galois extensions F /Q.
The paths through this subtree T are precisely the solutions g.
(This is the topic of ongoing work. Kundu and I have shown that there
is no Φ such that, whenever f ∈ Aut0 (Q) is a square, Φf is such a g.)

Russell Miller (CUNY)

Direct Construction of Scott Ideals

CiE 2023

4 / 13

Subgroups defined by Scott ideals
It remains open to what extent Aut0 (Q) is elementary within Aut(Q).
However, using Scott ideals, we can prove some positive results.
Definition
For each Scott ideal I in the Turing degrees, set
AutI (Q) = {f ∈ Aut(Q) : deg(f ) ∈ I}.
Theorem (M., submitted)
Every AutI (Q) as defined above is elementary within Aut(Q) for all
positive sentences, all existential and universal sentences, and for alarger class known as the Σ2 -separated sentences.
This theorem could yet extend to more complex sentences; again, thisis current work. But it appears that Scott-ideal subgroups AutI (Q) arecloser to elementary in Aut(Q) than ordinary principal-ideal subgroups
Autd (Q) are.
Russell Miller (CUNY)

Direct Construction of Scott Ideals

CiE 2023

5 / 13

Superapproximations
Since AutI (Q) is apparently a nicer subgroup of Aut(Q) than Auta (Q)is, we consider how, given an arbitrary set A of arbitrary degree a, toconstruct a (countable) Scott ideal containing a. The scheme is to finda set A1 of degree a1 that
S is PA relative to a0 = a, then continue witha2 , a3 , . . . and set IA = n Tan . But clearly each an+1 > an , so wecannot just compute these from A.
Definition
A superapproximation h of a set B is a total function h : ω 2 → 2 suchthat, for all e,lim h(e, s) = χB ′ (e).
s

B is A-superapproximable if A computes such an h.
If A superapproximates B, then B ′ is the limit of the A-computable h,and so B ′ ≤T A′ . Thus an A-superapproximation is a construction ofsome B that is low relative to A, though not necessarily ≤T A.
Russell Miller (CUNY)

Direct Construction of Scott Ideals

CiE 2023

6 / 13

Uniform Low Basis Thm. (Brattka-de Brecht-Pauly)
Theorem (B-deB-P, strengthening Jockusch & Soare)
There is a Turing functional Ψ such that, for every oracle set S ⊆ ω andevery e such that ΦSe decides an infinite subtree T of TQ , ΨS (e, x, s) isa total function of x and s and there exists a path P through T for whichlim ΨS (e, x, s) = χP ′ (x).

s→∞Thus ΨS superapproximates this path P, uniformly in S.
T may be chosen, uniformly in S, to be a tree all of whose paths have
PA-degree relative to S. Thus we have a uniform way ofsuperapproximating a set of PA-degree relative to (an arbitrary) S.

Russell Miller (CUNY)

Direct Construction of Scott Ideals

CiE 2023

7 / 13

Building the Scott ideal
Now, given A0 = A, we may uniformly construct an ascending
sequence
A0 <T A1 <T A2 <T · · ·with each An+1 of PA-degree over An , but with· · · ≤T A′2 ≤T A′1 ≤T A′0 = A′ .
Indeed these latter reductions may be given uniformly, by the Uniform
Low Basis Theorem. So the Turing ideal[IA =Tann

is a Scott ideal containing a = deg(A), in which every degree
an = deg(An ) is low relative to a in a uniform way.

Russell Miller (CUNY)

Direct Construction of Scott Ideals

CiE 2023

8 / 13

Describing the Scott ideal IA
Spector showed that every ascending sequence a0 < a1 < · · · ofTuring degrees has an exact pair: a pair of degrees b and c for which{d : (∃n) d ≤ an } = {d : d ≤ b & b ≤ c}.
bc

A A A  AA.
A .. AA a2 AA | AA
AAa1 AAAA|AAa0 IAAAAA

So IA = Tb ∩ Tc is a semiprincipal Turing ideal.
Russell Miller (CUNY)

Direct Construction of Scott Ideals

CiE 2023

9 / 13

A uniform exact pair
Theorem (M., following Spector; see LNCS proceedings)
There is a uniform procedure that, for every set A ⊆ ω, computes
superapproximations of two sets BA and CA such that{d : d ≤ b & d ≤ c} is a Scott ideal containing deg(A).
The procedure uses the Uniform Low Basis Theorem as above tocompute approximations to A′0 , then to A′1 , then A′2 , and so on for all
A′n , uniformly in A and n. From these A-computable approximations, itthen applies Spector’s method (as described and slightly updated in
Soare’s text) to compute approximations of the sets BA and CA
described by Spector. Spector had already noted that BA and CA lie
below (⊕n An )′ ; we add the superapproximability of their join here,making (BA ⊕ CA )′ ≤T A′ uniformly in A.

Russell Miller (CUNY)

Direct Construction of Scott Ideals

CiE 2023

10 / 13

A direct limit
Aut(Q) is traditionally regarded as a profinite group, the inverse limit offinite Galois groups over increasing number fields, and this is theapproach used to build its presentation here. But with computability, it
may also be viewed as a direct limit[Autd (Q)
Aut(Q) =d∈Dof countable subgroups. The directed system on these groups issimply inclusion, which corresponds to Turing reducibility:
Autc (Q) ⊆ Autd (Q) ⇐⇒ c ≤ d.

Russell Miller (CUNY)

Direct Construction of Scott Ideals

CiE 2023

11 / 13

Another direct limit
Since AutIa (Q) is likely a more elementary subgroup of Aut(Q) thanAuta (Q) is, one naturally also considers the direct limit of thesesubgroups:[AutIA (Q).
Aut(Q) =A⊆ω

The fact that these subgroups are uniformly superapproximated makes
this idea seem more feasible. But there’s a catch: what is the directed
system here? Of course we want to use inclusion maps. But when
does AutIA (Q) ⊆ AutIB (Q)?
Question
Assume that A ≤T B. Does it follow for our uniformly
superapproximated Scott ideals that IA ⊆ IB ?

Russell Miller (CUNY)

Direct Construction of Scott Ideals

CiE 2023

12 / 13

Monotonicity and the Uniform Low Basis Theorem
Definition
A function F : 2ω → 2ω is monotonic if, for all A and B,
A ≤T B =⇒ F (A) ≤T F (B)[ ⇐⇒ ((F (A))′ ≤1 (F (B))′ ].

We would have a positive answer above if the ULBT is monotonic.
Question
Does there exist a monotonic, uniformly superapproximable function
F : 2ω → 2ω such that, for every A, F (A) has PA-degree relative to A?
In particular, does the superapproximation given by
Brattka-de Brecht-Pauly satisfy monotonicity?
If such a function exists, we would apply it to build the sequence
A0 <T A1 <T · · · as before, knowing thatA ≤T B =⇒ (∀n)An ≤T Bn =⇒ IA ⊆ IB .
Russell Miller (CUNY)

Direct Construction of Scott Ideals

CiE 2023

13 / 13