GROUP

NOAM GREENBERG, ALEXANDER MELNIKOV, ANDRE NIES, AND DANIEL TURETSKY

Abstract. We apply methods of computable structure theory [AK00, EG00] to study ef-
fectively closed subgroups of S∞. The main result of the paper says that there exists an
effectively closed presentation ofZ^{2}which is not the automorphism group of any computable
structureM. In contrast, we show that every effectively closed discrete group is topologically
isomorphic to Aut(M) for some computable structureM. We also prove that there exists an
effectively closed compact (thus, profinite) subgroup ofS∞ that has no computable Polish
presentation. In contrast, every profinite computable Polish group is topologically isomorphic
to an effectively closed subgroup ofS∞. We also look at oligomorphic subgroups ofS∞; we
construct a Σ^{1}_{1} oligomorphic group in which the orbit equivalence relation is not uniformly
HYP. Our proofs rely on methods of computable analysis, techniques of computable structure
theory, elements of higher recursion theory, and the priority method.

The study of computable presentations of topological groups originated in computable field theory [MN79] and was mainly driven by Nerode’s interest in algorithmic aspects of Krull theory. Working under the supervision of Nerode, La Roche [LR81] proved that the corre- spondence between computable algebraic number field extensions and profinite groups is uni- formly effective, in the sense that will be clarified later. Quite interestingly, the algorithmic techniques developed in [LR81] allowed La Roche to prove a theorem on free profinite groups that was new even in the purely algebraic (non-computable) setting, see [Jar74] for the earlier and a weaker purely algebraic result. Based on the work of La Roche, Smith [Smi81, Smi79]

initiated the study of algorithmic presentations of profinite groups in their own right, i.e. not in the context of effective Galois theory.

Such investigations in computable topological groups have not been restricted to profinite groups (see., e.g., [GR93]), but the general theory of computable Polish groups is still in its infancy. Recently there has been an increasing interest in computable aspects of Polish and Banach spaces [PER89, BHW08, Mel13, McN15] and, consequently, in computable Polish groups [MM, Mel]. Many aspects of computable Polish groups are related to computable struc- ture theory [AK00, EG00] and computable Banach space theory [PER89]. Such connections are often quite subtle. For example, it turns out that many classical results of computable structure theory have simpler proofs in the more general setting of a computable Polish group action, see [MM]. On the other hand, the study of Pontryagin Duals of computable Polish abelian groups enjoys applications of non-trivial effective algebraic results, see [Mel]. It seems that effective algebra and computable topological group theory are two adjacent pieces of a bigger puzzle. This paper contributes to the general framework proposed in [Mel13] that is focused on establishing further technical connections between computable structure theory and computable analysis, see also [MN16, MN13, MM, GMKT, McN15, MS, Mel].

Recall that a countably infinite and discrete algebraic structure (e.g., a countable field of characteristic 0) is computable if its domain is ω and its operations and relations are Turing

The first author was partially supported by the Marsden Fund of New Zealand. The second author was partially supported by the Marsden Fund of New Zealand and Massey University Research Fund.

1

computable. Our main goal is to investigate automorphism groups of computable algebraic structures. For this purpose we introduce a new notion of an effectively closed group. (Our second main result will imply that the notion below is indeed new.)

Definition 0.1. We say that a subgroupGofS∞iseffectively closed (or Π^{0}_{1}for short) if there
is an effectively closed subset P of ω^{ω} such that G =P ∩S∞. An effectively closed presen-
tation, or a Π^{0}_{1}-presentation, of a group is an effectively closed subgroup of S∞ topologically
isomorphic to the group.

Automorphism groups of computable algebraic structures are clearly effectively closed. It is well-known that every closed subgroup of S∞ is equal to the automorphism group of some countable algebraic structure upon ω, see [Gao09]. It is natural to ask:

Is every effectively closed group equal to Aut(C) for some computableC?

We will see that the answer to this question is negative, which seems somewhat counterintu- itive. The reader perhaps suspects that the isomorphism type of any effectively closed sub- group ofS∞witnessing the negative answer should be, in some sense, non-trivial. Remarkably, already the two-element cyclic discrete group Z2 has a “bad” effectively closed presentation.

On the other hand, Z2 is (topologically) isomorphic to Aut(C) for some computableC.

Theorem 0.2.

(1) There exists an effectively closed presentation of the two-element cyclic groupZ2 such thatG6= Aut(C) for any computable structureC.

(2) Every effectively closed discrete group is topologically isomorphic to Aut(C) for some computable structureC.

The main difficulty in the proof of Theorem 0.2(1) is nesting strategies on top of each other and not losing the property of being a subgroup ofS∞. We leave open whether Theorem 0.2(2) can be extended to non-compact effectively closed groups.

One could also argue that Definition 0.1 is natural in its own right; effectively closed sets play a significant role in recursion theory, for some recent applications see [BC08, Rei08, HK14]. It could be the case that the notion is actually equivalent to one of the already existing notions restricted to closed subgroups of S∞. We compare Definition 0.1 with the mentioned above notions of acomputable Polish group [MM, Mel] and arecursive profinite group[LR81, Smi81].

(The formal definitions will be given in the preliminaries.) Every recursive profinite group is computable Polish, but there are computable Polish profinite groups with no recursive presentation [Mel]. Recall that the profinite groups are exactly the compact subgroups ofS∞, up to topological isomorphism.

Theorem 0.3.

(1) There exists an effectively closed compact (thus, profinite) subgroup of S∞ that has no computable Polish presentation (therefore, no recursive presentation).

