An Order-Theoretic Characterization of Consistent Inductive Inference

We may assume that the learner remembers observed labels and never makes a mistake on a previously seen input. This simple convention ensures that the mistake histories constructed below contain only distinct inputs. Formally, let $A_{0}$ be a consistent learner. On a realizable history $\tau$, define $A(\tau,x)$ to be the previously observed label when $x$ has already appeared, and $A_{0}(\tau,x)$ otherwise. On unrealizable histories, set $A=A_{0}$. Along any sequence labeled by a fixed $h\in H$, the two learners receive the same histories, and every prediction on which they differ is correct for $A$. Thus $A$ makes a subset of the mistakes of $A_{0}$ and remains consistent. With $f_{\tau}(x)=A(\tau,x)$, we have

By the axiom of choice, fix a well-order $<_{E}$ on $E=X\times 2$, to be used for every trace. For a trace $p$ and a history $\tau$, let

be the examples in $p$ that the current predictor misclassifies. Starting from $\tau_{0}=()$, recursively set

and stop when this error set is empty. The procedure presents the learner only with examples on which its current prediction is wrong. The order $<_{E}$ makes the selection deterministic whenever several such examples are available.

Every intermediate history has trace contained in $p$, and is therefore realizable. If $(x,b)\in p$ has an input already seen in $\tau_{k}$, its label agrees with the earlier observation because $p$ is a partial function. Normalization then gives $f_{\tau_{k}}(x)=b$. Hence no such example lies in $D_{p}(\tau_{k})$: every appended input is new, and the procedure stops after at most $|p|$ steps.

Denote its terminal history by $T(p)$, the canonical transcript of $p$, and let $r(p)=\operatorname{tr}(T(p))$. By construction and termination,

The transcript may omit many examples, but its terminal predictor agrees with the whole trace. Since the learner depends on an ordered history, the set $r(p)$ alone does not a priori record the information needed to recover that predictor. The following lemma shows that the canonical selection rule recovers the entire transcript from $r(p)$, and that deleting any unselected examples leaves the transcript unchanged.

Taking $q=r(p)$ and then taking traces gives

Next consider what happens when $p\subseteq q$. Until their runs diverge, every error available in $p$ is also available in $q$. The larger trace can introduce a smaller selected example at the first divergence, or it can prolong the transcript after the run on $p$ has stopped. We use an order on histories in which either change moves the transcript earlier.

Equip $E^{<\omega}$ with the strict Kleene–Brouwer order $<_{\mathrm{KB}}$: $\sigma<_{\mathrm{KB}}\tau$ if $\tau$ is a proper prefix of $\sigma$, or if neither is a prefix of the other and $\sigma_{j}<_{E}\tau_{j}$ at their first differing position $j$. Thus proper extensions precede their prefixes; otherwise the first different entry determines the comparison. This is a strict linear order. Write $\leq_{\mathrm{KB}}$ for its reflexive extension.

We compare traces primarily by their transcripts. Different traces may have the same transcript, so we also need a tie-break. Define $\triangleleft$ on $\mathcal{F}_{H}$ by comparing cardinalities first, and then comparing the $<_{E}$-increasing enumerations lexicographically among traces of the same cardinality.

This is a well-order. For a fixed cardinality $n$, a nonempty family of increasing enumerations has a lexicographically least member: choose the least occurring first coordinate, then the least second coordinate among those with that first coordinate, and continue for $n$ steps. A nonempty family of finite traces therefore has a least member by first choosing its least occurring cardinality. Moreover, $s\subsetneq p$ implies $s\triangleleft p$. This last property is the reason for using cardinality as the first tie-break: the transcript’s own trace must precede every larger trace having the same transcript.

Define $\prec$ on $\mathcal{F}_{H}$ by

This is the lexicographic order on the pairs $(T(p),p)$. Both constituent comparisons are strict linear orders, and the second distinguishes traces with equal transcripts. Thus $\prec$ is a strict linear order on $\mathcal{F}_{H}$.

