Multiple Permitting Notions For The Not Totally
ω-C.A. Computably Enumerable Degrees
Klaus Ambos-Spies
Universität Heidelberg
Department of Mathematics and Computer ScienceCiE 2023 - Batumi
Special Session on Classical Theories of Degrees
24 July 2023

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

1 / 36

Contents

Introduction: Permitting - its basic form and extensions
Array noncomputability - the first formalization of multiple permitting(The original definition, properties, and equivalent characterizations)Not totally ω-c.a. degrees - a stronger multiple permitting notion(Equivalent characterizations in terms of a.n.c. and multiply
permitting sets)
Concluding remarks

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

2 / 36

Introduction
Permitting - its basic form and some extensions

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

3 / 36

What is “Permitting”?

Permitting is a basic technique for constructing a computably
enumerable (c.e.) set B which is Turing reducible to a given c.e. set
A.
This is achieved by enumerating a new number x into B at a stages + 1 only if (for a given enumeration of A) a number ≤ x (or, moregenerally, ≤ f (x) for some computable function f ) enters A at stages + 1.
“straight permitting” (“f -bounded permitting”)
Obviously this ensures that B ≤T A (in fact, B ≤wtt A, and, in caseof straight permitting, even B ≤ibT A).

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

4 / 36

Typical applications of the Permitting Technique

We want to construct a c.e. set B Turing below a given c.e. set A
such that B has certain properties which (in part) can be ensured bymeeting positive requirements Pe (e ≥ 0) of the following type:
In order to meet Pe it suffices to pick a follower x (becoming awitness for the fact that Pe will be met). The follower may become“realized” at some stage. In this case the follower (or a certain
greater number) has to be enumerated into B.
In the presence of permitting, once x is realized we wait that A
permits x to enter B (and, if so, we put x into B). While waiting, we
iterate the attack on Pe with a new follower x 0 > x (and so on).

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

5 / 36

Which sets give Permitting?
In the above setting, any noncomputable c.e. set A will eventuallypermit.
So sets with properties which can be ensured by requirements of theabove described type can be found T-below (in fact, wtt-below or, incase of straight permitting, even ibT-below) any noncomputable c.e.
set.
Some classical examples:
For any noncomputable c.e. set A there is a simple set B ≤T A.
For any noncomputable c.e. set A there are Turing incomparable c.e.
sets B0 , B1 ≤T A (Muchnik).
I Any countable distributive lattice can be embedded into any proper
initial segment of the c.e. degrees (by an embedding that does notpreserve the least element).

I

I

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

6 / 36

Stronger forms of Permitting I: Almost-Everywhere andPrompt PermittingMore involved positive requirements or settings require stronger forms of
permitting in order to perform the construction below a given c.e. set A.
These stronger permittings, however, are given not by all sets. In fact, thesets giving such stronger permittings characterize important degree classes.
I

The requirement Pe is infinitary and requires that almost all numbers in
a computable ascending sequence x0 < x1 < x2 < . . . are enumerated
into B (“almost-everywhere permitting” – Martin, Yates, Cooper)
Corresponding permitting degrees: the high c.e. degrees (Martin)I

The follower has to be simultaneously permitted by the set A and someother noncomputable c.e. set (“prompt permitting” – Maass).
Corresponding permitting degrees: the noncappable c.e. degrees or,equivalently, the low-cuppable c.e. degrees (AS, Jockusch, Shore andSoare)

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

7 / 36

Stronger Forms of Permitting II: Multiple Permitting
Any follower x of a requirement Pe is associated with an entourage of≤ f (x) (larger) numbers (f a computable function) all of which needpermitting after becoming “realized” (“multiple permitting”)
Here f may be fixed or it may depend on the requirement (f = fe )The former case was discussed by Downey, Jockusch and Stob in 1990
(DJS1990) where it is argued that the sets and degrees giving this type of
permitting are the array noncomputable (a.n.c.) sets and their degrees,
respectively.
The latter case is treated in Downey, Greenberg and Weber (2007). In
contrast to DJS1990, however, only the degrees containing sets providing
the desired form of multiple permitting are described but the corresponding
sets are not characterized.
Here we will discuss these two types of multiple permitting.

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

8 / 36

Array noncomputability - the first formalization of multiple permitting(The original definition, properties, and equivalent characterizations)

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

9 / 36