(2) Every profinite computable Polish group is topologically isomorphic to an effectively closed subgroup ofS∞.

In particular, part (1.) of Theorem 0.3 shows that Definition 0.1 gives a new notion, while part (2.) establishes a connection between Definition 0.1 and computable Polish groups. In the preliminaries we will use similar ideas to suggest an extension of Definition 0.1 to groups that are not necessarily totally disconnected. We leave open whether Theorem 0.3(2) can be extended to arbitrary closed subgroups of S∞.

To finish the paper we look at the class of oligomorphic groups. There are closed subgroups
G of S∞ for which for every n there are only finitely many G-orbit equivalence classes ofn-
tuples. Oligomorphic groups are the automorphism groups ofℵ_{0}-categorical structures. These
structures are homogenous. Thus, if an effectively closed subgroup Gof S∞ is oligomorphic,
and equals Aut(M) for some computable structureM, then∼_{G}will in fact becomputable. We
approach the question “how complicated can∼_{G}be for an effectively closed oligomorphocG?”

If we could construct an effectively closed oigomorphic group with ∼_{G} not computable, we
would get another example for our main result Theorem 0.2(1). Oligomorphic groups lie at
the other extreme from profinite groups, for which every orbit equivalence class is finite, and
our initial hope was that it might perhaps be easier to handle them. Our intuition was wrong,
but the effective content of oligomorphic groups turned out to be interesting on its own right.

Note that even for Σ^{1}_{1} groups,∼_{G}is Σ^{1}_{1}; ifGis oligomorphic, then for eachn, the restriction
of ∼_{G} ton-tuples must be hyperarithmetic. Interetingly enough, this fact lacks uniformity in
the following sense.

Theorem 0.4. There is a Σ^{1}_{1}, closed oligomorphic subgroup of S∞ for which ∼_{G} is not
hyperarithmetic.

It would be interesting to obtain more information about the effective content of oligo-
morphic groups; in particular, we leave open whether a Π^{0}_{1} oligomorphic group can witness
Theorem 0.2(1).

The structure of this paper is as follows. The small preliminary Section 1 contains for- mal definitions, a description of the natural computable Polish presentation of S∞, and an equivalent definition of an effectively closed subgroup ofS∞in terms of this presentation. We arrange proofs according to the used methods. The proof of Theorem 0.3 can be found in Section 2. Section 3 contains the proof of Theorem 0.2(1), and the proofs of Theorem 0.2(2) and Theorem 0.4 are in Section 4, respectively.

1. Preliminaries

Throughout this paper we work in the category of topological groups. We only consider isomorphisms between groups that are both algebraic and topological, i.e., homeomorphisms;

so henceforth “isomorphic” means “topologically isomorphic”.

Definition 1.1. A computable Polish (metric) space is a triple (M, d,(α_{i})i∈ω), where (M, d)
is a Polish space, the sequence (αi)i∈ωis dense inM, and there exists a uniformly computable
procedure which on inputi, j∈ωand∈Q^{+}, outputs a rationalrsuch that|d(α_{i}, α_{j})−r|< .
The points from the dense computable sequence (αi)i∈ω are called special. A ball with a
rational radius and centred in a special point is called basic. Clearly, ω^{ω} under the usual
ultrametric forms a computable Polish space. The basic open balls are the usual clopen
neighbourhoods.

SupposeF :X→Yis a map between computable Polish spaces. The mapF iscomputable
if there exists a uniform procedure which, on input a basic open B ⊂ Y, lists a set of basic
open balls inX whose union is equal toF^{−1}(B). Note that we do not require to list all balls
contained inF^{−1}(B). This approach is equivalent to the definition from, e.g., [Mel13]. Observe
that the product of two (or more) computable Polish spaces is itself computable Polish. The
definition below generalises the old definition of a recursive profinite group [LR81, Smi81] to
arbitrary Polish groups.

Definition 1.2 ([MM]). A computable Polish presentation of a [second-countable Hausdorff]

topological groupGis a computably and completely metrized homeomorphic copy ofGupon
which the operations ·and ^{−1} are computable.

We now discuss the infinite permutation group S∞ ⊂ ω^{ω}. For two permutations σ and τ
of ω, let

D(σ, τ) = d(σ, τ) +d(σ^{−1}, τ^{−1})

2 ,

where d is the usual ultrametic on ω^{ω}. The dense computable subset of S∞ is given by
permutations of ω with finite support. Then (S∞, D) becomes a computable Polish group
which we call the natural Polish presentation ofS∞ for reasons that will be explained shortly.

Recall that a closed subsetCof a computable Polish space iseffectively closed or Π^{0}_{1}if there
exists a (Turing) computable enumeration of basic open balls whose union is the complement of
C, and recall Definition 0.1 of an effectively closed subgroup ofS∞. It seems quite natural and
certainly useful to define a Π^{0}_{1}-subgroup based on the natural computable Polish presentation
of S∞ ofω^{ω} instead. Luckily these notions coincide.

Proposition 1.3. A group G 5 S∞ is effectively closed (according to Definition 0.1) if and only if the domain of G is an effectively closed subset of the natural computable Polish presentation of S∞.

Proof. We prove a bit more. Suppose thatU is a basic open subset of ω^{ω}. Can we effectively
list basic open subsets of (S∞, D) whose union is equal to S∞∩U? Conversely, given a basic
openV in (S∞, D), can we list basic open sets whose unionU has the propertyU∩S∞=V?
In other words, is the metric D (on S∞) effectively compatible with the usual metric d (on
ω^{ω})?

Claim 1.4. The metricDdefined above is effectively compatible with the standard ultrametric
don ω^{ω}.