We claim that its least subtrace of $p$ is exactly $r(p)$. For any $s\subseteq p$, replay and comparison give

If the inequality is strict, the primary comparison gives $r(p)\prec s$. If the transcripts are equal, taking traces gives $r(p)=r(s)\subseteq s$. Either $r(p)=s$, or the inclusion is proper, in which case $r(p)\triangleleft s$. The tie-break therefore gives $r(p)\preceq s$ in this case as well. Since $r(p)\subseteq p$, we have proved

Suppose $m_{\prec}(p)=m_{\prec}(q)=s$. By (8), $r(p)=r(q)=s$, and replay yields

The terminal predictor $f_{T(s)}$ agrees with every example of $p$ and of $q$. They cannot assign opposite labels to a common input. Equal minima therefore imply compatibility, proving (2).

The finite construction and conflict separation are now established. Termination on each individual finite trace does not yet control an infinite sequence of different traces. To obtain that control, we use consistency on a fixed target and the following classical tree-ordering fact (Aschenbrenner and Pong, 2004, Definition 4.5 and Lemma 4.6). This fact turns the absence of infinite branches into a well-order on the corresponding finite histories.

Fix $h\in H$ and consider its mistake tree

This is the tree of histories labeled by $h$ on which $A$ errs at every round. To verify that it is prefix-closed, take a history $\tau=((x_{i},h(x_{i})))_{i<n}\in W_{h}$ and any $k\leq n$. Retain its first $k$ examples and discard the last $n-k$, obtaining $\sigma=((x_{i},h(x_{i})))_{i<k}$. At each retained round $i<k$, the learner receives exactly the same preceding history $((x_{j},h(x_{j})))_{j<i}$ and current input $x_{i}$ as in $\tau$. Its prediction is therefore unchanged, so it still makes a mistake at that round. Thus $\sigma$ is also a history labeled by $h$ on which $A$ errs at every round, and hence $\sigma\in W_{h}$. Every prefix of $\tau$, including the empty history when $k=0$, therefore belongs to $W_{h}$, which is precisely prefix-closure.

Normalization ensures that its histories have distinct inputs. An infinite branch would therefore give one infinite input sequence, labeled by this same $h$, on which $A$ makes a mistake at every round. Consistency rules out such a branch. By Lemma 3.3, $<_{\mathrm{KB}}$ well-orders $W_{h}$. The argument permits arbitrarily long finite branches and does not require a uniform finite bound on their lengths.

For every $p\in\mathcal{F}_{h}$, the entries of $T(p)$ lie in $p\subseteq\operatorname{graph}(h)$, and each is a mistake after the preceding entries. Thus $T(p)\in W_{h}$. To prove well-ordering of the traces themselves, take a nonempty $S\subseteq\mathcal{F}_{h}$. The set $\{T(p):p\in S\}$ has a $<_{\mathrm{KB}}$-least transcript $\tau$. Among the traces $p\in S$ with $T(p)=\tau$, choose the $\triangleleft$-least one, denoted $p_{*}$. Any $q\in S$ with a different transcript follows $p_{*}$ by the primary comparison; any distinct $q\in S$ with the same transcript follows $p_{*}$ by the tie-break. Hence $p_{*}$ is the $\prec$-least element of $S$.

It follows that $\prec|_{\mathcal{F}_{h}}$ is a well-order. Since $h$ was arbitrary and $\prec$ was constructed before fixing $h$, the same order satisfies the condition for every target. This completes the proof of Theorem 2.1.∎

Let $H_{\mathrm{fin}}\subseteq 2^{\omega}$ consist of the functions with finitely many positive inputs, and put $p^{+}=\{(x,1)\in p\}$ for each realizable trace $p$. Fix a well-order $\triangleleft$ on $\mathcal{F}_{H_{\mathrm{fin}}}$. Define $\prec$ by comparing traces first by decreasing $|p^{+}|$, then by increasing $|p|$, and finally by $\triangleleft$. Among the subtraces of $p$, the trace $p^{+}$ retains all its positive examples and has the smallest possible cardinality subject to doing so. Hence