Array Noncomputablity - Definition
A sequence F = {Fn }n≥0 of finite sets is a very strong array (v.s.a.) if(i) there is a computable function f such that f (n) is the canonical index
of Fn ,
(ii) Fm ∩ Fn = ∅ if m 6= n,(iii) 0S< |Fn | < |Fn+1 | for all n ≥ 0, and(iv) n≥0 Fn = ω.
A c.e. set A is F-array noncomputable (F-a.n.c.) if A is F-similar to any
c.e. set V , i.e.,∃∞ n (A ∩ Fn = V ∩ Fn )(equivalently, it suffices to require this for a single n).
A c.e. set A is array noncomputable (a.n.c.) if A is F-a.n.c. for some v.s.a.
F. And A is array computable (a.c.) otherwise.
A c.e. r-degree a is a.n.c. if there is an a.n.c. set in a. And a is a.c.
otherwise.
Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

10 / 36Why do array noncomputable sets multiply permit?
If (the entourage of) a follower x has to be permitted up to f (x)times then we choose a v.s.a. F of intervals Fn such that
|Fn | ≥ f (min Fn ) and choose the numbers x = min Fn as followers.
Then, whenever a member xm of the entourage of x needs permitting,
we enumerate the corresponding element ym of Fn into a “trigger set”
V . For any n sucht that A and V agree on Fn , this number ym has toenter A later thereby giving the required (straight) permitting.
NB: Actually, the a.n.c. sets provide more than the required permittings: if
we want A to change below x + 1 (for a straight permitting or below
f (x) + 1 for an f -bounded permitting) after a stage s then by putting x in
the trigger set V we actually achieve more, namely we make A to change onx. (I will come back to this.)

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

11 / 36

Basic Properties of the a.n.c. sets (DJS1990)
Array invariance up to wtt-equivalence: If F and F 0 are very strong arrays,
and A is F-a.n.c. then there is an F 0 -a.n.c. set B which is wtt-equivalent toA.
Failure of wtt-degree invariance: For any a.n.c. set A there is a c.e. set B
which is wtt-equivalent to A and not a.n.c.
Distribution of the array noncomputable T-degrees:
ANCT is closed upwards (in the u.s.l. of the c.e. degrees)
NonLow2 ⊂ ANCT
I ANC
T splits the jump classes Low2 \ Low1 (Downey 1993)
and Low1 as well as the classes Cap and NonCap
I There are a.c. T-degrees (a , a ) s.t. a ∨ a = 00
0 1
01
I No contiguous degree is a.n.c. (Downey 1993)
I

I

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

12 / 36

Simplicity Properties of the a.n.c. sets (DJS1990)
No a.n.c. set is dense simple (hh-simple, quasi-maximal, maximal).
No a.n.c. set is strongly h-simple (r-maximal, maximal)
Since DJS1990 also show that there is an a.n.c. finitely strongly h-simple (hence
h-simple, simple) set, the latter two results show which of the common simplicity
notions are compatible with array noncomputability:
r-maximal

sh-simple

fsh-simple
h-simplemaximalquasi-maximal

hh-simple

simpledense simple

Do the above negative results on the a.n.c. sets say that the corresponding
properties cannot be shared by any multiply permitting sets?

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

13 / 36

Multiply permitting vs. array noncomputability
In the abstract of DJS1990

it is said that the a.n.c. sets are precisely those sets which give multiple
permitting. As we have seen, however, the a.n.c. property might be a stronger
property. (Namely when we force an a.n.c. set A to permit x, we actually force x
itself into A.)
In order to decide whether the a.n.c. sets actually coincide with the multiply
permitting sets, we give a more faithful formalization of the latter notion andcompare it with array noncomputability.

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

14 / 36

The formal multiple permitting notion of AS2018
DEFINITION. Let A be a c.e. set, let {As }s≥0 be a computable enumeration ofA, let F = {Fn }n≥0 be a v.s.a., and let f be a computable function.
A is f -bounded F-permitting via {As } if, for any partial computable function ψ,∃∞ n ∀ x ∈ Fn (ψ(x) ↓ ⇒ A  f (x) + 1 6= Aψ(x)  f (x) + 1).
So, in order to force A to give f -bounded permittings, we define a partial
computable function ψ. Then, whenever we want A to f -permit some numberx ∈ Fn after some stage sx , we let ψ(x) = sx . For the infinitely many numbers n,such that A respects ψ on Fn , all corresponding requests will be fulfilled (i.e., A
will change on a number ≤ f (x) after stage sx ).
In particular, for f = id, we can force A to give straight permissions. (Recall thatin case of an F-a.n.c. set we obtained the corresponding permitting by
enumerating the number x in a trigger set V at stage sx thereby forcing x into A
later – provided that Fn is one of the intervals on which A and V agree.)

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