Proof of Claim. Suppose that a sub-basic open subsetU of ω^{ω} is specified by a finite partial
map σ. If σ is not injective, then V =∅. Otherwise, let τ_{1}, τ_{2}, . . . be the effective list of all
possible extensions ofσ^{−1} to an injective map with domain a finite initial segment ofω. Then
the sequence of pairs (τ_{i}^{−1}, τi), i= 1,2, . . . corrsponds to a sequence of respective basic open
balls in (S∞, D) whose union we set equal toV. Note that each element ofU∩S∞belongs to
one of these basic open sets, and thus toV. Conversely, eachf ∈V has a finite approximation
that is consistent with the restriction imposed by U.

Now suppose (σ, σ^{−1}) describes a basic open set V in (S∞, D), where σ is a permutation
of an initial segment of ω. Then the open set U can be taken equal to the collection of all
extensions of σ to an element of ω^{ω}. The correspondence is clearly effective.

LetP be a closed subset ofω^{ω}. It follows that we can uniformly pass from the enumeration
of P inω^{ω} to the enumeration of P ∩S∞ in (S∞, D) and back.

The proposition above allows us to extend Definition 0.1 to groups that are not necessarily embeddable intoS∞, but we leave this new notion outside the scope of this article.

Definition 1.5 ([LR81, Smi81]). A recursive presentation of a profinite group P is a uni- formly computable inverse system of finite groups, with surjective maps, whose inverse limit is isomorphic to P.

It is known that recursively presented profinite groups are exactly the automorphism groups of computable algebraic number fields over a computable subfield; see [LR81]. As we mentioned above, every recursive profinite group is computable Polish, but there are computable Polish profinite groups with no recursive presentation [Mel].

2. Effectively closed vs. computable Polish

Proof of Theorem 0.3(1). We construct an effectively closed gubgroup ofS∞that has no com- putable Polish presentation. We will be using the result below:

Fact 2.1 ([Mel], Cor. 1.8). Every computable Polish presentation of a profinite groupP can
be transformed into a 0^{0}-computable inverse systemF0 ←F1 ←F2. . ., with surjective maps,
whose limit is isomorphic to P.

For a set S of prime numbers let

P_{S} = Y

p∈S

Zp,

whereZp is the cyclic group of orderp. This group is profinite, as it is the inverse limit of the groups Q

p∈S∩nZp forn < ω.

First we observe that ifP_{S} has a computable Polish presentation thenS is Σ^{0}_{2}. To see this,
given such a presentation of P_{S}, by Fact 2.1, we produce a 0^{0}-computable inverse system rep-
resenting the group. By [Mel, Thm.1.9] we can use this to uniformly produce a 0^{0}-computable
presentation – in the sense of computable structure theory – of the discrete countable group
L

p∈SZp, which is the Pontryagin dual of P (see the book [Pon66] for more on Pontryagin’s
duality theory). Using the 0^{0}-computable presentation of L

p∈SZp we can 0^{0}-computably list
the prime orders of elements of the group, showing thatS is Σ^{0}_{2}.

So it suffices, given a Π^{0}_{2}-complete setS of primes, to build a computable structureM such
that Aut(M) is isomorphic to P_{S}. The structure M will be a graph consisting of infinitely
many disjoint components Cp, one for each primep. Every Cp will have a loop of length p,

x^{p}_{0}−x^{p}_{1}−. . .−x^{p}_{p−1}−x^{p}_{0}
and every node in the loop will have a [finite or infinite] chain

x^{p}_{i} −c^{p}_{i,1}−c^{p}_{i,2}−. . .

attached to it. The length of the chain depends on our approximation for the Π^{0}_{2} predicate
for p. Ifp /∈S then this predicate fires forp only finitely many times, say s; in this case, we
make the length of the ith chain equal to s+i. The result is a rigid component. If p ∈ S
then we make each of the pmany chains infinite. In this case the automorphism group of the
component will be isomorphic to Zp; each automorphism is determined by the image of x^{p}_{0},
which could be any x^{p}_{i}.

Because there is no interaction between the components, Aut(M) ∼=Q

p∈SAut(C_{p})∼= P_{S}.
This isomorphism is topological as well, because in both copies, the topology is the product
topology where the components Aut(Cp) andZp are discrete. In other words, in both Aut(M)
and C_{p}, the sub-basic clopen sets are determined by stating finitely many values for the

automorphism.

Proof of Theorem 0.3(2). LetP be a computable Polish profinite group. We need to produce
a Π^{0}_{1} presentation of P. By Fact 2.1, there is a 0^{0}-recursive presentation ofP. We will use a
fully relativised form of the fact below.

Fact 2.2 (LaRoche [LR81]). Every recursively presented profinite group is isomorphic to Gal(K/N), where K is a computably presented algebraic extension of Q, and N is a com- putable subfield of K.

In fact, N is a fixed field that corresponds to a natural recursive presentation of the free profinite group upon countably many generators, see [LR81]; we do not need this fact.

Fix a 0^{0}-computable fieldKand a 0^{0}-computable subfieldN ofKsuch that Aut(K/N)∼=P.
Our first step is to obtain a 0^{0}-computable relational structureF (with computable underlying
set and in a computable language) such that Aut(F) ∼= Aut(K/N) (all isomorphisms are
topological); then we obtain a computable structure ˆF such that Aut( ˆF)∼= Aut(F).

To define F, we start withK; by taking a 0^{0}-computably isomorphic copy we may assume
that N is computable. We name each elements of N by singleton unary predicate and re-
place the field operations by their graphs. This adjustment does not change the topological
isomorphism type of the automorphism group, so Aut(F)∼=P.

