11institutetext: Institute of Mathematical Sciences, National University of
Singapore
3 Prince George’s Park, Singapore 118402, Republic of Singapore
11email<EMAIL_ADDRESS>22institutetext: Department of Mathematics,
National University of Singapore
10 Lower Kent Ridge Road, Singapore 119076, Republic of Singapore
22email<EMAIL_ADDRESS>33institutetext: School of Computing,
National University of Singapore
Singapore 117417, Republic of Singapore
33email<EMAIL_ADDRESS>
# Learnability and Positive Equivalence Relations††thanks: D. Belanger (as
RF), Z. Gao (as RF) and S. Jain (as Co-PI), F. Stephan (as PI) have been
supported by the Singapore Ministry of Education Academic Research Fund grant
MOE2016-T2-1-019 / R146-000-234-112; the latter three have also been suported
by the Singapore Ministry of Education Academic Research Fund grant
MOE2019-T2-2-121 / R146-000-304-112. Furthermore, S. Jain is supported in part
by NUS grant C252-000-087-001. Part of the work was done while David Belanger
worked at Ghent University where he was supported by the BOF grant 01P01117.

David Belanger 11 Ziyuan Gao 22 Sanjay Jain 33
Wei Li and Frank Stephan, 222233

###### Abstract

Prior work of Gavryushkin, Khoussainov, Jain and Stephan investigated what
algebraic structures can be realised in worlds given by a positive (=
recursively enumerable) equivalence relation which partitions the natural
numbers into infinitely many equivalence classes. The present work
investigates the infinite one-one numbered recursively enumerable (r.e.)
families realised by such relations and asks how the choice of the equivalence
relation impacts the learnability properties of these classes when studying
learnability in the limit from positive examples, also known as learning from
text. For all choices of such positive equivalence relations, for each of the
following entries, there are one-one numbered r.e. families which satisfy it:
(a) they are behaviourally correctly learnable but not vacillatorily
learnable; (b) they are explanatorily learnable but not confidently learnable;
(c) they are not behaviourally correctly learnable. Furthermore, there is a
positive equivalence relation which enforces that (d) every vacillatorily
learnable one-one numbered family of languages closed under this equivalence
relation is already explanatorily learnable and cannot be confidently
learnable.

##  1 Introduction

Consider a learning scenario where all positive examples of a given target
concept $L$ belonging to a concept class $\mathcal{L}$ are shown sequentially
to a learner $M$. After processing each example, $M$ makes a conjecture as to
the identity of the target concept, based on some fixed representation system
of all concepts in $\mathcal{L}$. $M$ is said to successfully identify $L$ if
its sequence of conjectures converges to a correct hypothesis describing $L$.
This learning paradigm, due to Gold [20], is well-studied and has inspired the
development of a large number of other learning models in inductive inference
[21, 36].

In this work, we study how the interrelations between the elements of a domain
$X$ influences the learnability of classes of languages defined over $X$. The
domain of interest throughout this work is $\mathbb{N}$. We will be concerned
with _recursively enumerable (r.e.)_ equivalence relations defined on
$\mathbb{N}$ that induce infinitely many equivalence classes. The main
motivation for focussing on such relations comes from the study of r.e.
structures. Here, r.e. structures are given by a domain, recursive functions
representing basic operators in the structure, and some recursively enumerable
predicates, among which there is a recursively enumerable equivalence relation
$\eta$ with infinitely many equivalence classes which plays the role of
equality in the given structure. Such structures have been studied for a long
time; for example, Novikov [33] constructed a finitely generated group with
undecidable word-problem; in other words, there is a group which can be
represented using an r.e. but nonrecursive equivalence relation (as equality
of the group) but one cannot represent it using a recursive equivalence
relation $E$. On the other hand, for Noetherian rings [32], Baur [5] showed
that every r.e. Noetherian ring is a recursive ring, implying that the
underlying equality $\eta$ is always a recursive relation and that its
equivalence classes are uniformly recursive. Another example of an r.e.
equivalence relation is the relation of _provable equivalence_ with respect to
any formal system, say Peano Arithmetic (PA), where

> $x\sim_{\text{PA}}y$ holds iff $\alpha\leftrightarrow\beta$ is provable in
> PA.

Here $x$ and $y$ are the Gödel numbers of $\alpha$ and $\beta$, respectively,
according to some fixed Gödel numbering.
Fokina, Gavryushkin, Jain, Khoussainov, Semukhin, Stephan and Turetsky [15,
18, 19] focussed in a sequence of papers on the question of which type of
structures could be realised by an r.e. equivalence relation on $\mathbb{N}$
with infinitely many equivalence classes and how different relations compare
with respect to their ability to realise structures of certain type. Ershov
[12, 13], and following him Odifreddi [34], call r.e. equivalence relations
positive equivalence relations. Fokina, Kötzing and San Mauro [16] studied
Gold-style learnability of equivalence structures (with no computability
restrictions on the learner), and gave a structural characterisation of
families of equivalence structures with no infinite equivalence classes that
are learnable in the limit from informant. In follow-up work by Bazhenov,
Fokina and San Mauro [6], a model-theoretic characterisation of families of
general equivalence structures that are learnable in the limit from informant
was obtained.

Now a structure is realised by a positive equivalence relation $\eta$ iff
there is a bijection between the elements in the domain of the structure and
the equivalence classes of $\eta$ and all relations involved are r.e. and all
functions are realised by recursive functions which respect $\eta$. In the
simplest case of functions from the domain to the domain, they respect $\eta$
if they map $\eta$-equivalent numbers to $\eta$-equivalent numbers. This work
focusses on the study of learnability within the framework of families
realised by positive equivalence relations. In particular the topic of the
investigations is to what extent separations between learning criteria known
from inductive inference can be witnessed by $\eta$-closed sets, that is,
which of the positive equivalence relations witness a separation of two
learning criteria or collapse them. Furthermore one asks, whether certain
learning criteria can be void (non-existent) for certain equivalence relations
$\eta$. It could be shown that one single equivalence relation $\vartheta$
witnesses the two above mentioned collapses. The study of learning in a world
given by some $\eta$ is similar to that in complexity relative to an oracle;
one wants to know how robust the results from the non-relativised world are
and how much they generalise.

As mentioned earlier, a major topic investigated in this work is the
relationship between various learning criteria for a fixed but arbitrary
positive equivalence relation $\eta$ on $\mathbb{N}$. In particular, we study
the question of whether the strict hierarchy of learnability notions

$\mbox{Fin}\subset\mbox{Conf}\subset\mbox{Ex}\subset\mbox{Vac}\subset\mbox{BC}$

(see Definition 2), which holds with respect to the general class of uniformly
r.e. families (see [21]), carries over to the class of $\eta$-families for any
given positive equivalence relation $\eta$. Here for any learning criteria $A$
and $B$, we write $A\subset B$ to mean that the class of uniformly r.e.
families that are learnable under criterion $A$ is a strict subset of the
class of uniformly r.e. families that are learnable under criterion $B$. The
above inclusions follow directly from the definitions of the respective
learning criteria, so the main interesting question is whether the inclusions
are strict. It will be shown that many learnability relations that hold when
$\eta$ is just the usual equality relation on $\mathbb{N}$ carry over for
general $\eta$. In particular, the fact that the family of explanatorily
learnable classes of languages is a strict subset of the family of
behaviourally correctly learnable classes of languages, which is well-known
when $\eta$ is the equality relation [11, Theorem 3.1], holds for _any_
positive equivalence relation $\eta$ (see Theorem 11). On the other hand, we
show that for a special positive equivalence relation $\vartheta$, every
vacillatorily learnable $\vartheta$-family is already explanatorily learnable
(see Theorem 20); this is quite an interesting contrast to the case when
$\eta$ is the equality relation on $\mathbb{N}$, for which vacillatory
learning is known to be strictly more powerful than explanatory learning [8,
Theorem 3.3]. Furthermore, we extend the “non-union property” of explanatory
and behaviourally correct learning (that is, the family of explanatorily
(resp. behaviourally correctly) learnable classes is not closed under union)
[20] by showing that for any positive equivalence relation $\eta$, explanatory
learning is not closed under union with respect to $\eta$-families; we also
obtain a characterisation of all positive equivalence relations $\eta$ for
which behaviourally correct learning is closed under union with respect to
$\eta$-families (see Theorem 16). The current work thus serves a dual purpose:
first, casting inductive inference results in a more general framework, where
the elements of the domain over which concepts are defined can be interrelated
via any positive equivalence relation; second, modelling the learning of r.e.
structures endowed with any r.e. equality relation.

##  2 Preliminaries

Any unexplained recursion-theoretic notation may be found in [34, 37, 39]. The
set of natural numbers is denoted as $\mathbb{N}=\\{0,1,2,\ldots\\}$; the set
of all _partial recursive functions_ and of all _recursive functions_ of one,
and two arguments over $\mathbb{N}$ is denoted by ${\mathcal{P}}$,
${\mathcal{P}}^{2}$, ${\mathcal{R}}$ and ${\mathcal{R}}^{2}$ respectively. Any
function $\psi\in{\mathcal{P}}^{2}$ is called a _numbering of partial-
recursive functions_ — this numbering may or may not include all partial
recursive functions. Moreover, let $\psi\in{\mathcal{P}}^{2}$; the notion
$\psi_{e}$ stands for $\lambda x.\psi(e,x)$ and
${\mathcal{P}}_{\psi}=\\{\psi_{e}\mid e\in\mathbb{N}\\}$. A numbering
$\varphi\in{\mathcal{P}}^{2}$ is said to be an _acceptable numbering_ or
_Gödel numbering_ of all partial recursive functions if
${\mathcal{P}}_{\varphi}={\mathcal{P}}$ and for every numbering
$\psi\in{\mathcal{P}}^{2}$, there is a $c\in{\mathcal{R}}$ such that
$\psi_{e}=\varphi_{c(e)}$ for all $e\in\mathbb{N}$ (see [37]). Throughout this
paper, $\varphi_{0},\varphi_{1},\varphi_{2},\ldots$ is a fixed acceptable
numbering of all partial recursive functions and $W_{0},W_{1},W_{2},\ldots$ is
a fixed _numbering of all recursively enumerable sets_ (abbr. r.e. sets) of
natural numbers, where $W_{e}$ is the domain of $\varphi_{e}$ for all
$e\in\mathbb{N}$.

Let $e,x\in\mathbb{N}$; if $\varphi_{e}(x)$ is defined then we say that
$\varphi_{e}(x)$ _converges_. Otherwise, $\varphi_{e}(x)$ is said to
_diverge_. Furthermore, if the computation of $\varphi_{e}(x)$ halts within
$s$ steps of computation then we write
$\varphi_{e,s}(x)\\!\downarrow=\varphi_{e}(x)$; otherwise $\varphi_{e,s}(x)$
diverges. For all $e,s\in\mathbb{N}$ the set $W_{e,s}$ is defined as the
domain of $\varphi_{e,s}$. Given any set $S$, $S^{*}$ denotes the set of all
finite sequences of elements from $S$. By $D_{0},D_{1},D_{2},\ldots$ we denote
any fixed canonical indexing of all finite sets of natural numbers. _Turing
reducibility_ is denoted by $\leqslant_{T}$; $A\leqslant_{T}B$, where
$A,B\subseteq\mathbb{N}$, holds if $A$ can be computed via a Turing machine
which uses $B$ as an oracle; that is, it can give information on whether or
not $x$ belongs to $B$. $A\equiv_{T}B$ means that $A\leqslant_{T}B$ and
$B\leqslant_{T}A$ both hold. The symbol $K$ denotes the _diagonal halting
problem_ , i.e., $K=\\{e:e\in\mathbb{N},\;\varphi_{e}(e)\\!\downarrow\\}$.
Moreover, the _jump_ of $K$, denoted by $K^{\prime}$, is the relativised
halting problem $\\{e:e\in\mathbb{N},\;\varphi_{e}^{K}(e)\\!\downarrow\\}$,
where $\varphi_{0}^{K},\varphi_{1}^{K},\varphi_{2}^{K},\ldots$ is an
acceptable numbering of all partial-$K$-recursive functions, which are partial
functions depending on the input as well as on answers to queries of the form
“is $x$ in $K$?”.