15 / 36

The formal multiple permitting notion of AS2018 (ctd.)
DEFINITION. Let A be a c.e. set, let {As }s≥0 be a computable enumeration ofA, let F = {Fn }n≥0 be a v.s.a., and let f be a computable function.
A is f -bounded F-permitting via {As } if, for any partial computablefunction ψ,∃∞ n ∀ x ∈ Fn (ψ(x) ↓ ⇒ A  f (x) + 1 6= Aψ(x)  f (x) + 1).
A is f -bounded F-permitting if A is f -bounded F-permitting via some {As };A is F-permitting if A is f -bounded F-permitting for some f ; and A is
multiply permitting if A is F-permitting for some F.
If A is f -bounded F-permitting for the identity function (f = id) then A is
straight F-permitting, and if A is straight F-permitting for some F then A
is straight multiply permitting. (Remark. These straight permitting notions
were not explicitly introduced in AS2018.)

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

16 / 36

Multiple permitting: basic properties
In AS2018 we have shown the following on our formal multiple permitting notion.
The notion is independent of the underlying enumerations: if A is f -bounded
F-permitting and {As }s≥0 is any computable enumeration of A, then A is
f -bounded F-permitting via {As }s≥0 .
The notion is independent of the underlying arrays: if A is multiply
permitting then, for any v.s.a. F, there is a computable function f = fF
such that A is f -bounded F-permitting. (In contrast, the a.n.c. sets are notarray invariant – though they are array invariant up to wtt-equivalence.)
The notion is wtt-invariant (in fact closed upward under ≤wtt ): If A is
multiply permitting, B is c.e., and A ≤wtt B then B is multiply permitting
too. (In contrast, the a.n.c. sets are not closed under wtt-equivalence.)
Relation to a.n.c.: The wtt-degrees of the a.n.c. and multiply permitting
degrees coincide. Moreover, any F-a.n.c. set is straight F-permitting, butthere are multiply permitting sets which are not a.n.c.
The question whether the a.n.c. sets coincide with the straight multiply permitting sets,
however, is not discussed in AS2018.

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

17 / 36Straight multiple permitting vs. array noncomputable
THEOREM (AS). Any multiply permitting set is straight multiply permitting(but, in general, not via the same v.s.a. F).
COROLLARY. There are straight multiply permitting sets which are arraycomputable. In fact, for any a.n.c. set A there is a wtt-equivalent straightmultiply permitting set which is not a.n.c.
So, up to wtt-equivalence, the array noncomputable sets and the (straight)
multiply permitting sets coincide, but the a.n.c. sets form a proper subclass of theclass of the straight multiply permitting sets which in turn coincides with theclass of the multiply permitting sets.
So if we prove results on degrees, it does not matter with which notion we work.
If we consider properties of sets, however, there might be a difference. By looking
at the simplicity properties of the (straight) multiply permitting sets we show thatsuch differences actually occur.

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

18 / 36

Simplicity properties of the multiply permitting sets
As mentioned before, Downey, Jockusch and Stob have completely analysed thesimplicity properties of the a.n.c. sets. In particular, they have shown thata.n.c. sets are not dense simple (hence not hh-simple and not maximal)
a.n.c. sets are not strongly h-simple (hence not r-maximal and not maximal)
The former extends to the multiply permitting sets (thereby giving a considerable
stronger result).
THEOREM (AS2018). No multiply permitting set is dense simple.
COROLLARY. No multiply permitting set (hence no a.n.c. set) is wtt-reducible to any
dense simple (hh-simple, maximal) set.
COROLLARY. Any high c.e. degree contains both, multiple permitting sets and notmultiply permitting sets.
The latter, however, does not extend to the multiply permitting sets.
THEOREM (Monath 2018) There is a multiply permitting r-maximal set.
Note that these results completely characterize the (common) simplicity properties thata multiply permitting set may have.
Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

19 / 36

Simplicity properties: a.n.c. vs. m.p. (summary)r-maximal

sh-simple

fsh-simple
h-simplemaximalquasi-maximal

hh-simple

simpledense simple

Simplicity properties compatible (incompatible) with array noncomputability

r-maximal

sh-simple

fsh-simple
h-simplemaximalquasi-maximal

hh-simple

simpledense simple

Simplicity properties compatible (incompatible) with multiply permitting

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

20 / 36