The next step is a version of Marker’s existential extension which preserves the automor- phism group.

Proposition 2.3. For any∅^{0}-computable relational structureA there is a computable struc-
ture B such that Aut(A) and Aut(B) are isomorphic.

Proof. We use the following piece of folklore in computable structure theory.

Fact 2.4(Folklore, e.g., [GK02]). LetSbe a Σ^{0}_{2}set. There exists a uniform procedure which,
for each x∈ω, outputs a computable copy of ω ifx∈S, and outputs a computable copy of
ω^{2} otherwise.

We assume that the underlying set of A is computable, with a computable language. To
define B, fix an n-ary relation of A. For every tuple ¯a ∈ A^{n} we add a new infinite set C_{¯}_{a}^{P}
of elements (these are pairwise disjoint). We link these “blow ups” of tuples by adding the
relation y ∈ C_{x}^{P}_{¯} to B. Next, for every tuple ¯a ∈ A^{n} we define a linear ordering L^{P}_{¯}_{a} of C_{a}_{¯}^{P},
which is isomorphic to ω if P(¯a) holds in A, and isomorphic to ω^{2} otherwise. We add the
relation y1, y2 ∈ C_{x}_{¯}^{P}&y1 <_{L}P

¯

x y2 to the structre B. It follows from Fact 2.4 that B has a computable copy.

To show that Aut(A) ∼= Aut(B), we notice that both ω and ω^{2} are rigid. Thinking of
the underlying set of A as a (computable, definable) subset of B, we observe that every
automorphism ofB is determined by its restriction to A, and that every automorphism ofA
can be extended to an automorphism ofB. Let Φ : Aut(B)→Aut(A) be this restriction map,
Φ(τ) =τ A; it is the required isomorphism. To see that it is topological, in the slightly less
immediate direction, we need to check that it is an open map. We take a sub-basic clopen
subset of Aut(B), which is the collection of automorphisms of B which extend some finite
mapσ. The point is that σ may mention some elements ofB\A. Nonetheless, Φ[σ] is clopen
in Aut(A). If q ∈ C_{¯}_{a}^{P} is mapped to some p ∈ C_{¯}_{b}^{P}, then to the image of [σ] we add the
restriction that ¯a is mapped to ¯b. Since ω and ω^{∗} are rigid, mapping ¯a to ¯b is equivalent to

mapping q top.

This completes the proof of Theorem 0.3(2).

3. Proof of Theorem 0.2

We must construct a Π^{0}_{1}presentation ofZ2which is not equal to Aut(M) for any computable
structureM (upon the domain ofω).

Informal idea. We explain the basic idea behind diagonalising against the eth partial com-
putable structure M_{e}. We work in ω^{ω}. We start by enumerating a certain neighbourhood
into the complement of the presentation, and we say that we “forbid” the neighbourhood. For
some basic ¯a→¯bwithin this neighbourhood, we must have ¯a6→¯binM_{e}, as witnessed by some
first-order atomicφ(unlessMe is not total). Then, for some ¯c, it should be the case thatφ(¯c)
or¬φ(¯c), and thus necessarily either ¯a6→¯cor ¯c6→¯b. Until this happens the construction will

proceed in some fixed basic neighbourhood, say ¯a→c. Once we see¯ φevaluated on ¯c(if ever)
and says that ¯c6→¯b, then we switch to ¯c→¯band forbid ¯a→¯c. The key here is that we don’t
have to instantly forbid the neighbourhoods, butM_{e}must (unless it is not total). We can put
sub-neighbourhoods of a given neighbourhood into our effectively open set one-by-one. Thus,
we can delay our decision and do the opposite in the group presentation.

The trickier part is nesting the strategies on top of each other. For that, our construction will proceed only within nested clopen subsets extending ¯x↔y, where ¯¯ xis an initial segment ofω, ¯yis a permutation of ¯x, and the order of this permutation is 2. If we make sure ¯x¯a6→x¯¯b inMe, we can still fix a tuple ¯y¯cand repeat the basic diagonalisation idea, as above. It must be the case that either ¯x¯a6→y¯¯cor ¯y¯c6→x¯¯bis witnessed by some first-orderφ, but both events can be restricted to the neighbourhood ¯x ↔ y. The key here is to choose numbers in ¯¯ c to be very large, so that both neighbourhoods ¯x¯a→y¯¯cor ¯y¯c→x¯¯b contain sub-neighbourhoods isolated by finite permutations of order 2. Then the construction can proceed in one of the two neighbourhoods. With some care we will end up with a copy of Z2. The rest is handled by priority nonsense.

Proof. Fix a computable listing (M_{e})e∈ω of all (partial) computable structures upon the do-
main ω. We construct a Π^{0}_{1}-subgroup P of the standard copy of S∞, and meet the require-
ments:

P 6= Aut(M_{e}),
for each e. We will also (globally) ensure thatP ∼=Z2.

We will identify finite injective partial maps and the respective basic neighbourhoods inS∞

determined by their possible extensions.

Definition 3.1. We say that an injective finite map ¯x→y¯isnice if it is a finite permutation of an initial segment ofω and has order 2 (i.e., is an involution). We write ¯x↔y¯to emphasise that the map and its respective basic neighbourhood are nice.

All our diagonalisation strategies will be working within (0,1)↔(1,0). Some of the basic
neighbourhoods will be enumerated into the complement of P. If we enumerate a certain
neighbourhood into S∞ \P, we say that we forbid the neighbourhood. There will be no
interaction between the process of approximating Id_{ω} and the procedure of approximating
the only non-identity element of P.

