# Maximal towers and ultrafilter bases
in computability theory

Steffen Lempp  ,  Joseph S. Miller  ,
André Nies  and  Mariya I. Soskova  Department of Mathematics, University of
Wisconsin–Madison, 480 Lincoln Drive, Madison, WI 53706, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Department of
Computer Science, University of Auckland, Private bag 92019, Auckland, New
Zealand<EMAIL_ADDRESS>
###### Abstract.

The tower number $\mathfrak{t}$ and the ultrafilter number $\mathfrak{u}$ are
cardinal characteristics from set theory, They are based on combinatorial
properties of classes of subsets of $\omega$ and the almost inclusion relation
$\subseteq^{*}$ between such subsets. We consider analogs of these cardinal
characteristics in computability theory.

We say that a sequence ${\left\langle{G_{n}}\right\rangle}_{n\in\omega}$ of
computable sets is a _tower_ if $G_{0}=\omega$, $G_{n+1}\subseteq^{*}G_{n}$,
and $G_{n}\smallsetminus G_{n+1}$ is infinite for each $n$. A tower is
_maximal_ if there is no infinite computable set contained in all $G_{n}$. A
tower ${\left\langle{G_{n}}\right\rangle}_{n\in\omega}$ is an _ultrafilter
base_ if for each computable $R$, there is $n$ such that $G_{n}\subseteq^{*}R$
or $G_{n}\subseteq^{*}\overline{R}$; this property implies maximality of the
tower. A sequence ${\left\langle{G_{n}}\right\rangle}_{n\in\omega}$ of sets
can be encoded as the “columns” of a set $G\subseteq\omega$. Our analogs of
$\mathfrak{t}$ and $\mathfrak{u}$ are the mass problems of sets encoding
maximal towers, and of sets encoding towers that are ultrafilter bases,
respectively. The relative position of a cardinal characteristic broadly
corresponds to the relative computational complexity of the mass problem. We
use Medvedev reducibility to formalize relative computational complexity, and
thus to compare such mass problems to known ones.

We show that the mass problem of ultrafilter bases is equivalent to the mass
problem of computing a function that dominates all computable functions, and
hence, by Martin’s characterization, it captures highness. On the other hand,
the mass problem for maximal towers is below the mass problem of computing a
non-low set. We also show that some, but not all, noncomputable low sets
compute maximal towers: Every noncomputable (low) c.e. set computes a maximal
tower but no 1-generic $\Delta^{0}_{2}$-set does so.

We finally consider the mass problems of maximal almost disjoint, and of
maximal independent families. We show that they are Medvedev equivalent to
maximal towers, and to ultrafilter bases, respectively.

###### Key words and phrases:

sequences of computable sets, mass problems, Medvedev reducibility, cardinal
characteristics, highness, ultrafilters

###### 2020 Mathematics Subject Classification:

Primary 03D30

Lempp was partially supported by Simons Collaboration Grant for Mathematicians
#626304. Miller was partially supported by grant #358043 from the Simons
Foundation. Nies was partially supported by the Marsden fund of New Zealand,
grant 19-UOA-346. Soskova was partially supported by NSF Grant DMS-1762648.
The authors thank Jörg Brendle and Noam Greenberg for helpful discussions
during a workshop at the Casa Matemática Oaxaca in August 2019, where this
research received its initial impetus.

###### Contents

  1. 1 Introduction
  2. 2 Basics of the mass problems $\mathcal{T}_{\mathbb{B}}$
  3. 3 Complexity of $\mathcal{T}$ and of $\mathcal{U}$
  4. 4 Maximal independent families in computability
  5. 5 The co-computably enumerable case
  6. 6 Ultrafilter bases for other Boolean algebras

##  1\. Introduction

Cardinal characteristics measure how far the set-theoretic universe deviates
from satisfying the continuum hypothesis. They are natural cardinals greater
than $\aleph_{0}$ and at most $2^{\aleph_{0}}$. For instance, the _bounding
number_ $\mathfrak{b}$ is the least size of a collection of functions
$f\colon\omega\to\omega$ such that no single function dominates the entire
collection.111This is less commonly, but perhaps more sensibly, called the
_unbounding number_. Related is the _dominating number_ $\mathfrak{d}$, the
least size of a collection of functions $f\colon\omega\to\omega$ such that
every function is dominated by some function in the collection. Here, for
functions $f,g\colon\omega\to\omega$, we say that $g$ _dominates_ $f$ if
$g(n)\geq f(n)$ for sufficiently large $n$. An important program in set theory
is to prove less than or equal-relations between characteristics in ZFC, and
to separate them in suitable forcing extensions.

Analogs of cardinal characteristics in computability theory were first studied
by Rupprecht [14, 15] and further investigated by Brendle, Brooke-Taylor, Ng,
and Nies [2]. An article by Greenberg, Kuyper, and Turetsky [7], in part based
on Rupprecht’s work, provides a systematic approach to the two connected
settings of set theory and computability, at least for certain types of
cardinal characteristics. The relevant characteristics are given by binary
relations, such as the domination relation $\leq^{*}$ between functions; their
computability-theoretic analogs are ordered by reducibilities that measure
relative computability. A well understood example of this is how the relation
$\leq^{*}$ gives rise to the bounding number $\mathfrak{b}(\leq^{*})$ and the
dominating number $\mathfrak{d}(\leq^{*})$, and their analogs in
computability, which are highness and having hyperimmune degree. A general
reference in set theory is the survey paper by Blass [1]. The recent brief
survey by Soukup [18] contains a diagram displaying the ZFC inequalities
between the most important characteristics in this setting, along with
$\mathfrak{b}(\leq^{*})$ and $\mathfrak{d}(\leq^{*})$.

In this paper, we consider cardinal characteristics that do not fit into the
framework of Rupprecht, and Greenberg et al. [7]. In particular, we initiate
the study of the computability-theoretic analogs of the ultrafilter, tower,
and independence numbers. These characteristics are defined in the setting of
subsets of $\omega$ up to almost inclusion $\subseteq^{*}$; we give
definitions below.

The _ultrafilter number_ $\mathfrak{u}$ is the least size of a subset of
$[\omega]^{\omega}$ with upward closure a nonprincipal ultrafilter on
$\omega$. We note that one cannot in general require here that the subset is
linearly ordered by $\subseteq^{*}$. Recall that an ultrafilter $F$ on
$\omega$ is a $P$-point if for each partition
${\left\langle{C_{n}}\right\rangle}$ of $\omega$ such that $C_{n}\not\in F$
for each $n$, there is $A\in F$ such that $C_{n}\cap A$ is finite for each
$n$. An ultrafilter with a linear base is a $P$-point. Shelah (see Wimmers
[19]) has shown that the non-existence of $P$-points is consistent with ZFC,
so it is consistent that a version of $\mathfrak{u}$ relying on linear bases
would be undefined.

The _tower number_ $\mathfrak{t}$ is the minimum size of a subset of
$[\omega]^{\omega}$ that is linearly ordered by $\subseteq^{*}$ and cannot be
extended by adding a new element below all given elements. To define the
_pseudointersection number_ $\mathfrak{p}$, the requirement in the definition
of towers that the sets in the class be linearly ordered under $\subseteq^{*}$
is weakened to requiring that every finite subset of the class has an infinite
intersection. So, trivially, $\mathfrak{p}\leq\mathfrak{t}$. In celebrated
work, Malliaris and Shelah [12] showed (in ZFC) that
$\mathfrak{p}=\mathfrak{t}$ (see also [18]). It is not hard to see that ZFC
proves $\mathfrak{t}\leq\mathfrak{u}$. It is consistent that
$\mathfrak{t}<\mathfrak{u}$ (see [1] for both statements).

A class $\mathcal{C}$ of subsets of $\omega$ is _independent_ if any
intersection of finitely many sets in $\mathcal{C}$ or their complements is
infinite. The _independence number_ $\mathfrak{i}$ is the least cardinal of a
maximal independent family. There has been much work recently on
$\mathfrak{i}$ in set theory, in particular, the descriptive complexity of
maximal independent families, such as in Brendle, Fischer, and Khomskii [3].

###  1.1. Comparing the complexity of the analogs in computability

The main setting for our analogy is given by the Boolean algebra of computable
sets modulo finite differences. We consider maximal towers, the closely
related maximal almost disjoint sets, and thereafter ultrafilter bases and
maximal independent sets. As already demonstrated in the above-mentioned
papers [14, 15, 2, 7], the relative position of a cardinal characteristic
tends to correspond to the relative computational complexity of the associated
class of objects.

Note that the usual formal definitions of computation relative to an oracle
only directly apply to functions $f\colon\omega\to\omega$, and to subsets of
$\omega$ (simply called sets from now on, and identified with their
characteristic functions). The complexity of other objects is studied
indirectly, via names that are functions on $\omega$ giving discrete
representations of the object in question. A particular choice of names has to
be made. For instance, real numbers can be named by rapidly converging Cauchy
sequences of rational numbers.

The witnesses for cardinal characteristics are always uncountable. In
contrast, in our setting, the analogous objects are countable. They will be
considered as sequences of sets rather than unordered collections. For, a
single set $X$ can be used as a name for such a sequence of sets: Let
$X^{[n]}$ denote the “column” $\\{u\colon\langle u,n\rangle\in X\\}$.222For
definiteness, we employ the usual computable Cantor pairing function $\langle
x,n\rangle$. Note that $\langle x,n\rangle\geq x,n$. This property is useful
in simplifying notation in some of the constructions below. To every set $X$,
we can associate a sequence ${\left\langle{X_{n}}\right\rangle}_{n\in\omega}$
in a canonical way by setting $X_{n}=X^{[n]}$. (When introducing terminology,
we will sometimes ignore the difference between
${\left\langle{X_{n}}\right\rangle}_{n\in\omega}$ and $X$.) An alternate
viewpoint is that a set $X$ is a name for the unordered collection of sets in
its coded sequence. Although such a name includes more information than is in
the unordered family, this information is suppressed when we quantify over all
names; our results can be read in this context.

With this naming system, one can now use sequences as oracles in computations.
We view the combinatorial classes of sequences as mass problems. To measure
their relative complexity, we compare them via _Medvedev reducibility_
$\leq_{s}$: Let $\mathcal{C}$ and $\mathcal{D}$ be sets of functions on
$\omega$, also known as _mass problems_. We say that $\mathcal{C}$ is Medvedev
reducible to $\mathcal{D}$ and write $\mathcal{C}\leq_{s}\mathcal{D}$ if there
is a Turing functional $\Theta$ such that $\Theta^{g}\in\mathcal{C}$ for each
$g\in\mathcal{D}$. Less formally, we say that functions in $\mathcal{D}$
uniformly compute functions in $\mathcal{C}$. We will also refer to the weaker
_Muchnik reducibility_ : $\mathcal{C}\leq_{w}\mathcal{D}$ if each function in
$\mathcal{D}$ computes a function in $\mathcal{C}$.

With subsequent research in mind, we will set up our framework to apply to
general countable Boolean algebras rather than merely the Boolean algebra of
the computable sets. Throughout, we fix a countable Boolean algebra
$\mathbb{B}$ of subsets of $\omega$ closed under finite differences. Our basic
objects will be sequences of sets in $\mathbb{B}$. We will obtain meaningful
results already when we fix a countable Turing ideal $\mathcal{I}$ and let
$\mathbb{B}$ be the sets with degree in $\mathcal{I}$. While we mainly study
the case when $\mathbb{B}$ consists of the computable sets, in Section 6, we
briefly consider two other cases: the $K$-trivial sets and the primitive
recursive sets.

###  1.2. The mass problem $\mathcal{T}_{\mathbb{B}}$ of maximal towers

######  Definition 1.1.

We say that a sequence ${\left\langle{G_{n}}\right\rangle}_{n\in\omega}$ of
sets in $\mathbb{B}$ is a $\mathbb{B}$-_tower_ if $G_{0}=\omega$,
$G_{n+1}\subseteq^{*}G_{n}$, and $G_{n}\smallsetminus G_{n+1}$ is infinite for
each $n$. If $\mathbb{B}$ consists of the computable sets, we use the term
_tower of computable sets_.

######  Definition 1.2.

We say that a function $p$ is _associated with_ a tower $G$ if $p$ is
increasing and $p(n)\in\bigcap_{i\leq n}G_{i}$ for each $n$.

The following fact is elementary.

######  Fact 1.3.

A tower $G$ uniformly computes a function $p$ associated with it.

###### Proof.

Let $\Phi$ be the Turing functional such that $\Phi^{G}(0)=\min(G_{0})$, and
$\Phi^{G}(n+1)$ is the least number in $\bigcap_{i\leq n+1}G_{i}$ greater than
$\Phi^{G}(n)$. This $\Phi$ establishes the required uniform reduction. ∎

######  Definition 1.4.

Given a countable Boolean algebra $\mathbb{B}$ of sets, the mass problem
$\mathcal{T}_{\mathbb{B}}$ is the class of sets $G$ such that
${\left\langle{G_{n}}\right\rangle}_{n\in\omega}$ is a $\mathbb{B}$-tower that
is _maximal_ , i.e., such that for each infinite set $R\in\mathbb{B}$, there
is $n$ such that $R\smallsetminus G_{n}$ is infinite.

Clearly, being maximal implies that no associated function is computable. In
particular, a maximal tower is never computable. (Note that our notion of
maximality only requires that the tower cannot be extended from below, in
keeping with our set-theoretic analogy.)