Alternative characterizations of the a.n.c. T-degrees
DJS1990 and DJS1996 have given the following two alternative characterizationsof the a.n.c. degrees. Both are based on an analysis of the complexity of thefunctions computable by sets of a.n.c. degree (with respect to growth rate andthe complexity of computable approximations of these functions in terms of theirmindchanges, respectively).
THEOREM (DJS1996). For a c.e. set A, the following are equivalent.
(i) degT (A) is a.n.c.
(ii) For any function h ≤wtt ∅0 there is a function g ≤T A which is not
dominated by h.
(Note that, by a classical result of Martin, there is a corresponding
characterization of the nonlow2 degrees where h ≤wtt ∅0 is replaced by h ≤T ∅0 .)DJS1996 use this equivalence to extend the notion of an a.n.c. degree toarbitrary degrees and show that it is a very useful tool in this extended
setting too.
Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

21 / 36

Alternative characterizations of the a.n.c. T-degrees (ctd.)

THEOREM (DJS1990). Let f be a strictly increasing computable function and
let A be a c.e. set. The following are equivalent.
(i) degT (A) is a.n.c.
(ii) There is a set B ≤T A such that B is not f -computably approximable.
(And similarly, for functions g in place of sets B.)
Here a function g is f -computably approximable (f -c.a.) if there is a computableapproximation g (−, −) of g such that|{s : g (x, s + 1) 6= g (x, s)}| ≤ f (x).

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

22 / 36

A.n.c. T-degrees vs. a.n.c. and m.p. sets
The preceding characterizations of the a.n.c. degrees proved to be very useful and led to
new related notions which turned out to be as important (maybe even more important)tools for the study of the c.e. degrees and sets, and there are many applications of arraynoncomputability in the literature working with these characterizations.
Still, sometimes, working with these characterizations is rather tedious, and working
with the multiply permitting (or a.n.c.) sets may not only simplify the arguments but at
the same time may also give some stronger results.
Assume that we want to show that we can find a c.e. set A with a certain property P in
any given a.n.c. degree a where P can be forced by a priority argument. Then a typical
proof in the literature using the degree characterization of the a.n.c. degrees repeats thepriority argument for constructing a P-set A and combines it with the necessary
permitting (which is somewhat implicitly given by the degree characterization) to makeA ≤T a together with some coding to make a ≤T A. In particular, the proof is synthetic(constructive).
In many cases, using the same basic ideas, we can show that any m.p. set A has thisproperty P. This is done by an analytic (modular) proof for which it suffices to consider
a single requirement of the construction of a P-set in isolation (so the tedious parts ofthe combinatorics of the priority proof and the coding become completely superfluous
and the permitting part becomes simplified). Moreover, since the class of the m.p. sets
is closed upwards under wtt-reducibility in the c.e. sets we get a stronger result.
Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

23 / 36

Not totally ω-c.a. degrees - a stronger multiple permitting notion(Equivalent characterizations in terms of a.n.c. and multiply permitting
sets)

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

24 / 36

A stronger variant of multiple permitting

The array noncomputable sets and the multiply permitting sets have been designed togive the required permitting in a priority construction where, in order to meet arequirement Re , a sequence of up to f (x) numbers has to be permitted where thecomputable function f does not depend on the requirement. In many constructions,however, there is such a dependence. So the function f has to be replaced by asequence of computable functions fe , hence a stronger multiple permitting is needed.
Following a suggestion of Joe Miller, Downey, Greenberg and Weber (2007) introduced
the class of the not totally ω-c.a. degrees which contain the sets with this stronger
permitting property. Their definition of this class is obtained by adjusting thecharacterization of the a.n.c. degrees in terms of the mind-change complexity of thecomputed functions.
DEFINITION (DGW2007). A c.e. degree a is not totally ω-c.a. if there is a functiong ≤T a that is not ω-c.a., i.e., that is not f -c.a. for any computable function f .

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

25 / 36