The basic strategy. We describe the basic diagonalisation strategy, forMe, in isolation. The
strategy will be working within a nice σ_{e}= ¯x↔y.¯

(1) Forbid ¯xn→x(n¯ + 1), where n=lth(¯x). (Note that ¯xn→x(n¯ + 1) will be forbidden by the construction anyway because of its proximity toIdω, so we could simply wait until this happens.)

(2) Wait for Me to separate some ¯x¯a and ¯x¯b extending ¯xn and ¯x(n+ 1) (and having
the same length) by a first-order atomic formula φ. Until this happens, if ever, let
the construction proceed within the nice neighbourhood ¯xn ↔yn. One-by-one, start¯
forbidding all other sub-neighbourhoodsσe = ¯x ↔y¯of the form ¯xn→yk,¯ k6=n. (If
M_{e}is total but never gives such aφ, then run a back-and-forth argument on extensions
of ¯xn and ¯x(n+ 1) to build an automorphism of Me extending ¯xn→x(n¯ + 1).)
(3) If such a φ is found, choose ¯c consisting of very large and fresh numbers (and of the

same length as ¯aand ¯b). Proceed as follows:

(a) Extend the finite partial maps ¯x¯a→ y¯¯c and ¯y¯c→ x¯¯b to [finite] permutations of order 2, let N1 and N2 be the respective nice sub-neighbourhoods. Since ¯x↔ y¯ is nice, bothN1 and N2 belong to ¯x↔y. By the choice of ¯¯ c, these permutations

have not been forbidden yet. Stop the process of forbidding sub-neighbourhoods of ¯x↔y¯initiated at substep (2).

(b) Forbid what is left of ¯xn ↔yn. (Note that weaker priority strategies have been¯ working in this neighbourhood.)

(c) Start forbidding extensions of N2, one-by-one, and let the construction [i.e., all
the weaker priority strategies] proceed within N_{1}. Forbid all basic open neigh-
bourhoods that do not containIdω and are disjoint formN1 and N2.

(4) Wait for M_{e} to evaluate φ on ¯y¯c, thus witnessing either ¯x¯a 6→ y¯¯c or ¯y¯c 6→ x¯¯b in
Aut(Me). If this never happens, the construction will forever stay insideN1.

Case 1: ¯x¯a6→y¯¯cin Aut(M_{e}), as witnessed byφ. In this case Aut(M_{e})∩N_{1} =∅. Proceed
as above to (eventually) completely forbidN2and keep all weaker priority actions
restricted toN_{1}. We will see that in this case the only non-zero element of P is
insideN1.

Case 2: ¯y¯c 6→ x¯¯b in Aut(Me), as witnessed by φ. In this case stop forbidding N2 and forbid what is left ofN1. Choose a nice τ within N2 and restrict the actions of all weaker priority strategies toτ. Similarly to Case 1, the only non-zero element ofP will be contained in τ.

Priority and initialisation. We order the strategies according to the index of the partial computable structure that they are guessing, with smaller indices corresponding to stronger priority. Every time a basic strategy changes its mind about the neighbourhood in which the construction [i.e., the weaker priority strategies]should proceed, we initialise all weaker priority strategies. This is done by picking a new nice neighbourhood σi within the current neighbourhood of the higher priority strategy in which it allows the construction to proceed.

We also make sure that the diameter of the nice neighbourhood σi of the ith strategy is at
most 2^{−i} (equivalently, we could require that the domain of the finite nice map contains at
least ielements).

Construction. At the beginning of the construction, we will fix a nice basic neighbourhood of Id (say, (0,1) ↔ (0,1)) and some other nice neighbourhood (say, (0,1)↔ (1,0)) disjoint from it. From this point on, we keep forbidding all (not necessarily nice) sub-neighbourhoods of (0,1)↔(0,1) that do not containIdω. We setσ0 = (0,1)↔(1,0).

Verification. We verify some of the key properties of the construction, stage-by-stage.

Claim 3.2. SupposeM_{e} is total, and ¯xn6→x(n¯ + 1) Aut(M_{e}) . Then at stage (2) we can find

¯

x¯a and ¯x¯b extending ¯xn and ¯x(n+ 1), respectively, and a first-order atomic formula φ that separates ¯x¯aand ¯x¯b.

Proof of Claim. Suppose such ¯x¯a and ¯x¯b and an atomic φ do not exist. This means that

¯

xn → x(n¯ + 1) can be extended to an automorphism of M_{e} in a back-and-forth fashion,

contradicting ¯xn6→x(n¯ + 1).

We follow the notation and the terminology used in the construction.

Claim 3.3. Suppose substage (3) is reached. Then there exists a tuple ¯cand nice neighbour- hoods N1 and N2 with the desired properties.

Proof of Claim. Recall that only finitely many basic neighbourhoods can be forbidden at every stage of the construction. In particular, only finitely many sub-neighbourhoods ofσe= ¯x↔y¯

of the form ¯xn → yk,¯ k 6= n, have been enumerated into the complement of the effectively closed set that we build. In particular, we can choose ¯cso that ¯x¯a→y¯¯chas not been forbidden yet. Furthermore, choosing ¯clarge enough we can ensure that both ¯x¯a→y¯¯cand ¯y¯c→x¯¯bcan be extended to finite permutations of order 2 which have not yet been forbidden. This is done by simply setting σ(j) =iifσ(i) =j already, and by declaringσ(k) =kfor all other k.

The importance of choosing ¯c very large in (3) is best illustrated by the simple example below.