###  1.3. The mass problem $\mathcal{U}_{\mathbb{B}}$ of ultrafilter bases

We now define the mass problem $\mathcal{U}_{\mathbb{B}}$ corresponding to the
ultrafilter number. Since all filters of our Boolean algebras are countable,
any base will compute a linearly ordered base by taking finite intersection.
So we can restrict ourselves to linearly ordered bases. This is not always
possible in the set theory setting, as discussed in the introduction.

######  Definition 1.5.

Given a countable Boolean algebra $\mathbb{B}$ of sets, let
$\mathcal{U}_{\mathbb{B}}$ be the class of sets $F$ such that $F$ is a
$\mathbb{B}$-tower as in Definition 1.1 and for each set $R\in\mathbb{B}$,
there is $n$ such that $F_{n}\subseteq^{*}\overline{R}$ or
$F_{n}\subseteq^{*}R$. We will call a set $F$ in $\mathcal{U}_{\mathbb{B}}$ a
$\mathbb{B}$-_ultrafilter base_.

Each ultrafilter base is a maximal tower. In the cardinal setting, one has
$\mathfrak{t}\leq\mathfrak{u}$. Correspondingly, since
$\mathcal{U}_{\mathbb{B}}\subseteq\mathcal{T}_{\mathbb{B}}$, we trivially have
$\mathcal{T}_{\mathbb{B}}\leq_{s}\mathcal{U}_{\mathbb{B}}$ via the identity
reduction. The following indicates that for many natural Boolean algebras,
ultrafilter bases necessarily have computational strength.

######  Proposition 1.6.

Suppose that the degrees of sets in $\mathbb{B}$ form a Turing ideal
$\mathcal{K}$. Then for each $\mathbb{B}$-ultrafilter base $F$ and associated
function $p$ in the sense of Definition 1.2, the function $p$ is not dominated
by a function with Turing degree in $\mathcal{K}$.

###### Proof.

Assume that there is a function $f\geq p$ in $\mathcal{K}$. The conditions
$n_{0}=0$ and $n_{k+1}=f(n_{k})+1$ define a sequence that is computable from
some oracle in $\mathcal{K}$, and for every $k$ we have that $[n_{k},n_{k+1})$
contains an element of $\bigcap_{i\leq k}F_{i}$. So the set

$E=\bigcup_{i\in\omega}\;[n_{2i},n_{2i+1})$

is in $\mathcal{K}$, and clearly $F_{n}\not\subseteq^{*}E$ and
$F_{n}\not\subseteq^{*}\overline{E}$ for each $n$. Therefore, $F$ is not a
$\mathbb{B}$-ultrafilter base. ∎

###  1.4. The Boolean algebra of computable sets

We finish the introduction by summarizing our results in the case that
$\mathbb{B}$ is the Boolean algebra of all computable sets. By Theorem 3.1,
every non-low set computes a set in $\mathcal{T}_{\mathbb{B}}$, and this is
uniform. This is not a characterization, however, because by Corollary 5.3,
every noncomputable c.e. set computes a maximal tower. On the other hand, we
know that there are noncomputable (necessarily low) sets that do not compute
maximal towers; in particular, no 1-generic $\Delta^{0}_{2}$-set does so. This
is because 1-generic $\Delta^{0}_{2}$-sets are index guessable by Theorem 3.4,
and by Proposition 2.4, no index guessable set can compute a maximal tower.
Here, an oracle $G$ is _index guessable_ if $\emptyset^{\prime}$ can find a
computable index for $\varphi_{e}^{G}$ uniformly in $e$, provided that
$\varphi_{e}^{G}$ is computable. We do not know whether index guessability
characterizes the oracles that are unable to compute a maximal tower. It seems
unlikely; index guessability appears to be stronger than necessary.

As already mentioned, in the setting of cardinal characteristics,
$\mathfrak{t}<\mathfrak{u}$ is consistent with ZFC. Since non-low oracles can
be computably dominated, it follows from Proposition 1.6 that there is a
member of $\mathcal{T}_{\mathbb{B}}$ that does not compute any member of
$\mathcal{U}_{\mathbb{B}}$. In other words,
$\mathcal{U}_{\mathbb{B}}\not\leq_{w}\mathcal{T}_{\mathbb{B}}$ in the case
that $\mathbb{B}$ consists of the computable sets.

The separation above only uses the fact that members of
$\mathcal{U}_{\mathbb{B}}$ are not computably dominated; in fact, they are
_high_. As we show in Theorems 3.6 and 3.8, $\mathcal{U}_{\mathbb{B}}$ is
Medvedev equivalent to the mass problem of dominating functions. In Section 4,
we prove that the mass problem $\mathcal{I}_{\mathbb{B}}$ of maximal
independent families is also Medvedev equivalent to the mass problem of
dominating functions. Thus, in the case that $\mathbb{B}$ is the Boolean
algebra of computable sets, we have
$\mathcal{U}_{\mathbb{B}}\equiv_{s}\mathcal{I}_{\mathbb{B}}$. Interestingly,
we do not have a direct proof. Contrast this with the equivalence of
$\mathcal{T}_{\mathbb{B}}$ and $\mathcal{A}_{\mathbb{B}}$, the mass problem of
maximal almost disjoint families; this equivalence is direct and holds for an
arbitrary Boolean algebra, as we will see presently.

##  2\. Basics of the mass problems $\mathcal{T}_{\mathbb{B}}$

###  2.1. The equivalent mass problems $\mathcal{T}_{\mathbb{B}}$ and
$\mathcal{A}_{\mathbb{B}}$

Recall that in set theory, the almost disjointness number $\mathfrak{a}$ is
the least possible size of a maximal almost disjoint (MAD) family of subsets
of $\omega$. In our analogous setting, we call a sequence
${\left\langle{F_{n}}\right\rangle}_{n\in\omega}$ of sets in $\mathbb{B}$
_almost disjoint_ (AD) if each $F_{n}$ is infinite and $F_{n}\cap F_{k}$ is
finite for distinct $n$ and $k$.

######  Definition 2.1.

In the context of a Boolean algebra $\mathbb{B}$ of sets, the mass problem
$\mathcal{A}_{\mathbb{B}}$ is the class of sets $F$ such that
${\left\langle{F_{n}}\right\rangle}_{n\in\omega}$ is a _maximal almost
disjoint_ (MAD) family in $\mathbb{B}$. Namely, the sequence is AD, and for
each infinite set $R\in\mathbb{B}$, there is $n$ such that $R\cap F_{n}$ is
infinite.

######  Fact 2.2.

$\mathcal{A}_{\mathbb{B}}\leq_{s}\mathcal{T}_{\mathbb{B}}\leq_{s}\mathcal{A}_{\mathbb{B}}$.

###### Proof.

We suppress the subscript $\mathbb{B}$. To check that
$\mathcal{A}\leq_{s}\mathcal{T}$, given a set $G$, let $\mathrm{Diff}(G)$ be
the set $F$ such that $F_{n}=G_{n}\smallsetminus G_{n+1}$ for each $n$.
Clearly, the operator $\mathrm{Diff}$ can be seen as a Turing functional. If
$G$ is a maximal $\mathbb{B}$-tower, then $F=\mathrm{Diff}(G)$ is MAD. For, if
$R\in\mathbb{B}$ is infinite, then $R\smallsetminus G_{n}$ is infinite for
some $n$, and hence $R\cap F_{i}$ is infinite for some $i<n$.

For $\mathcal{T}\leq_{s}\mathcal{A}$, given a set $F$, let $G=\mathrm{Cp}(F)$
be the set such that

$x\in G_{n}\leftrightarrow\forall i<n\,[x\not\in F_{n}].$

Again, $\mathrm{Cp}$ is a Turing functional. If $F$ is an almost disjoint
family of sets from $\mathbb{B}$, then $G$ is a $\mathbb{B}$-tower, and if $F$
is MAD, then $G$ is a maximal tower. ∎

Recall that a maximal tower is not computable. Hence no MAD family is
computable. (This corresponds to the cardinal characteristics being
uncountable.)

###  2.2. Descriptive complexity and index complexity for maximal towers

For the rest of this section, as well as the subsequent three sections, we
will mainly be interested in the case that $\mathbb{B}$ is the Boolean algebra
of all computable sets. We will omit the parameter $\mathbb{B}$ when we name
the mass problems. In the final section, we will consider other Boolean
algebras.

Besides looking at the relative complexity of mass problems such as
$\mathcal{T}$ and $\mathcal{U}$, one can also look at the individual
complexity of their members (as sets encoding sequences). Recall that a
characteristic index for a set $M$ is a number $e$ such that
$\chi_{M}=\varphi_{e}$. The following two questions arise:

  1. (1)

How low in the arithmetical hierarchy can the set be located?

  2. (2)

How hard is it to find characteristic indices for the sequence members?

#### Arithmetical complexity

######  Fact 2.3.

No maximal tower $G$ is c.e., and no MAD set is co-c.e.

###### Proof.

For the first statement, note that otherwise there is a computable function
$p$ associated with $G$. The range of $p$ would extend the tower $G$.

For the second statement, note that the reduction $\mathrm{Cp}$, introduced
above to show that $\mathcal{T}\leq_{s}\mathcal{A}$, turns a co-c.e. set $F$
into a c.e. set $G$. ∎

We will return to Question (1) in Section 5, where we show that c.e. MAD sets
exist in every nonzero c.e. degree, and that some ultrafilter base is co-c.e.

#### Complexity of finding characteristic indices for the sequence members

In several constructions of towers
${\left\langle{G_{n}}\right\rangle}_{n\in\omega}$ below, such as in Corollary
5.3 and Theorem 5.4, the oracle $\emptyset^{\prime\prime}$ is able to compute,
given $n$, a characteristic index for $G_{n}$. The oracle $\emptyset^{\prime}$
does not suffice by the following result.

######  Proposition 2.4.

Suppose that $G$ is a maximal tower. The oracle ${\emptyset^{\prime}}$ is not
able to compute, from input $n$, a characteristic index for $G_{n}$.

###### Proof.

Assume the contrary. Then there is a computable function $f$ such that
$\varphi_{\lim_{s}f(n,s)}$ is the characteristic function of $G_{n}$. Let
$\widehat{G}$ be defined as follows. Given $n$ and $x$, compute the least
$s>x$ such that $\varphi_{f(n,s),s}(x)\downarrow$. If the output is not $0$,
put $x$ into $\widehat{G}_{n}$. Clearly $\widehat{G}$ is computable. Since
$G_{n}=^{*}\widehat{G}_{n}$ for each $n$, $\widehat{G}$ is a maximal tower,
contrary to Fact 2.3, or to the earlier observation that maximal towers cannot
be computable. ∎

##  3\. Complexity of $\mathcal{T}$ and of $\mathcal{U}$

In this section, we compare our two principal mass problems, maximal towers
and ultrafilter bases, to well-known benchmark mass problems: non-lowness and
highness. We also define index guessability. No index guessable oracle
computes a maximal tower. We show that every 1-generic $\Delta^{0}_{2}$-set is
index guessable.

As we said above, we restrict ourselves to the case that $\mathbb{B}$ is the
Boolean algebra of computable sets.

###  3.1. Maximal towers, non-lowness, and index guessability

We now show that each non-low oracle computes a set in $\mathcal{T}$. The
result is uniform in the sense of mass problems. Let NonLow denote the class
of oracles $Z$ such that $Z^{\prime}\not\leq_{T}\emptyset^{\prime}$.

######  Theorem 3.1.

$\mathcal{T}\leq_{s}\mathrm{NonLow}$.

###### Proof.

In the following, $x$, $y$, and $z$ denote binary strings; we identify such a
string $x$ with the number whose binary expansion is $1x$. For example, the
string $000$ is identified with 8, the number with binary representation
$1000$. Define a Turing functional $\Theta$ for the Medvedev reduction as
follows: Set $\Theta^{Z}=G$, where for each $n$,

$G_{n}=\\{x\colon\,n\leq s:=|x|\land
Z^{\prime}_{s}\operatorname{\upharpoonright}n=x\operatorname{\upharpoonright}n\\}.$

Here $Z^{\prime}$ denotes the jump of $Z$, which is computably enumerated
relative to $Z$ in a standard way. Note that, for each $n$, for sufficiently
large $s$, the string $Z^{\prime}_{s}\operatorname{\upharpoonright}n$ settles.
So it is clear that for each $n$, we have $G_{n+1}\subseteq^{*}G_{n}$ and
$G_{n}\smallsetminus G_{n+1}$ is infinite. Also $G_{n}$ is computable.

Suppose now that $R$ is an infinite set such that $R\subseteq^{*}G_{n}$ for
each $n$. Then for each $k$,

$Z^{\prime}(k)=\lim_{x\in G_{k},|x|>k}x(k)=\lim_{x\in R,|x|>k}x(k),$

and hence $Z^{\prime}\leq_{T}R^{\prime}$. So if $Z\in\mathrm{NonLow}$, then
$R$ cannot be computable, and hence $\Theta^{Z}\in\mathcal{T}$. ∎

######  Remark 3.2.

The proof above yields a more general result. Suppose that $\mathcal{K}$ is a
countable Turing ideal and $\mathbb{B}$ is the Boolean algebra of sets with
degree in $\mathcal{K}$. Then
$\mathcal{T}_{\mathbb{B}}\leq_{s}\mathrm{NonLow}_{\mathcal{K}}$, where
$\mathrm{NonLow}_{\mathcal{K}}:=\\{Z\colon\forall
R\in\mathcal{K}\,[Z^{\prime}\not\leq_{T}R^{\prime}]\\}$.