Some basic facts on the not totally ω-c.a. degrees(DGW2007) The class of the n.t.ω-c.a. degrees is properly contained in the classof the a.n.c. degrees.
(DGW2007) The class of the n.t.ω-c.a. degrees is closed upwards in the c.e.
degrees, it properly contains the class of the c.e. nonlow2 degrees is properly
contained in the class of the n.t.ω-c.a. degrees, ...
(DGW2007) The class of the n.t.ω-c.a. degrees is definable: a c.e. degree abounds a critical triple iff a is n.t.ω-c.a.
Related to this AS and Losert (ta) have shown that the lattice S7 can beembedded in the c.e. degrees below a c.e. degree a iff a is n.t.ω-c.a. For
comparison, the nonmodular 5-element lattice N5 can be embedded below any c.e.
degree a > 0, whereas - as shown by Downey and Greenberg (2020) - bounding
the embedding of the nondistributive modular 5-element lattice M5 requires a still
stronger permitting notion, namely a set of not totally < ω ω -c.a. degree.
(Barmpalias, Downey, Greenberg 2010) A c.e. degree a contains a c.e. set which is
not wtt-reducible to any h-simple set iff a is n.t.ω-c.a.

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

26 / 36

Are there universally a.n.c. sets?

In case of the a.n.c. degrees we can single out the sets which give the desired form of
permitting, namely the a.n.c. sets (up to wtt-equivalence) and the multiply permitting
sets. Can we do the same for the stronger multiple permitting pertaining to then.t.ω-c.a. degrees?
Since the lengths of the members in a v.s.a. F correspond to the number f (x) ofpermissions needed, a set A which is F-a.n.c. for all very strong arrays F will have thedesired permitting power. Unfortunately, however, as observed by DJS1990 already, suchsets do not exist.
For guaranteeing the desired uniform multiple permitting, however, sets which areuniversally a.n.c. in a weaker sense suffice. Such sets were introduced by AS and Losert.

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

27 / 36

Some notions of universally a.n.c. sets
DEFINITION (AS and Losert (ta)).
(i) Let {F e }e≥0 be a standard numbering of the very strong arrays (together with thefinite initial segments of such arrays). A c.e. set A is uniformly universally a.n.c. if, forany e such that F e is a v.s.a., Ahei = {x : he, xi ∈ A} is F e -a.n.c.
(ii) A c.e. set A is universally a.n.c. if, for any v.s.a. F, there is a number e such that
Ahei is F-a.n.c.
(iii) A c.e. set A has the uniform bounding property if there is a s.i. computable function
f such that, for any v.s.a. F there is an F-a.n.c. set B such that B ≤f −T A.
THEOREM (AS and Losert (ta)). The above notions coincide up to wtt-equivalence.
Moreover the c.e. degrees which contain sets with these properties are just the n.t.ω-c.a.
degrees.
Moreover, obviously, the class of the sets with the uniform bounding property is closed
upward under wtt-reducibility in the c.e. sets (whereas the other two notions are not
wtt-invariant).

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

28 / 36

How about uniformly multiply permitting sets?
As mentioned before, if A is multiply permitting then, for any v.s.a. F, there is acomputable function f such that A is f -bounded F-permitting. In general,
however, this function f depends on the chosen array. For obtaining the desired(n.t.ω-c.a.)-permitting, we need that this bound is array-independent.
DEFINITION (AS and Losert (ta)). A c.e. set A is uniformly multiply permitting
if there is a computable function f such that A is F-permitting via f for all v.s.a.s
F.
THEOREM (AS and Losert (ta)). A c.e. set is uniformly multiply permitting iff it
is wtt-equivalent to some set with the uniform bounding property. Hence a c.e.
degree a is uniformly multiply permitting iff a is not totally ω-c.a. Moreover, theclass of the uniformly multiply permitting sets is closed upwards under
wtt-reducibility in the c.e. sets.

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

29 / 36

Working with uniformly multiply permitting sets

Just as in case of the a.n.c. degrees, working with uniformly multiply permitting
sets in place of the degree characterization of the not totally ω-c.a. degrees cangreatly simplify some of the proofs and – at the same time – strengthen the
results. Again constructive proofs can be replaced by analytic ones thereby
avoiding the machinery of priority arguments and coding and simplifying thepermitting part.
In the following we give an example (more examples can be found in AS and
Losert (ta) and AS, Losert and Monath (ta)).

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

30 / 36

Uniformly multiply permitting sets: a sample application
We give a greatly simplified proof of Barmpalias, Downey and Greenberg’s result of 2010that any totally ω-c.a. degree a contains a c.e. set which is not wtt-reducible to any
h-simple set.
THEOREM (AS-Losert (ta)). No uniformly multiply permitting set is hypersimple.
By wtt-upward closure of the uniformly multiply permitting sets we get the desired result.
COROLLARY (AS-Losert (ta)). No uniformly multiply permitting set is wtt-reducible toany hypersimple set. (Hence any not totally ω-c.a. degree a contains a c.e. set which is
not wtt-reducible to any h-simple set.)
Since (by Dekker) any c.e. degree contains an h-simple set, we further get a general
inhomogeneity result in this setting (contrasting a homogeneity theorem of Monath forthe multiply permitting sets).
COROLLARY (AS-Losert (ta)). Any not totally ω-c.a. degree a contains a c.e.
wtt-degree which is not uniformly multiply permitting.

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