For $\sigma\in(\mathbb{N}\cup\\{\\#\\})^{\ast}$ and $n\in\mathbb{N}$ we write
$\sigma(n)$ to denote the element in the $n$th position of $\sigma$. For any
finite sequence $\sigma$ we use $|\sigma|$ to denote the length of $\sigma$.
Further, whenever $n\leqslant|\sigma|$, $\sigma[n]$ denotes the sequence
$\sigma(0),\sigma(1),\ldots,\sigma(n-1)$. The concatenation of two sequences
$\sigma$ and $\tau$ is denoted by $\sigma\circ\tau$; for convenience, and
whenever there is no possibility of confusion, this is occasionally denoted by
$\sigma\tau$.

A class $\mathcal{L}$ is said to be _uniformly r.e._ (or just _r.e._) if there
is an r.e. set $S\subseteq\mathbb{N}$ such that $\mathcal{L}=\\{W_{i}:i\in
S\\}$. A class is said to be _one-one r.e._ , if the r.e. set $S$ as above
additionally satisfies the condition that for $i,j\in S$, $W_{i}=W_{j}$ iff
$i=j$. An r.e. class $\mathcal{L}=\\{B_{0},B_{1},\ldots\\}$ is said to be
_uniformly recursive_ or an _indexed family_ if there exists a recursive
function $f\in{\mathcal{R}}^{2}$ such that for all $i,x\in\mathbb{N}$, if
$x\in B_{i}$ then $f(i,x)=1$ else $f(i,x)=0$.

##  3 Learnability

Recursion-theoretic notation mainly follows the textbooks of Odifreddi [34],
Rogers [37] and Soare [39]. Background on inductive inference may be found in
[21]. Let $\mathcal{L}$ be a class of r.e. languages. Throughout this paper,
the mode of data presentation is that of a _text_. A text is any infinite
sequence of natural numbers and the $\\#$ symbol, where the symbol $\\#$
indicates a pause in the data presentation. More formally, a _text_ $T_{L}$
for a language $L\in\mathcal{L}$ is any total mapping
$T_{L}:\mathbb{N}\to\mathbb{N}\cup\\{\\#\\}$ such that
$L=\operatorname{range}(T_{L})-\\{\\#\\}$. We use $\operatorname{content}(T)$
to denote the set $\operatorname{range}(T)-\\{\\#\\}$, i.e., the content of a
text $T$ contains only the natural numbers appearing in $T$. Furthermore, for
every $n\in\mathbb{N}$ we use $T[n]$ to denote the finite sequence
$T(0),\ldots,T(n-1)$, i.e., the _initial segment_ of length $n$ of $T$.
Analogously, for a finite sequence $\sigma\in(\mathbb{N}\cup\\{\\#\\})^{\ast}$
we use $\operatorname{content}(\sigma)$ to denote the set of all numbers in
the range of $\sigma$.

###### Description 1

Further basic ingredients of the notions considered in this paper are as
follows.

  1. (1)

For each positive equivalence relation $\eta$, one can define an infinite
sequence $a_{0},a_{1},\ldots$ of least representatives of the equivalence
classes where each $a_{n}$ is the ascending limit of approximations $a_{n,t}$
where $a_{n,t}$ is the least natural number which is not $\eta_{t}$-equivalent
to any $a_{m,t}$ with $m<n$ (where $\eta_{t}$ denotes the approximation to
$\eta$ after $t$ steps of enumeration and is closed under reflexivity and
transitivity). Alternatively, one can obtain $\eta$ from a construction of
such a sequence where the $a_{n,t}$ approximate the $a_{n}$ from below and
whenever an $a_{n,t+1}\neq a_{n,t}$ then $a_{n,t+1}=a_{m,t}$ for some $m>n$
and whenever $a_{n,t}$ is not in the list at $t+1$ then it is put into the
equivalence class of some $a_{m,t}$ with $m<n$. Some algorithms to construct
the equivalence relation $\eta$ explain on how to update these approximations
to $a_{0},a_{1},\ldots$ and one should note that (the construction implies)
the limit satisfies $a_{0}<a_{1}<\ldots$ and that for each $n$ there are only
finitely many $t$ with $a_{n,t}<a_{n,t+1}$.

  2. (2)

The classes whose learnability are considered are given by a uniformly r.e.
one-one numbering of sets $B_{0},B_{1},\ldots$ where each set $B_{k}$ is a
union of $\eta$-equivalence classes; however, the indices $k$ of $B_{k}$ are
usual natural numbers and not equivalence-classes of $\eta$. Such a family is
called an $\eta$-family below and note that $\eta$-families are always
infinite.

  3. (3)

Infinite indexed families as considered by Angluin [1] are too restrictive, as
they might not exist for some $\eta$; however, every infinite indexed family
has a one-one numbering and thus using the notion of infinite uniformly r.e.
one-one numberings is the adequate choice for the present work.

  4. (4)

The learner sees an infinite sequence $x_{0},x_{1},\ldots$ of members of one
set $B_{k}$ (such sequences are called texts and can have pauses represented
by a special pause symbol $\\#$) and the learner has to find in the limit an
r.e. index for $B_{k}$, which may or may not be equal to $k$.

  5. (5)

The hypotheses issued by the learners are always indices from a hypothesis
space given as a numbering of $\eta$-closed r.e. sets; the most general
hypothesis space is that of the $\eta$-closures of the members of a given
acceptable numbering of all r.e. sets.

  6. (6)

The present work focusses on the following learning criteria [3, 8, 10, 14,
20, 21, 35, 36]: Explanatory learning, where the hypotheses of the learner
converge on every text for a set $B_{k}$ to a single index of $B_{k}$;
Confident learning, which is explanatory learning with the additional
requirement that the learner also on texts not belonging to any language in
the class has to converge to some index; Behaviourally correct learning, which
is more general than explanatory learning and where the learner is only
required to output on any text for $B_{k}$ almost always an index for $B_{k}$
but these indices can all be different; Vacillatory learning, where a learner
is vacillatory iff it is a behaviourally correct learner for the class, with
the additional constraint that on every text for a language $B_{k}$ in the
class, the set of all hypotheses issued in response to this text is finite
(thus, some of these hypotheses are output infinitely often).

We now provide formal definitions of these criteria as well as the criterion
of _finite_ learning (sometimes known as _one-shot learning_ in the
literature; see [20, 40]), which is a more restrictive version of explanatory
learning. In the following definitions, a learner $M$ is a recursive function
mapping $(\mathbb{N}\cup\\{\\#\\})^{*}$ into $\mathbb{N}\cup\\{?\\}$; the $?$
symbol allows $M$ to abstain from conjecturing at a stage. If $M$ is presented
with a text $T$ for any $\eta$-closed set $L$, it is enough to assume that
$\operatorname{content}(T)$ contains _at least one_ element of each
$\eta$-equivalence class contained in $L$; since $\eta$ is r.e., $M$ on $T$
could simulate a complete text for $L$ by enumerating at each stage $s$ the
$s$-th approximation of the current input’s $\eta$-closure.

The main learning criteria studied in this paper are _explanatory learning_
(also called _learning in the limit_) introduced by Gold [20] and
_behaviourally correct learning_ , which goes back to Feldman [14], who called
it _matching in the limit_ ; later, it was also studied by Bārzdiņs̆, Case,
Lynes and Smith [3, 4, 10, 11]. A fairly natural learning constraint on these
criteria is _conservativeness_ [1], which requires that any syntactic (resp.
semantic) mind change by the explanatory (resp. behaviourally correct) learner
occur only if the learner’s original conjecture does not account for all the
data revealed in the text so far.

Furthermore, we will also consider _finite learning_ (see [20, 40]), which is
sometimes known as _one-shot learning_ in the literature. Other learning
criteria studied in this paper include _confident learning_ (see [21, 36]),
which requires the learner to converge syntactically on every text for any
language (even if it is outside the class to be learnt), and _vacillatory
learning_ (see [8]), according to which a learner is permitted to vacillate
between finitely many correct indices in the limit.

######  Definition 2 (Angluin [1], Bārzdiņš [3], Case and Smith [11], Feldman
[14], Gold [20], Osherson, Stob and Weinstein [36], Trakhtenbrot and Bārzdiņš
[40])

Let $\mathcal{L}$ be any class of r.e. languages.

  1. (1)

$M$ _explanatorily ( Ex) learns_ $\mathcal{L}$ if, for every $L$ in
$\mathcal{L}$ and each text $T_{L}$ for $L$, there is a number $n$ for which
$L=W_{M(T_{L}[n])}$ and, for every $j\geqslant n$, $M(T_{L}[j])=M(T_{L}[n])$.

  2. (2)

$M$ _behaviourally correctly ( BC) learns_ $\mathcal{L}$ if, for every $L$ in
$\mathcal{L}$ and each text $T_{L}$ for $L$, there is a number $n$ for which
$L=W_{M(T_{L}[j])}$ whenever $j\geqslant n$.

  3. (3)

$M$ _finitely ( Fin) learns_ $\mathcal{L}$ if, for every $L$ in $\mathcal{L}$
and each text $T_{L}$ for $L$, there is a number $n$ for which
$L=W_{M(T_{L}[n])}$ and for every $m<n$, $M(T_{L}[m])=\,?$ and for every
$j\geqslant n$, $M(T_{L}[j])=M(T_{L}[n])$.

  4. (4)

$M$ _confidently ( Conf) learns_ $\mathcal{L}$ if $M$ Ex learns $\mathcal{L}$
and $M$ converges on every text for any language, that is, for every
$L\subseteq\mathbb{N}$ and text $T_{L}$ for $L$, there is a number $n$ such
that for every $j\geqslant n$, $M(T_{L}[j])=M(T_{L}[n])$.

  5. (5)

$M$ _vacillatorily ( Vac) learns_ $\mathcal{L}$ if $M$ BC learns $\mathcal{L}$
and for every $L$ in $\mathcal{L}$ and each text $T_{L}$ for $L$,
$\\{M(T_{L}[n]):n\geqslant 1\\}$ is finite.

  6. (6)

$M$ _conservatively explanatorily learns_ $\mathcal{L}$ if $M$ Ex learns
$\mathcal{L}$ and for all $n\in\mathbb{N}$, $k\geqslant 1$, $M(T[n])\neq
M(T[n+k])$ only if $\operatorname{content}(T[n+k])\not\subseteq W_{M(T[n])}$.

  7. (7)

$M$ _conservatively behaviourally correctly learns_ $\mathcal{L}$ if $M$ BC
learns $\mathcal{L}$ and for all $n\in\mathbb{N}$, $k\geqslant 1$,
$W_{M(T[n])}\neq W_{M(T[n+k])}$ only if $\operatorname{content}(T$
$[n+k])\not\subseteq W_{M(T[n])}$.

We will also consider the learning constraint of _monotonicity_ [24, 29, 41].
Furthermore, we give some results concerning the dependence of learnability on
the choice of hypothesis space. When considering learnability based on the
choice of hypothesis space $\\{H_{0},H_{1},H_{2},\ldots\\}$, one replaces the
hypotheses $W_{0},W_{1},\ldots$ in Definition 2 by $H_{0},H_{1},\ldots$. This
work studies three types of requirements on the learner’s hypothesis space:
the hypothesis space can be class-comprising, class-preserving or _exact_
[28].

A learner $M$ is said to be _monotonic_ [41] if, for all texts $T$ for some
language in the target class, whenever $M$ on input $T[n]$ outputs $j_{n}$ and
then at some subsequent step outputs $j_{n+k}$ on input $T[n+k]$, the
condition $W_{j_{n}}\cap\operatorname{content}(T)\subseteq
W_{j_{n+k}}\cap\operatorname{content}(T)$ holds.

A learner $M$ is said to be _strongly monotonic_ [24] if, for all texts $T$,
whenever $M$ on input $T[n]$ outputs $j_{n}$ and then at some subsequent step
outputs $j_{n+k}$ on input $T[n+k]$, the condition $W_{j_{n}}\subseteq
W_{j_{n+k}}$ holds.

A learner $M$ is said to be _weakly monotonic_ [29] if, for all texts $T$,
whenever $M$ on input $T[n]$ outputs $j_{n}$ and then at some subsequent step
outputs $j_{n+k}$ on input $T[n+k]$, the condition
$\operatorname{content}(T[j+k])\subseteq W_{j_{n}}\Rightarrow
W_{j_{n}}\subseteq W_{j_{n+k}}$ holds.

A learner $M$ is said to be _class-comprising_ [28, 30] if it learns the
target class $\mathcal{L}$ with respect to at least one hypothesis space
$\\{H_{0},H_{1},\ldots\\}$; note that learnability automatically implies
$\mathcal{L}\subseteq\\{H_{0},H_{1},\ldots\\}$.

Unless otherwise stated, the learner’s hypothesis space will be taken as the
$\eta$-closure of $W_{0},W_{1},\ldots$; in other words, the learner is class-
comprising. For the notions of class-preserving and exact learning, one
considers some other recursively enumerable hypothesis space
$H_{0},H_{1},\ldots$ for interpreting the hypothesis of the learner. Only
uniformly recursively enumerable hypothesis spaces are considered.

A learner $M$ is said to be _class-preserving_ [28, 30] if it learns the
target class $\mathcal{L}$ with respect to at least one hypothesis space
$\\{H_{0},H_{1},\ldots\\}$ such that $\\{H_{0},H_{1},\ldots\\}=\mathcal{L}$.

A learner $M$ is said to be _exact_ [28, 30] if it learns the target class
$\mathcal{L}:=\\{L_{0},L_{1},\ldots\\}$ using $\\{L_{0},L_{1},\ldots\\}$ as
its hypothesis space (in other words, for all $i\in\mathbb{N}$, the learner
outputs $i$ to signal that its conjecture is $L_{i}$).

Lange and Zeugmann [30] showed that for learning uniformly recursive families,
learnability is to some extent independent of the choice of hypothesis space
in that exact, class-preserving and class-comprising explanatory learnability
all coincide. Jain, Stephan and Ye [23] observed more generally that for any
finite (resp. explanatorily) learnable uniformly r.e. family $\mathcal{L}$ and
hypothesis space $\mathcal{H}:=\\{H_{0},H_{1},\ldots\\}$ such that
$\mathcal{H}$ and $\mathcal{L}$ consist of the same set of members (possibly
ordered differently), one can uniformly construct a finite (resp. explanatory)
learner for $\mathcal{L}$ with respect to $\mathcal{H}$ from an r.e. index of
$\\{{\left\langle d,x\right\rangle}:x\in H_{d}\\}$. Thus, as the present paper
deals exclusively with uniformly r.e. families, it will be assumed throughout
that finite (resp. explanatory) learning, class-preserving finite (resp.
explanatory) learning and exact finite (resp. explanatory) learning are all
equivalent (this equivalence may, however, fail if other learning constraints
are imposed at the same time).

In some cases we consider learners using oracles. In this case the learning
criterion $I$ when the learners are allowed use of oracle $A$ is denoted by
$I[A]$.

For every learning criterion $I$ considered in the present paper, there exists
a recursive enumeration $M_{0},M_{1},\ldots$ of the learning machines such
that if a class is $I$-learnable, then some $M_{i}$ $I$-learns the class. We
fix one such enumeration of learning machines. We will also consider
combinations of various learning criteria; for example, one could require a
learner to be both confident and behaviourally correct.

Throughout this work, we only consider positive equivalence relations that
induce _infinitely_ many equivalence classes. For any positive equivalence
relation $\eta$ and $x\in\mathbb{N}$, let $[x]$ be $\\{y:y\,\eta\,x\\}$.
Furthermore, for any $D\subseteq\mathbb{N}$, $[D]$ denotes $\bigcup_{x\in
D}[x]$. For any finite $\\{i_{0},\ldots,i_{n}\\}\subseteq\mathbb{N}$, the set
$[\\{a_{i_{0}},a_{i_{1}},\ldots,a_{i_{n}}\\}]$ will simply be denoted by
$[a_{i_{0}},a_{i_{1}},\ldots,$ $a_{i_{n}}]$. An _$\eta$ -family_ $\mathcal{L}$
is a uniformly r.e. one-one infinite family, each of whose members is a union
of $\eta$-equivalence classes. Note that uniformly recursive infinite families
might not exist for some $\eta$ and therefore an $\eta$-family is the nearest
notion to a uniformly recursive family which exists for each positive
equivalence relation $\eta$. A set is _$\eta$ -infinite_ (resp. $\eta$-finite)
if it is equal to a union of infinitely (resp. finitely) many
$\eta$-equivalence classes; note that an $\eta$-infinite set may not
necessarily be recursively enumerable. A set is _$\eta$ -closed_ if it is
either $\eta$-finite or $\eta$-infinite. In this paper, all families are
assumed to consist of only $\eta$-closed sets (for some given $\eta$). For
brevity’s sake, we do not use any notation to indicate the dependence of
$a_{n}$ on $\eta$; the choice of $\eta$ will always be clear from the context.
A family $\mathcal{A}$ of sets is called a _superfamily_ of another family
$\mathcal{B}$ of sets iff $\mathcal{A}\supseteq\mathcal{B}$.

A useful notion that captures the idea of the learner converging on a given
text is that of a _locking sequence_ , or more generally that of a
_stabilising sequence_. A sequence $\sigma\in(\mathbb{N}\cup\\{\\#\\})^{*}$ is
called a _stabilising sequence_ [17] for a learner $M$ on some language $L$ if
$\operatorname{content}(\sigma)\subseteq L$ and for all
$\tau\in(L\cup\\{\\#\\})^{*}$, $M(\sigma)=M(\sigma\circ\tau)$. A sequence
$\sigma\in(\mathbb{N}\cup\\{\\#\\})^{*}$ is called a _locking sequence_ [7]
for a learner $M$ on some language $L$ if $\sigma$ is a stabilising sequence
for $M$ on $L$ and $W_{M(\sigma)}=L$. The following proposition due to Blum
and Blum [7] will be occasionally useful.

######  Proposition 3 (Blum and Blum [7])

If a learner $M$ explanatorily learns some language $L$, then there exists a
locking sequence for $M$ on $L$. Furthermore, all stabilising sequences for
$M$ on $L$ are also locking sequences for $M$ on $L$.

The following theorem due to Kummer [26] will be useful for showing that a
given family of r.e. sets has a one-one numbering.

######  Theorem 4 (Kummer [26])

Suppose $L_{0},L_{1},L_{2},\ldots$ and $H_{0},$ $H_{1},H_{2},\ldots$ are two
numberings such that the following conditions hold:

  1. (1)

for all $i,j\in\mathbb{N}$, $L_{i}\neq H_{j}$;

  2. (2)

$H_{0},H_{1},H_{2},\ldots$ is a one-one numbering;

  3. (3)

for all $i\in\mathbb{N}$ and all finite $D\subseteq L_{i}$, there are
infinitely many $j$ such that $D\subseteq H_{j}$.

Then $\\{L_{i}:i\in\mathbb{N}\\}\cup\\{H_{j}:j\in\mathbb{N}\\}$ has a one-one
numbering.

##  4 Results for all Positive Equivalence Relations: Fin, Conf, Ex, Vac and
BC Learning

In the present section, we investigate the relationship between the main
learning criteria – namely, finite, confident, explanatory, vacillatory and
behaviourally correct learning – with respect to families closed under any
given positive equivalence relation. The first part of this section will
study, for any general positive equivalence relation $\eta$, the learnability
of a particular $\eta$-family known as the _ascending family for $\eta$_. As
will be seen later, the ascending family provides a useful basis for
constructing $\eta$-families that witness the separation of various
learnability notions.

###### Definition 5

For all $n\in\mathbb{N}$, $A_{n}$ denotes the set $[a_{0},a_{1},...,$
$a_{n-1}]$. The family $\\{A_{n}:n\in\mathbb{N}\\}$ will be denoted by
${\mathcal{A}}_{\eta}$, and is called the _ascending family for $\eta$_.

Note that each member of ${\mathcal{A}}_{\eta}$ is $\eta$-finite; furthermore,
${\mathcal{A}}_{\eta}$ is an $\eta$-family because $\eta$ induces infinitely
many equivalence classes and for all $n$, $a_{n}$ can be approximated from
below (c.f. Description 1, item (1)). ${\mathcal{A}}_{\eta}$ is analogous to
the family $\mbox{INIT}:=\\{\\{y:y<x\\}:x\in\mathbb{N}\\}$ defined in [22,
Section 4.3]. For brevity’s sake, we do not use any notation to indicate the
dependence of $A_{n}$ on $\eta$; the choice of $\eta$ will always be clear
from the context.

In the second part of this section, we study the question of whether the
learning hierarchy

$\mbox{Fin}\subset\mbox{Conf}\subset\mbox{Ex}\subset\mbox{Vac}\subset\mbox{BC}.$

is strict for the class of $\eta$-families (for any given positive equivalence
relation $\eta$). It turns out that while the two chains of inclusions
$\mbox{Fin}\subset\mbox{Conf}\subset\mbox{Ex}$ and
$\mbox{Vac}\subset\mbox{BC}$ hold for _all_ positive equivalence relations,
there is a positive equivalence relation $\vartheta$ for which every
vacillatorily learnable $\vartheta$-family is also explanatorily learnable.
The construction of $\vartheta$ will be given in the next section. We begin
with a few basic examples of $\eta$-families to illustrate some of the notions
introduced so far.

######  Example 6 (Ershov [12])

If $A$ is a recursive and coinfinite set, then
$x\,\eta_{A}\,y\,\Leftrightarrow\,(x=y\vee(x\in A$ $\wedge$ $y\in A))$ is a
positive equivalence relation. ${\mathcal{F}}:=\\{A\\}\cup\\{\\{x\\}:x\notin
A\\}$ is an $\eta_{A}$-family since (1) every equivalence class of $\eta_{A}$
is either $A$ or a singleton $\\{x\\}$ with $x\notin A$, which implies that
${\mathcal{F}}$ is infinite and each member of ${\mathcal{F}}$ is
$\eta_{A}$-closed, and (2) there is a uniformly recursive one-one numbering
$\\{F_{i}\\}_{i\in\mathbb{N}}$ of ${\mathcal{F}}$; for example, one could set
$F_{0}=A$ and $F_{i+1}=\\{x_{i}\\}$ for all $i$, where
$x_{1},x_{2},x_{3},\ldots$ is a one-one recursive enumeration of
$\mathbb{N}-A$. ${\mathcal{F}}$ is also finitely learnable via a learner that
outputs ? until it sees the first number $x$ in the input; if $x\in A$ then
$A$ is conjectured, and if $x\notin A$ then $\\{x\\}$ is conjectured.

######  Example 7 (Ershov [12])

If $R$ is an r.e. set and $D_{0},D_{1},D_{2},\ldots$ is a one-one numbering of
all finite sets, then $x\,\eta_{R}\,y\Leftrightarrow D_{x}\triangle
D_{y}\subseteq R$ is a positive equivalence relation ($\triangle$ denotes the
symmetric difference). If $S\cap R=\emptyset$, then $L_{S}:=\\{x:D_{x}\cap
S\neq\emptyset\\}$ is $\eta_{R}$-closed. Suppose $\mathbb{N}-R$ contains an
infinite r.e. set $C$. Let ${\mathcal{F}}$ consist of all sets
$L_{C^{\prime}}$ such that $C^{\prime}=C-F$ for some finite set $F$. Then
${\mathcal{F}}$ is an $\eta_{R}$-family that is not behaviourally correctly
learnable.

The next theorem shows that for any positive equivalence relation $\eta$, the
ascending family witnesses that explanatory learning is strictly more powerful
than confident learning.

###### Theorem 8

For every positive equivalence relation $\eta$, the ascending family
${\mathcal{A}}_{\eta}$ is explanatorily learnable but not confidently
learnable. One can add the set $\mathbb{N}$ to ${\mathcal{A}}_{\eta}$ and
obtain an $\eta$-family which is not behaviourally correctly learnable.

Proof. Note that all members of the ascending family are $\eta$-finite and for
each member $A_{n}$, the learner can find in the limit $n$ as follows: At each
time $t$, the learner takes $n_{t}$ – the $t$-th approximation to $n$ – to be
the least number such that $a_{n_{t},t}$ has not yet appeared in the text and
this $n_{t}$ converges to $n$: From the time $t$ onwards where all $a_{m,t}$
with $m\leqslant n$ have converged to their final value $a_{m}$ and
furthermore all $a_{m}$ with $m<n$ have appeared in the text, it holds that
$n_{t}=n$ and that therefore the conjecture is $A_{n}$ which can be given by a
default index for this set.

Now assume, by way of contradiction, that ${\mathcal{A}}_{\eta}$ has a
confident learner $N$. By [21, Exercise 5–14], there is some
$\sigma\in\mathbb{N}^{*}$ such that for all $\tau\in\mathbb{N}^{*}$,
$N(\sigma\tau)=N(\sigma)$. Since $A_{0}\subset A_{1}\subset
A_{2}\subset\ldots$ and almost all of the $A_{i}$’s contain
$\operatorname{content}(\sigma)$, one can pick a least $n$ such that
$W_{N(\sigma)}\neq A_{n}$ and $\operatorname{content}(\sigma)\subseteq A_{n}$.
Then $\sigma$ could be extended to a text $T$ for $A_{n}$ such that $N$ on $T$
converges to $N(\sigma)$ – an incorrect index for $A_{n}$, contradicting the
fact that $N$ confidently learns ${\mathcal{A}}_{\eta}$.
Furthermore, if one adds $\mathbb{N}$ to ${\mathcal{A}}_{\eta}$, the resulting
family contains $\mathbb{N}$ and a strictly ascending sequence of sets whose
union is $\mathbb{N}$, thus by Gold [20] the family is not learnable from
positive data. This applies to all learning criteria considered in this paper.
∎

The following proposition provides a method for establishing that a given
uniformly r.e. family is an $\eta$-family.

###### Proposition 9

Every uniformly r.e. superfamily of ${\mathcal{A}}_{\eta}$ that consists of
$\eta$-closed sets is an $\eta$-family; in particular, the families of all
$\eta$-finite sets and all $\eta$-closed r.e. sets are $\eta$-families.

Proof. According to Kummer’s theorem (cf. Theorem 4), a union of two disjoint
uniformly r.e. families has a one-one numbering whenever every finite subset
of any member of one family has infinitely many supersets in the other family
and the latter family has a one-one numbering. So let $E_{0},E_{1},\ldots$ be
the given r.e. family and let $A_{0},A_{1},\ldots$ be the default one-one
enumeration of the ascending $\eta$-family. Now one chooses for the second
family ${\mathcal{F}}_{2}$ the family of all sets $A_{2k}$ and for the first
family ${\mathcal{F}}_{1}$ all those sets $E_{k}$ which are not in
${\mathcal{F}}_{2}$. Note that all sets $A_{2k+1}$ are therefore in
${\mathcal{F}}_{1}$. For completing the proof, one has to show that
${\mathcal{F}}_{1}$ is a uniformly r.e. family.
Let $E_{k,t}$ denote the $t$-th approximation to $E_{k}$. For this one defines
sets $U_{k,n,t}$ as follows:

> If (i) $a_{n,t}\notin E_{k,t}$ and (ii) either $n$ is odd and all
> $a_{m,t}\in E_{k,t}$ with $m<n$ or $a_{n+1,t}\in E_{k,t}$,
>
> then one enumerates into $U_{k,n,t}$ all elements of $E_{k,t}$ until either
> $a_{n,t}$ is enumerated into $E_{k,s}$ for some $s\geqslant t$ or there is
> an $m\leqslant n+1$ and $s\geqslant t$ with $a_{m,s}\neq a_{m,t}$.
>
> If this happens, one lets $h$ be the largest element enumerated into
> $U_{k,n,t}$ so far and one enumerates into $U_{k,n,t}$ all elements of
> $A_{2h+1}$ which contains all elements enumerated into $U_{k,n,t}$ so far.

Note that $A_{2h+1}$ mentioned at the end of this algorithm is not a member of
the second numbering ${\mathcal{F}}_{2}$. It is easy to see that the numbering
of all $U_{k,n,t}$ is a family of uniformly r.e. sets and that each of these
sets is either equal to $E_{k}$ in the case that the condition associated to
$(n,k)$ witnesses this (either $n$ is odd and $a_{n}$ is the least non-element
of $E_{k}$ or $a_{n}\notin E_{k}$ while $a_{n+1}\in E_{k}$) or the set is
explicitly made to be an $A_{2h+1}$ which is not contained in the second
numbering ${\mathcal{F}}_{2}$ but in the numbering of the $E_{k}$. There is
only one set which is not captured by this numbering but might be in the
numbering of the $E_{k}$: This is the set $\mathbb{N}$. If this set is also in
the numbering, then one has to add it afterwards explicitly to
${\mathcal{F}}_{1}$. In the case that one has a family which does not respect
$\eta$, one can also for this achieve the result — although it is not the
intention of the current work to consider such families — by adding the
members of a further numbering of sets $\tilde{U}_{k,x,y,t}$ which are equal
to $E_{k}$ in the case that $x\,\eta_{t}\,y$ and $x\in E_{k,t}$ and $y\notin
E_{k}$; in the case that this is not satisfied, the set $\tilde{U}_{k,x,y,t}$
is made equal to some set of the form $A_{2h+1}$ when the violation of the
condition is discovered.
As the class of all $\eta$-finite sets and the class of all $\eta$-closed r.e.
sets are uniformly r.e. superfamilies of the ascending $\eta$-family, these
classes are also $\eta$-families. ∎

A minor modification of the proof of Proposition 9 reveals a slightly more
general result: for any positive equivalence relation $\eta$ and any strictly
increasing recursive enumeration $e_{0},e_{1},e_{2},\ldots$, every uniformly
r.e. superfamily of $\\{A_{e_{i}}:i\in\mathbb{N}\\}$ is an $\eta$-family. This
variant of Proposition 9 will be occasionally useful for showing that a given
uniformly r.e. class is an $\eta$-family.

###### Proposition 10

Let $f$ be any strictly increasing recursive function. Then, for any given
positive equivalence relation $\eta$, every uniformly r.e. superfamily of
$\\{A_{f(i)}:i\in\mathbb{N}\\}$ consisting of $\eta$-closed sets is an
$\eta$-family.

The next result shows that for any given positive equivalence relation $\eta$,
behaviourally correct learning is more powerful than explanatory learning with
respect to the class of $\eta$-families.

###### Theorem 11

For every positive equivalence relation $\eta$, there is an $\eta$-family
which is behaviourally correctly learnable but not explanatorily learnable.

Proof. The $\eta$-family of all $\eta$-finite sets is behaviourally correctly
learnable: When $D$ is the set of all data items the learner has seen so far,
then it conjectures the set $\\{x:\exists y\in D\,[x\,\eta\,y]\\}$. It is
straightforward to compute indices of these sets from lists of elements in the
set $D$. Next, we distinguish two cases: first, when the family of all
$\eta$-finite sets is explanatorily learnable; second, when this family is not
explanatorily learnable. In the case that this family is not explanatorily
learnable, the proof is already completed; so assume that it has an
explanatory learner $M$. We construct another $\eta$-family that is
behaviourally correctly learnable but not explanatorily learnable.
One considers the class which contains for each $n$ the following sets:

  1. 1.

$A_{n}=\\{x:\exists k<n\,[x\,\eta\,a_{k}]\\}$;

  2. 2.

$F_{n}=\\{x:\exists k\neq n\,[x\,\eta\,a_{k}]\\}$;

  3. 3.

If $W_{n}$ is finite then for all $m\leqslant|W_{n}|$ and $m>n$ the set
$B_{n,m}=\\{x:\exists k<m$ $[k\neq n$ $\wedge$ $x\,\eta\,a_{k}]\\}$.

This class is a superfamily of the ascending $\eta$-family $A_{0},A_{1},$
$\ldots$ and so by Proposition 9, it is sufficient to show that it is
uniformly r.e. for proving that it is an $\eta$-family. The enumeration-
procedure checks for each combination of certain indexing parameters
(described in detail below) whether these witness that the corresponding set
is in the class; when an error is discovered with respect to the parameters,
the enumerated set is overwritten by enumerating some member of the ascending
family which contains all the numbers enumerated so far (this is possible
because any finite set $D$ is contained in the ascending family $\\{x:\exists
k<\max(D)+1\,[x\,\eta\,a_{k}]\\}$, where $\max(\emptyset)$ is defined to be
$1$).
We now describe in detail the enumeration procedures for (i) $A_{n}$, (ii)
$F_{n}$ and (iii) $B_{n,m}$.

  1. i.

$A_{n}$ can be enumerated from the parameter $n$ and no check is needed.

  2. ii.

One can, in the limit, compute for every $n$ the value $a_{n}$ and a
stabilising sequence $\sigma_{n}$ of $M$ for the set $[a_{n}]$. $F_{n}$ can be
enumerated based on $a_{n}$ and a stabilising sequence $\sigma_{n}$ of the
explanatory learner $M$ for $[a_{n}]$; specifically, one has that
$F_{n}=\\{x:\exists\tau\in([a_{n}]\cup[x])^{*}\,[M(\sigma_{n}\circ
x\circ\tau)\neq M(\sigma_{n})]\\}$. Thus, at time $t$, one can make a guess
$e_{n,t}$ for the enumeration procedure of $F_{n}$ based on the value of
$a_{n,t}$ and a guess $\tau_{s}$ for the actual string $\sigma_{n}$, where,
given a default enumeration $\tau_{0},\tau_{1},\tau_{2},\ldots$ of all finite
sequences, $s$ is the least index $s^{\prime}$ such that
$\tau_{s^{\prime}}\in([a_{n,t}]_{t}\cup\\{\\#\\})^{*}$, and
$\tau_{s^{\prime}}$ “appears” to be a stabilising sequence of $M$ for
$[a_{n,t}]$, in the sense that for all
$\tau^{\prime}\in([a_{n,t}]_{t}\cup\\{\\#\\})^{*}$ of length at most $t$,
$M(\tau_{s^{\prime}}\circ\tau^{\prime})=M(\tau_{s^{\prime}})$ (if no such
$\tau_{s^{\prime}}$ exists, then set $\tau_{s}=\lambda$); here $[a_{n,t}]_{t}$
refers to the set of elements enumerated into $[a_{n,t}]$ up to and including
stage $t$, based on some fixed enumeration of $[a_{n,t}]$. One may then choose
$e_{n,t}$ such that
$W_{e_{n,t}}=\\{x:\exists\tau\in([a_{n,t}]\cup[x])^{*}\,[M(\tau_{s}\circ
x\circ\tau)\neq M(\tau_{s})]\\}$. The set $F_{n}$ can be enumerated from a
pair $(n,t)$ which uses the guess of the index $e_{n,t}$ for the enumeration
procedure of $F_{n}$ at time $t$ and which enumerates $W_{e_{n,t}}$ until an
$s>t$ is found with $e_{n,s}\neq e_{n,t}$; if that latter happens, then the
enumeration is stopped and some member of the ascending family is enumerated
which contains all the numbers so far enumerated. For sufficiently large $t$,
the procedure will enumerate from $(n,t)$ the set $F_{n}$.

  3. iii.

For the set $B_{n,m}$, one considers all triples $(n,m,t)$ where $W_{n,t}$ has
at least $m$ elements and then one will enumerate for this triple all elements
equivalent to some $a_{k,t}$ with $k<m\wedge k\neq n$ until an $s>t$ is found
such that $a_{k,t}\neq a_{k,s}$ for some $k\leqslant m$ or $W_{n,s}\neq
W_{n,t}$. If that happens, the parameters are invalid and the set is made
equal to some member of the ascending family which contains all the data
enumerated so far.

The so defined family is a superset of all $\eta$-cosingletons $F_{n}$. If the
family was explanatorily learnable, then every $F_{n}$ would have a locking
sequence $\tau_{n}$ which can be found in the limit. If $W_{n}$ is finite,
then $\tau_{n}$ must contain an element $h\geqslant|W_{n}|$, due to $A_{n}$
being in the class, and $B_{n,|W_{n}|}$ being in the class and containing all
elements of $F_{n}$ strictly below $|W_{n}|$ and perhaps some others more.
Therefore one can check using the halting problem oracle $K$ whether $W_{n}$
enumerates at least $\max(range(\tau_{n}))+1$ elements. If the answer is “yes”
then $W_{n}$ must be infinite; if the answer is “no” then $W_{n}$ must be
finite. Thus one could decide relative to $K$ whether $n$ is in the set
$\mathrm{FIN}=\\{n:W_{n}$ is finite$\\}$. But this is impossible, as
$\mathrm{FIN}$ is $\Sigma_{2}$-complete, while $K$ is only
$\Sigma_{1}$-complete—see [34, Proposition X.9.6]. Thus the family cannot be
explanatorily learnable.

It remains to show that the so constructed $\eta$-family is behaviourally
correctly learnable. So a behaviourally correct learner $N$ would first find
in the limit the following pieces of information, the indices issued on the
way to find these pieces of information enumerate something, but might not
enumerate any set in the constructed $\eta$-family:

  1. 1.

The least number $n$ such that $a_{n}$ does not appear in the text;

  2. 2.

An index $e_{n}$ such that $W_{e_{n}}=F_{n}$.

Furthermore, let $t$ be the number of input items (including repetitions and
pause symbols) from the text processed so far and $m=\min\\{k>n:a_{k,t}$ has
not yet appeared in the text$\\}$.
In the case that $m=n+1$, the learner conjectures $A_{n}$. In the case that
$m>n+1$, the learner checks whether $W_{n,t}$ has more than $m$ elements.
If the answer is “yes”, then the learner conjectures an index for an r.e. set
which first starts enumerating all elements of $B_{n,m}$ until it happens that
there is an $s>t$ with $W_{n,s}\neq W_{n,t}$ or $\exists k\leqslant
m\,[a_{k,s}\neq a_{k,t}]$; if that happens then the learner enumerates
$W_{e_{n}}$ which is equal to $F_{n}$.
If the answer is “no”, then the learner directly enumerates all members of
$W_{e_{n}}$.
There is always one $n$ for which $a_{n}$ is not contained in the set; it is
clear that the learner finds the least such $n$ in the limit; furthermore, in
the case that it exists, the learner also finds the second least $m$ such that
$a_{m}$ is not in the set in the limit. Now one of the following cases holds:

  1. 1.

$m=n+1$: In this case, the learner will conjecture $A_{n}$ almost always, thus
it behaviourally correctly learns that set and this is the only set for which
$a_{n}$ and $a_{m}$ with the above condition are the two least non-elements.

  2. 2.

$n+1<m$ and $m\leqslant|W_{n}|$ and $W_{n}$ is finite: In this case, for all
sufficiently large $t$, $W_{n,t}=W_{n}$ and $a_{k,t}=a_{k}$ for all
$k\leqslant m$ and all $a_{k}$ with $k<m\wedge k\neq n$ have appeared in the
text; in these circumstances, the learner will conjecture $B_{n,m}$ and this
set is correct.

  3. 3.

$\max(n+1,|W_{n}|)<m$: This case does not occur, there is no set with the two
least non-elements $a_{n}$ and $a_{m}$ in the $\eta$-family considered.

  4. 4.

$m$ does not exist: Then the set to be learnt is $F_{n}$. When $t$ is
sufficiently large then it holds that either $W_{n}$ is infinite and all
$k\leqslant n+1$ satisfy the below statement $(*)$ or $W_{n}$ is finite and
all $k\leqslant|W_{n}|$ satisfy $(*)$. Here $(*)$ is the statement that
$a_{k,t}=a_{k}$ and whenever $k\neq n$ then $a_{k,t}$ has appeared among the
first $t$ input data items of the text. One can see that in both the “either-
case” and the “or-case”, the set conjectured by the learner is $F_{n}$.

This case-distinction completes the proof by verifying that $N$ is a correct
behaviourally correct learner for the family. ∎

Vacillatory learning, according to which a learner is allowed to switch
between any finite number of correct indices in the limit, is known to be
strictly weaker than behaviourally correct learning for general families of
r.e. sets [8]. The next main result – Theorem 13 – asserts that for any given
positive equivalence relation $\eta$, this relation between the two criteria
holds even for certain $\eta$-families. We begin with the following
proposition, from which the separation result may be deduced.

###### Proposition 12

If the class of $\eta$-finite sets is vacillatorily learnable then one can
relative to the halting problem $K$ compute a sequence $e_{0},e_{1},\ldots$ of
characteristic indices of $\eta$-finite and $\eta$-closed sets
$E_{0},E_{1},\ldots$ which form a partition of $\mathbb{N}$.

Proof. Let $M$ be the vacillatory learner for the class of all $\eta$-finite
sets. Assume that all $E_{m}$ and $e_{m}$ with $m<n$ are computed. Now one
finds with help of $K$ the first $k$ such that
$a_{k}\notin\bigcup_{m<n}E_{m}$. Furthermore, there is a finite sequence
$\sigma$ of elements $\eta$-equivalent to $a_{k}$ such that any further finite
sequence $\tau$ of elements $\eta$-equivalent to $a_{k}$ satisfies that
$M(\sigma\tau)$ equals to $M(\rho)$ for some prefix $\rho$ of $\sigma$; if
such a sequence would not exist, one could construct a text for the
equivalence class of $a_{k}$ on which $M$ outputs infinitely many different
hypotheses. $M$ has issued at most $|\sigma|+1$ many different indices on
prefixes of $\sigma$. Now let $F_{n}$ be the union of the sets
$\bigcup_{m<n}E_{m}$ and the set of all $x$ for which there is a $\tau$
consisting of elements which are $\eta$-equivalent to $a_{k}$ or to $x$ such
that $M(\sigma x\tau)$ contains an index not in the finite set
$\\{M(\rho):\rho\preceq\sigma\\}$. Note that $F_{n}$ does not contain any
element $\eta$-equivalent to $a_{k}$ by the choice of $\sigma$; furthermore,
whenever for an $x$ there is no prefix $\rho\preceq\sigma$ with $W_{M(\rho)}$
enumerating $\\{y:y\,\eta\,x$ $\vee$ $y\,\eta\,a_{k}\\}$ then $x\in F_{n}$.
Furthermore, it follows from the definition of $F_{n}$ that $F_{n}$ is
$\eta$-closed. Now let $R=\\{\rho\preceq\sigma:W_{M(\rho)}\cap
F_{n}=\emptyset\\}$ and note that $R$ can be determined using the halting
problem $K$ as an oracle. Note that $R$ is finite. The set
$E_{n}=\bigcup_{\rho\in R}W_{M(\rho)}$ is $\eta$-finite and the complement of
$F_{n}$; thus one can from the enumeration-procedures of $F_{n}$ and $E_{n}$
compute a characteristic index $e_{n}$ of $E_{n}$. Furthermore, the
cardinality $c_{n}$ of $R$ is an upper bound on the number of $a_{k}$ in
$E_{n}$ and $E_{n}$ is $\eta$-finite. As every $a_{k}$ appears in exactly one
$E_{n}$ and as all $E_{n}$ are $\eta$-closed, the $E_{n}$ form a partition of
$\mathbb{N}$ into $\eta$-finite sets. ∎

###### Theorem 13

For every positive equivalence relation $\eta$, there is an $\eta$-family
which is behaviourally correctly learnable but not vacillatorily learnable.

Proof. One can use Proposition 12 to construct, in the case that the class of
$\eta$-finite sets is vacillatorily learnable, the following class which is
behaviourally correctly learnable but not vacillatorily learnable: The family
contains (i) all members $A_{n}$ of the ascending family; (ii) all sets
$F_{n}$ as constructed in the proof of Proposition 12; (iii) in the case that
$W_{n}$ is finite, all sets $A_{m}\cap F_{n}$ with $m\leqslant|W_{n}|$. For
this class, one can show as in Theorem 11 that it is a $\eta$-family and that
it is behaviourally correctly learnable and that it is not explanatorily
learnable; the latter proof can be adjusted to a proof that it is not
vacillatorily learnable. To see this, consider a vacillatory learner; for this
learner one can compute using $K$ a sequence $\sigma$ of elements in $F_{n}$
such that every extension $\sigma\tau$ of it using for $\tau$ only elements
from $F_{n}$ satisfies that $M(\sigma\tau)=M(\rho)$ for a prefix $\rho$ of
$\sigma$. Now if $W_{n}$ is finite then there are at least $|W_{n}|-c_{n}$
many sets of the form $A_{m}\cap F_{n}$, $m\in\mathbb{N}$, in the class (where
$c_{n}$ is computed using $K$ as in Proposition 12) and for each of them,
either some $M(\rho)$ with $\rho\preceq\sigma$ must be an index for it or
$\sigma$ contains an element outside the set $A_{m}\cap F_{n}$. Note that the
smallest number outside $A_{m}$ is at least $m$. Thus if $W_{n}$ is finite and
if one takes $d_{n}=\max(range(\sigma))+|\sigma|+c_{n}$, then
$d_{n}\geqslant|W_{n}|$. Therefore one can compute from $n$ the number $d_{n}$
using $K$ and then check using $K$ whether $|W_{n}|\leqslant d_{n}$. If this
is true then $W_{n}$ is finite else $W_{n}$ is infinite. Thus the existence of
a vacillatory learner would lead to an incorrect result about the arithmetic
hierarchy [34, Proposition X.9.6] and therefore the $\eta$-family constructed
is not vacillatorily learnable. ∎

Moving down the learning hierarchy given at the start of the present section,
the following theorem shows that for any positive equivalence relation $\eta$,
finite learning can be more restrictive than confident learning with respect
to $\eta$-families.

###### Theorem 14

Let $\eta$ be any given positive equivalence relation such that there is at
least one finitely learnable $\eta$-family. Then there is an $\eta$-family
that is confidently learnable but not finitely learnable.

Proof. Let $B_{0},B_{1},\ldots$ be any finitely learnable $\eta$-family. Now,
for every set $B_{n}$ there is a finite subset $C_{n}$ such that $B_{n}$ is
the only superset in this family. These sets $C_{n}$ must exist, as they are
the data-items observed so far when the finite learner conjectures $B_{n}$
from the default text of $B_{n}$ and as the conjecture cannot be revised,
there cannot be an $m\neq n$ with $C_{n}\subseteq B_{m}$. Now one considers
the family in which one replaces $B_{2}$ by $\mathbb{N}$. This family has a
confident learner which first issues the same conjectures as the finite
learner until it has seen all data in $C_{0}\cup C_{1}$. If that happens,
$\mathbb{N}$ is the only consistent hypothesis and the learner makes a mind
change to that set. As this new class is not inclusion-free, it is not
finitely learnable. ∎

##  5 The Non-Union Theorem and Finitely Learnable Classes

As Gold [20] observed, the class consisting of $\mathbb{N}$ and all finite
sets is not learnable in any sense considered in the present paper. Thus
adding only one set to the learnable class of all finite set makes it
unlearnable. This is not true for all classes. For example, in the case that
one considers languages made of strings, Angluin [1, Example 1] provided the
class of all non-erasing pattern languages which can be learnt from positive
data explanatorily. If one adds a single set, then the class is still
explanatorily learnable, the reason being that the set of shortest strings in
a non-erasing pattern language defines this pattern language uniquely; if now
the set of shortest strings of the new language coincides with that of one of
the members of the class, then one can add in one more string on which the two
languages differ and use these finitely many strings to detect the difference.

Similarly the union of two disjoint infinite explanatorily learnable classes
of r.e. languages may not even be behaviourally correctly learnable. Blum and
Blum [7] noted that the family of explanatorily (resp. behaviourally
correctly) learnable classes of recursive functions is also not closed under
union. This section deals with the question of whether the non-union property
of explanatory (resp. vacillatory, behaviourally correct) learning holds for
the class of $\eta$-families, where $\eta$ is any given positive equivalence
relation. For any learning criterion $I$ and any positive equivalence relation
$\eta$, say that $I$ is _closed under union with respect to $\eta$_ iff for
any $\eta$-families $\mathcal{L}$ and $\mathcal{H}$ such that
$\mathcal{L}\cup\mathcal{H}$ is an $\eta$-family, if $\mathcal{L}$ and
$\mathcal{H}$ are $I$-learnable, then $\mathcal{L}\cup\mathcal{H}$ is
$I$-learnable. Somewhat interestingly, while explanatory and vacillatory
learnability are not closed under union with respect to any $\eta$, the answer
for behaviourally correct learning depends on whether or not there are at
least two $\eta$-infinite r.e. sets.

###### Proposition 15

Let $\eta$ be any given positive equivalence relation. If $\mathbb{N}$ is the
only $\eta$-infinite r.e. set, then $\mathbb{N}$ is not contained in any
behaviourally correctly learnable $\eta$-family.

Proof. Assume that $\\{B_{0},B_{1},...\\}$ is a behaviourally correctly
learnable $\eta$-family containing $\mathbb{N}$. By [2, Corollary 3], there is
a tell-tale set $H$ for $\mathbb{N}$. Here a set $S$ is said to be a tell-tale
with respect to $\mathcal{L}$ for a language $L\in\mathcal{L}$ if $S\subseteq
L$, $S$ is finite and for all $L^{\prime}\in\mathcal{L}$, $S\subseteq
L^{\prime}\subseteq L$ implies $L=L^{\prime}$ (cf. [1]). Now there is a
maximal subset $H^{\prime}$ of $H$ such that $H^{\prime}$ is contained in
infinitely many $B_{i}$. If now $H^{\prime}=H$ then there is a
$B_{i}\neq\mathbb{N}$ which contains $H$ and thus $H$ is not a tell-tale for
$\mathbb{N}$. If there is an $x\in H-H^{\prime}$ then there is an $n$ such
that no $B_{m}$ with $m>n$ contains $H^{\prime}\cup\\{x\\}$ as a subset. Now
one can one-one enumerate the union of all $B_{m}$ with $m>n$ such that
$H^{\prime}\subseteq B_{m}$; this union is an $\eta$-infinite r.e. set which
does not contain $x$, but such a set does not exist. So this case does not
hold either. ∎

###### Theorem 16

Let $\eta$ be any given positive equivalence relation. Then the following
hold.

  1. (a)

There are disjoint, explanatorily (resp. vacillatorily) learnable
$\eta$-families $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ for which
$\mathcal{L}_{1}\cup\mathcal{L}_{2}$ is an $\eta$-family that is not
explanatorily (resp. vacillatorily) learnable.

  2. (b)

Behaviourally correct learning is closed under union with respect to $\eta$
iff $\mathbb{N}$ is the only $\eta$-infinite r.e. set.

Proof. We split the proof into two main cases.

Case 1: $\mathbb{N}$ is the only $\eta$-infinite r.e. set. Let
$\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ be any two behaviourally correctly
learnable $\eta$-families such that $\mathcal{L}_{1}\cup\mathcal{L}_{2}$ is an
$\eta$-family. By Proposition 15, both $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$
contain only $\eta$-finite sets. Thus $\mathcal{L}_{1}\cup\mathcal{L}_{2}$
contains only $\eta$-finite sets. Note that any class of $\eta$-finite sets is
behaviourally correctly learnable: on input $\sigma$, a BC learner conjectures
$\bigcup_{x\in\operatorname{content}(\sigma)}[x]$. Therefore
$\mathcal{L}_{1}\cup\mathcal{L}_{2}$ is also behaviourally correctly
learnable, and so behaviourally correct learning is closed under union with
respect to $\eta$. This proves the “if” direction of statement (b).

Next, it is shown that explanatory (resp. vacillatory) learning is not closed
under union with respect to $\eta$. Set

$\begin{split}\mathcal{L}_{1}&=\\{A_{2n+1}:n\in\mathbb{N}\\}\cup\\{[a_{k}]:k\in\mathbb{N}\\},\\\
\mathcal{L}_{2}&=\\{A_{2n+2}:n\in\mathbb{N}\\}\cup\\{[a_{k},a_{l}]:k,l\in\mathbb{N}\wedge
k<l\\}.\end{split}$

Note that $\mathcal{L}_{1}$ has the following uniformly r.e. numbering: for
all $n,s\in\mathbb{N}$,

$\begin{split}L_{2n}&=A_{2n+1},\\\ L_{2{\left\langle
n,s\right\rangle}+1}&=[a_{n,s}].\end{split}$

Similarly, $\mathcal{L}_{2}$ has the following uniformly r.e. numbering
$\\{H_{0},H_{1},H_{2},\ldots\\}$. For all $n\in\mathbb{N}$, set
$H_{2n}=A_{2n+2}$. For all $m,n,s\in\mathbb{N}$, if $a_{m,s}=a_{m}$ and
$a_{m+n+1,s}=a_{m+n+1}$, set $H_{2{\left\langle
m,n,s\right\rangle}+1}=[a_{m,s},a_{m+n+1,s}]$, and if there is a least $t>s$
such that $a_{m,t}\neq a_{m,s}$ or $a_{m+n+1,t}\neq a_{m+n+1,s}$, set
$H_{2{\left\langle m,n,s\right\rangle}+1}=A_{2n^{\prime}+2}$, where
$n^{\prime}$ is the least $k$ such that $A_{2k+2}$ contains all the elements
enumerated into $H_{2{\left\langle m,n,s\right\rangle}+1}$ up until stage $t$.
A similar proof shows that $\mathcal{L}_{1}\cup\mathcal{L}_{2}$ has a
uniformly r.e. numbering. Thus by Proposition 10,
$\mathcal{L}_{1},\mathcal{L}_{2}$ and $\mathcal{L}_{1}\cup\mathcal{L}_{2}$ are
$\eta$-families.

The following learner $M$ explanatorily learns $\mathcal{L}_{1}$. On input
$\sigma$, $M$ first checks whether or not
$a_{0}\in\operatorname{content}(\sigma)$. If
$a_{0}\in\operatorname{content}(\sigma)$, then $M$ conjectures $A_{2n+1}$ for
the least $n$ such that $a_{2n,|\sigma|}\in\operatorname{content}(\sigma)$ and
$a_{2n+1,|\sigma|}\notin\operatorname{content}(\sigma)$. If
$a_{0}\notin\operatorname{content}(\sigma)$ and
$\operatorname{content}(\sigma)\neq\emptyset$, then $M$ conjectures
$[\min(\operatorname{content}(\sigma))]$. If
$\operatorname{content}(\sigma)=\emptyset$, then $M$ outputs a default index,
say $A_{1}$. An explanatory learner for $\mathcal{L}_{2}$ can be constructed
similarly.

Now assume, by way of contradiction, that $\mathcal{L}_{1}\cup\mathcal{L}_{2}$
were vacillatorily learnable by some learner $N$. Note that a slight variant
of Proposition 3 applies to vacillatory learners: if $N$ vacillatorily learns
a language $L$, then there exist a sequence $\sigma\in(L\cup\\{\\#\\})^{*}$
and a finite set $F$ of indices such that
$\operatorname{content}(\sigma)\subseteq L$ and for all
$\tau\in(L\cup\\{\\#\\})^{*}$, $N(\sigma\circ\tau)\in F$. In particular, there
exist such a sequence $\sigma_{0}\in([a_{0}]\cup\\{\\#\\})^{*}$ and such a
finite set $F_{0}$ of indices for $N$ on $L=[a_{0}]$. By the choice of
$\sigma_{0}$ and $F_{0}$ and the fact that $N$ vacillatorily learns all sets
of the form $[a_{0},a_{k}]$, where $k>0$, it follows that the r.e. set

$\\{x:\exists\tau\in[a_{0},x]^{*}\,[N(\sigma_{0}\circ\tau)\notin F_{0}]\\}$

is an $\eta$-infinite r.e. subset of $\mathbb{N}-[a_{0}]$. But this
contradicts the assumption that there is no $\eta$-infinite r.e. set different
from $\mathbb{N}$. Thus neither explanatory nor vacillatory learning is closed
under union with respect to $\eta$.

Case 2: There is an $\eta$-infinite r.e. set that is different from
$\mathbb{N}$. Let $B$ be any $\eta$-infinite r.e. set that is different from
$\mathbb{N}$, and fix some $k$ such that $a_{k}\notin B$. Let $\eta_{s}$ be
the equivalence relation obtained by enumerating $\eta$-equivalent pairs of
elements of $B$ for $s$ steps and keeping the relation closed transitively and
reflexively. Furthermore, $b_{n,s}$ is the $n$-th element in the order of the
enumeration satisfying that all elements before it in the enumeration are not
$\eta_{s}$ equivalent to $b_{n,s}$. Now set

$\begin{split}\mathcal{L}_{1}&=\\{A_{n+k+1}:n\in\mathbb{N}\\},\\\
\mathcal{L}_{2}&=\\{\\{x:\exists m<n\,\exists
s\,[x\,\eta_{s}\,b_{m,s}]\\}:n\in\mathbb{N}\\}\cup\\{\mathbb{N}\\}.\end{split}$

By Proposition 10, $\mathcal{L}_{1}$ is an $\eta$-family. Furthermore, a proof
similar to that of Proposition 9 shows that every uniformly r.e. superfamily
of $\\{\\{x:\exists m<n\,\exists
s\,[x\,\eta_{s}\,b_{m,s}]\\}:n\in\mathbb{N}\\}$ is an $\eta$-family; in
particular, $\mathcal{L}_{2}$ is an $\eta$-family.

By Theorem 8, $\mathcal{L}_{1}$ is explanatorily learnable. An explanatory
learner $M$ for $\mathcal{L}_{2}$ works as follows: on input $\sigma$, if
$a_{k}\in\operatorname{content}(\sigma)$, then $M$ outputs a canonical index
for $\mathbb{N}$; if $a_{k}\notin\operatorname{content}(\sigma)$, then $M$
conjectures $\\{x:\exists m<n\,\exists s\,[x\,\eta_{s}\,b_{m,s}]\\}$ for the
least $n$ found such that
$b_{n,|\sigma|}\notin\operatorname{content}(\sigma)$, where $b_{n,|\sigma|}$
is defined as earlier. If $M$ is presented with a text for $\mathbb{N}$, then
$M$ will always output a canonical index for $\mathbb{N}$ after $a_{k}$
appears in the text. If $M$ is presented with a text $T$ for some set
$\\{x:\exists m<n\,\exists s\,[x\,\eta_{s}\,b_{m,s}]\\}$, then there is an
$s_{0}$ large enough so that $b_{m}\in\operatorname{content}(T[s_{0}])$ for
all $m<n$ and $b_{m,s_{0}}=b_{m}$ for all $m\leqslant n$; thus
$M(T[s^{\prime}])$ equals some canonical index for $\\{x:\exists m<n\,\exists
s\,[x\,\eta_{s}\,b_{m,s}]\\}$ whenever $s^{\prime}\geqslant s_{0}$.

Since $\mathcal{L}_{1}\cup\mathcal{L}_{2}$ contains $\mathbb{N}$ and the
infinite ascending chain $\\{A_{k+1}\subset A_{k+2}\subset\ldots\subset
A_{k+i}\subset\ldots\\}$ whose union is $\mathbb{N}$,
$\mathcal{L}_{1}\cup\mathcal{L}_{2}$ is not behaviourally correctly learnable.
Hence, under the present case assumption, explanatory (resp. vacillatory,
behaviourally correct) learning is not closed under union with respect to
$\eta$. (In particular, this proves the “only if” direction of statement (b).)
∎

The next result establishes the non-union theorem for finite learning of
$\eta$-families, where $\eta$ is any positive equivalence relation such that
at least one finitely learnable $\eta$-family exists. It may be worth noting
that, in contrast to explanatory learnability, there is a positive equivalence
relation $\vartheta$ for which no $\vartheta$-family is finitely (or even
confidently) learnable, as will be seen in the subsequent section.

###### Theorem 17

Let $\eta$ be any given positive equivalence relation such that at least one
$\eta$-family is finitely learnable. Then there are finitely learnable
$\eta$-families $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ for which
$\mathcal{L}_{1}\cup\mathcal{L}_{2}$ is an $\eta$-family that is not finitely
learnable. Furthermore, $\mathcal{L}_{2}-\mathcal{L}_{1}$ contains a single
language.

Proof. Let $\\{B_{0},B_{1},B_{2},\ldots\\}$ be a finitely learnable
$\eta$-family, as witnessed by some learner $M$. By a slight variant of
Proposition 3 for finite learning, there exists for every $i\in\mathbb{N}$ a
finite sequence $\sigma_{i}\in(B_{i}\cup\\{\\#\\})^{*}$ and an index $e$ with
$W_{e}=B_{i}$ such that $M(\tau)=\leavevmode\nobreak\ ?$ for any proper prefix
$\tau$ of $\sigma_{i}$ and for all $\sigma\in(B_{i}\cup\\{\\#\\})^{*}$,
$M(\sigma_{i}\circ\sigma)=e$. Set $F_{i}:=\operatorname{content}(\sigma_{i})$.
The family $\\{F_{0},F_{1},F_{2},\ldots\\}$ is _uniformly recursively
generable_ [29] in that there is a total effective procedure that, on every
input $i$, generates all elements of $F_{i}$ and stops. Furthermore, if there
were some $j\neq i$ such that $F_{i}\subseteq B_{j}$, then one could extend
$\sigma_{i}$ to a text $T$ for $B_{j}$ and so $M$ would not finitely learn
$B_{j}$ on $T$ because it outputs an index for $B_{i}$ on $\sigma_{i}$. Thus
$F_{i}$ is a _characteristic sample_ [27, 31] for $B_{i}$ in the sense that
$F_{i}\subseteq B_{i}$ and for all $j\neq i$, $F_{i}\not\subseteq B_{j}$. The
family $\mathcal{L}_{1}:=\\{[F_{0}],[F_{1}],[F_{2}],\ldots\\}$ is therefore an
$\eta$-family. Note that $\mathcal{L}_{1}$ is finitely learnable: on any given
text, a finite learner outputs $?$ until it identifies the least $i$ (if there
is any such $i$) such that — (1) $F_{i}$ is contained in the range of the
current input and (2) one has seen at least $i$ data items, including pause
symbols, in the text — then the learner conjectures $[F_{i}]$. Condition (2)
is only delaying the learning and is needed to make the learner recursive.
Furthermore, it is possible to check for any $i$ whether or not $F_{i}$
belongs to the range of the current input because
$\\{F_{0},F_{1},F_{2},\ldots\\}$ is uniformly recursively generable).

Let $\mathcal{L}_{2}$ be the family $\\{[F_{0}\cup
F_{1}]\\}\cup(\mathcal{L}_{1}-\\{[F_{j}]:[F_{j}]\subset[F_{0}\cup F_{1}]\\}$.
Since $[F_{0}\cup F_{1}]$ is $\eta$-finite, there are only finitely many
indices $j$ such that $[F_{j}]\subset[F_{0}\cup F_{1}]$ and therefore
$\mathcal{L}_{2}$ is a finite variant of $\mathcal{L}_{1}$. It follows that
$\mathcal{L}_{2}$ is also an $\eta$-family. Note that $\mathcal{L}_{2}$ is
finitely learnable: on input $\sigma$, a finite learner outputs $?$ until it
identifies the least $i$ (if there is any such $i$) such that $F_{i}$ is
contained in the range of the current input and either $i\in\\{0,1\\}$ or
$[F_{i}]\not\subseteq[F_{0}\cup F_{1}]$. If $i\in\\{0,1\\}$, then the learner
conjectures $[F_{0}\cup F_{1}]$, and if $i>1$, then it conjectures $[F_{i}]$.
Suppose the learner is presented with a text for $[F_{0}\cup F_{1}]$. Then the
least $j$ such that $F_{j}$ is contained in the range of the text and either
$j\in\\{0,1\\}$ or $F_{j}\not\subseteq[F_{0}\cup F_{1}]$ must be either $0$ or
$1$; thus the learner will settle on the conjecture $[F_{0}\cup F_{1}]$. If
the learner is presented with a text for some $[F_{j}]$ with
$[F_{j}]\not\subseteq[F_{0}\cup F_{1}]$, then, since $j\notin\\{0,1\\}$ and
$j$ is the least index $j^{\prime}$ such that $F_{j^{\prime}}$ is contained in
the range of the text and $[F_{j^{\prime}}]\not\subseteq[F_{0}\cup F_{1}]$,
the learner will settle on the conjecture $[F_{j}]$.

Now consider $\mathcal{L}_{1}\cup\mathcal{L}_{2}$; this is an $\eta$-family
because it is the union of the $\eta$-family $\mathcal{L}_{1}$ and
$\\{[F_{0}\cup F_{1}]\\}$. Since any finite subset of $[F_{0}]$ is contained
in $[F_{0}\cup F_{1}]$, $[F_{0}]$ does not have a finite characteristic sample
– which, as was pointed out earlier, must exist for every language in a
finitely learnable family. Thus $\mathcal{L}_{1}\cup\mathcal{L}_{2}$ is not
finitely learnable. ∎

Note that confidently learnable classes (where learners are possibly non-
partial-recursive) are closed under union [36, Exercise 4.6.2C] and that
similarly adding single languages does not destroy confident learnability. The
remainder of this section considers a less restrictive notion of closure under
union for learning criteria; this is motivated by the fact that the union of
two $\eta$-families is not necessarily an $\eta$-family: Letting $\eta$ to be
equality-relation and $A$ be a nonrecursive r.e. set, the $\eta$-families
$\\{2x:x\notin A\\}\cup\\{2x,2x+1:x\in A\\}$ and $\\{2x+1:x\notin
A\\}\cup\\{2x,2x+1:x\in A\\}$ satisfy the property that their union is not an
$\eta$-family.

###### Definition 18

(1) Given uniformly r.e. families (with corresponding one-one indexing)
$\mathcal{L}:=\\{L_{0},\linebreak[3]L_{1},\ldots\\}$ and
$\mathcal{H}:=\\{H_{0},H_{1},\ldots\\}$, say that $\mathcal{L}$ is _one-one
reducible to $\mathcal{H}$_ iff there is a one-one recursive function $f$ such
that for all $e\in\mathbb{N}$, $L_{e}=H_{f(e)}$.

(2) An $\eta$-family ${\cal K}$ is the strong union of $\mathcal{L}$ and
$\mathcal{H}$ iff ${\cal K}=\mathcal{L}\cup cH$ and there are one-one
reductions from $\mathcal{L}$ to ${\cal K}$ and from $\mathcal{H}$ to ${\cal
K}$.

(3) For any learning criterion $I$ and any positive equivalence relation
$\eta$, say that $I$ is _strongly closed under union with respect to $\eta$_
iff for any $I$-learnable $\eta$-families $\mathcal{L}$ and $\mathcal{H}$,
also every strong union of $\mathcal{L}$ and $\mathcal{H}$ is exactly
$I$-learnble.

###### Theorem 19

For any positive equivalence relation $\eta$, confident learning is strongly
closed under union with respect to $\eta$ but neither finite nor explanatory
learning is strongly closed under union with respect to $\eta$.

Proof. Suppose $\mathcal{L}:=\\{L_{0},L_{1},L_{2},\ldots\\}$ and
$\mathcal{H}:=\\{H_{0},H_{1},H_{2},\ldots\\}$ are exactly confidently
learnable $\eta$-families such that
$\mathcal{L}\cup\mathcal{H}=\\{B_{0},B_{1},B_{2},\ldots\\}$ is an
$\eta$-family, $\mathcal{L}$ is one-one reducible to
$\mathcal{L}\cup\mathcal{H}$ and $\mathcal{H}$ is one-one reducible to
$\mathcal{L}\cup\mathcal{H}$. Let $f$ and $g$ be recursive functions such that
for all $n\in\mathbb{N}$, $L_{n}=B_{f(n)}$ and $H_{n}=B_{g(n)}$, and let
$M_{1}$ and $M_{2}$ be exact confident learners for $\mathcal{L}$ and
$\mathcal{H}$ respectively. An exact confident learner $N$ for
$\mathcal{L}\cup\mathcal{H}$ works as follows: on input $\sigma$, simulate
$M_{1}$ and $M_{2}$ and let $d$ and $e$ be their respective outputs on
$\sigma$. If $f(d)=g(e)$, then $N$ outputs $f(d)$. If $f(d)\neq g(e)$, then
$N$ searches for an $s>|\sigma|$ such that there is a least $x$ with $x\in
B_{f(d),s}\triangle B_{g(e),s}$ (such $s$ and $x$ must exist because
$B_{0},B_{1},B_{2},\ldots$ is a one-one numbering and $f(d)\neq g(e)$). Set

$N(\sigma)=\left\\{\begin{array}[]{ll}f(d)&\mbox{if
$x\in\operatorname{content}(\sigma)\cap B_{f(d),s}$ or
$x\notin\operatorname{content}(\sigma)\cup B_{f(d),s}$;}\\\ g(e)&\mbox{if
$x\in\operatorname{content}(\sigma)\cap B_{g(e),s}$ or
$x\notin\operatorname{content}(\sigma)\cup B_{g(e),s}$.}\end{array}\right.$

On any text $T$, both $M_{1}$ and $M_{2}$ will converge; suppose $M_{1}$ and
$M_{2}$ converge to $d_{0}$ and $e_{0}$ respectively. If $f(d_{0})=g(e_{0})$,
then $N$ will converge to $f(d_{0})$; if $f(d_{0})\neq g(e_{0})$, then $N$
will converge to $f(d_{0})$ (resp. $g(e_{0})$) if the least $x$ such that
$x\in B_{f(d_{0})}\triangle B_{g(e_{0})}$ satisfies
$x\in\operatorname{content}(T)\cap B_{f(d_{0})}$ or
$x\notin\operatorname{content}(T)\cup B_{f(d_{0})}$ (resp.
$x\in\operatorname{content}(T)\cap B_{g(e_{0})}$ or
$x\notin\operatorname{content}(T)\cup B_{g(e_{0})}$). Furthermore, if $T$ is a
text for any $B_{\ell}\in\mathcal{L}\cup\mathcal{H}$, then at least one of
$M_{1}$ and $M_{2}$ converges on $T$ to a correct index for $B_{\ell}$, so
that $\ell\in\\{f(d_{0}),g(e_{0})\\}$. If $f(d_{0})=g(e_{0})$, then
$\ell=f(d_{0})=g(e_{0})$ and so $N$ will output $\ell$ in the limit; if
$\ell=f(d_{0})\neq g(e_{0})$, then there is a least $x$ in
$B_{f(d_{0})}\triangle B_{g(e_{0})}$ such that either
$x\in\operatorname{content}(T)\cap B_{f(d_{0})}$ or
$x\notin\operatorname{content}(T)\cup B_{f(d_{0})}$, and so $N$ will again
output $\ell$ in the limit; a similar argument applies if $\ell=g(e_{0})\neq
f(d_{0})$. It follows that $N$ exactly confidently learns
$\mathcal{L}\cup\mathcal{H}$.

For explanatory learning, one notes that the classes $\mathcal{L}_{1}$ and
$\mathcal{L}_{2}$ in both Cases 1 and 2 of the proof of Theorem 16 are
$\eta$-families with only finitely much intersection, and so if
$\mathcal{L}_{1}=\\{C_{0},C_{1},C_{2},\ldots\\}$ and
$\mathcal{L}_{2}=\\{E_{0},E_{1},E_{2},\ldots\\}$, then, setting $F_{2i}=C_{i}$
and $F_{2i+1}=E_{i}$ for all $i\in\mathbb{N}$,
$\\{F_{0},F_{1},F_{2},\ldots\\}$ is a almost a one-one uniformly r.e.
numbering of $\mathcal{L}_{1}\cup\mathcal{L}_{2}$ (finitely many languages may
have two indices). Then $i\mapsto 2i$ and $i\mapsto 2i+1$ are recursive
functions witnessing the one-one reductions of $\mathcal{L}_{1}$ to
$\mathcal{L}_{1}\cup\mathcal{L}_{2}$ and of $\mathcal{L}_{2}$ to
$\mathcal{L}_{1}\cup\mathcal{L}_{2}$ respectively. This can be easily modified
to have a 1–1 indexing of $\mathcal{L}_{1}\cup\mathcal{L}_{2}$. Furthermore,
the classes $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ in both Cases 1 and 2 of
the proof of Theorem 16 are explanatorily learnable (even exactly). Thus
explanatory learning is not strongly closed under union. A similar argument
based on the proof of Theorem 17 shows that finite learning is also not
strongly closed under union. ∎

##  6 Learnability of Families Closed Under Special Positive Equivalence
Relations

So the general results were that for every positive equivalence relation
$\eta$, for each of the following conditions, there are $\eta$-families which
satisfy it: (a) the family is explanatory learnable but not confidently
learnable; (b) the family is behaviourally correctly learnable but not
vacillatorily learnable; (c) the family is not behaviourally correctly
learnable. The picture does not provide $\eta$-families which are confidently
learnable and also not separate out the notion of vacillatory learning from
explanatory learning. The first main result of this section is to construct a
positive equivalence relation $\vartheta$ such that there is no confidently
learnable $\vartheta$-family and furthermore all vacillatorily learnable
$\vartheta$-families are explanatory learnable. Thus one cannot separate for
all $\eta$ the notions of vacillatory and explanatory learning and one also
cannot show that every $\eta$ has a confidently learnable $\eta$-family. The
second main result shows that there is a positive equivalence relation $\zeta$
for which there are confidently learnable $\zeta$-families but no finitely
learnable $\zeta$-families.

###### Theorem 20

There is a positive equivalence relation $\vartheta$ satisfying:

  1. (1)

There is only one $\vartheta$-infinite r.e. set, namely $\mathbb{N}$.

  2. (2)

Every $\vartheta$-family contains an infinite ascending chain $B_{0}\subset
B_{1}\subset\cdots$ of $\vartheta$-finite sets whose union is $\mathbb{N}$. In
particular, no $\vartheta$-family is confidently learnable and every
behaviorally correctly learnable $\vartheta$-family consists only of
$\vartheta$-finite languages.

  3. (3)

Every vacillatory learnable $\vartheta$-family is explanatorily learnable.

Proof. Recall that $W_{n}$ denotes the $n$-th recursively enumerable set, and
$W_{n,s}$ is the finite part of $W_{n}$ that is enumerated before the given
stage $s\in\mathbb{N}$. Recall also the definitions of $a_{m}\in\mathbb{N}$
and $A_{n}=[a_{0},a_{1},\ldots,a_{n-1}]$.

Construction of $\vartheta$: Initially, let $a_{m,0}=m$ for all $m$ — that is,
to start, $\vartheta$ consists wholly of singleton equivalence classes. Then,
for each $s=0,1,\ldots$ in turn, search for a triple $n,k,\ell<s$ satisfying:

  * •

$n<\ell$ and $k<\ell$;

  * •

$[a_{k,s}]_{s}\cap W_{n,s}=\emptyset$; and

  * •

$[a_{\ell,s}]_{s}\cap W_{n,s}\neq\emptyset$.

If such a triple $n,k,\ell$ exists, then select one with $\ell$ as small as
possible, merge the classes $[a_{k}]$ and $[a_{\ell}]$ together, that is, let
$a_{k,s}\vartheta a_{\ell,s}$ (along with any of its implications based on
$\vartheta$ being equivalence relation), and then set
$a_{\ell^{\prime},s+1}=a_{\ell^{\prime},s}$, for $\ell^{\prime}<\ell$ and
$a_{\ell^{\prime},s+1}=a_{\ell^{\prime}+1,s+1}$, for
$\ell^{\prime}\geqslant\ell$, so that each $a_{m,s+1}$ is again the least
element of the $m$-th class. If no such triple exists, then
$a_{\ell^{\prime},s+1}=a_{\ell^{\prime},s}$ for all $\ell^{\prime}$. Then move
on to the next value of $s$. This completes the construction.

###### Claim 21

The equivalence relation $\vartheta$ thus produced has infinitely many classes
(as demanded in the last paragraph of Section 2).

Proof: It is enough to verify that each $m\in\mathbb{N}$ serves the role of
$\ell$ only finitely many times, and hence that each $a_{m}$ reaches some
limiting value. This is easily seen by induction on $m$: after each $a_{k}$,
$k<m$ has reached its limiting value, $a_{m,\cdot}$, changes its value for
each pair $n,k<m$ at most once. Thus, each $a_{m}=\lim_{s\to\infty}a_{m,s}$,
reaches its limiting value.

###### Claim 22

For each $W_{n}$ which is $\vartheta$-closed, either: $W_{n}\subseteq A_{n}$,
or $W_{n}=A_{m}$ for some $m\geqslant n$, or $W_{n}=\mathbb{N}$. In
particular, $\vartheta$ satisfies part (1) of the theorem.

Proof: If a $\vartheta$-closed $W_{n}$ contains (the limiting value of) a
given $a_{\ell}$ with $\ell\geqslant n$, then by construction $W_{n}$ also
contains $\\{a_{0},\ldots,a_{\ell-1}\\}$. Hence if $W_{n}$ is
$\vartheta$-closed and not contained in $A_{n}$, we have either $W_{n}=A_{m}$
for some $m$, or $W_{n}=\mathbb{N}$.

###### Claim 23

If $\mathcal{L}$ is a $\vartheta$-family then for every $n$ there are
infinitely many $L\in\mathcal{L}$ such that $A_{n}\subseteq L$.

Proof: By induction on $n$. The base case, where $A_{0}=\emptyset$, is
trivial. For $n\geqslant 1$, let $U=\bigcup\\{L\in\mathcal{L}:A_{n-1}\subseteq
L\\}$. Clearly $U$ is $\vartheta$-closed and r.e.; and by the induction
hypothesis $U$ has infinitely many different summands $L$, so $U$ is
$\vartheta$-infinite by a pigeonhole argument. It follows by Claim 22 that
$U=\mathbb{N}$, and in particular $a_{n-1}\in U$. Thus $a_{n-1}$ is an element
of one of $U$’s summands $L_{0}$, so that $A_{n}\subseteq L_{0}$. Repeat the
construction with $L_{0}$ omitted from $\mathcal{L}$ to get a second such
$L_{1}$, then $L_{2}$, and so on.

Note that by Proposition 15 and part (1) of the theorem, every behaviourally
correctly learnable $\vartheta$-family contains only $\vartheta$-finite sets.
Thus, in light of Claims 22 and 23, part (2) of the theorem is true.

###### Claim 24

Every vacillatory learnable $\vartheta$-family is explanatory learnable.

Proof: Suppose $\mathcal{L}$ is a $\vartheta$-family with vacillatory learner
$M$; we know from part (2) of the Theorem (that is, from the previous claim)
that $\mathcal{L}$ consists only of $\vartheta$-finite sets. Given an
enumeration of a language $L\in\mathcal{L}$, the learner $M$ outputs at most
finitely many indices, say with maximum $n^{*}$; and given this $n^{*}$, we
know from an earlier claim that either $L\subseteq A_{n^{*}}$, or $L=A_{m}$
for some $m\geqslant n^{*}$. So the new explanatory learner $N$ works by
watching for the largest $n$ output by $M$; then $N$ watches to see if $a_{n}$
is a member of $L$ and if so, $N$ conjectures that $L=A_{m}$ for the least $m$
such that $a_{m}$ does not belong to the input text; otherwise $N$ conjectures
that $L$ is an appropriate subset of $A_{n}$ (which consists of the elements
$a_{i}$, $i<n$, which have appeared in the input text). It is easy to verify
that $N$ explanatorily learns $\mathcal{L}$. ∎

According to Theorem 14, for every positive equivalence relation $\eta$ such
that there is at least one finitely learnable $\eta$-family, there is also an
$\eta$-family that is confidently but not finitely learnable. The next main
result complements this theorem by showing that there is a positive
equivalence relation $\zeta$ for which no finitely learnable $\zeta$-family
exists even though there are confidently learnable $\zeta$-families.

###### Description 25

One defines a positive equivalence relation $\zeta$ using a dense simple set
$Z$ with $0\notin Z$ as below; recall for this that a set is dense simple iff
it is recursively enumerable, coinfinite and the sequence $a_{0},a_{1},\ldots$
of its non-elements in ascending order grows faster than every recursive
function. It is known that such sets $Z$ exist [34].
Now one defines that $x\,\zeta\,y$ iff there is an $n$ with
$a_{n}\leqslant\min\\{x,y\\}\leqslant\max\\{x,y\\}<a_{n+1}$. This relation is
positive, as $x\,\zeta\,y$ is equivalent to

$\forall z\,[\min\\{x,y\\}<z\leqslant\max\\{x,y\\}\Rightarrow z\in Z]$

which is an r.e. condition. Furthermore, in coincidence with the notation used
in this paper, each $a_{n}$ is the least element of its equivalence class and
the $a_{n}$ are the ascending limits of the approximations $a_{n,t}$ which are
the non-elements (in ascending order) of the set $Z_{t}$ of the first $t$
elements enumerated into $Z$, so that $Z_{0}=\emptyset$ and $a_{n,0}=n$. As
$Z$ is coinfinite, there are infinitely many $a_{n}$’s and so $\zeta$ induces
infinitely many equivalence classes.

###### Theorem 26

There is a confidently learnable $\zeta$-family but no finitely learnable
$\zeta$-family.

Proof. First one defines $B_{n}=\\{x:x\,\zeta\,n\vee x\,\zeta\,a_{n}\vee
n\leqslant x\leqslant a_{n}\\}$. Note that $n\leqslant a_{n,0}\leqslant a_{n}$
and thus the minimum of $B_{n}$ is the maximum of all $a_{m}$ with
$a_{m}\leqslant n$. Furthermore, each two different sets $B_{n}$ and $B_{m}$
have the different maxima $a_{n}$ and $a_{m}$ (among different $a_{i}$’s),
respectively, and therefore the so defined family is an r.e. one-one family of
$\zeta$-closed sets. So it is a $\zeta$-family. A confident learner
conjectures on an input sequence $\sigma$, whenever it exists, the least $n$
such that $range(\sigma)\subseteq B_{n,|\sigma|}$; however, if such a set does
not exist since none of the finitely many sets with
$\min(B_{n,|\sigma|})\leqslant\min(range(\sigma))$ contains $range(\sigma)$,
then the learner conjectures $B_{0}$. Note that all $B_{n}$ are $\eta$-finite
and each number is only contained in finitely many $B_{n}$. Thus, whenever
there is an $n$ for which $B_{n}$ contains all the data in the text then the
learner converges to an index of $B_{n}$ for the least such $n$ and when no
such $n$ exists then the learner converges to an index of $B_{0}$. Hence the
learner is confident and learns the family.
Second let $E_{0},E_{1},\ldots$ be any $\zeta$-family and assume by way of
contradiction that it is finitely learnable. Then for each $E_{n}$ there is a
finite subset $C_{n}\subseteq E_{n}$ such that the finite learner conjectures
some index different from $?$ after having seen the elements $C_{n}$; the
mapping, call it $f$, from $n$ to an explicit list of the set $C_{n}$ is
recursive and so is $g$ defined by $g(n)=\max\\{\max(C_{m}):m\leqslant
2^{n}\\}$. Also the function $g$ is recursive and by choice of $Z$, there is
an $n$ with $g(n)<a_{n}$. It follows that the $2^{n}+1$ sets $E_{m}$ with the
indices satisfying $m\leqslant 2^{n}$ are all learnt based on data which is
contained in $[a_{0}$, $a_{1}$, $\ldots$, $a_{n-1}]$ and therefore there are
two distinct numbers $m,k\leqslant 2^{n}$ such that the $\zeta$-closure of
$C_{m}$ and $C_{k}$ are the same sets. It follows that both sets $C_{m}$ and
$C_{k}$ must be subsets of both $E_{m}$ and $E_{k}$ and so the finite learner
must err when learning the sets $E_{m}$ and $E_{k}$. Hence the given
$\zeta$-family is not finitely learnable. ∎

##  7 Weakly Confident and Class-Preserving Learning

As Osherson, Stob and Weinstein [36] had already observed, confidence is a
real restriction on explanatory or behaviourally correct learning; in
particular, even the relatively simple family of all finite sets is not
confidently behaviourally correctly learnable. In the present section, we
examine a variant of confident learning known as _weak confident learning_ ,
where the learner’s sequence of hypotheses is required to converge only on
each text whose range is contained in some language to be learnt. Such a
learning property may be desirable in situations where a text for some target
language may have missing data due to noise [9]. One can see, for example,
that since the family of all finite sets is closed under taking subsets, it is
weakly confidently explanatorily learnable.

We also study the effect of requiring _class-preservingness_ of the learner’s
hypothesis space on the strength of confident as well as weakly confident
learning. Our first observation is that there are positive equivalence
relations $\eta$ for which class-preserving learning is indeed a restriction
on confidence with respect to the class of $\eta$-families.

###### Theorem 27

There is a positive equivalence relation $\eta$ for which there is a
$\eta$-finite family that is confidently learnable but not class-preservingly
confidently learnable.

Proof. Take $\eta$ to be the positive equivalence relation
$x\,\eta\,y\Leftrightarrow x=y$. Now consider the class $\mathcal{L}$
comprising all $2$-element sets $\\{x,y\\}$ with $x,y\in\mathbb{N}$, $x\neq
y$, and all singletons $\\{z\\}$ with $z\in K^{\prime}$.

Define a confident learner $M$ as follows. On input $\sigma$, if
$|\operatorname{content}(\sigma)|\leqslant 2$, then $M$ conjectures
$\operatorname{content}(\sigma)$; if $|\operatorname{content}(\sigma)|>2$,
then $M$ outputs a default index. Then $M$ will converge on any text $T$
containing at most two elements to a canonical index for
$\operatorname{content}(T)$, and so it explanatorily learns every language in
$\mathcal{L}$; if, on the other hand, $\operatorname{content}(T)$ contains
more than two elements, $M$ will converge to a default index. Hence $M$
confidently learns $\mathcal{L}$.

Assume that $\mathcal{L}$ has a class-preserving confident learner $N$. Then,
given any $n\in\mathbb{N}$, one can check via oracle $K$ whether or not $n\in
K^{\prime}$ as follows: feed $N$ with the text $n\circ n\circ n\circ\ldots$
until $N$ converges to some index $e$ (this can be checked using oracle $K$).
Then $x\in K^{\prime}$ holds iff $W_{e}=\\{n\\}$ (the latter condition can
also be checked using oracle $K$), and so $K^{\prime}\leqslant_{T}K$, but this
is impossible. ∎

The remainder of this section will consider a less stringent variant of
confidence called _weak confidence_. It will be shown that for every positive
equivalence relation $\eta$, there is an $\eta$-family witnessing the
separation between explanatory learning and weak confident learning.

###### Definition 28

For any given uniformly r.e. family $\mathcal{L}=\\{L_{0},L_{1},\ldots\\}$, a
text $T$ is said to be _consistent with $\mathcal{L}$_ iff there is an $e$
such that $\operatorname{content}(T)\subseteq L_{e}$. A learner $M$ is _weakly
confident_ iff $M$ converges on every text that is consistent with the target
class $\mathcal{L}$.

We first observe that for any positive equivalence relation $\eta$, weak
confidence is indeed a less stringent learning constraint than confidence with
respect to the class of $\eta$-families.

###### Theorem 29

Let $\eta$ be any given positive equivalence relation. Then
${\mathcal{A}}_{\eta}$ is weakly confidently learnable but not confidently
learnable.

Proof. It has been proven in Theorem 8 that the ascending family is not
confidently learnable. Furthermore, the explanatory learner constructed in the
proof of Theorem 8 is in fact weakly confident. To see this, note that for any
text $T$ such that $\operatorname{content}(T)\subseteq A_{e}$ for some
$e\in\mathbb{N}$, there is a least $a_{n}$ such that
$a_{n}\notin\operatorname{content}(T)$, and so the explanatory learner
constructed in the proof of Theorem 8 will, on $T$, converge to an index for
$A_{n}$. ∎

The next result separates weak confident learning from its class-preserving
variant.

###### Theorem 30

Let $\eta$ be any given positive equivalence relation. The class $\mathcal{L}$
consisting of all members of ${\mathcal{A}}_{\eta}$ and all $[a_{n+1}]$ with
$n\in K^{\prime}$ is an $\eta$-family that is weakly confidently learnable but
not class-preservingly weakly confidently learnable.

Proof. Note that $\mathcal{L}$ has a uniformly r.e. one-one numbering. First,
a uniformly r.e. numbering of $\mathcal{L}$ may be obtained as follows: for
all $n,s,t\in\mathbb{N}$, set

$\displaystyle L_{{\left\langle 2n,s,t\right\rangle}}$ $\displaystyle=$
$\displaystyle A_{n},$ $\displaystyle L_{{\left\langle
2n+1,s,t\right\rangle}}$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}[a_{n+1}]&\mbox{if $\forall
s^{\prime}\geqslant s\,\forall t^{\prime}\geqslant
t\,[\varphi^{K_{s^{\prime}}}_{n,t^{\prime}}(n)\downarrow]$;}\\\
A_{n+2}&\mbox{otherwise.}\end{array}\right.$

Thus $\mathcal{L}$ is a uniformly r.e. superfamily of ${\mathcal{A}}_{\eta}$,
and so by Proposition 9, $\mathcal{L}$ is also an $\eta$-family.

Let $M$ be a learner that works as follows on input $\sigma$. If
$a_{0}\in\operatorname{content}(\sigma)$ and $n$ is the least number for which
$a_{n,|\sigma|}\notin\operatorname{content}(\sigma)$, $M$ outputs a canonical
index for $A_{n}$; if $a_{0}\notin\operatorname{content}(\sigma)$ and
$\operatorname{content}(\sigma)\neq\emptyset$, then $M$ conjectures
$[\min(\operatorname{content}(\sigma))]$; if
$\operatorname{content}(\sigma)=\emptyset$, then $M$ just outputs a default
index. Then $M$ will make infinitely many mind changes on a given text $T$
only if, for all $n\in\mathbb{N}$, $a_{n}$ appears in $T$; thus, since no
language in $\mathcal{L}$ contains $\\{a_{n}:n\in\mathbb{N}\\}$, $M$ will
converge on every text for any $L\in\mathcal{L}$. Furthermore, given any text
$T$ for $A_{n}$, where $n\in\mathbb{N}$, there is an $s$ large enough so that
$a_{n,t}=a_{n}$, $a_{m}\in\operatorname{content}(T[t])$ and $a_{m,t}=a_{m}$
whenever $t\geqslant s$ and $m<n$, and so $M(T[t])$ is equal to a canonical
index for $A_{n}$ whenever $t\geqslant s$. Similarly, given any text
$T^{\prime}$ for $[a_{n+1}]$, where $n\in\mathbb{N}$, $a_{0}$ will not appear
in $T^{\prime}$ and so $M$ will converge to an index for $[x]$, where $x$ is
the least element of $[a_{n+1}]$ to appear in $T^{\prime}$. Thus $M$ is a
weakly confident learner of $\mathcal{L}$.

Assume, by way of contradiction, that $\mathcal{L}$ has a class-preserving
weakly confident learner $N$. Then, given any $n\in\mathbb{N}$, one can check
via oracle $K$ whether or not $n\in K^{\prime}$ as follows. Feed $N$ with the
text $a_{n}\circ a_{n}\circ a_{n}\circ\ldots$ until $N$ converges to an index
(since $N$ is weakly confident and $a_{n}\in A_{n+1}\in\mathcal{L}$, $N$ must
converge on this text), say $e$. Then $n\in K^{\prime}$ holds iff $a_{n+1}\in
W_{e}\wedge a_{0}\notin W_{e}$; the latter condition can be checked using
oracle $K$. This implies $K^{\prime}\leqslant_{T}K$, a contradiction. ∎

The next two results clarify the relationship between explanatory learning and
weakly confident learning of one-one $\eta$-closed families for any given
positive equivalence relation $\eta$.

###### Theorem 31

Let $\eta$ be any given positive equivalence relation. If there are at least
two $\eta$-infinite r.e. sets, then there is an $\eta$-family that is
explanatorily learnable but not weakly confidently learnable.

Proof. Let $B$ be any $\eta$-infinite r.e. set such that $B\neq\mathbb{N}$.
Fix some $b\notin B$. Let $\eta_{s}$ be the equivalence relation obtained by
enumerating $\eta$-equivalent pairs of elements of $B$ for $s$ steps and
keeping the relation closed transitively and reflexively. Furthermore,
$b_{n,s}$ is the $n$-th element in the order of the enumeration satisfying
that all elements before it in the enumeration are not $\eta_{s}$ equivalent
to $b_{n,s}$. Now set

$\begin{split}B_{0}&=\mathbb{N},\\\ B_{n+1}&=\\{x:\exists m<n\,\exists
s\,[x\,\eta_{s}\,b_{m,s}]\\}\end{split}$

for all $n\in\mathbb{N}$. As was shown in the proof of Theorem 16,
$\mathcal{L}:=\\{B_{n}:n\in\mathbb{N}\\}$ is explanatorily learnable. On the
other hand, $\mathcal{L}$ is not weakly confidently learnable. For, if $N$
were a weakly confidently learner for $\mathcal{L}$, then one could build a
text $T^{\prime}$ that is the limit of sequences
$\sigma_{0}\circ\sigma_{1}\circ\ldots\circ\sigma_{s}$ of strings, where, for
all $n$, $\sigma_{n}$ is the first string in $B_{n+1}^{*}$ found such that $N$
on input $\sigma_{0}\circ\ldots\circ\sigma_{n}$ outputs an r.e. index for
$B_{n+1}$; note that since $B_{n+i}\subset B_{n+i+1}$ for all $i$, such
strings $\sigma_{0},\sigma_{1},\ldots$ must exist. Then $T^{\prime}$ is a text
consistent with $\mathcal{L}$ (since $\mathbb{N}\in\mathcal{L}$) on which $N$
makes infinitely many mind changes, which contradicts the fact that $N$ is
weakly confident. ∎

###### Theorem 32

Let $\eta$ be any given positive equivalence relation. If $\mathbb{N}$ is the
only $\eta$-infinite r.e. set, then there is an $\eta$-family that is
explanatorily learnable but not weakly confidently learnable.

Proof. Let $\mathcal{L}$ be the class containing all $\eta$-closed sets
$A_{n+1}$ and $[a_{1},a_{n+2}]$ for $n\in\mathbb{N}$. An explanatory learner
$M$ may work as follows. On input $\sigma$, $M$ checks whether or not
$a_{0}\in\operatorname{content}(\sigma)$. If
$a_{0}\in\operatorname{content}(\sigma)$, then $M$ determines the least $n$
such that $a_{n+1,|\sigma|}\notin\operatorname{content}(\sigma)$ and outputs a
canonical index for $A_{n+1}$. If $a_{0}\notin\operatorname{content}(\sigma)$,
then $M$ determines the least $n$ such that
$a_{n+2,|\sigma|}\in\operatorname{content}(\sigma)$ (if such an $n$ exists)
and outputs a canonical index for $[a_{1},a_{n+2}]$; if no such $n$ exists,
then $M$ just outputs any default index.

Now assume for the sake of a contradiction that $\mathcal{L}$ has a weakly
confident learner $N$. Since $[a_{1}]\subseteq[a_{1},a_{n+2}]\in\mathcal{L}$
for all $n\in\mathbb{N}$, $N$ must (by the property of weak confidence)
converge on any text for $[a_{1}]$. In particular, there exists a stabilising
sequence $\sigma$ for $[a_{1}]$, that is, a sequence $\sigma\in[a_{1}]^{*}$
such that for all $\tau\in[a_{1}]^{*}$, $N(\sigma)=N(\sigma\tau)$ (see Section
3). Set $A:=\\{x:\exists\tau\in([a_{1},x]^{*}\,[N(\sigma)\neq
N(\sigma\tau)]\\}$. Since $N$ explanatorily learns $[a_{1},a_{n+2}]$ for all
$n\in\mathbb{N}$, $A$ must contain $a_{n+2}$ for all but at most one
$n\in\mathbb{N}$. On the other hand, for all $x\in[a_{1}]$, $x\notin A$ by the
choice of $\sigma$. Thus, taking $B=\bigcup_{x\in A}[x]$, $B$ is an
$\eta$-infinite r.e. set that is not equal to $\mathbb{N}$, contrary to the
hypothesis of the theorem. ∎

##  8 Monotonic, Conservative and Class-Preserving Learning

In this section, we turn out attention to _monotonic_ and _conservative_
learning of $\eta$-families for any given positive equivalence relation
$\eta$. Monotonicity and conservativeness are fairly natural learning
constraints that have been well-studied in the context of uniformly recursive
families [29] as well as more general classes of r.e. sets [25]. We first
revisit the ascending family, which was briefly studied in Section 4, and
prove that this class is in fact conservatively explanatorily learnable for
every positive equivalence relation.

###### Theorem 33

For every positive equivalence relation $\eta$ such that $[x]$ is infinite for
each $x$, ${\mathcal{A}}_{\eta}$ is conservatively explanatorily learnable.

Proof. It has already been shown in Theorem 8 that this family is
explanatorily learnable. One may modify the explanatory learner constructed in
the proof of this theorem to obtain a conservative explanatory learner $N$ as
follows: If the original learner’s conjecture at step $t$ is $A_{n_{t}}$ and
there is a least $s\geqslant t$ such that for some $m\leqslant n_{t}$,
$a_{m,s}\neq a_{m,s+1}$, then $N$ only enumerates elements of $A_{n_{t}}$
until step $s-1$; in particular, $N$ will not enumerate any $a_{i,t}$ with
$i\geqslant n_{t}$ into its conjecture. Thus if there is a first subsequent
step $t^{\prime}>t$ such that $a_{m,t^{\prime}}\neq a_{m,t^{\prime}-1}$ for
some $m\leqslant n_{t}$, $N$ can check in finitely many steps whether or not
the range of the current input contains some element not belonging to its
prior conjecture; if so, then it updates its conjecture to
$A_{n_{t^{\prime}}}$; otherwise, it repeats its prior conjecture. If there is
a first subsequent step $t^{\prime}>t$ at which the text enumerates
$a_{n_{t},t}$ but $a_{n_{t},t}\,\eta\,a_{m,t}$ for some $m<n_{t}$, then by
construction $N$ would not have enumerated $a_{n_{t},t}$ in its prior
conjecture and thus it is conservative in this case as well. ∎

The next result shows that for any positive equivalence relation $\eta$, there
is an $\eta$-subfamily of the ascending family for $\eta$ that has no class-
preserving conservatively behaviourally correct learner.

###### Theorem 34

For every positive equivalence relation $\eta$, there is an $\eta$-family
contained in ${\mathcal{A}}_{\eta}$ that is neither class-preservingly
conservatively behaviourally correctly learnable nor class-preservingly
strongly monotonically behaviourally correctly learnable.

Proof. Let $\mathcal{L}$ contain all $A_{2n}$ with $n\in\mathbb{N}$ and all
$A_{2n+1}$ where $W_{n}$ is finite. This class is r.e., as one can choose
$L_{\langle n,0\rangle}=A_{2n}$ and $L_{\langle n,m+1\rangle}=A_{2n+1}$ in the
case that $|W_{n}|\leqslant m$ and $A_{2n+2}$ in the case that $|W_{n}|>m$.
This enumeration is clearly r.e. and one can conclude by Proposition 10 that
there is an $\eta$-family for this class. Now assume that there is a class-
preserving conservatively behaviourally correct learner for the family. If
this learner does not output on any sequence from $A_{2n+1}^{*}$ a hypothesis
containing $a_{2n}$ (which can be computed using $K$) and which is in
$A_{2n+1}-A_{2n}$, then the learner does not learn $A_{2n+1}$ and thus $W_{n}$
is infinite. If this learner outputs on some sequence from $A_{2n+1}^{*}$ a
hypothesis containing $a_{2n}$ then one tests with $K$ whether the hypothesis
also contains $a_{2n+1}$. If so, again $W_{n}$ is infinite, as due to class-
preservingness of the learner, the only possible hypotheses issued are
$A_{2n+2}$ or a superset of this set and then the learner cannot learn
$A_{2n+1}$ by conservativeness. If not then the only hypothesis possible is
$A_{2n+1}$ by class-preservingness of the learner and therefore $A_{2n+1}$ is
in the class and $W_{n}$ is finite. Thus the existence of a class-preserving
conservatively behaviourally correct learner for $\mathcal{L}$ allows to
decide with the halting problem whether a given set $W_{n}$ is finite or
infinite and that is impossible; thus such a learner cannot exist. Finally, we
note that this proof by contradiction also works if one assumes that the
learner is class-preservingly strongly monotonically behaviourally correct. ∎

###### Theorem 35

For every positive equivalence relation $\eta$, there is an $\eta$-subfamily
of ${\mathcal{A}}_{\eta}$ that is conservatively explanatorily learnable but
not class-preservingly conservatively explanatorily learnable.

Proof. Let $f$ be a limit recursive function approximable from below that
dominates all recursive functions (for an example of such a function $f$, see
the proof of [38, Lemma 7.3(a)]); without loss of generality, assume that $f$
is strictly monotonically increasing. Define, for all $n\in\mathbb{N}$,

$B_{n}:=\\{x:\exists m\leqslant f(n)\,[x\,\eta\,a_{m}]\\}.$

By Theorem 8, $\mathcal{L}=\\{B_{n}:n\in\mathbb{N}\\}$ is conservatively
explanatorily learnable. Assume that $M$ were a class-preserving conservative
explanatory learner for $\mathcal{L}$. Let $g$ be a recursive function such
that for all $n\in\mathbb{N}$, $g(n)$ is one more than the maximum of the
range of the first $\sigma\in\mathbb{N}^{*}$ found for which $M$ makes $n$
mind changes on $\sigma$ and when $M(\tau_{1})\neq M(\tau_{2})$ and
$M(\tau_{2})\neq M(\tau_{3})$ for prefixes $\tau_{1},\tau_{2},\tau_{3}$ of
$\sigma$ with $\tau_{1}\subseteq\tau_{2}\subseteq\tau_{3}$, then
$\operatorname{content}(\tau_{1})\subseteq W_{M(\tau_{3})}$. Since $f$
dominates all recursive functions, there is some $n$ such that
$g(3n+3)\leqslant f(n)$. Note that all hypotheses that $M$ issues on prefixes
of $\sigma$ are based on subsets of $B_{n}$. There are more than $n$ different
hypotheses output by $M$ on prefixes of $\sigma$ and each must be equal to
some $B_{m}$ with $m<n$, which is impossible. ∎

The next theorem considers the question: given any positive equivalence
relation $\eta$, can one always find an $\eta$-family witnessing the
separation of monotonic behaviourally correct and explanatory learning? It
turns out that this is indeed the case iff there are at least two distinct
$\eta$-infinite r.e. sets.

###### Theorem 36

Let $\eta$ be any given positive equivalence relation. The following
conditions are equivalent.

  1. (1)

There is an $\eta$-family that is explanatorily learnable but not
monotonically behaviourally correctly learnable.

  2. (2)

There is an $\eta$-family that is class-preservingly weakly monotonically
explanatorily learnable but not monotonically behaviourally correctly
learnable.

  3. (3)

There is an $\eta$-infinite r.e. set that is different from $\mathbb{N}$.

Proof. It is immediate that $(2)\Rightarrow(1)$. It will be shown that (1)
$\Rightarrow$ (3) $\Rightarrow$ (2).

(1) $\Rightarrow$ (3). Suppose $\mathbb{N}$ is the only $\eta$-infinite r.e.
set. Consider any $\eta$-family $\mathcal{L}$ that is explanatorily learnable,
as witnessed by some learner $P$. First, Proposition 15 implies that for all
$L\in\mathcal{L}$, $L$ is the union of finitely many equivalence classes of
$\eta$. Let $Q$ be a learner such that on input $\sigma$, $Q$ conjectures
$\bigcup_{x\in\operatorname{content}(\sigma)}[x]$. Note that $Q$ is strongly
monotonic by construction. Moreover, given any $L\in\mathcal{L}$, $Q$ on any
text for $L$ will conjecture $L$ in the limit because $L$ is composed of only
finitely many equivalence classes.

(3) $\Rightarrow$ (2). Suppose there is an $\eta$-infinite r.e. set $B_{0}$
such that for some $k\in\mathbb{N}$, $a_{k}\notin B_{0}$. Let $\mathcal{L}$ be
the $\eta$-family comprising $B_{0}$ and
$B_{n+1}:=A_{n+k+1}=\bigcup_{m\leqslant n+k}[a_{m}]$ for all $n\in\mathbb{N}$.

The following learner $M$ explanatorily learns $\mathcal{L}$ and is both
weakly monotonic and class-preserving. On input $\sigma$:

Case 1: $a_{k}\notin\operatorname{content}(\sigma)$. $M$ conjectures $B_{0}$.

Case 2: $a_{k}\in\operatorname{content}(\sigma)$.

Case 2.1: There is an $n\in\mathbb{N}$ such that
$a_{n+k+1,|\sigma|}\notin\operatorname{content}(\sigma)$ and $a_{m,|\sigma|}$
$\in\operatorname{content}(\sigma)$ whenever $m\leqslant n+k$. $M$ outputs an
index $e$ such that

$W_{e}=\left\\{\begin{array}[]{ll}\bigcup_{m\leqslant
n+k}[a_{m,|\sigma|}]&\mbox{if }\\{a_{m}:m\leqslant k\\}\ \subseteq\\\
&\\{a_{m,|\sigma|}:m\leqslant n+k\\};\\\
B_{1}&\mbox{otherwise.}\end{array}\right.$

Case 2.2: Neither Case 1 nor Case 2.1. $M$ conjectures $B_{1}$.

Note that $M$ always outputs an index for $B_{0}$ or for a set
$\bigcup_{m\leqslant n}[a_{m}]$ with $n\geqslant k$, and hence it is class-
preserving. By Case 1 and the fact that $a_{k}\notin B_{0}$, $M$ on any text
for $B_{0}$ will always conjecture $B_{0}$. In particular, $M$ on any text for
$B_{0}$ strongly monotonically explanatorily learns $B_{0}$. If $M$ is
presented with a text $T$ for some $B_{n+1}$, then there is an $s$ large
enough so that $\\{a_{m}:m\leqslant
n+k\\}\subseteq\operatorname{content}(T[s])$ and for all $t\geqslant s$ and
$m\leqslant n+k+1$, $a_{m,t}=a_{m}$. By Case 2, for all $t\geqslant s$, $M$ on
$T[t]$ will conjecture $B_{n+1}$. Hence $M$ is a class-preserving explanatory
learner of $\mathcal{L}$. To see that $M$ is also weakly monotonic on every
text for any set $B_{n+1}$, let $\tau_{1}$ and $\tau_{2}$ be any two sequences
in $(B_{n+1}\cup\\{\\#\\})^{*}$ such that $\tau_{2}$ extends $\tau_{1}$, and
consider the following case distinction.

Case i: $a_{k}\notin\operatorname{content}(\tau_{2})$. Then $M$ conjectures
$B_{0}$ on both $\tau_{1}$ and $\tau_{2}$.

Case ii: $a_{k}\notin\operatorname{content}(\tau_{1})$ and
$a_{k}\in\operatorname{content}(\tau_{2})$. Since $M$ on $\tau_{1}$ will
conjecture $B_{0}$ but $a_{k}\notin B_{0}$, the weak monotonicity condition is
satisfied vacuously.

Case iii: $a_{k}\in\operatorname{content}(\tau_{1})$. Suppose $M$ on
$\tau_{1}$ conjectures $B_{1}$. As $a_{k}\in\operatorname{content}(\tau_{2})$,
$M$ on $\tau_{2}$ must output a set $B_{i}$ with $i\geqslant 1$, and therefore
$W_{M(\tau_{1})}\subseteq W_{M(\tau_{2})}$. Suppose $M$ on $\tau_{1}$
conjectures some set $B_{n+1}$ with $n\geqslant 1$. Then there is some
$n^{\prime}\geqslant n$ and subset $\\{i_{0},\ldots,i_{n+k}\\}$ of
$\\{0,\ldots,n^{\prime}+k\\}$ with $i_{0}<\ldots<i_{n+k}$ such that

  1. (1)

For all $j\in\\{0,\ldots,n+k\\}$, $a_{i_{j},|\tau_{1}|}=a_{j}$;

  2. (2)

$\\{a_{m,|\tau_{1}|}:m\leqslant
n^{\prime}+k\\}\subseteq\operatorname{content}(\tau_{1})$.

Note that for all $s,t\in\mathbb{N}$ with $s\leqslant t$,
$\\{a_{m}:m\in\mathbb{N}\\}\subseteq\\{a_{m,t}:m\in\mathbb{N}\\}\subseteq\\{a_{m,s}:m\in\mathbb{N}\\}$.
Thus, there is some $\ell\geqslant n+k$ such that
$a_{\ell,|\tau_{2}|}=a_{n+k}=a_{i_{n+k},|\tau_{1}|}$, from which it follows
that

$\begin{split}\\{a_{m}:m\leqslant
n+k\\}&\subseteq\\{a_{m,|\tau_{2}|}:m\leqslant\ell\\}\\\ \leavevmode\nobreak\
&\subseteq\\{a_{m,|\tau_{1}|}:m\leqslant i_{n+k}\\}\\\ \leavevmode\nobreak\
&\subseteq\operatorname{content}(\tau_{1})\\\ \leavevmode\nobreak\
&\subseteq\operatorname{content}(\tau_{2}).\end{split}$

Consequently, $M$ on $\tau_{2}$ will conjecture a set containing
$\bigcup_{m\leqslant n+k}[a_{m}]$, and so $W_{M(\tau_{1})}\subseteq
W_{M(\tau_{2})}$.

Now consider any behaviourally correct learner $N$ of $\mathcal{L}$. It will
be shown that $N$ cannot be monotonic. Since $N$ behaviourally correctly
learns $B_{0}$, there is some $\sigma\in B_{0}^{*}$ such that
$W_{N(\sigma)}=B_{0}$. Pick some $n\in\mathbb{N}$ such that $a_{n+k+1}\in
B_{0}$ and $\operatorname{content}(\sigma)\subseteq B_{n+1}$; such an $n$
exists because $\sigma$ is finite and $B_{0}$ is an $\eta$-infinite r.e. set.
As $N$ also behaviourally correctly learns $B_{n+1}$, there is some $\tau\in
B_{n+1}^{*}$ such that $W_{N(\sigma\circ\tau)}=B_{n+1}$. But
$a_{n+k+1}\in(B_{0}\cap B_{n+2})-(B_{n+1}\cap B_{n+2})=(W_{N(\sigma)}\cap
B_{n+2})-(W_{N(\sigma\circ\tau)}\cap B_{n+2})$ implies that $W_{N(\sigma)}\cap
B_{n+2}\not\subseteq W_{N(\sigma\circ\tau)}\cap B_{n+2}$, and since
$\operatorname{content}(\sigma\tau)\subseteq B_{n+2}\in\mathcal{L}$, it may be
concluded that $N$ does not learn $B_{n+2}$ monotonically – a contradiction. ∎

##  9 Conclusion

The present work studied how the relations between the most basic inference
criteria for learning from text are impacted when the only classes to be
considered for learning are uniformly r.e. one-one families of sets which are
closed under a given positive equivalence relation $\eta$. One considers the
chain of implications finitely learnable $\Rightarrow$ confidently learnable
$\Rightarrow$ explanatorily learnable $\Rightarrow$ vacillatorily learnable
$\Rightarrow$ behaviourally correctly learnable which is immediate from the
definitions. When choosing $\eta$ as the explicitly constructed $\vartheta$
from Theorem 20, the implication from explanatorily learnable to vacillatorily
learnable becomes an equivalence and the criterion of confidently learnable
becomes void, that is, no $\vartheta$-family satisfies it. For the positive
equivalence relation $\zeta$ from Description 25, there is a $\zeta$-family
which is confidently learnable, but none which is finitely learnable.
Furthermore, in the case that a finitely learnable $\eta$-family exists for
some $\eta$, then there is also a confidently learnable $\eta$-family which is
not finitely learnable. For all choices of $\eta$, the implications from
confident to explanatory learning and from vacillatory to behaviourally
correct learning cannot be reversed and the class of all $\eta$-closed r.e.
set is an $\eta$-family which cannot be learnt behaviourally correctly. The
learnability of $\eta$-families with additional constraints such as
monotonicity and conservativeness was also investigated; one interesting
finding was that the separability of learning criteria for $\eta$-families is
sometimes contingent on the existence of at least two $\eta$-infinite sets.
Besides investigating the situation for further learning criteria, future work
can investigate to which extent the results generalise to arbitrary uniformly
r.e. families of $\eta$-closed sets. Here one would get that the family of all
$\eta$-singletons is r.e. and finitely, thus confidently learnable: the
learner generates an index of the $\eta$-equivalence class to be learnt from
the first data-item observed and keeps this hypothesis forever. So one has one
more level in the learning hierarchy. However, the collapse of vacillatory
learning to explanatory learning for the constructed equivalence relation
$\vartheta$ generalises to uniformly r.e. families.

## References

  * [1] Dana Angluin.  Inductive inference of formal languages from positive data.  Information and Control, 45:117–135, 1980.
  * [2] Ganesh Baliga, John Case and Sanjay Jain.  The synthesis of language learners.  Information and Computation, 152(1):16–43, 1999.
  * [3] Janis M. Bārzdiņs̆.  Two theorems on the limiting synthesis of functions.  In Janis M. Bārzdiņs̆, editor, Theory of Algorithms and Programs I, volume 210 of Proceedings of the Latvian State University, pages 82–88. Latvian State University, Riga, 1974.  In Russian.
  * [4] Janis M. Bārzdiņs̆.  Inductive inference of automata, functions and programs.  In American Mathematical Society Translations, pages 107–122, 1977\.  Appeared originally in the Proceedings of the 20-th International Congress of Mathematicians 1974, Volume 2, pages 455–460, 1974. In Russian.
  * [5] Walter Baur.  Rekursive Algebren mit Kettenbedingungen.  Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 20:37–46, 1974. In German.
  * [6] Nikolay Bazhenov, Ekaterina Fokina and Luca San Mauro.  Learning families of algebraic structures from informant.  Information and Computation, 275:104590, 2020.
  * [7] Lenore Blum and Manuel Blum.  Toward a mathematical theory of inductive inference.  Information and Control, 28:125–155, 1975.
  * [8] John Case.  The power of vacillation in language learning.  SIAM Journal on Computing, 28(6):1941–1969, 1999.
  * [9] John Case, Sanjay Jain and Frank Stephan.  Vacillatory and BC learning on noisy data.  Theoretical Computer Science, 241(1–2):115–141, 2000.
  * [10] John Case and Chris Lynes.  Machine inductive inference and language identification. _Proceedings of the Ninth International Colloquium on Automata, Languages and Programming_ , Lecture Notes in Computer Science 140 (1982):107–115.
  * [11] John Case and Carl Smith.  Comparison of identification criteria for machine inductive inference.  Theoretical Computer Science, 25:193–220, 1983.
  * [12] Yuri L. Ershov.  Positive equivalences.  Algebra and Logic, 10(6):378–394, 1974.
  * [13] Yuri L. Ershov.  Theory of numberings. Nauka, Moscow, 1977 (in Russian).
  * [14] Jerome A. Feldman.  Some decidability results on grammatical inference and complexity.  Information and Control 20(3):244–262, 1972.
  * [15] Ekaterina B. Fokina, Bakhadyr Khoussainov, Pavel Semukhin and Daniel Turetsky.  Linear orders realized by c.e. equivalence relations.  The Journal of Symbolic Logic, 81(2):463–482, 2016.
  * [16] Ekaterina B. Fokina and Timo Kötzing and Luca San Mauro.  Limit learning equivalence structures.  Proceedings of the 30th International Conference on Algorithmic Learning Theory (ALT 2019), pages 383–403, 2019.
  * [17] Mark Fulk.  A study of inductive inference machines.  Ph.D. Thesis, SUNY/Buffalo, 1985.
  * [18] Alex Gavryushkin, Sanjay Jain, Bakhadyr Khoussainov and Frank Stephan.  Graphs realised by r.e. equivalence relations.  Annals of Pure and Applied Logic, 165:1263–1290, 2014.
  * [19] Alex Gavryushkin, Bakhadyr Khoussainov and Frank Stephan.  Reducibilities among Equivalence Relations induced by Recursively Enumerable Structures.  Theoretical Computer Science, 612:137–152, 2016.
  * [20] E. Mark Gold.  Language identification in the limit.  _Information and Control_ 10:447–474, 1967.
  * [21] Sanjay Jain, Daniel N. Osherson, James S. Royer and Arun Sharma.  _Systems That Learn_.  MIT Press, Second Edition, 1999.
  * [22] Sanjay Jain and Arun Sharma.  The intrinsic complexity of language identification.  Journal of Computer and System Sciences, 52:393–402, 1996.
  * [23] Sanjay Jain, Frank Stephan and Nan Ye.  Prescribed learning of r.e. classes.  _Theoretical Computer Science,_ 410:1796–1806, 2009.
  * [24] Klaus P. Jantke.  Monotonic and non-monotonic inductive inference of functions and patterns.  In: Dix J., Jantke K.P., Schmitt P.H., editors, _Nonmonotonic and Inductive Logic,_ volume 543 of _Lecture Notes in Computer Science_ , pages 161–177, 1991.
  * [25] Timo Kötzing and Martin Schirneck.  Towards an atlas of computational learning theory.  _33rd Symposium on Theoretical Aspects of Computer Science (STACS)_ , pages 47:1–47:13, 2016.
  * [26] Martin Kummer.  An easy priority-free proof of a theorem of Friedberg.  Theoretical Computer Science 74:249–251, 1990.
  * [27] Steffen Lange and Thomas Zeugmann.  Types of monotonic language learning and their characterization.  In: David Haussler, editor, _Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, July 27–29, 1992, Pittsburgh, Pennsylvania_ , pages 377–390, New York, NY, 1992\. ACM Press.
  * [28] Steffen Lange and Thomas Zeugmann.  Language learning in dependence on the space of hypotheses.  Proceedings of the Sixth Annual Conference on Computational Learning Theory, COLT 1993, pages 127–136, 1993.
  * [29] Steffen Lange and Thomas Zeugmann.  Monotonic versus non-monotonic language learning.  In: Dix J., Jantke K.P., Schmitt P.H., editors, _Nonmonotonic and Inductive Logic,_ volume 659 of _Lecture Notes in Computer Science_ , pages 254–269, 1993.
  * [30] Steffen Lange and Thomas Zeugmann.  Learning recursive languages with bounded mind changes.  _International Journal of Foundations of Computer Science_ , 4:157–178, 1993.
  * [31] Yasuhito Mukouchi.  Characterization of finite identification.  In: K.P. Jantke, editor, _Analogical and Inductive Inference, International Workshop AII ’92, Dagstuhl Castle, Germany, October 1992, Proceedings_ , volume 642 of _Lecture Notes in Artificial Intelligence_ , pages 260–267, 1992.
  * [32] Emmy Noether.  Idealtheorie in Ringbereichen.  Mathematische Annalen, 83:24–66, 1921.
  * [33] Petr Sergeevich Novikov.  On the algorithmic unsolvability of the word problem in group theory.  Trudy Matematicheskogo Instituta imeni V.A. Steklova, Academy of Sciences of the USSR, 44:3–143, 1955.
  * [34] Piergiorgio Odifreddi.  Classical Recursion Theory.  North-Holland, Amsterdam, 1989.
  * [35] Piergiorgio Odifreddi.  Classical Recursion Theory, Volume II.  Elsevier, Amsterdam, 1999.
  * [36] Daniel Osherson, Michael Stob and Scott Weinstein.  Systems That Learn, An Introduction to Learning Theory for Cognitive and Computer Scientists.  Bradford — The MIT Press, Cambridge, Massachusetts, 1986.
  * [37] Hartley Rogers.  Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.
  * [38] James S. Royer and John Case.  Subrecursive programming systems: Complexity & succinctness. Progress in Theoretical Computer Science.  Birkhäuser Boston, Inc., Boston, MA, 1994.
  * [39] Robert Soare.  Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets.  Springer-Verlag, Heidelberg, 1987.
  * [40] Boris A. Trakhtenbrot and Janis M. Bārzdiņs̆.  Konetschnyje awtomaty (powedenie i sinetez).  Nauka, Moscow, 1970, in Russian.  English Translation: Finite Automata-Behavior and Synthesis, _Fundamental Studies in Computer Science 1_ , North-Holland, Amsterdam, 1975\.
  * [41] Rolf Wiehagen.  A thesis in inductive inference.  In: Dix J., Jantke K.P., Schmitt P.H., editors, _Nonmonotonic and Inductive Logic,_ volume 543 of _Lecture Notes in Computer Science_ , pages 184–207, 1991.