We next introduce a property of oracles that we call _index guessability_ ; it
implies that an oracle does not compute a maximal tower. As usual, let
${\left\langle{\Phi_{e}}\right\rangle}_{e\in\omega}$ be an effective list of
the Turing functionals with one input, and write $\varphi_{e}$ for
$\Phi_{e}^{\emptyset}$. Note that if $L$ is a $\Delta^{0}_{2}$-oracle, then
$\emptyset^{\prime\prime}$ can compute from $e$ a characteristic index for
$\Phi_{e}^{L}$ in case that the function $\Phi_{e}^{L}$ is computable. To be
index guessable means that ${\emptyset^{\prime}}$ suffices.

######  Definition 3.3.

We call an oracle $L$ _index guessable_ if ${\emptyset^{\prime}}$ can compute
from $e$ an index for $\Phi_{e}^{L}$ whenever $\Phi_{e}^{L}$ is a computable
function. In other words, there is a functional $\Gamma$ such that

$\Phi_{e}^{L}$ is computable $\Rightarrow$
$\Phi_{e}^{L}=\varphi_{\Gamma({\emptyset^{\prime}};e)}$.

No assumption is made on the convergence of $\Gamma({\emptyset^{\prime}};e)$
in case $\Phi_{e}^{L}$ is not a computable function.

Clearly, being index guessable is closed downward under $\leq_{T}$. A total
function is computable if and only if its graph is computable, in a uniform
way. So for index guessability of $L$, it suffices that there is a Turing
functional $\Gamma$ such that $\Gamma({\emptyset^{\prime}};e)$ provides an
index for $\Phi_{e}^{L}$ in case it is a computable $\\{0,1\\}$-valued
function.

Every index guessable oracle $D$ is low. To see this, for $i\in\omega$, let
$B_{i}=\\{t\colon i\in D^{\prime}_{t}\\}$. If $i\in D^{\prime}$ then $B_{i}$
is cofinite, otherwise $B_{i}=\emptyset$. There is a computable function $g$
such that $\Phi_{g(i)}^{D}$ is the characteristic function of ${B_{i}}$. To
show that $D^{\prime}\leq_{T}{\emptyset^{\prime}}$, on input $i$, let
$\emptyset^{\prime}$ compute a computable index $r(i)$ for $B_{i}$. Now use
$\emptyset^{\prime}$ again to determine $\lim_{k}\varphi_{r(i)}(k)$, which
equals $D^{\prime}(i)$.

By Proposition 2.4, an index guessable oracle $D$ does not compute a maximal
tower. The following provides examples of such oracles.

######  Theorem 3.4.

If $L$ is $\Delta^{0}_{2}$ and $1$-generic, then $L$ is index guessable.

###### Proof.

Suppose that $F=\Phi_{e}^{L}$ and $F$ is a computable set. Let $S_{e}$ be the
c.e. set of strings $\sigma$ above which there is a $\Phi_{e}$-splitting in
the sense that

$S_{e}=\\{\sigma\colon(\exists
p)(\exists\tau_{1}\succ\sigma)(\exists\tau_{2}\succ\sigma)\,\Phi_{e}^{\tau_{1}}(p)\neq\Phi_{e}^{\tau_{2}}(p)\\}.$

Suppose that $S_{e}$ is dense along $L$. Then we claim that the set

$C_{e}=\\{\tau\colon(\exists p)\,\Phi_{e}^{\tau}(p)\neq F(p)\\}$

is also dense along $L$, i.e., for every $k$, there is some $\tau\succeq
L\operatorname{\upharpoonright}k$ such that $\tau\in C_{e}$. Indeed, let
$\sigma\succeq L\operatorname{\upharpoonright}k$ be a member of $S_{e}$ and
let $p$, $\tau_{1}$, and $\tau_{2}$ witness this. Let $\tau_{i}$ for $i=1$ or
$2$ be such that $\Phi_{e}^{\tau_{i}}(p)\neq F(p)$. Then $\tau_{i}\succeq
L\operatorname{\upharpoonright}k$ is in $C_{e}$. The set $C_{e}$ is c.e. and
hence $L$ meets $C_{e}$, contradicting our assumption that $F=\Phi_{e}^{L}$.

It follows that $S_{e}$ is not dense along $L$. In other words, there is some
least $k_{e}$ such that there is no splitting of $\Phi_{e}$ above
$L\operatorname{\upharpoonright}k_{e}$. On input $e$, the oracle
$\emptyset^{\prime}$ can compute $k_{e}$ and
$L\operatorname{\upharpoonright}k_{e}$. This allows $\emptyset^{\prime}$ to
find an index for $F$, given by the following procedure: To compute $F(p)$,
find the least $\tau\succeq L\operatorname{\upharpoonright}k_{e}$ such that
$\Phi_{e}^{\tau}(p)\downarrow$ (in $|\tau|$ many steps). Such a $\tau$ exists
because $\Phi_{e}^{L}(p)\downarrow$. By our choice of $k_{e}$, it follows that
$\Phi_{e}^{\tau}(p)=\Phi_{e}^{L}(p)=F(p)$. ∎

We summarize the known implications:

1-generic $\Delta^{0}_{2}$ $\Rightarrow$ index guessable $\Rightarrow$
computes no maximal tower $\Rightarrow$ low.

The last arrow does not reverse by Theorem 5.1 below; the others might. In
particular, we ask whether any oracle that computes no maximal tower is index
guessable. This would strengthen Theorem 3.1. Note that the following
potential weakening of index guessability of $L$ still implies that the oracle
computes no maximal tower: For each $S\leq_{T}L$ such that each $S_{n}$ is
computable, there is binary computable function $f$ such that
$S_{n}=\varphi_{\lim_{s}f(n,s)}$ for each $n$.

######  Aside.

We pause briefly to mention a potential connection of our topic to
computational learning theory. One says that a class $S$ of computable
functions is _EX-learnable_ if there is a total Turing machine $M$ such that
$\lim_{s}M(f\operatorname{\upharpoonright}s)$ exists for each $f\in S$ and is
an index for $f$. For an oracle $A$, one says that $S$ is _EX $[A]$-learnable_
if there is an oracle machine $M$ that is total for each oracle and such that
$\lim_{s}M^{A}(f\operatorname{\upharpoonright}s)$ exists for each $f\in S$ and
is an index for $f$. One calls an oracle $A$ _EX-trivial_ if EX = EX$[A]$.
Slaman and Solovay [16] showed that $A$ is EX-trivial if and only if $A$ is
$\Delta^{0}_{2}$ and has 1-generic degree. This used an earlier result of
Haught that the Turing degrees of the 1-generic $\Delta^{0}_{2}$-sets are
closed downward.

###  3.2. Ultrafilter bases and highness

Let $\text{Tot}=\\{e\colon\varphi_{e}\text{ is total}\\}$. Let
$\mathrm{DomFcn}$ denote the mass problem of functions $h$ that dominate every
computable function and also satisfy $h(s)\geq s$ for all $s$. Note that a set
$F$ is high if and only if $\text{Tot}\leq_{T}F^{\prime}$. To represent
highness by a mass problem in the Medvedev degrees, one can equivalently
choose the set of functions dominating each computable function, or the set of
approximations to Tot, i.e., the $\\{0,1\\}$-valued binary functions $f$ such
that $\lim_{s}f(e,s)=\text{Tot}(e)$. This follows from the next fact; we omit
the standard proof.

######  Fact 3.5.

$\mathrm{DomFcn}$ is Medvedev equivalent to the mass problem of approximations
to _$\text{Tot}=\\{e\colon\varphi_{e}\text{ is total}\\}$_.

We show that exactly the high oracles compute ultrafilter bases, and that the
reductions are uniform. By Fact 3.5, it suffices to show that
$\mathcal{U}\equiv_{s}\mathrm{DomFcn}$. We will obtain the two Medvedev
reductions through separate theorems, with proofs that are unrelated.

######  Theorem 3.6.

Every ultrafilter base uniformly computes a dominating function. In other
words, $\mathcal{U}\geq_{s}\mathrm{DomFcn}$.

Our proof is directly inspired by a proof of Jockusch [8, Theorem 1,
(iv)$\implies$(i)], who showed that any family of sets containing exactly the
computable sets must have high degree.

######  Lemma 3.7.

There is a uniformly computable sequence $P_{0},P_{1},\dots$ of nonempty
$\Pi^{0}_{1}$-classes such that for every $e$,

  * •

if $\varphi_{e}$ is total, then $P_{e}$ contains a single element, and

  * •

if $\varphi_{e}$ is not total, then $P_{e}$ contains only bi-immune elements.

###### Proof.

Note that each Martin-Löf (or even Kurtz) random set is bi-immune: For an
infinite computable set $R$, the class of sets containing $R$ is a
$\Pi^{0}_{1}$-null class and hence determines a Kurtz test. A similar fact
holds for the class of sets disjoint from $R$.

For each $s$, let $n_{s}$ be the largest number such that $\varphi_{e,s}$
converges on $[0,n_{s})$. We build the $\Pi^{0}_{1}$-class $P_{e}$ in stages,
where $P_{e,s}$ is the nonempty clopen set we have before stage $s$ of the
construction. Let $P_{e,0}=2^{\omega}$.

_Stage $0$._ Start constructing $P_{e}$ as a nonempty $\Pi^{0}_{1}$-class
containing only Martin-Löf random elements.

_Stage $s$._ If $n_{s}=n_{s-1}$, continue the construction that is currently
underway, which will produce a nonempty $\Pi^{0}_{1}$-class of random
elements.

On the other hand, if $n_{s}>n_{s-1}$, fix a string $\sigma$ such that
$[\sigma]\subseteq P_{e,s}$ and $|\sigma|>s$. Let $P_{e,s+1}=[\sigma]$. End
the construction that we have been following and start a new construction for
$P_{e}$, starting at stage $s+1$, as a nonempty $\Pi^{0}_{1}$-subclass of
$[\sigma]$ containing only Martin-Löf random elements.

It is clear that if $\varphi_{e}$ is total, then $P_{e}$ will be a singleton.
Otherwise, there will be a final construction of a nonempty
$\Pi^{0}_{1}$-class of randoms which will run without further interruption. ∎

Of course, when $P_{e}$ is a singleton, its lone element must be computable.

###### Proof of Theorem 3.6.

For any set $C$, let $S_{C}=\\{X\in 2^{\omega}\colon C\subseteq X\\}$. Note
that if $C$ is computable (or even merely c.e.), then $S_{C}$ is a
$\Pi^{0}_{1}$-class. Let $Q_{e}=\\{X\colon\overline{X}\in P_{e}\\}$ be the
$\Pi^{0}_{1}$-class of complements of elements of $P_{e}$.

Now let $F$ be an ultrafilter base. We have that

$\displaystyle\varphi_{e}\text{ is total}\iff$ $\displaystyle(\exists
i)(\exists n)\;[F_{i}\smallsetminus[0,n]\text{ is a subset of some }$
$\displaystyle\qquad\qquad X\in P_{e}\text{ or its complement}]$
$\displaystyle\iff$ $\displaystyle(\exists i)(\exists n)\;[P_{e}\cap
S_{F_{i}\smallsetminus[0,n]}\neq\emptyset\text{ or }Q_{e}\cap
S_{F_{i}\smallsetminus[0,n]}\neq\emptyset].$

Even though $S_{F_{i}\smallsetminus[0,n]}$ is a $\Pi^{0}_{1}$-class, we cannot
hope to compute an index using $F$. However, $S_{F_{i}\smallsetminus[0,n]}$ is
a $\Pi^{0}_{1}[F]$-class uniformly in $i,n$. Using the fact that the
nonemptiness of a $\Pi^{0}_{1}[F]$-class is a $\Pi^{0}_{1}[F]$-property, we
see that $\text{Tot}=\\{e\colon\varphi_{e}\text{ is total}\\}$ is
$\Sigma^{0}_{2}[F]$. Note that the $\Sigma^{0}_{2}$-index does not depend on
$F$. Since Tot is also $\Pi^{0}_{2}$, it is $\Delta^{0}_{2}[F]$ via a fixed
pair of indices, and hence Turing reducible to $F^{\prime}$ via a fixed
reduction. One direction of the usual proof of the (relativized) Limit Lemma
now shows that we can uniformly compute an approximation to Tot from $F$.
Hence, from $F$ we can uniformly compute a dominating function by Fact 3.5. ∎

######  Theorem 3.8.

Every dominating function uniformly computes an ultrafilter base. In other
words, $\mathcal{U}\leq_{s}\mathrm{DomFcn}$.

###### Proof.

Let ${\left\langle{\psi_{e}}\right\rangle}_{e\in\omega}$ be an effective
listing of the $\\{0,1\\}$-valued partial computable functions defined on an
initial segment of $\omega$. Let $V_{e,k}=\\{x\colon\psi_{e}(x)=k\\}$ so that
${\left\langle{(V_{e,0},V_{e,1})}\right\rangle}$ is an effective listing that
contains all pairs of computable sets and their complements.