Example 3.4. In the notation as above, suppose ¯x¯a → x¯¯b is (0,1,2,7,11) → (0,1,3,2,5).

It extends ¯xn → y(n¯ + 1) which is (0,1,2) → (0,1,3). Fix A, B, C very large, they could be equal to 100,101,102. Consider (0,1,2,7,11) → (1,0,101,102,103) and (1,0,101,102,103) → (0,1,3,2,5). We could extend them to [finite] permutations, say to (0,1,2,7,11,101,102,103) → (1,0,101,102,103,2,7,11) and (1,0,2,3,5,101,102,103) → (0,1,102,101,103,3,2,5), respectively. Recall we were slowly forbidding all neighbourhoods in ¯x ↔ y¯ except for extensions of ¯xn ↔ yn, which is (0,¯ 1,2) → (1,0,2) in this particu- lar case. But 101 is large enough so that (0,1,2,7,11) → (1,0,101,102,103) has not been forbidden yet. The neighbourhood (1,0,2,3,5,101,102,103)→(0,1,102,101,103,3,2,5) has not been forbidden since 102 is large enough. We could easily extend each of these finite maps to permutations of ω 103 of order 2 by making all the rest i < 103 stable under the permutation. This will give us nice extensions of (0,1,2,7,11)→(1,0,101,102,103) and (1,0,101,102,103) → (0,1,3,2,5) which have not been forbidden yet in the construction.

(Note that 2 was accidentally mentioned in the domain of the second permutation, due to the choice of ¯b and ¯a. If it was not the case, we’d have to choose a large fresh D and map 2↔D, just to make sure the extension is not forbidden.) Note that both neighbourhoods are contained within the basic neighbourhood of (0,1)↔(1,0).

Claim 3.5. Suppose the eth strategy is never initialised after stage s. Regardless of the
outcome, there exists ans^{0} ≥sand a nice neighbourhoodN^{e}such that all the weaker priority
strategies (j > e) perform their actions withinN^{e}.

Proof of Claim. The strategy may never find a φ and a pair of witnesses at substage (2), in
which case all weaker priority strategies will work within ¯xn ↔ yn. Otherwise, depending¯
on the outcome, it may either stay within N_{1} forever, or it may eventually switch toN_{2} and

never change the neighbourhood again.

The basic module of the eth strategy makes sure that no element in the eventually stable
neighbourhood N^{e} can be in Aut(M_{e}) if M_{e} is total. Note that, whenever a strategy is
initialised it can pick a nice neighbourhood within the part ofS∞that has not been forbidden
yet by the higher priority strategies. A straightforward inductive argument shows that for
everye, theeth strategy eventually never changes its neighbourhood that it keeps unforbidden,
and therefore every strategy is eventually never initialised.

Theeth strategy ensures that some niceτ_{e}determined by its stableN^{e}is the approximation
of P \ {Id_{ω}}. It follows from the construction that all elements of S∞ in (0,1)↔ (0,1) that
do not extend τ_{e} will be eventually forbidden by the e’th strategy. Also, all neighbourhoods
outside (0,1)↔(0,1) that do not containIdω will be forbidden in the construction.

Note that the diameter of the nice eventually stable neighbourhoodN_{e}is at most 2^{−e}, and
N^{e+1} ⊂N^{e} for every e. It follows that the intersection of all these eventually stable N^{e} is a
singleton whose only element is the limit of the ∆^{0}_{2} sequence (τ_{e})e∈ω. The singleton describes
the only non-Id element Θ of the Π^{0}_{1} set P that we end up with. Note that τ_{e}^{2} =Id_{supp(τ}_{e}_{)},

for each e. It follows that Θ^{2} =Idω. Thus, P ∼=Z2.

4. Discrete Π^{0}_{1}-presented groups and oligomorphic groups

We know that Z2 has a complicated Π^{0}_{1} presentation, but it is also clear that Z2 has a

“nice” presentation equal to Aut(M) for some computableM. This elementary observation is
a special case of the more general result: Every discrete Π^{0}_{1}-presented group P is isomorphic
to Aut(M) for some computable structureM (Theorem 0.2(2)).

To prove the theorem we analyse the complexity of the orbit equivalence relation. LetGbe
a subgroup of S∞. For alln < ω, the groupGacts on the collection ω^{n} ofn-tuples of natural
numbers; the resulting orbit equivalence relation ∼_{G} is defined on ω^{<ω} by letting ¯a∼_{G} ¯b if

|¯a|=|¯b|and there is someσ ∈G such thatσ(¯a) = ¯b. We prove the following:

Proposition 4.1. IfGis a discrete, effectively closed subgroup ofS∞, then∼_{G} is hyperarith-
metic.

(This means that for each n, the orbit equivalence relation forn-tuples is hyperarithmetic, uniformly in n.)

Proposition 4.2. If G is an effectively closed subgroup of S∞ and ∼_{G} is hyperarithmetic,
then there is a computable structure M such thatG∼= Aut(M).

Theorem 0.2(2) then follows. Proposition 4.2 is itself the conjunction of two lemmas.

Lemma 4.3. Every closed subgroup G of S∞ is equal to Aut(M) for some structure M
computable from ∼_{G}.

Lemma 4.4. For every hyperarithmetic structureM there is a computable structureN such that Aut(N)∼= Aut(M).

Lemma 4.4 is a generalisation of Proposition 2.3. Say that M is ∆^{0}_{γ} for some computable
ordinal γ. We use a generalisation of Fact 2.4 that allows us to code membership in a Σ^{0}_{α}
class into an isomorphism type of one of two rigid linear orderings which satisfy the same
computable Π_{γ} infinitary formulas but are separated thereafter. For example, we can produce
a copy ofω^{γ+1}if a Σ^{0}_{γ}fact holds, and a copy ofω^{γ+2}otherwise; for our purposes, the complexity
does not need to be tight. See [GK02, Prop.4.12]. The argument then is the same as that of
Proposition 2.3.