31 / 36

U.m.p. sets: a sample application (Proof of the theorem)
Let A be h-simple and let f be a strictly increasing computable function f . It suffices todefine a v.s.a. F = {Fn }n≥0 such that A is not f -bounded F -permitting.
Let F̂ = {F̂m }m≥0 be the unique v.s.a.i. such that F̂0 = {0} and, for any m ≥ 0,
S`
r`
F̂m+1 = F̂m+1∪ F̂m+1
where |F̂m+1| = | m0 ≤m F̂m0 | + 1 andr`
max F̂m+1= f (max F̂m+1) + 1.

Now, since A is h-simple, there are infinitely many m such that F̂m ⊆ A. So, since A isc.e., we get an infinite computable sequence 0 =< m0 < m1 < m2 < . . . such thatF̂mn ⊆ A (for all n ≥ 0).
S
S
Let F0 = m≤m0 F̂m and Fn+1 = mn <m≤mn+1 F̂m .
Note, that for any n, Fn = Ln ∪ Mn ∪ Rn such that |Mn | > |{x : x < min Mn }|,f (max Mn ) < max Rn , and Mn ∪ Rn ⊆ A.
It remains to show that A is not f -bounded F -permitting. For this sake it suffices todefine a partial computable function ψ such that for all n ≥ 0,(∗) ∃x ∈ Fn (ψ(x) ↓ & Aψ(x)  f (x) + 1 = A  f (x) + 1).
Given n, define ψ on Fn as follows: Wait for s0 such that Mn ∪ Rn ⊆ As0 then we use thenumbers x ∈ Mn in order of magnitude to attack (∗) by letting ψ(x) be the current stage
where we start a new attack when A repels the previous attack. Since the only numbers≤ f (max Mn ) which are not in As0 are less than min Mn and since there are more numbers
in Mn than to the left of it, eventually we succeed.
Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

32 / 36

Concluding Remarks

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

33 / 36

Summary
We looked at the a.n.c. degrees and the not totally ω-degrees, i.e., the classes ofdegrees which contain c.e. sets which provide multiple permittings of computablybounded finite sequences of numbers where in the first case the computable boundmust not depend on requirements whereas in the second case such a dependance
may exist.
For either of these degree classes we isolated the c.e. sets which give the desired
permittings, namely the multiply permitting sets and the uniformly multiply
permitting sets, respectively. In the former case, a sufficient condition for providing
the desired permittings were known before, namely the a.n.c. sets. In the lattercase no related notions had been introduced previously.
In either case we have shown that our formal multiple permitting notion is upward
closed under wtt-reducibility in the c.e. sets.
We have explained the usefulness and advantages of our formal multiple
permitting notions, in particular for proving (and extending) results dealing withstrong reducibilities or structural properties of sets involving multiple permittings.

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

34 / 36

An outlook
The work we have presented might be extended in two directions:
The a.n.c. and the not totally ω-c.a. degrees are only the lowest two levels of the
Downey-Greenberg Hierarchy (2020) of the not totally α-c.a. degrees (α < ε0 )where the complexity of a c.e. degree a is measured in terms of the mind-change
complexity of the computable approximations of the functions ≤T a.
It seems that the question of the existence of corresponding multiply-permittingset notions for such higher levels has not yet been explored.
Plain permittings are provided not only by c.e. sets but also by almost-c.e. sets
(i.e., left-c.e. reals). These sets (reals) play an important role in computable
analysis and algorithmic randomness. So it is natural to ask whether (or how) thenotion of an a.n.c. or (uniformly) permitting set can be adjusted to these larger
class of sets.
A definition of array noncomputability for the almost-c.e. sets has been proposed(and applied) by AS, Fang, Losert, Merkle and Monath, and the notion of auniversally a.n.c. almost-c.e. set pertaining to the not totally-ω-c.a. degrees has
been introduced (and applied) by AS, Losert and Monath (see AS, Losert, Monath[ta]).
Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

35 / 36

THANK YOU!

Klaus Ambos-Spies (Heidelberg University) Multiple Permitting & Not Totally ω-C.A.

CiE 2023 - Batumi

36 / 36