Let $T=\\{0,1,2\\}^{<\infty}$. Uniformly in $\alpha\in T$, we will define a
set $S_{\alpha}$. We first explain the basic idea and then modify it to make
it work. The basic idea is to start with $S_{\emptyset}=\omega$ and build
$S_{\alpha\widehat{\ }k}=S_{\alpha}\cap V_{e,k}$ for $k=0,1$ and $e=|\alpha|$,
that is, we split $S_{\alpha}$ according to the listing above. We then
consider the leftmost path $g$ so that $S_{g\operatorname{\upharpoonright}e}$
is infinite for each $e$. A dominating function $h$ can eventually discover
each initial segment of this path and use this to compute a set $F$ such that
$F_{e}=^{*}S_{g\operatorname{\upharpoonright}e}$ for each $e$.

The problem is that both $S_{\alpha}\cap V_{e,0}$ and $S_{\alpha}\cap V_{e,1}$
could be finite (because $e$ is not a proper index of a computable set). In
this case we still need to make sure that $F_{e}\smallsetminus F_{e+1}$ is
infinite. So the rightmost option at level $n$ is a set $S_{\alpha\widehat{\
}2}=\widetilde{S}_{\alpha}$ that simply removes every other element from
$S_{\alpha}$. The sets $S_{\alpha\widehat{\ }k}$ for $k\leq 1$ will be subsets
of $\widetilde{S}_{\alpha}$.

We now provide the details. The set $S_{\alpha}$ is enumerated in increasing
fashion, and possibly finite. So each $S_{\alpha}$ is computable, but not
uniformly in $\alpha$. All the sets and functions defined below can be
interpreted at stages.

Let $S_{\emptyset,s}=[0,s)$. If we have defined (at stage $s$) the set
$S_{\alpha}=\\{r_{0}<\cdots<r_{k}\\}$, let $\widetilde{S}_{\alpha}$ contain
the numbers of the form $r_{2i}$. Let $S_{\alpha\widehat{\
}2}=\widetilde{S}_{\alpha}$. Let $S_{\alpha\widehat{\
}k}=\widetilde{S}_{\alpha}\cap V_{e,k}$ for $k=0,1$, $e=|\alpha|$. We define a
uniform list of Turing functionals $\Gamma_{e}$ so that the sequence
${\left\langle{\Gamma^{h}_{e}(t)}\right\rangle}_{t\in\omega}$ is nondecreasing
and unbounded, for each $e$ and each oracle function $h$ such that $h(s)\geq
s$ for each $s$. We will let $F_{e}=\\{\Gamma^{h}_{e}(t)\colon t\in\omega\\}$.

_Definition of $\Gamma_{e}$._ Given an oracle function $h$, we will write
$a_{s}$ for $\Gamma^{h}_{e}(s)$. Let $a_{0}=0$. Suppose $s>0$ and $a_{s-1}$
has been defined. Check if there is $\alpha\in T$ of length $e$ such that
$|S_{\alpha,h(s)}|\geq s$. If there is no such $\alpha$, let $a_{s}=a_{s-1}$.
Otherwise, let $\alpha$ be leftmost such. If $\max S_{\alpha,h(s)}>a_{s-1}$,
let $a_{s}=\max S_{\alpha,h(s)}$. Otherwise, again let $a_{s}=a_{s-1}$.

Note that the sequence $\\{a_{s}\\}_{s<\omega}$ is unbounded because for the
rightmost string $\alpha\in T$ of length $e$, the set $S_{\alpha,t}$ consists
of the numbers in $[0,t)$ divisible by $2^{e}$. We may combine the functionals
$\Gamma_{e}$ to obtain a functional $\Psi$ such that $(\Psi^{h})_{e}=F_{e}$
for each $h$ with $h(s)\geq s$ for each $s$.

######  Claim 3.9.

If $h\in\mathrm{DomFcn}$, then $F=\Psi^{h}\in\mathcal{U}$.

To verify this, let $g\in 2^{\omega}$ denote the leftmost path in
$\\{0,1,2\\}^{\omega}$ such that the set
$S_{g\operatorname{\upharpoonright}e}$ is infinite for every $e$. Note that
$g$ is an infinite path, because for every $\alpha$, if the set $S_{\alpha}$
is infinite then so is $S_{\alpha\widehat{\ }2}$.

Fix $e$ and let $\alpha=g\operatorname{\upharpoonright}e$. Let $p(s)$ be the
least stage $t$ such that $S_{\alpha,t}$ has at least $s$ elements. Since $h$
dominates the computable function $p$, we will eventually always pick $\alpha$
in the definition of $a_{s}=\Gamma^{h}_{e}(s)$. Hence $F_{e}=^{*}S_{\alpha}$.
This implies that $F_{e}$ is computable and $F_{e+1}\subseteq^{*}F_{e}$.
Clearly, if $S_{\alpha}$ is infinite, then
$S_{\beta}\subset_{\infty}S_{\alpha}$ for every $\beta\succ\alpha$. Thus
$F_{e+1}\subset_{\infty}^{*}F_{e}$.333Here, $A\subset_{\infty}B$ means that
$A\subseteq B$ and $B\smallsetminus A$ is infinite. We define
$\subset_{\infty}^{*}$ similarly.

Now let $R$ be a computable set. Pick $e$ such that $R=V_{e,0}$ and
$\overline{R}=V_{e,1}$. If $g(e)=0$, then
$S_{g\,\operatorname{\upharpoonright}{e+1}}\subseteq V_{e,0}$ and hence
$F_{e+1}\subseteq^{*}R$. Otherwise,
$S_{g\,\operatorname{\upharpoonright}{e+1}}\subseteq V_{e,1}$ and hence
$F_{e+1}\subseteq^{*}\overline{R}$. ∎

##  4\. Maximal independent families in computability

In this short section, we determine the complexity of the computability-
theoretic analog of the independence number $\mathfrak{i}$ for the Boolean
algebra of computable sets. It turns out that in the context of the computable
sets, _maximal independent families_ behave in a way similar to ultrafilter
bases.

Given a sequence ${\left\langle{F_{n}}\right\rangle}_{n\in\omega}$, for each
binary string $\sigma$ we write

(1)
$F_{\sigma}=\bigcap_{\sigma(i)=1}F_{i}\cap\bigcap_{\sigma(i)=0}\overline{F}_{i}.$

We call (a set $F$ encoding) such a sequence _independent_ if each set
$F_{\sigma}$ is infinite.

######  Definition 4.1.

Given a Boolean algebra of sets $\mathbb{B}$, the mass problem
$\mathcal{I}_{\mathbb{B}}$ is the class of sets $F$ such that
${\left\langle{F_{n}}\right\rangle}_{n\in\omega}$ is a family that is _maximal
independent_ , namely, it is independent, and for each set $R\in\mathbb{B}$,
there is $\sigma$ such that $F_{\sigma}\subseteq^{*}R$ or
$F_{\sigma}\subseteq^{*}\overline{R}$.

In the following, we let $\mathbb{B}$ be the Boolean algebra of computable
sets, and we drop the parameter $\mathbb{B}$ as usual. An easy modification of
the proof of Theorem 3.6 yields the following

######  Theorem 4.2.

Every maximal independent family $F$ uniformly computes a dominating function.
In other words, $\mathcal{I}\geq_{s}\mathrm{DomFcn}$.

###### Proof.

Define the $\Pi^{0}_{1}$-classes $P_{e}$ as in Lemma 3.7. As before let
$Q_{e}=\\{X\colon\overline{X}\in P_{e}\\}$ be the $\Pi^{0}_{1}$-class of
complements of elements of $P_{e}$. Recall that for any set $C$, we let
$S_{C}=\\{X\in 2^{\omega}\colon C\subseteq X\\}$. Now we have that

$\displaystyle\varphi_{e}\text{ is total}\iff$
$\displaystyle(\exists\sigma)(\exists n)\;[F_{\sigma}\smallsetminus[0,n]\text{
is a subset of some }$ $\displaystyle\qquad\qquad X\in P_{e}\text{ or its
complement}]$ $\displaystyle\iff$ $\displaystyle(\exists\sigma)(\exists
n)\;[P_{e}\cap S_{F_{\sigma}\smallsetminus[0,n]}\neq\emptyset\text{ or
}Q_{e}\cap S_{F_{\sigma}\smallsetminus[0,n]}\neq\emptyset]$

As before, this shows that from $F$ one can uniformly compute a dominating
function. ∎

######  Theorem 4.3.

Every dominating function $h$ uniformly computes a maximal independent family.
In other words, $\mathcal{I}\leq_{s}\mathrm{DomFcn}$.

In fact, we will prove that a dominating function $h$ uniformly computes a set
$F$ such that the $=^{*}$-equivalence classes of the sets $F_{e}$ freely
generate the Boolean algebra of computable sets modulo finite sets.

###### Proof.

As in the proof of Theorem 3.8, let
${\left\langle{\psi_{e}}\right\rangle}_{e\in\omega}$ be an effective listing
of the $\\{0,1\\}$-valued partial computable functions defined on an initial
segment of $\omega$, and let $V_{e,k}=\\{x\colon\psi_{e}(x)=k\\}$ for $k=0,1$.

In Phase $e$ of the construction, we will define a computable set $F_{e}$ such
that $F_{e}=\Theta_{e}^{h}$ for a Turing functional $\Theta_{e}$ determined
uniformly in $e$. Suppose we have defined $\Theta_{i}$ for $i<e$, and thereby
the sets $F_{\sigma}$ defined in (1), where $\sigma$ is a string of length
$e$.

The idea for building $F_{e}$ is to try to follow $V_{e,0}$ while maintaining
independence from the previous sets. We apply this strategy separately on each
$F_{\sigma}$. Using $h$ as an oracle we compute recursively an increasing
sequence ${\left\langle{r^{e}_{n}}\right\rangle}_{n\in\omega}$. We carry out
the attempts on intervals $[r^{e}_{n},r^{e}_{n+1})$. If $V_{e,0}$ appears to
split $F_{\sigma}$ on the current interval, then we follow it; otherwise, we
merely make sure that $F_{e}$ remains independent from $F_{\sigma}$ on the
interval by putting one number in and leaving another one out. To decide which
case holds, we consult the dominating function.

We now provide the details for Phase $e$. As $e$ is fixed, we drop the
superscripts $e$. By $\sigma$ we will always denote a string of length $e$.
Let $r_{0}=0$. If $r_{n}$ has been defined, let $r_{n+1}>r_{n}$ be the least
number $r$ such that for each $\sigma$

  * (a)

$|[r_{n},r)\cap F_{\sigma}|\geq 2$, and

  * (b)

if there are $u,w\in\mathrm{dom}(\psi_{e,h(r_{n})})\cap F_{\sigma}$ with
$r_{n}\leq u<w$ such that $\psi_{e}(u)=1$ and $\psi_{e}(w)=0$, then $r>w$ for
the least such $w$.

We define $F_{e}(x)=\Theta_{e}^{h}(x)$ for $x\in[r_{n},r_{n+1})$ as follows.
For each $\sigma$,

  * •

if condition (b) holds and $\psi_{e}$ is defined on $[r_{n},r_{n+1})$, then
let $F_{e}(x)=\psi_{e}(x)$;

  * •

otherwise, if $x=\min([r_{n},r_{n+1})\cap F_{\sigma})$, let $F_{e}(x)=1$, else
let $F_{e}(x)=0$.

_Verification._ By induction on $e$, one verifies that $F_{\sigma}$ is
infinite for each $\sigma$ with $|\sigma|=e$, and that the sequence
${\left\langle{r^{e}_{n}}\right\rangle}_{n\in\omega}$ defined in Phase $e$ of
the construction is infinite. Thus $\Theta^{h}_{e}$ is total for each function
$h$. So $F\leq_{T}h$ where $F_{e}=\Theta^{h}_{e}$, and $F$ is an independent
family.

######  Claim 4.4.

Each set $F_{e}$ is computable.

We verify this by induction on $e$. Suppose it holds for each $i<e$. So
$F_{\sigma}$ is computable for $|\sigma|=e$.

First assume that $\psi_{e}$ is partial. Then for sufficiently large $n$,
condition (b) does not apply, and so the sequence
${\left\langle{r_{n}}\right\rangle}_{n\in\omega}$ and hence $F_{e}$ are
computable.

Now assume that $\psi_{e}$ is total. Let

$D_{e}=\\{\sigma\colon\,|\sigma|=e\land|F_{\sigma}\cap
V_{e,0}|=|F_{\sigma}\cap V_{e,1}|=\infty\\}.$

Define a function $p$ by letting $p(m)$ be the least stage $s$ such that for
each $\sigma\not\in D_{e}$, condition (a) holds with $r_{n}=m$ and $r=s$, and
for each $\sigma\in D_{e}$, there are $u,w\in\mathrm{dom}({\psi_{e,s}})$ such
that $m\leq u<w$ as in condition (b). (Let $p(m)=0$ if $m$ is not of the form
$r_{n}$.) Since $F_{\sigma}$ is computable for each $\sigma$ of length $e$,
the function $p$ is computable. Since $h$ dominates $p$, for sufficiently
large $n$, we will define $r_{n+1}$ by checking $\psi_{e}$ at a stage
$h(r_{n})\geq p(r_{n})$; since we chose the witnesses minimal, $r_{n+1}$ is
determined by stage $p(r_{n})$. So we might as well check $\psi_{e}$ at that
stage and do not need $h$. Hence the sequence
${\left\langle{r_{n}}\right\rangle}_{n\in\omega}$ and therefore $F_{e}$ are
computable.

######  Claim 4.5.