Lemma 4.3 is an observation that the standard construction of a structure M such that
G = Aut(M) does in fact give us a structure computable from ∼_{G}, see [Gao09]. For any n
and for every ∼_{G}-equivalence class ofn-tuples we define ann-ary relation which defines that
class. Closure of Gis used to show that Aut(M)⊆G.

It remains to prove Proposition 4.1.

Proof of Proposition 4.1. Σ^{1}_{1} subsets ofω^{ω} have the perfect set property in a strongly effective
way: if a Σ^{1}_{1} set A does not have a perfect subset then all elements ofA are hyperarithmetic,
and so by Spector’s Σ^{1}_{1} bounding, they are all computable from some 0^{(γ)} for some fixed
computable ordinal γ. (See [Sac90], Thm. 6.2.III.)

By Proposition 1.3,G is a Π^{0}_{2} subset ofω^{ω}. If all elements of Gare 0^{(γ)}-computable, then
0^{(γ+2)}computes a listing of the elements ofG; it then follows that∼_{G}is 0^{(γ+3)}-computable.

This proves Theorem 0.2(2).

Remark 4.5. Note that ifGis an effectively closed discrete group, then it has a hyperarithmetical presentation in the sense of computable structure theory (upon the domain of ω). It is easy to see that this observation gives a characterization of discrete effectively closed groups in terms of hyperarithmetically presented groups;

we outline the proof of the less obvious implication.

Let G be a countable (discrete) group. Use Cayley’s theorem and mapg∈Gto the permutationh7→gh, call itσg. The image is discrete: σg is isolated by the neighbourhoode7→g. This way we obtain anH 5S∞

(topologically) isomorphic to G which is furthermore arithmetical in the diagram ofG, in particular ∼H is HYP. Lemma 4.3 gives a HYPM such that H ∼=Aut(M), and Lemma 4.4 allows to build a computableN such thatG∼=H∼=Aut(M)∼=Aut(N).

4.1. Proof of Theorem 0.4. Recall that a (closed) oligomorphic group is a (closed) subgroup ofS∞such that for everynthere are only finitely manyG-orbit equivalence classes ofn-tuples.

We construct of Σ^{1}_{1}, closed oligomorphic subgroup ofS∞for which∼_{G}is not hyperarithmetic.

We work in the admissible structure L_{ω}ck

1 . The idea is to use a cofinal ω-sequence hα_{n}i
inω^{ck}_{1} which is approximated effectively (in the sense ofL_{ω}^{ck}

1 -computability) with only finitely
many changes to each value. We define the orbit equivalence relation ∼_{G} rather than G.

We break up classes of n-tuples into two whenever we see a change in the value of α_{n}; this
happens only finitely many times, so at the end we get only finitely many classes ofn-tuples.

The entire equivalence relation is not hyperarithmetic, as we can recover the sequence hα_{n}i
from it. To ensure that the equivalence relation is indeed the orbit equivalence relation of a
closed group we need to ensure that it is invariant under permutations, taking subsequences,
and has the back-and-forth property. This can be done dynamically, but in fact it is easy to
give an explicit definition of the relation.

To the details. For a non-decreasing sequence k = hk_{n}i of natural numbers define an
equivalence relation ∼_{k} on ω^{<ω}. For ¯a,¯b ∈ ω^{<ω} of the same length n, if they are both
injective, then we let ¯a∼_{k}¯bif for everym < nthere are at leastn−m manyi < nsuch that
a_{i}=b_{i} mod 2^{k}^{m}. We then extend this to non-injective tuples in the obvious way.

We first observe:

• ∼_{k} is an equivalence relation.

• If ¯a∼_{k}¯bthen for any subsequence ¯a^{0} of ¯aand ¯b^{0} of ¯bchosen in the same way, ¯a^{0}∼_{k}¯b^{0}.

• ∼_{k} is invariant under permutations: for any n-tuples ¯a,¯b and permutationσ of n, if

¯

a∼_{k}¯bthen ¯a◦σ∼_{k}¯b◦σ.

• ∼_{k} has the back and forth property: if ¯a∼_{k}¯b then for all c < ω there is some d < ω
such that ¯ac∼_{k}¯bd.

• For everyn there are only finitely many∼_{k}-equivalence classes of n-tuples.

We then let G_{k} be the collection of all f ∈ S∞ such that for all ¯a and ¯b, if f(¯a) = ¯b then

¯

a ∼_{k} ¯b. It is a closed subgroup of S∞; the properties just listed ensure that ∼_{k} is the orbit
equivalence relation of the action ofG_{k}, and that this action is oligomorphic.

We now start to work effectively. Since the Σ1 projectum of L_{ω}ck

1 is ω, there is a ∆2(L_{ω}ck
1 )
increasing sequence hα_{n}i_{n<ω} which is cofinal inω_{1}^{ck}; see [Sac90] for an excellent exposition of
higher recursion theory. In fact,hα_{n}ihas afinite-change approximation (see [BGM17]): there
is a ∆1(L_{ω}ck

1 ) array (that is, aL_{ω}ck

1 -computable array)hα_{n,s}in<ω,s<ω_{1}^{ck} such that writingα_{n,ω}ck
1

forα_{n}, we have:

• For all limit ordinalss≤ω^{ck}_{1} , for all n,α_{n,s} = limt→sα_{n,t}; and

