• No results found

The main result of the paper says that there exists an effectively closed presentation ofZ2which is not the automorphism group of any computable structureM


Academic year: 2022

Share "The main result of the paper says that there exists an effectively closed presentation ofZ2which is not the automorphism group of any computable structureM"


Full text




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 ofZ2which 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 Σ11 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.



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 subgroupGofSiseffectively closed (or Π01for short) if there is an effectively closed subset P of ωω such that G =P ∩S. An effectively closed presen- tation, or a Π01-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 ofSwitnessing 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∼Gwill in fact becomputable. We approach the question “how complicated can∼Gbe 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 Σ11 groups,∼Gis Σ11; 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 Σ11, 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 Π01 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 ofSin 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 Π01if 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 Π01-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∩Sbelongs 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 ofSthat 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 00-computable inverse systemF0 ←F1 ←F2. . ., with surjective maps, whose limit is isomorphic to P.

For a set S of prime numbers let

PS = Y



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 ifPS has a computable Polish presentation thenS is Σ02. To see this, given such a presentation of PS, by Fact 2.1, we produce a 00-computable inverse system rep- resenting the group. By [Mel, Thm.1.9] we can use this to uniformly produce a 00-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 00-computable presentation of L

p∈SZp we can 00-computably list the prime orders of elements of the group, showing thatS is Σ02.

So it suffices, given a Π02-complete setS of primes, to build a computable structureM such that Aut(M) is isomorphic to PS. 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,

xp0−xp1−. . .−xpp−1−xp0 and every node in the loop will have a [finite or infinite] chain

xpi −cpi,1−cpi,2−. . .

attached to it. The length of the chain depends on our approximation for the Π02 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 xp0, which could be any xpi.

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

p∈SAut(Cp)∼= PS. 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 Cp, the sub-basic clopen sets are determined by stating finitely many values for the