Suppose that $\psi_{e}$ is total. Then for each string $\tau=\sigma\widehat{\
}a$ of length $e+1$, $F_{\tau}\subseteq^{*}V_{e,0}$ or $F_{\tau}\cap
V_{e,0}=^{*}\emptyset$.

If $\sigma\not\in D_{e}$, then this is immediate since
$F_{\sigma}\subseteq^{*}V_{e,i}$ for some $i$. Otherwise, Phase $e$ of the
construction ensures that $F_{\sigma\widehat{\ }0}=^{*}F_{\sigma}\cap
V_{e,0}$.

By the last claim, the $=^{*}$-equivalence classes of the $F_{e}$ freely
generate the Boolean algebra of the computable sets modulo finite sets. In
particular, $F$ is a maximal independent family. ∎

As mentioned in the introduction, we do not know at present whether there is a
“natural” Medvedev equivalence between the two mass problems $\mathcal{U}$ and
$\mathcal{I}$ as is the case for $\mathcal{A}$ and $\mathcal{T}$. This would
require direct proofs avoiding the detour via the mass problem of dominating
functions. For what it is worth, the cardinal characteristics $\mathfrak{u}$
and $\mathfrak{i}$ are incomparable (i.e., ZFC cannot determine their order).

##  5\. The co-computably enumerable case

Recall from Fact 2.3 that no maximal tower, and in particular no ultrafilter
base, can be computably enumerable. In contrast, in this section we will see
that even ultrafilter bases can have computably enumerable complement. As in
the previous sections, we are restricting our attention to the Boolean algebra
of all computable sets.

Recall that a coinfinite c.e. set $A$ is called _simple_ if it meets every
infinite c.e. (or, equivalently, computable) set; $A$ is called _$r$ -maximal_
if $\overline{A}\subseteq^{*}\overline{R}$ or $\overline{A}\subseteq^{*}R$ for
each computable set $R$. Each $r$-maximal set is simple. For more background,
see, e.g., Soare [17].

###  5.1. Computably enumerable MAD sets, and co-c.e. towers

We will show that if $A$ is a noncomputable c.e. set, then there is a co-c.e.
maximal tower $G\leq_{T}A$. Given that it is more standard to build c.e.
rather than co-c.e. sets, it will be convenient to first build a c.e. MAD set
$F\leq_{T}A$ and then use the Medvedev reduction in Fact 2.2 to get a co-c.e.
maximal tower. We employ a priority construction with requirements that act
only finitely often.

######  Theorem 5.1.

For each noncomputable c.e. set $A$, there is a MAD c.e. set $F\leq_{T}A$.

###### Proof.

The construction is akin to Post’s construction of a simple set. In
particular, it is compatible with permitting.

Let ${\left\langle{M_{e}}\right\rangle}_{e\in\omega}$ be a uniformly c.e.
sequence of sets such that $M_{2e}=W_{e}$ and $M_{2e+1}=\omega$ for each $e$.
We will build an auxiliary c.e. set $H\leq_{T}A$ and let the c.e. set
$F\leq_{T}A$ be defined by $F^{[e]}=H^{[2e]}\cup H^{[2e+1]}$. The purpose of
the sets $M_{2e+1}$ is to make the sets $H^{[2e+1]}$, and hence the sets
$F^{[e]}$, infinite. The construction also ensures that $H$, and hence $F$, is
AD, and that $\bigcup_{n}H^{[n]}$ is coinfinite.

As usual, we will write $H_{e}$ for $H^{[e]}$. We provide a stage-by-stage
construction to meet the requirements

$P_{n}\colon M_{e}\smallsetminus\bigcup_{i<n}H_{i}\text{ infinite
}\Rightarrow|H_{e}\cap M_{e}|\geq k\text{, where }n=\langle e,k\rangle.$

(Note that the union is over all $i$ such that $i<n$, not $i<e$.) At stage
$s$, we say that $P_{n}$ is _permanently satisfied_ if $|H_{e,s}\cap
M_{e,s}|\geq k$.

_Construction._

_Stage $s>0$_. See if there is $n<s$ such that $P_{n}$ is not permanently
satisfied, and, where $n=\langle e,k\rangle$, there is $x\in
M_{e,s}\smallsetminus\bigcup_{i<n}H_{i,s}$ such that

$x>\max(H_{e,s-1})$, $x\geq 2n$, and $A_{s}\operatorname{\upharpoonright}x\neq
A_{s-1}\operatorname{\upharpoonright}x$.

If so, choose $n$ least, and put $\langle x,e\rangle$ into $H$ (i.e., put $x$
into $H_{e}$).

_Verification._ Each $H_{e}$ is enumerated in increasing fashion and hence
computable.

Each $P_{n}$ is active at most once. This ensures that $\bigcup_{e}H_{e}$ is
coinfinite: For each $N$, if $x<2N$ enters this union, then this is due to the
action of a requirement $P_{n}$ with $n<N$, so there are at most $N$ many such
$x$.

To see that a requirement $P_{n}$ for $n=\langle e,k\rangle$ is met, suppose
that its hypothesis holds. Then there are potentially infinitely many
candidates $x$ that can go into $H_{e}$. Since $A$ is noncomputable, one of
them will be permitted.

Now, by the choice of $M_{2e+1}$ and the fact that $\bigcup_{e}H_{e}$ is
coinfinite, each $H_{2e+1}$, and hence each $F_{e}$, is infinite. By
construction, for $e<m$, we have $|H_{e}\cap H_{m}|\leq m$. So the family
described by $H$, and therefore also the one described by $F$, is almost
disjoint.

To show that $F$ is MAD, it suffices to verify that if $M_{e}$ is infinite
then $M_{e}\cap F_{p}$ is infinite for some $p$. If all the $P_{e,k}$ are
permanently satisfied during the construction, we let $p=e$. Otherwise, we let
$k$ be least such that $P_{n}$ is never permanently satisfied where $n=\langle
e,k\rangle$. Then its hypothesis fails, so
$M_{e}\subseteq^{*}\bigcup_{i<n}H_{i}$. ∎

Since an index guessable set computes no MAD set by Proposition 2.4, we obtain
the following

######  Corollary 5.2.

No noncomputable, c.e. set $L$ is index guessable.

Downey and Nies have given a direct proof of this fact (see [6]).

######  Corollary 5.3.

For each noncomputable c.e. set $A$, there is a co-c.e. set $G\leq_{T}A$ such
that $G\in\mathcal{T}$, i.e.,
${\left\langle{G_{n}}\right\rangle}_{n\in\omega}$ is a maximal tower.

###### Proof.

Let $F$ be the MAD set obtained above. Recall the Turing reduction
$\mathrm{Cp}$ showing that $\mathcal{T}\leq_{s}\mathcal{A}$ in Fact 2.2. The
set $G=\mathrm{Cp}(F)$, given by

$x\in G_{n}\leftrightarrow\forall i<n\,[x\not\in F_{n}]$

is as required. ∎

###  5.2. Co-c.e. ultrafilter bases

######  Theorem 5.4.

There is a co-c.e. ultrafilter base $F$.

###### Proof.

We adapt the construction from the proof of the main result in [11], which
states that there is an $r$-maximal set $A$ such that the index set
$\mathrm{Cof}_{A}=\\{e\colon W_{e}\cup A=^{*}\omega\\}$ is
$\Sigma^{0}_{3}$-complete. Both the original and the adapted version make use
of the fact that we are given a c.e. index for a computable set and also one
for its complement (see the pairs $(V_{e,0},V_{e,1})$ below). Our proof can
also be viewed as a variation on the proof of Theorem 3.8 in the setting of
co-c.e. sets. We remark that by standard methods, one can extend the present
construction to include permitting below a given high c.e. set.

We build a co-c.e. tower $F$ by providing uniformly co-c.e. sets $F_{e}$ for
$e\in\omega$ that form a descending sequence with $F_{e}\supseteq F_{e+1}$. We
achieve the latter condition by agreeing that whenever we remove $x$ from
$F_{e}$ at a stage $s$, we also remove it from all $F_{i}$ for $i>e$.
Furthermore, no element is ever removed from $F_{0}$, so $F_{0}=\omega$.

Let ${\left\langle{(V_{e,0},V_{e,1})}\right\rangle}_{{}_{e\in\omega}}$ be an
effective listing of all pairs of disjoint c.e. sets as defined in the proof
of Theorem 3.8. The construction will ensure that the following requirements
are met:

$\displaystyle M_{e}$ $\displaystyle\colon F_{e}\smallsetminus F_{e+1}\text{
is infinite,}$ $\displaystyle P_{e}$ $\displaystyle\colon V_{e,0}\cup
V_{e,1}=\omega\Rightarrow F_{e+1}\subseteq^{*}V_{e,0}\vee
F_{e+1}\subseteq^{*}V_{e,1}.$

This suffices to establish that $F$ is an ultrafilter base.

The tree of strategies is $T=\\{0,1,2\\}^{<\infty}$. Each string $\alpha\in T$
of length $e$ is tied to $M_{e}$ and also to $P_{e}$. We write $\alpha\colon
M_{e}$ and $\alpha\colon P_{e}$ to indicate that we view $\alpha$ as a
strategy of the respective type.

_Streaming._ For each string $\alpha\in T$ with $|\alpha|=e$, at each stage of
the construction, we have a set $S_{\alpha}$, thought of as a stream of
numbers used by $\alpha$. Each time $\alpha$ is initialized, $S_{\alpha}$ is
removed from $F_{e+1}$, and $S_{\alpha}$ is reset to be empty. Also,
$S_{\alpha}$ is enlarged only at stages at which $\alpha$ appears to be on the
true path. We will verify the following properties:

  1. (1)

$S_{\emptyset}=\omega$;

  2. (2)

if $\alpha$ is not the empty node, then $S_{\alpha}$ is a subset of
$S_{\alpha^{-}}$ (where $\alpha^{-}$ is the immediate predecessor of
$\alpha$);

  3. (3)

at every stage, $S_{\gamma}\cap S_{\beta}=\emptyset$ for incomparable strings
$\gamma$ and $\beta$;

  4. (4)

$x$ is in $F_{e+1}$ at the time a number $x$ first enters $S_{\alpha}$;

  5. (5)

if $\alpha$ is along the true path of the construction, then $S_{\alpha}$ is
an infinite computable set.

Note that $S_{\alpha}$ is d.c.e. uniformly in $\alpha$. The set $S_{\alpha}$
is finite if $\alpha$ is to the left of the true path of the construction;
$S_{\alpha}$ is an infinite computable set if $\alpha$ is along the true path;
and $S_{\alpha}$ is empty if $\alpha$ is to the right of the true path.

The _intuitive strategy $\alpha\colon P_{e}$:_ Only strategies associated with
a string of length $\leq e$ can remove numbers from $F_{e+1}$. A strategy
$\alpha\colon P_{e}$ thins out $S_{\alpha}$ by removing some of its elements
from $F_{e+1}$. It regards the set of remaining numbers as its private version
of $F_{e+1}$. It has to make sure that no strategies $\beta$ to its right
remove numbers from $F_{e+1}$ that it wants to keep. On the other hand, it can
only process a number $x$ once it knows whether $x$ is in $V_{e,0}$ or
$V_{e,1}$. The solution to this conflict is that $\alpha$ _reserves_ a number
$x$ from the stream $S_{\alpha}$, which by initialization withholds it from
any action of such a $\beta$. It then waits until all numbers $\leq x$ are in
$V_{e,0}\cup V_{e,1}$. If that never happens for some reserved $x$, then
$\alpha$ is satisfied finitarily with eventual outcome $2$. Otherwise, it will
eventually process $x$: If $x\in V_{e,0}$, it continues its attempt to build
$F_{e+1}$ inside $V_{e,0}$; else it continues to build $F_{e+1}$ inside
$V_{e,1}$. It takes outcome $0$ or $1$, respectively, according to which case
applies. Each time the apparent outcome is $0$, the content of the output
stream based on the assumption that the true outcome is $1$ is removed from
$F_{e+1}$. So if $0$ is the true outcome, then indeed
$F_{e+1}\subseteq^{*}V_{e,0}$.

The _intuitive strategy $\alpha\colon M_{e}$_ simply removes every other
element of $S_{\alpha}$ from $F_{e+1}$. Then $\alpha:P_{e}$ actually only
works with the stream of remaining numbers. There is no further interaction
between the two types of strategies. (Note here that making $F_{e+1}$ smaller
is to the advantage of $P_{e}$.) Recall that if $\alpha$ is initialized,
$S_{\alpha}$ is removed from $F_{e+1}$, and $S_{\alpha}$ is reset to be empty.

_Construction._

Stage $0$. Let $\delta_{0}$ be the empty string. Let $F_{e}=\omega$ for each
$e$. Initialize all strategies.

_Stage_ $s>0$. Let $S_{\emptyset,s}=[0,s)$. Stage $s$ consists of substages
$e=0,\ldots,s-1$, during which we inductively define $\delta_{s}$, a string of
length $s$.

_Substage $e$._ We suppose that
$\alpha=\delta_{s}\operatorname{\upharpoonright}e$ and $S_{\alpha}$ have been
defined.

The strategy $\alpha\colon M_{e}$ acts as follows. If at the current stage
$S_{\alpha}=\\{r_{0}<\cdots<r_{k}\\}$ and $r_{k}$ is new in $S_{\alpha}$, it
puts $r_{k}$ into $\widetilde{S}_{\alpha}$ if and only if $k$ is even;
otherwise, $r_{k}$ is removed from $F_{e+1}$.