• For everyn < ω, there are only finitely many stagess < ω_{1}^{ck} such thatαn,s 6=αn,s+1.
Given such a sequence we define, for each s≤ω_{1}^{ck},

kn,s= X

m≤n

#{t < s : αm,t6=αm,t+1}.

this defines sequences ks fors ≤ω_{1}^{ck}. Our final equivalence relation is ∼_{k}=∼_{k}

ωck1

. The fact that we used powers of 2 means that as fort < s, for alln,kn,t≤kn,s, the equivalence relation

∼_{k}_{n,t} refines the equivalence relation∼_{k}_{n,s}. This shows that∼_{k} is Π_{1}(L_{ω}ck

1 ), that is, it is Σ^{1}_{1}.
It follows that G_{k} is Σ^{1}_{1} as well.

The final relation ∼_{k}=∼_{k}

ωck1

is not hyperarithmetic: we can see that ω_{1}^{∼}^{k} > ω_{1}^{ck}, as in an
effective fashion over L_{ω}^{∼}k

1 [∼_{k}] we can recover hα_{n}i: for alln < ω and s < ω_{1}^{ck}, if the number
of ∼_{k}_{s}-equivalence classes of n-tuples is the same as that of ∼_{k}, thenαn=αn,s.

References

[AK00] C. Ash and J. Knight. Computable structures and the hyperarithmetical hierarchy, volume 144 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, 2000.

[BC08] Paul Brodhead and Douglas Cenzer. Effectively closed sets and enumerations. Arch. Math. Logic, 46(7-8):565–582, 2008.

[BGM17] Laurent Bienvenu, Noam Greenberg, and Benoit Monin. Continuous higher randomness. J. Math.

Log., 17(1):1750004, 53, 2017.

[BHW08] V. Brattka, P. Hertling, and K. Weihrauch. A tutorial on computable analysis. InNew computational paradigms, pages 425–491. Springer, New York, 2008.

[EG00] Y. Ershov and S. Goncharov.Constructive models. Siberian School of Algebra and Logic. Consultants Bureau, New York, 2000.

[Gao09] Su Gao.Invariant descriptive set theory, volume 293 ofPure and Applied Mathematics (Boca Raton).

CRC Press, Boca Raton, FL, 2009.

[GK02] S. Goncharov and J. Knight. Computable structure and antistructure theorems. Algebra Logika, 41(6):639–681, 757, 2002.

[GMKT] Noam Greenberg, Alexander G. Melnikov, Julia F. Knight, and Daniel Turetsky. Uniform procedures in uncountable structures.To appear.

[GR93] Xiaolin Ge and J. Ian Richards. Computability in unitary representations of compact groups. In Logical methods (Ithaca, NY, 1992), volume 12 ofProgr. Comput. Sci. Appl. Logic, pages 386–421.

Birkh¨auser Boston, Boston, MA, 1993.

[HK14] Kojiro Higuchi and Takayuki Kihara. On effectively closed sets of effective strong measure zero.Ann.

Pure Appl. Logic, 165(9):1445–1469, 2014.

[Jar74] Moshe Jarden. Algebraic extensions of finite corank of Hilbertian fields.Israel J. Math., 18:279–307, 1974.

[LR81] Peter La Roche. Effective Galois theory.J. Symbolic Logic, 46(2):385–392, 1981.

[McN15] Timothy H. McNicholl. A note on the computable categoricity of`^{p}spaces. InEvolving computability,
volume 9136 ofLecture Notes in Comput. Sci., pages 268–275. Springer, Cham, 2015.

[Mel] A. Melnikov. Computable topological groups and Pontryagin duality. To appear in Transactions of The American Mathematical Society.

[Mel13] Alexander G. Melnikov. Computably isometric spaces.J. Symbolic Logic, 78(4):1055–1085, 2013.

[MM] Alexander G. Melnikov and Antonio Montalb´an. Computable polish group actions.To appear.

[MN79] G. Metakides and A. Nerode. Effective content of field theory. Ann. Math. Logic, 17(3):289–320, 1979.

[MN13] Alexander G. Melnikov and Andr´e Nies. The classification problem for compact computable metric spaces. InThe nature of computation, volume 7921 ofLecture Notes in Comput. Sci., pages 320–328.

Springer, Heidelberg, 2013.

[MN16] Alexander G. Melnikov and Keng Meng Ng. Computable structures and operations on the space of continuous functions.Fund. Math., 233(2):101–141, 2016.

[MS] Timothy H. McNicholl and D. M. Stull. The isometry degree of a computable copy ofl^{p}.To appear.

[PER89] Marian B. Pour-El and J. Ian Richards.Computability in analysis and physics. Perspectives in Math- ematical Logic. Springer-Verlag, Berlin, 1989.

[Pon66] L. S. Pontryagin.Topological groups. Translated from the second Russian edition by Arlen Brown.

Gordon and Breach Science Publishers, Inc., New York-London-Paris, 1966.

[Rei08] Jan Reimann. Effectively closed sets of measures and randomness.Ann. Pure Appl. Logic, 156(1):170–

182, 2008.

[Sac90] Gerald E. Sacks. Higher recursion theory. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1990.

[Smi79] Rick L. Smith.THE THEORY OF PROFINITE GROUPS WITH EFFECTIVE PRESENTATIONS.

ProQuest LLC, Ann Arbor, MI, 1979. Thesis (Ph.D.)–The Pennsylvania State University.

[Smi81] Rick L. Smith. Effective aspects of profinite groups.J. Symbolic Logic, 46(4):851–863, 1981.