Proof of Theorem 0.3(2). LetP be a computable Polish profinite group. We need to produce a Π01 presentation of P. By Fact 2.1, there is a 00-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 00-computable fieldKand a 00-computable subfieldN ofKsuch that Aut(K/N)∼=P. Our first step is to obtain a 00-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 00-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 Σ02set. 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 ∈ An we add a new infinite set C¯aP of elements (these are pairwise disjoint). We link these “blow ups” of tuples by adding the relation y ∈ CxP¯ to B. Next, for every tuple ¯a ∈ An we define a linear ordering LP¯a of Ca¯P, which is isomorphic to ω if P(¯a) holds in A, and isomorphic to ω2 otherwise. We add the relation y1, y2 ∈ Cx¯P&y1 <LP


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¯aP is mapped to some p ∈ C¯bP, 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 Π01presentation 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 Me. 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→¯binMe, 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, butMemust (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 (Me)e∈ω of all (partial) computable structures upon the do- main ω. We construct a Π01-subgroup P of the standard copy of S, and meet the require- ments:

P 6= Aut(Me), 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 Meis 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 N1. Forbid all basic open neigh- bourhoods that do not containIdω and are disjoint formN1 and N2.

(4) Wait for Me 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(Me), as witnessed byφ. In this case Aut(Me)∩N1 =∅. Proceed as above to (eventually) completely forbidN2and keep all weaker priority actions restricted toN1. 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. SupposeMe is total, and ¯xn6→x(n¯ + 1) Aut(Me) . 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 Me 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 ans0 ≥sand a nice neighbourhoodNesuch that all the weaker priority strategies (j > e) perform their actions withinNe.

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 N1 forever, or it may eventually switch toN2 and

never change the neighbourhood again.

The basic module of the eth strategy makes sure that no element in the eventually stable neighbourhood Ne can be in Aut(Me) if Me is total. Note that, whenever a strategy is initialised it can pick a nice neighbourhood within the part ofSthat 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τedetermined by its stableNeis 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 neighbourhoodNeis at most 2−e, and Ne+1 ⊂Ne for every e. It follows that the intersection of all these eventually stable Ne is a singleton whose only element is the limit of the ∆02 sequence (τe)e∈ω. The singleton describes the only non-Id element Θ of the Π01 set P that we end up with. Note that τe2 =Idsupp(τe),

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


4. Discrete Π01-presented groups and oligomorphic groups

We know that Z2 has a complicated Π01 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 Π01-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ωγ+1if a Σ0γfact holds, and a copy ofωγ+2otherwise; 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. Σ11 subsets ofωω have the perfect set property in a strongly effective way: if a Σ11 set A does not have a perfect subset then all elements ofA are hyperarithmetic, and so by Spector’s Σ11 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 Π02 subset ofωω. If all elements of Gare 0(γ)-computable, then 0(γ+2)computes a listing of the elements ofG; it then follows that∼Gis 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 mapgGto 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 ofSsuch that for everynthere are only finitely manyG-orbit equivalence classes ofn-tuples.

We construct of Σ11, closed oligomorphic subgroup ofSfor which∼Gis not hyperarithmetic.

We work in the admissible structure Lωck

1 . The idea is to use a cofinal ω-sequence hαni inωck1 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αni 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 = hkni 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 ai=bi mod 2km. 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 ¯a0 of ¯aand ¯b0 of ¯bchosen in the same way, ¯a0k¯b0.

• ∼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 Gk 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 ofGk, 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αnin<ω which is cofinal inω1ck; see [Sac90] for an excellent exposition of higher recursion theory. In fact,hαnihas afinite-change approximation (see [BGM17]): there is a ∆1(Lωck

1 ) array (that is, aLωck

1 -computable array)hαn,sin<ω,s<ω1ck such that writingαn,ωck 1

forαn, we have:

• For all limit ordinalss≤ωck1 , for all n,αn,s = limt→sαn,t; and

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

kn,s= X


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

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


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


kn,t refines the equivalence relation∼kn,s. This shows that∼k is Π1(Lωck

1 ), that is, it is Σ11. It follows that Gk is Σ11 as well.

The final relation ∼k=∼k


is not hyperarithmetic: we can see that ω1k > ω1ck, as in an effective fashion over Lωk

1 [∼k] we can recover hαni: for alln < ω and s < ω1ck, if the number of ∼ks-equivalence classes of n-tuples is the same as that of ∼k, thenαnn,s.


[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`pspaces. 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 oflp.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.


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.


Related documents

(To say z is a density-one point means that every effectively closed class containing z has density one at z. functions are, essentially, the variation functions of

All known examples of the structures of finite computable dimension k &gt; 1 are not the prime models of their theories. Hence it was an open problem as to whether there exists a

One may restrict attention to the groups that have a strictly finite presentation: a profinite (or pro-p) group G has this property if it has a finite presentation as a profinite

Specker showed that the original statement in Ramsey’s theorem cannot be made effective: there exists a computable standard partition of a computable copy of ω such that no

A computable structure S is relatively computably categorical if between any two (possibly noncomputable) presentations A and B of S, there is an isomorphism computable in deg(A)

Thinking combinatorially (abstractly), an n-polytope P is a poset with properties modelled on those of the face lattice of a convex n-polytope.. Symmetry is described by Aut(P ),

In any consistent, effectively generated formal theory including elementary arithmetic there exists a sentence of arithmetic which is neither provable nor disprovable.... Two

A computably metrized space is called e↵ectively compact if there exists a computable function that, given n, outputs the index of a finite tuple of basic open balls of radii &lt; 2

That makes Γ a Cayley graph C (G , S ), with inverse-closed connection set S Difficulty: Any group automorphism of G leaving the connection set S invariant induces an extra

A recursive presentation of a profinite group P is a uniformly computable inverse system of finite groups, with surjective homomor- phisms, whose inverse limit is isomorphic to P..

There is an oracle A such that every nonempty higher A-effectively closed set contains some sequence which is not higher A-ML random.. Again, the A constructed is higher ∆ 0 2

Since closed surfaces are easily understood given a triangulation, we also get that any two presentations, as topological spaces, of a closed surface are arithmetically

We of course require the standard group operations to be computable with respect to the computable dense set, but this is not what makes the case of Polish groups different from

Having an automatic presentation is a very strong condition on a structure; for instance, it implies that the structure is computable in linear time and that the first-order theory

The first part of Theorem 1.7 says that both profinite and connected compact groups admit very low complexity listings among all computable Polish groups, but these lists

Goncharov and Knight [GK02] showed that the class of all computable equivalence struc- tures with infinitely many infinite classes has a Friedberg enumeration, and noted that

In the last section we will construct an FA presentation of the group ( Z , +) 2 which is new in the sense that any nontrivial cyclic subgroup in that presentation is not

Abstract We describe a strongly minimal theory S in an effective language such that, in the chain of countable models of S, only the second model has a computable presentation..

It is not hard to show that every (Turing) computable linear ordering admits a polynomial-time presentation [Gri90], and the same can be said about any torsion-free abelian

An example is given of a (unary) permutation algebra that is automatic as a relational structure, but has no presentation as a sequential automatic algebra.. Finally, we stress that

We show for each positive integer a that, if M is a minor-closed class of matroids not containing all rank-(a + 1) uni- form matroids, then there exists an integer c such that

The second main result says that there is a Turing computable embedding of the class of rank-homogeneous trees into the class of torsion-free Abelian groups.. The third main result

STRONG KOCHEN-SPECKER THEOREM The incompatibility between the assumptions (1) and (2) is not maximal in the following sense: For any set of observables there exists an