The strategy $\alpha\colon P_{e}$ picks the first applicable case below.

Case 1: Each reserved number of $\alpha$ has been processed: If there is a
number $x$ from $\widetilde{S}_{\alpha}$ greater than $\alpha$’s last reserved
number (if any) and greater than the last stage $\alpha$ was initialized, pick
$x$ least and _reserve_ it. Note that $x<s$ since by definition
$S_{\emptyset,s}=[0,s)$. Initialize $\alpha\widehat{\ }2$, and let
$\alpha\widehat{\ }2$ be eligible to act next.

Note that if Case 1 does not apply then $\alpha$ has a unique reserved, but
unprocessed number $x$.

Case 2: $[0,x]\subseteq V_{e,0}\cup V_{e,1}$ and $x\in V_{e,0}$: Let $t$ be
the greatest stage $<s$ at which $\alpha$ was initialized. Add $x$ to
$S_{\alpha\widehat{\ }0}$ and remove from $F_{e+1}$ all numbers in the
interval $(t,x)$ that are not in $S_{\alpha\widehat{\ }0}$. Declare that
$\alpha$ has _processed_ $x$. Let ${\alpha\widehat{\ }0}$ be eligible to act
next.

Case 3: $[0,x]\subseteq V_{e,0}\cup V_{e,1}$ and $x\in V_{e,1}$: Let $t$ be
the greatest stage $<s$ at which $\alpha$ was initialized or $\alpha\widehat{\
}0$ was eligible to act. Add $x$ to $S_{\alpha\widehat{\ }1}$ and remove from
$F_{e+1}$ all numbers in the interval $(t,x)$ that are not in
$S_{\alpha\widehat{\ }1}$. Declare that $\alpha$ has _processed_ $x$. Let
${\alpha\widehat{\ }1}$ be eligible to act next.

Case 4: Otherwise, that is, $[0,x]\not\subseteq V_{e,0}\cup V_{e,1}$: Let $t$
be the greatest stage $<s$ at which $\alpha$ was initialized, or
$\alpha\widehat{\ }0$ or $\alpha\widehat{\ }1$ was eligible to act. Let
$S_{\alpha\widehat{\ }2}=\widetilde{S}_{\alpha}\cap(t,s)$. Let
$\alpha\widehat{\ }2$ be eligible to act.

We define $\delta_{s}(e)=i$ where $\alpha\widehat{\ }i$, $0\leq i\leq 2$, has
been declared eligible to act next. If $e+1<s$, then carry out the next
substage. Else initialize all the strategies $\beta$ such that
$\delta_{s}<_{L}\beta$ and end stage $s$.

_Verification._ By construction and our convention above, $F_{e}$ is co-c.e.,
and $F_{e}\supseteq F_{e+1}$ for each $e$.

Let $g\in 2^{\omega}$ denote the true path, namely, the leftmost path in
$\\{0,1,2\\}^{\omega}$ such that $\forall
e\;\exists^{\infty}s\,[g\operatorname{\upharpoonright}e\preceq\delta_{s}]$. In
the following, given $e$, let $\alpha=g\operatorname{\upharpoonright}e$, and
let $s_{\alpha}$ be the largest stage $s$ such that $\alpha$ is initialized at
stage $s$. Note that $s_{\alpha}$ exists: The only concern would be that
$\alpha$ has the form $\tilde{\alpha}\widehat{\ }2$ and we are at substage
$|\tilde{\alpha}|$ in Case 1; however, $\alpha$ can only be initialized once
in that way unless $\delta_{r}<_{L}\alpha$ at a later stage $r$, namely, when
the number $\tilde{\alpha}$ has reserved is processed.

We verify a number of claims.

######  Claim 5.5.

The “streaming properties” (1)–(5) hold.

(1) and (2) hold by construction.

(3) Assume this fails for incomparable $\gamma$ and $\beta$, so $x\in
S_{\gamma}\cap S_{\beta}$ at stage $s$. We may as well assume that
$\gamma=\alpha\widehat{\ }i$ and $\beta=\alpha\widehat{\ }k$ where $i<k$. By
construction, $k\leq 1$ is not possible, so $k=2$. Since $x\in
S_{\alpha\widehat{\ }i}$ and $i\leq 1$, $x$ was reserved by $\alpha$ at some
stage $t\leq s$. So $x$ can never enter $S_{\alpha\widehat{\ }2}$ by the
initialization of $\alpha\widehat{\ }2$ when $x$ was reserved.

(4) is true by construction.

(5) holds inductively, by the definition of the true path and because
$S_{\alpha}$ is enumerated in increasing fashion at stages $\geq s_{\alpha}$.

######  Claim 5.6.

$F_{e}=^{*}S_{\alpha}$.

The claim is verified by induction on $e$. We show that for all $x>s_{\alpha}$
we have $x\in F_{e}$ if and only if $x\in S_{\alpha}$. It holds for $e=0$
because $F_{0}=S_{\emptyset}=\omega$. For the inductive step, let
$\gamma=g\operatorname{\upharpoonright}(e+1)$.

First, we verify that $F_{e+1}\cap(s_{\gamma},\infty)\subseteq S_{\gamma}$.
Suppose that $x>s_{\gamma}$ and $x\in F_{e+1}$. Then $x\in F_{e}$ and
$x>s_{\alpha}$, so by the inductive hypothesis $x\in S_{\alpha}$. By
construction, any element $x$ that is not promoted to $S_{\gamma}$ is also
removed from $F_{e+1}$ unless $x$ is the last element $\alpha$ reserves.
However, if $x$ is the last reserved element, then necessarily
$\gamma=\alpha\widehat{\ }2$ and this strategy is initialized when this
element is reserved, so $x<s_{\gamma}$ contrary to our assumption.

Next, we verify that $S_{\gamma}\cap(s_{\gamma},\infty)\subseteq F_{e+1}$.
Suppose that $x\in S_{\gamma}$ and $x>s_{\gamma}$. Then $x\in S_{\alpha}$, so
by the inductive hypothesis $x\in F_{e}$. At a stage $s\geq s_{\gamma}$, an
element $x$ of $S_{\alpha}$ cannot be removed from $F_{e+1}$ by a strategy
$\beta>_{L}\alpha$ because $S_{\beta}\cap S_{\alpha}=\emptyset$ by (3) as
verified above and since $\beta$ can only remove elements from $S_{\beta}$. So
$x$ can only be removed by $\alpha\colon M_{e}$ or $\alpha\colon P_{e}$.

If $\alpha\colon M_{e}$ removes $x$ from $F_{e+1}$, then
$x\not\in\widetilde{S}_{\alpha}$, which contradicts that $x\in S_{\gamma}$.
So, by construction, the only way $x$ can be removed from $F_{e+1}$ is by the
strategy $\alpha\colon P_{e}$, but since $x>s_{\gamma}$ this would mean that
$x$ is not promoted to $S_{\gamma}$ either contrary to our assumption.

######  Claim 5.7.

Each requirement $M_{e}$ is met, namely, $F_{e}\smallsetminus F_{e+1}$ is
infinite.

To see this, recall that $\alpha=g\operatorname{\upharpoonright}e$. By the
foregoing claim, the action of $\alpha:M_{e}$ removes infinitely many elements
of $S_{\alpha}\subseteq F_{e}$ from $F_{e+1}$.

######  Claim 5.8.

Each requirement $P_{e}$ is met.

Suppose the hypothesis of $P_{e}$ holds. Then every number that $\alpha$
reserves is eventually processed. So either $g(e)=0$, in which case
$F_{e+1}\subseteq^{*}V_{e,0}$ by Claim 5.6, or $g(e)=1$, in which case
$F_{e+1}\subseteq^{*}V_{e,1}$, also by Claim 5.6. ∎

##  6\. Ultrafilter bases for other Boolean algebras

As mentioned, we have set up our framework to apply to general countable
Boolean algebras rather than merely the Boolean algebra of the computable sets
mainly with subsequent research in mind. In this last section of our paper, we
provide two results in the setting of other Boolean algebras of sets.

Recall that $K(x)$ denotes the prefix-free complexity of a string $x$, and
that a set $A\subseteq\omega$ is _$K$ -trivial_ if $\exists c\,\forall
n\,K(A\operatorname{\upharpoonright}n)\leq K(0^{n})+c$. For more background on
$K$-trivial sets, see, e.g., Nies [13, Ch. 5] or Downey and Hirschfeldt [5,
Ch. 11]. Note that by combining results of various authors, the $K$-trivial
degrees form a Turing ideal in the $\Delta^{0}_{2}$-degrees (see, e.g., Nies
[13, Sections 5.2, 5.4]). Thus the $K$-trivial sets form a Boolean algebra.

######  Theorem 6.1.

There is a $\Delta^{0}_{2}$-ultrafilter base for the Boolean algebra of the
$K$-trivial sets.

###### Proof.

Kučera and Slaman [10] noted that there is a $\Delta^{0}_{2}$-function $h$
that dominates all functions that are partial computable in some $K$-trivial
set. We use $h$ in a variation of the proof of Theorem 3.8.

Let ${\left\langle{V_{e,0},V_{e,1}}\right\rangle}_{e\in\omega}$ be a uniform
listing of the $K$-trivials and their complements given by wtt-reductions to
${\emptyset^{\prime}}$; such a listing exists by Downey, Hirschfeldt, Nies,
and Stephan [4] (see also [13, Theorem 5.3.28]). Let $T=\\{0,1\\}^{<\infty}$.

For each $\alpha\in T$, we define a (possibly finite) $K$-trivial set
$S_{\alpha}$. Let $S_{\emptyset}=\omega$. Suppose we have defined the set
$S_{\alpha}=\\{r_{0}<r_{1}<\cdots\\}$. Let $\widetilde{S}_{\alpha}$ contain
the numbers of the form $r_{2i}$. Let $S_{\alpha\widehat{\
}k}=\widetilde{S}_{\alpha}\cap V_{e,k}$ for $e=|\alpha|$ and $k=0,1$. Note
that all these sets are $K$-trivial.

Uniformly recursively in ${\emptyset^{\prime}}$, we build sets $F_{e}$, given
by nondecreasing unbounded sequences of numbers $a^{e}_{0}\leq
a^{e}_{1}\leq\ldots$. Suppose we have defined $a^{e}_{k-1}$. Let $\alpha\in T$
be the leftmost string of length $e$ such that $S_{\alpha}$ has at least $k+1$
elements less than $h(k)$. If $\alpha$ exists, let $a^{e}_{k}$ be the $k$-th
element of $S_{\alpha}$, unless this is less than $a^{e}_{k-1}$, in which case
we let $a^{e}_{k}=a^{e}_{k-1}$.

Let $g\in 2^{\omega}$ denote the leftmost path in $\\{0,1\\}^{\omega}$ such
that for every $e$, the set $S_{g\operatorname{\upharpoonright}e}$ is
infinite. Fix $e$ and let $\alpha=g\operatorname{\upharpoonright}e$. Let
$p(k)$ be the $(k+1)$-st element of $S_{\alpha}$. Since $h$ dominates the
function $p$, eventually in the definition of $F_{e}$ we will always pick
$\alpha$. Hence $F_{e}=^{*}S_{\alpha}$. In particular, $F_{e}$ is $K$-trivial.
Also, the sequences ${\left\langle{a^{e}_{k}}\right\rangle}_{k\in\omega}$ are
unbounded for each $e$, so $F$ is $\Delta^{0}_{2}$. Clearly, if $S_{\alpha}$
is infinite then $S_{\alpha}\supset_{\infty}S_{\beta}$ for $\alpha\prec\beta$.
So $F_{e+1}\subset^{*}_{\infty}F_{e}$.

To verify that $F$ is an ultrafilter base for the $K$-trivials, let $R$ be a
$K$-trivial set. Pick $e$ such that $R=V_{e,0}$ and $\overline{R}=V_{e,1}$. If
$g(e)=0$ then $S_{g\,\operatorname{\upharpoonright}{e+1}}\subseteq V_{e,0}$,
and hence $F_{e+1}\subseteq^{*}R$. Otherwise
$S_{g\,\operatorname{\upharpoonright}{e+1}}\subseteq V_{e,1}$, and hence
$F_{e+1}\subseteq^{*}\overline{R}$. ∎

######  Remark 6.2.

Any ultrafilter base for the $K$-trivials must have high degree. We can see
this by modifying the proof of Theorem 3.6: Every Martin-Löf random set $X$ is
Martin-Löf random relative to every $K$-trivial (i.e., $K$-trivial sets are
_low for ML-randomness_). Hence neither $X$ nor $\overline{X}$ contains an
infinite $K$-trivial subset.

Finally, we consider the Boolean algebra of primitive recursive sets. One says
that an oracle $L$ is of PA degree if it computes a completion of Peano
arithmetic. Recall that $L$ is of PA degree if and only if it computes a
separating set for each disjoint pair of c.e. sets.

######  Theorem 6.3.

An oracle $C$ computes an ultrafilter base for the primitive recursive sets if
and only if $C^{\prime}$ is of PA degree relative to ${\emptyset^{\prime}}$.

###### Proof.

We modify the proof of Jockusch and Stephan [9, Theorem 2.1]. They call a set
$S\subseteq\omega$ _$p$ -cohesive_ if $S$ is cohesive for the primitive
recursive sets. Their theorem states that $S$ is $p$-cohesive if and only if
$S^{\prime}$ is of PA degree relative to ${\emptyset^{\prime}}$.