Conflicting traces have different positive parts, so conflict separation holds. For a fixed target $h$, the value $|p^{+}|$ is bounded by the finite number of positive inputs of $h$. The first comparison therefore has only finitely many possible values on $\mathcal{F}_{h}$. Within each such value, cardinality and $\triangleleft$ give a well-order. Thus $\prec|_{\mathcal{F}_{h}}$ is a well-order. The decoder $g_{r}$ predicts $1$ exactly at the positive inputs retained in $r$. The induced learner remembers observed positive inputs and predicts $0$ elsewhere; each mistake reveals a new positive input of the target.

For comparison, consider the different protocol in which each finite prefix need only be realized by some hypothesis, possibly a different one for each prefix. Every finite prefix of $(0,1),(1,1),(2,1),\ldots$ is realized by a member of $H_{\mathrm{fin}}$, but the entire sequence is not. It is therefore permitted by that alternative protocol and excluded from ours. This distinction explains why our theorem imposes well-foundedness on the traces of each fixed target.

Our learner shares the central idea of Littlestone’s Standard Optimal Algorithm (SOA): every mistake forces a decrease in an ordered state. SOA predicts so that a mistake reduces the Littlestone dimension of the hypotheses agreeing with the history, yielding a uniform mistake bound when this dimension is finite (Littlestone, 1988). Here the state is a least subtrace, decoded into a predictor, and descent is controlled by well-foundedness for each target rather than by a finite dimension.

Bousquet et al. (2021, Section 3) extend the descent argument using ordinal Littlestone dimension. Their online protocol requires only realizability of each finite prefix. Our condition instead reflects the requirement of one common target: the same order serves all targets, but it need be well-founded only on each target’s traces.

Theorem 2.1 resolves the characterization problem for consistency raised in Section 5 of Lu (2024). The main guarantee studied there allows a mistake bound depending on $h$, but requires it to hold uniformly over input sequences. This hypothesis-wise requirement sits between the classical uniform bound, independent of both target and sequence, and consistency, which requires only finitely many mistakes for each individual target–sequence pair.

The distinction is strict, as the following example shows.

The maps $p\mapsto m(p)$ and $r\mapsto g_{r}$ give a labeled compression–reconstruction representation, with no uniform bound on the retained sample size. Equation (9) connects it to stable compression (Hanneke and Kontorovich, 2021), while the use of a preference order recalls order compression schemes (Darnstädt et al., 2013). Those schemes order a reconstruction class; here the order is on finite traces, and conflict separation makes the decoder well-defined. In the converse, canonical mistake transcripts and replay recover a predictor from an unordered subtrace. The Kleene–Brouwer order converts the absence of infinite mistake histories for each target into the required well-foundedness.

The countability criterion in Proposition 4.2 has an effective counterpart on $X=\omega$. A total computable consistent learner exists if and only if there is a total computable function $F:\omega\times\omega\to 2$ such that

For necessity, every $h\in H$ must equal $A(\tau,\cdot)$ at some $h$-realizable finite history $\tau$: otherwise, repeatedly choosing an input on which the current predictor disagrees with $h$ gives infinitely many mistakes against that fixed target. Effectively enumerating all finite histories therefore supplies the required family. For sufficiency, at a history of length $n$, follow the least index $i\leq n$ whose predictor agrees with the history, or predict $0$ if none does. This finite search defines a total computable learner even on unrealizable histories. For target $F(k,\cdot)$, there are at most $k$ mistakes before round $k$; thereafter, every mistake permanently eliminates an index below $k$, so the total is at most $2k$. This is the fixed-target analogue of the projection and enumeration argument of Kalociński and Steifer (2025, Lemma 3 and Theorem 5), whose protocol requires realizability of every finite prefix.