$\Rightarrow:$ Suppose that $C$ computes an ultrafilter base $F$ for the
primitive recursive sets. Let $g\leq_{\mathrm{T}}F$ be a function associated
with $F$ as in Definition 1.2. Then the range $S$ of $g$ is $p$-cohesive.
Hence $S^{\prime}$ and therefore $C^{\prime}$ is of PA relative to
${\emptyset^{\prime}}$ by one implication of [9, Theorem 2.1].

$\Leftarrow:$ We modify the proof of the other implication of [9, Theorem
2.1]. Let ${\left\langle{A_{i}}\right\rangle}_{i\in\omega}$ be a uniformly
recursive list of all the primitive recursive sets. We call $i$ a _primitive
recursive index for $A_{i}$_ (or _index_ , for short). By our hypothesis on
$C$, there is a function $g\leq_{\mathrm{T}}C^{\prime}$ such that

$\displaystyle|A_{i}\cap A_{n}|<|A_{i}\cap\overline{A}_{n}|$
$\displaystyle\Rightarrow$ $\displaystyle g(i,n)=0$
$\displaystyle|A_{i}\cap\overline{A}_{n}|<|A_{i}\cap A_{n}|$
$\displaystyle\Rightarrow$ $\displaystyle g(i,n)=1$

(because the conditions on the left are both $\Sigma^{0}_{2}$, and so
$C^{\prime}$ computes a separating set for them).

We inductively define a $C^{\prime}$-computable sequence of indices
${\left\langle{e_{n}}\right\rangle}_{n\in\omega}$. Let $e_{0}$ be an index for
$\omega$. If $e_{n}$ has been defined and $A_{e_{n}}=\\{r_{0}<r_{1}<\cdots\\}$
(possibly finite), let $e^{\prime}_{n}$ be an index, uniformly obtained from
$e_{n}$, such that $A_{e^{\prime}_{n}}=\\{r_{0},r_{2},\ldots\\}$. Now let

$A_{e_{n+1}}=A_{e^{\prime}_{n}}\cap\overline{A}_{n}$ if
$g(e^{\prime}_{n},n)=0$, and

$A_{e_{n+1}}=A_{e^{\prime}_{n}}\cap A_{n}$ if $g(e^{\prime}_{n},n)=1$.

By induction on $n$, one verifies that $A_{e_{n}}$ is infinite and
$A_{e_{n+1}}\subset_{\infty}A_{e_{n}}$. Since $g\leq_{\mathrm{T}}C^{\prime}$,
the numbers $e_{n}$ have a uniformly $C$-computable approximation
${\left\langle{e_{n,x}}\right\rangle}_{x\in\omega}$.

Let the ultrafilter base $F\leq_{\mathrm{T}}C$ be given by
$F_{n}(x)=A_{e_{n,x}}(x)$. Then $F_{n}=^{*}A_{e_{n}}$ is primitive recursive.
Since $F_{n+1}\subseteq^{*}\overline{A}_{n}$ or $F_{n+1}\subseteq^{*}A_{n}$
for each $n$, the set $F$ is an ultrafilter base for the primitive recursive
sets. ∎

## References

  * [1] Andreas R. Blass.  Combinatorial cardinal characteristics of the continuum.  In: Matthew Foreman and Akihiro Kanamori, editors, Handbook of Set Theory, volume 1, pages 395–489. Springer, Dordrecht Heidelberg London New York, 2010.
  * [2] Jörg Brendle, Andrew D. Brooke-Taylor, Keng Meng Ng, and André O. Nies.  An analogy between cardinal characteristics and highness properties of oracles.  In: Proceedings of the 13th Asian Logic Conference: Guangzhou, China, pages 1–28. World Scientific, 2013.  http://arxiv.org/abs/1404.2839.
  * [3] Jörg Brendle, Vera V. Fischer, and Yurii D. Khomskii.  Definable maximal independent families.  Proceedings of the American Mathematical Society, 147(8):3547–3557, 2019.
  * [4] Rodney G. Downey and Denis R. Hirschfeldt and André O. Nies, and Frank Stephan.  Trivial reals.  In Proceedings of the 7th and 8th Asian Logic Conferences, pages 103–131, Singapore, 2003. Singapore University Press.
  * [5] Rodney G. Downey and Denis R. Hirschfeldt.  Algorithmic randomness and complexity.  Springer–Verlag, Berlin, 2010.  855 pages.
  * [6] André O. Nies (editor).  Logic Blog 2019.  Available at http://arxiv.org/abs/2003.03361, 2019.
  * [7] Noam Greenberg, Rutger Kuyper, and Daniel D. Turetsky.  Cardinal invariants, non-lowness classes, and Weihrauch reducibility.  Computability, 8(3-4):305–346, 2019.
  * [8] Carl G. Jockusch, Jr.  Degrees in which the recursive sets are uniformly recursive.  Canad. J. Math., 24:1092–1099, 1972.
  * [9] Carl G. Jockusch, Jr. and Frank Stephan.  A cohesive set which is not high.  Math. Log. Quart., 39:515–530, 1993.
  * [10] Antonín Kučera and Theodore A. Slaman.  Low upper bounds of ideals.  J. Symbolic Logic, 74:517–534, 2009.
  * [11] Steffen Lempp, André O. Nies, and D. Reed Solomon.  On the filter of computably enumerable supersets of an r-maximal set.  Archive for Mathematical Logic, 40(6):415–423, 2001.
  * [12] Maryanthe Malliaris and Saharon Shelah.  General topology meets model theory, on $\mathfrak{p}$ and $\mathfrak{t}$.  Proceedings of the National Academy of Sciences, 110(33):13300–13305, 2013.
  * [13] André O. Nies.  Computability and Randomness, volume 51 of Oxford Logic Guides.  Oxford University Press, Oxford, 2009.  444 pages. Paperback version 2011.
  * [14] Nicholas A. Rupprecht.  Effective correspondents to cardinal characteristics in Cichoń’s diagram.  PhD thesis, University of Michigan, 2010.
  * [15] Nicholas A. Rupprecht.  Relativized Schnorr tests with universal behavior.  Arch. Math. Logic, 49(5):555–570, 2010.
  * [16] Theodore A. Slaman and Robert M. Solovay.  When oracles do not help.  In Proceedings of the fourth annual workshop on Computational learning theory, pages 379–383. Morgan Kaufmann Publishers Inc., 1991.
  * [17] Robert I. Soare.  Recursively Enumerable Sets and Degrees.  Perspectives in Mathematical Logic, Omega Series. Springer–Verlag, Heidelberg, 1987.
  * [18] David Soukup.  Two infinite quantities and their surprising relationship.  arXiv preprint arXiv:1803.04331, 2018.
  * [19] Edward L. Wimmers.  The Shelah P-point independence theorem.  Israel Journal of Mathematics, 43:28–48, 1982.


rightsretained 978-1-4503-6819-3/20/04 https://doi.org/10.1145/3334480.XXXXXXX

# Safe Handover in Mixed-Initiative Control for Cyber-Physical Systems

Frederik Wiehr
Anke Hirsch
Florian Daiber
Antonio Krüger

Alisa Kovtunova
Stefan Borgwardt

Ernie Chang
Vera Demberg

Marcel Steinmetz
Jörg Hoffmann

German Research Center for Artificial Intelligence (DFKI)  Saarland
Informatics Campus  Institute of Theoretical Computer Science, TU Dresden
<EMAIL_ADDRESS>Saarland University  Saarland Informatics
Campus<EMAIL_ADDRESS>Saarland University  Saarland Informatics
Campus<EMAIL_ADDRESS>
(2020)

###### Abstract

For mixed-initiative control between cyber-physical systems (CPS) and its
users, it is still an open question how machines can safely hand over control
to humans. In this work, we propose a concept to provide technological support
that uses formal methods from AI – description logic (DL) and automated
planning – to predict more reliably when a hand-over is necessary, and to
increase the advance notice for handovers by planning ahead of runtime. We
combine this with methods from human-computer interaction (HCI) and natural
language generation (NLG) to develop solutions for safe and smooth handovers
and provide an example autonomous driving scenario. A study design is proposed
with the assessment of qualitative feedback, cognitive load and trust in
automation.

###### keywords:

criticality; mixed-initiative control; safety; cyber-physical system; car
driving; multimodal interaction; human-computer interaction; natural language
generation; description logics; automated planning; critical interaction;
interdisciplinary

††conference: CHI’20 April 25–30, 2020, Honolulu, HI, USA

<ccs2012> <concept> <concept_id>10003120.10003121</concept_id>
<concept_desc>Human-centered computing Human computer interaction
(HCI)</concept_desc> <concept_significance>500</concept_significance>
</concept> <concept>
<concept_id>10003120.10003121.10003122.10003334</concept_id>
<concept_desc>Human-centered computing User studies</concept_desc>
<concept_significance>100</concept_significance> </concept> </ccs2012>

<ccs2012> <concept> <concept_id>10003120.10003121</concept_id>
<concept_desc>Human-centered computing Human computer interaction
(HCI)</concept_desc> <concept_significance>500</concept_significance>
</concept> <concept>
<concept_id>10003120.10003121.10003122.10003334</concept_id>
<concept_desc>Human-centered computing User studies</concept_desc>
<concept_significance>100</concept_significance> </concept> </ccs2012>

[500]Human-centered computing Human computer interaction (HCI) [100]Human-
centered computing User studies

##  1 Introduction

Mixed-initiative control systems have shown that when decisions are made or
suggested by automated systems it is essential that an explanation should be
provided [13]. An example of such a system is found in autonomous driving,
where the cyber-physical system (CPS) derives responses from navigation
functions based on human input.

Proposed system architecture

The purpose of this paper is to develop a framework to support a safe and
stress-limiting handover of control to the driver, combining benefits derived
from formal AI methods, human-computer interaction (HCI) and natural language
generation (NLG). The system must alert the user in the “best possible way”
when a handover is required. Practically, this poses the challenge that human
factors may render the handover process difficult to achieve [11], in part due
to the lack of _situation awareness_ in the presence of a secondary task
embedded in the experimental setups. The driver, if distracted, must be able
to promptly re-establish awareness of the situation, using sensory cues from
the environment. The autonomous car can support this situation awareness by
communicating its knowledge of the situation at the time of the transition.
Moreover, the system may interact with the user, or takeover in the case of
non-response.

Towards this end, we describe our implemented framework which utilizes the
relevant environment-state information from the open-source simulator for the
autonomous system AirSim [31], and propose a preliminary study design on the
effect of varying the modality and timeliness of explanations in a simulated
driving experience, with four handover situations.

##  2 Related Work

The related work in HCI can be separated into user modeling, situation
awareness/vigilance, and multimodal interaction.

User modeling enables a system to maintain a conceptual understanding of the
user (user model [22], in which user differences need to be modeled
explicitly). Tailoring hand-over requests by the system to individual users
makes it possible to take into account the user’s experience as well as
individual differences relating to cognitive capacity.

Situation awareness describes the human’s awareness of the environment, e.g. a
critical situation for a task at hand [11]. Such information depends strongly
on the situation (e.g. a pilot approaching an airport vs. a driver navigating
in dense traffic). Prior research utilizes operational quantitative human
factors to assess the situation awareness of human operators [2]. In highly
automated systems, the risk of humans being out-of-the-loop increases and thus
a potential handover is more difficult to achieve [11]. The degree of
vigilance influences the ability of a human to attend to the environment. Past
research has developed vigilance measures based on questionnaires, and sensors
assessing heart rate, eye movement and skin conductance [10].

Multimodal interaction has the potential to increase the usability and thus
the safety of operation [6]. It has been used for mobile applications and
environments, including gesture and speech [33], eye tracking and face
detection [26], and tangible interaction [21] to adapt to the user’s needs.
Moreover, the styles of visualization can improve “trust” in autonomous
driving [16], while identified feedback factors [23, 16] improve the
understandability and trust of system decisions made in autonomous driving.

##  3 Architecture

###  3.1 Planning

The reasoning capabilities of modern AI planners [12, 30] provide the
possibility to foresee _critical situations_ the autonomous system’s decisions
may lead to in the future, i.e. situations that cannot be reliably handled by
the system on its own. Identifying such situations ahead of time is not only
crucial for a successful transfer of control to the user, but may actually
allow the handover to be avoided altogether in certain cases.

To identify and to anticipate critical situations, a planner builds upon an
abstract model consisting of two major components: (1) _state features_ that
allow representation of an abstract view of the world for a specific point in
time (e.g. current position and speed of the car), and the (2) _actions_ the
autonomous system can do at an abstract level (e.g. accelerating, changing
lanes).

In our architecture, AI planning is used for two purposes: (1) _monitoring_ ,
and (2) _replanning_. By default, in (1) the planner is only used to test the
autonomous system’s decisions via simulations within the abstract world model;
and (2) uses planning to check the existence of an alternative to the
autonomous system’s decisions in order to avoid other critical situations.

###  3.2 Description Logics

Knowledge representation based on description logics (DLs) allows us to
describe the complex environment in a so-called ontology, specifying
constraints for the system states and for reasoning about the domain
knowledge. Ontologies have, for example, been proposed for real-time patient
monitoring [20, 29], detecting composite dance movements in annotated ballet
videos [27], and weather and turbine monitoring [3].

By design, description logics are close to human reasoning and can supply
explanations for decisions made by a cyber-physical system based on an
ontology. The DL component in our architecture provides input for the planning
component. By performing Boolean temporal query answering over a sequence of
potential future states, the DL component assesses the criticality level of
this route. Temporal queries describe different potentially dangerous
situations on a road. The level of criticality that is reported to the
planning component depends on the number and severity of the situations that
are detected.

###  3.3 Natural Language Generation

Description logic expressions serve as the semantic inputs to natural language
generation (NLG) systems, which is analogous to the task of data-to-text
generation. Traditionally, this is dealt with using a pipeline consisting of
_content planning_ , _sentence planning_ and _linguistic realization_ [28].
While the format of the data varies from task to task, it typically involves
the linearization step [25] where structured data are converted into
sequences, before being processed by downstream systems for _linguistic
realization_.

In the task of delivering handover message, NLG systems face a two-fold
challenge: (1) there is insufficient annotated data for every situation, (2)
handover messages should not cognitively overload the user, but instead be at
a situationally-appropriate level; see [9, 7, 15]. To this end, our proposed
NLG system adopts (A) semi-supervised NLG techniques [19, 4, 32, 5] that
minimize the required data and (B) an automatic quality estimator [8] that
assesses the information density of the message.

###  3.4 Human-Computer Interaction

For safe handovers in this context, the interaction side needs to be
considered and adapted depending on the anticipated critical situation by the
planner and DL component. Therefore, user modeling techniques can be applied
to assess differences implied by the situation (such as cognitive load and
vigilance: see below), as well as slowly changing individual user differences
such as task familiarity (e.g. differentiating between novices and expert
operators) [17]. To provide a basis for adaptations such as a multimodal hand-
over realization, the HCI component of the system uses ontologies to provide
access to and allow for interpretation of the user models [18]. Although
general user modeling is already established, the special safety-critical
aspects of handover situations are still insufficiently addressed by prior
research. Interface adaptations for cyber-physical systems have to be
carefully integrated with the handover planning and DL components with a focus
on safety critical situations. This includes developing concepts that respect
cognitive implications of human operators.

##  4 Conclusion & Outlook

Handover Timing

††margin:  Acknowledgments This work was partially supported by DFG grant
389792660 as part of TRR 248 (https://perspicuous-computing.science) and BMBF
grant 01IW17004 (http://tractat.dfki.de).

To gain insights into the use of a planner combined with description logics,
we have chosen highly automated driving as a use case for handover in safety
critical situations. Specifically, we plan to investigate handover scenarios
where the driver has to take over control of the car in a driving simulator
while performing a secondary task. The car or the systems can signal the
handover in four different conditions. A goal here would be to test whether
drivers would perceive additional verbal explanations as beneficial compared
to a classical handover technique. The classic hand-over simply issues a
notification at point B. Furthermore, the beep could be combined with either
(a) a preceding request to take over (planner) or (b) a subsequent explanation
about why the user had to take over (DL). The last condition could be a
combination of planner and DL where the participants get an explanation and a
request before the beep which signals them to take over. Planning enables the
car to initiate the handover in time (at point A, see Figure 4) whereas the
description logic alone can only generate the explanation in situ (at B). The
criticality of the handover situation can be increased by approaching a
construction zone in the driving simulator. Furthermore, the cause of an
additional danger can be introduced by different driving scenarios of the cars
in front of the participant. To avoid learning effects, four different driving
scenarios should be combined with the four aforementioned conditions, like a
unpredictable driver with odd steering behavior, a car that drives to the left
lane, a very slow driver with sudden braking or a truck with an unsecured
load. Quantitative as well as qualitative data will be collected to conduct
statistical analysis as well as participants’ personal evaluation of each
handover condition. The NASA-TLX [14] and the Trust in Automation
Questionnaire (TiA) [24] could assess cognitive load and trust in automated
systems, respectively. Last, a semi-structured interview can be conducted to
let the participants rank the different conditions and give reasons for the
ranking.

A current design error in today’s safety-critical systems is that these do not
feature built-in concepts to pre-plan, or to recognize and explain problem
causes to the user. Programs running in CPS participate in actions and
decisions that affect humans, especially in highly automated vehicles, when a
handover needs to be performed in critical situations. With the approach of
combining formal methods with HCI, we believe that generating verbal and
visual explanations in a timely manner using planning and description logics
can ease the process for the user of regaining situational awareness and allow
for a safe handover of control. We would like to further develop this idea
during the workshop and discuss possible scenarios and experimental designs.

## Acknowledgements

This research was funded in part by the German Research Foundation (DFG) as
part of SFB 248 “Foundations of Perspicuous Software Systems”. We sincerely
thank the anonymous reviewers for their insightful comments that helped us to
improve this paper.

## References

  * [1]
  * [2] Marilyn Jager Adams, Yvette J. Tenney, and Richard W. Pew. 1995.  Situation awareness and the cognitive management of complex systems.  Human Factors 37, 1 (1995), 85–104.  $\mathtt{D}$OI:http://dx.doi.org/10.1518/001872095779049462
  * [3] Sebastian Brandt, Elem Güzel Kalayci, Roman Kontchakov, Vladislav Ryzhikov, Guohui Xiao, and Michael Zakharyaschev. 2017.  Ontology-Based Data Access with a Horn Fragment of Metric Temporal Logic. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI’17). AAAI Press, 1070–1076.
  * [4] Ernie Chang, David Adelani, Xiaoyu Shen, and Vera Demberg. 2020a.  Unsupervised Pidgin Text Generation By Pivoting English Data and Self-Training. In In Proceedings of Workshop at ICLR.
  * [5] Ernie Chang, Jeriah Caplinger, Alex Marin, Xiaoyu Shen, and Vera Demberg. 2020b.  DART: A Lightweight Quality-Suggestive Data-to-Text Annotation Tool.  arXiv preprint arXiv:2010.04141 (2020).
  * [6] Philip R. Cohen and David R. McGee. 2004.  Tangible multimodal interfaces for safety-critical applications.  Commun. ACM 47, 1 (2004), 41–46.
  * [7] Matthew W Crocker, Vera Demberg, and Elke Teich. 2016.  Information density and linguistic encoding (IDeaL).  KI - Künstliche Intelligenz 30, 1 (2016), 77–81.
  * [8] José GC de Souza, Michael Kozielski, Prashant Mathur, Ernie Chang, Marco Guerini, Matteo Negri, Marco Turchi, and Evgeny Matusov. 2018\.  Generating e-commerce product titles and predicting their quality. In Proceedings of the 11th International Conference on Natural Language Generation. 233–243.
  * [9] Vera Demberg and Asad Sayeed. 2011.  Linguistic cognitive load: Implications for automotive UIs.  Proc. of AutomotiveUI 2011 (2011).
  * [10] Mica R. Endsley. 1995.  Measurement of situation awareness in dynamic systems.  Human Factors 37, 1 (1995), 65–84.
  * [11] Mica R. Endsley. 1996.  Automation and situation awareness.  Automation and human performance: Theory and applications (1996), 163–181.
  * [12] Malik Ghallab, Dana S. Nau, and Paolo Traverso. 2004.  Automated planning - theory and practice.  Elsevier.
  * [13] Bryce Goodman and Seth R. Flaxman. 2017.  European Union Regulations on Algorithmic Decision-Making and a "Right to Explanation".  AI Magazine 38, 3 (2017), 50–57.  https://www.aaai.org/ojs/index.php/aimagazine/article/view/2741
  * [14] Sandra G Hart and Lowell E Staveland. 1988.  Development of NASA-TLX (Task Load Index): Results of empirical and theoretical research.  In Advances in psychology. Vol. 52. Elsevier, 139–183.
  * [15] Katja I. Häuser, Vera Demberg, and Jutta Kray. 2019.  Effects of Aging and Dual-Task Demands on the Comprehension of Less Expected Sentence Continuations: Evidence From Pupillometry.  Frontiers in Psychology 10 (March 2019).  $\mathtt{D}$OI:http://dx.doi.org/10.3389/fpsyg.2019.00709
  * [16] Renate Häuslschmid, Max von Bülow, Bastian Pfleging, and Andreas Butz. 2017.  SupportingTrust in Autonomous Driving. In Proceedings of the 22nd International Conference on Intelligent User Interfaces (IUI ’17). Association for Computing Machinery, New York, NY, USA, 319–329.  $\mathtt{D}$OI:http://dx.doi.org/10.1145/3025171.3025198
  * [17] Dominik Heckmann and Antonio Krüger. 2003.  A user modeling markup language (UserML) for ubiquitous computing. In International Conference on User Modeling (UM). 393–397.
  * [18] Dominik Heckmann, Tim Schwartz, Boris Brandherrn, Michael Schmitz, and Margeritta von Wilamowitz-Moellendorff. 2005.  Gumo – the general user model ontology. In International Conference on User Modeling (UM). 428–432.
  * [19] Xudong Hong, Ernie Chang, and Vera Demberg. 2019.  Improving Language Generation from Feature-Rich Tree-Structured Data with Relational Graph Convolutional Encoders. In Proceedings of the 2nd Workshop on Multilingual Surface Realisation (MSR 2019). 75–80.
  * [20] Anna Hristoskova, Vangelis Sakkalis, Giorgos Zacharioudakis, Manolis Tsiknakis, and Filip De Turck. 2014.  Ontology-driven monitoring of patient’s vital signs enabling personalized medical detection and alert.  Sensors 14, 1 (2014), 1598–1628.  $\mathtt{D}$OI:http://dx.doi.org/10.3390/s140101598
  * [21] Vaiva Kalnikaite, Stefan Kreitmayer, Yvonne Rogers, Jon Bird, Nicolas Villar, Khaled Bachour, Stephen Payne, Peter M. Todd, Johannes Schöning, and Antonio Krüger. 2011.  How to nudge in Situ. In Proceedings of the 13th international conference on Ubiquitous computing - UbiComp '11. ACM Press.  $\mathtt{D}$OI:http://dx.doi.org/10.1145/2030112.2030115
  * [22] Alfred Kobsa and Wolfgang Wahlster. 1989.  User Models in Dialog Systems.  Springer.
  * [23] Jeamin Koo, Jungsuk Kwac, Wendy Ju, Martin Steinert, Larry Leifer, and Clifford Nass. 2015.  Why did my car just do that? Explaining semi-autonomous driving actions to improve driver understanding, trust, and performance.  International Journal on Interactive Design and Manufacturing (IJIDeM) 9, 4 (2015), 269–275.
  * [24] Moritz Körber. 2018.  Theoretical considerations and development of a questionnaire to measure trust in automation. In Congress of the International Ergonomics Association. Springer, 13–30.
  * [25] Simon Mille, Anja Belz, Bernd Bohnet, Emily Pitler, and Leo Wanner (Eds.). 2018.  Proceedings of the First Workshop on Multilingual Surface Realisation. Association for Computational Linguistics, Melbourne, Australia.  https://www.aclweb.org/anthology/W18-3600
  * [26] Jörg Müller, Juliane Exeler, Markus Buzeck, and Antonio Krüger. 2009.  Reflective Signs: Digital signs that adapt to audience attention. In IEEE International Conference on Pervasive Computing and Communications (PerCom). 17–24.
  * [27] Katerina El Raheb, Theofilos Mailis, Vladislav Ryzhikov, Nicolas Papapetrou, and Yannis E. Ioannidis. 2017.  BalOnSe: Temporal Aspects of Dance Movement and Its Ontological Representation. In The Semantic Web – 14th International Conference, ESWC 2017, Portorož, Slovenia, May 28 - June 1, 2017, Proceedings, Part II. 49–64.  $\mathtt{D}$OI:http://dx.doi.org/10.1007/978-3-319-58451-5_4
  * [28] Ehud Reiter and Robert Dale. 1997.  Building applied natural language generation systems.  Natural Language Engineering 3, 1 (March 1997), 57–87.  $\mathtt{D}$OI:http://dx.doi.org/10.1017/s1351324997001502
  * [29] Ahlem Rhayem, Mohamed Ben Ahmed Mhiri, Mayssa Ben Salah, and Faïez Gargouri. 2017.  Ontology-based system for patient monitoring with connected objects. In Knowledge-Based and Intelligent Information & Engineering Systems: Proceedings of the 21st International Conference KES-2017, Marseille, France, 6 - 8 September 2017. 683–692.  $\mathtt{D}$OI:http://dx.doi.org/10.1016/j.procs.2017.08.127
  * [30] Silvia Richter and Matthias Westphal. 2010.  The LAMA Planner: Guiding cost-based anytime planning with landmarks.  J. Artif. Intell. Res. 39 (2010), 127–177.  $\mathtt{D}$OI:http://dx.doi.org/10.1613/jair.2972
  * [31] Shital Shah, Debadeepta Dey, Chris Lovett, and Ashish Kapoor. 2018.  AirSim: High-fidelity visual and physical simulation for autonomous vehicles. In Field and Service Robotics. Springer, 621–635.
  * [32] Xiaoyu Shen, Ernie Chang, Hui Su, Cheng Niu, and Dietrich Klakow. 2020\.  Neural Data-to-Text Generation via Jointly Learning the Segmentation and Correspondence. In Proceedings of the 58th Annual Meeting of the Association for ….
  * [33] Rainer Wasinger, Antonio Krüger, and Oliver Jacobs. 2005.  Integrating intra and extra gestures into a mobile and multimodal shopping assistant. In International Conference on Pervasive Computing. 297–314.