arXiv CSopen access

Globally Consistent Coloring Schemes for Language Identification

Globally Consistent Coloring Schemes for Language Identification Moses Charikar∗

Jon Kleinberg†

Chirag Pabbaraju‡

July 14, 2026

Abstract

arXiv:2607.11606v1 [cs.CL] 13 Jul 2026

We study how little extra information is needed to make adversarial language learning possible. In Gold’s model of language identification in the limit, a learner is given an enumeration of the strings from an unknown target language chosen from a countable list of candidate languages. The learner guesses the identity of the language over the course of the enumeration, and it succeeds if, after some finite time, all of its guesses are the correct language. Classical results of Gold and Angluin show that many natural collections cannot be learned in this way. Recent work on trace colorings, motivated by the success of annotation and thinking-trace strategies in language learning, overcomes this obstruction by annotating every symbol of every observed string with a color. We ask whether the learner really needs this whole sequence of colors, or whether one color at the end of each string (a terminal coloring) is enough to facilitate language identification. We show that just one terminal bit per string is enough for every countable collection of infinite languages. In fact, the colorings can be chosen collection-independently: there is a single assignment of a two-color terminal coloring to every infinite language such that the same preassigned colorings identify every countable subcollection. Thus, in this model, an entire color trace can be compressed to one bit attached to the end of each example. This optimal compression has a set-theoretic cost. Our global construction uses almostdisjoint families and a transfinite recursion, and we prove that this kind of strong nonconstructivity is unavoidable for any bounded number of colors. As a notion of constructivity, we use the standard formalism of Borel maps (a regularity condition satisfied by natural explicit constructions); we show that no global terminal coloring with a finite number of colors defined by a Borel map can identify all countable subcollections. By contrast, known trace-coloring constructions are Borel when encoded as terminal colorings, but require infinitely many terminal colors. Our lower bound uses the Galvin-Prikry theorem (an infinite-dimensional generalization of Ramsey’s Theorem) to canonicalize any Borel coloring into a finite-prefix coloring, and then proves that finite-prefix colorings cannot support identification for all countable collections. These results give a sharp tradeoff between where the annotation is placed, how many colors it uses, and how explicitly the coloring rule can be defined.

∗

Stanford University. Email: [email protected]. Cornell University. Email: [email protected]. ‡ Stanford University. Email: [email protected]. †

1

1

Introduction

Dramatic advances in the power of large language models have rewakened interest in abstract models of language learning. These models can be viewed as formalisms for language acquisition that operate at a level of abstraction more general than any particular architecture or algorithm, and in this way they seek principles that might exist outside the specific assumptions of any architectural or algorithmic decisions we have made in current systems. One of the very earliest and most influential of these formalisms is Gold’s notion of language identification in the limit [Gol67], which presents language learning as a game played between an adversary and an algorithm. The adversary thinks of a secret language K that is known to come from a countable collection of candidate languages L1 , L2 , L3 , . . .; the adversary presents the strings of K to the algorithm one-by-one; and in each step the algorithm tries to guess the identity of the language. (As usual, a language is simply a set of finite strings, and we will generally think of all the languages in the collection as infinite sets unless noted otherwise.) In particular, in each step t the adversary presents a string wt from the secret language K, and the algorithm guesses an index it , with the goal that Lit = K. The algorithm wins this game if there is some t∗ such that Lit = K for all t ≥ t∗ , and if it does this, then it has achieved identification in the limit. Given that the model is based on worst-case assumptions about the adversary’s choice of language K and its enumeration of K, the game is very hard for the algorithm to win, and Gold’s original theorem showed that identification in the limit was not possible in general even for language collections L1 , L2 , L3 , . . . as simple as the regular languages [Gol67], Angluin subsequently characterized the very limited cases in which the algorithm can succeed at this task [Ang80]. Trace colorings. Because language learning appears to be more tractable in practice than the bleak view suggested by Gold’s negative result, attention turned to strengthenings of the underlying assumptions that could produce formalisms reflecting this tractability. Arguably the most widespread of these strengthenings was the introduction of probabilistic assumptions: the language choice may be adversarial, but the enumeration of the examples from the language comes from an underlying distribution that therefore constrains the adversary. A recent line of work, in contrast, has explored a set of assumptions that enhance the tractability of the model while maintaining its core worst-case style. This line of work is based on the observation that in practice, training data for language learning often comes annotated with additional metadata or trace data that helps further explain the training data’s membership in its underlying language [BHK26, PF25, PSV26]. For example, training datasets consisting of computer code often comes with comments in the code; training datasets consisting of solutions to math problems often contain the written step-by-step reasoning of expanded solution sets. In such cases, the expanded meta-data or annotations have proved very helpful for training. Indeed, guided in part by this insight, recent developments in large language models have greatly extended the set of annotations via chain-of-thought mechanisms that explicitly add thinking tokens to the output of the model [WWS+ 22]. All of these annotations have been viewed, in this recent line of theoretical work, as computational traces: extra information that accompanies the strings of the language as they are presented to the learner [BHK26, PF25, PSV26]. The idea in the theoretical models arising from this research is the following: we attach an annotation symbol to each symbol of each string, and we present this to the algorithm as part of the enumeration of strings in a language learning problem. In this way, the language learning works with these “annotated strings” — where each symbol has an annotation added to it — rather than the raw strings themselves. In the work of Peng et al. (2026), these traces come from an underlying machine model, in 2

that we assume the language being learned is the set of inputs recognized by a state machine (a finite automaton, a pushdown automaton, or a Turing machine), and the annotating trace is the state sequence of the accepting path [PSV26]. In the work of Bhattamishra et al. (2026), the traces are more expansive, drawn from the power-set of the vocabulary [BHK26]. More recently, Charikar et al. (2026) abstracted these types of computational traces away from explicit machine models and into the notion of trace colorings: they consider any labeling that assigns a color to each symbol of each string in the language, representing an arbitrary step-by-step annotation of the string [CKP26]. The idea in each of these papers is that when the learner is presented with the annotated version of the string, it can solve the problem of identification in the limit for some class of languages. Charikar et al. (2026) showed that there is a trace coloring scheme using a finite set of colors for which a learner can solve identification in the limit for every countable collection of candidate languages [CKP26]. In terms of the resource requirements of the trace coloring scheme for annotation, one of the key goals is to reduce the number of colors required, so that the annotation can be as compact as possible per symbol. Viewed in these terms, the main result of Charikar et al. (2026) is that there is a trace coloring using k + 1 colors, where k is the size of the underlying alphabet. They also show that for the special case of regular languages, they can improve the resource requirements dramatically, via a trace coloring that uses only two colors. These results leave open several basic questions. First, the bound of k + 1 is strong in one sense, since it is only linear in the alphabet size, but it raises the natural question of whether the number of colors in a trace coloring that supports identification in the limit actually needs to grow with the alphabet size at all. Second, a generally unstated resource constraint for trace coloring is that a color is assigned to each symbol of the string — that is, the annotation works symbol-by-symbol — but in principle we might be able to get away with annotating many fewer of the symbols in the string. The most extreme version of this would be a terminal coloring, which only provides a single annotation at the end of the entire string, and yet still supports identification in the limit.1 The present work: Qualitatively stronger resource bounds. In this paper, we show that dramatically stronger resource bounds are achievable for trace colorings: for any countable collection of languages (where as before we assume all languages are infinite), there is a terminal coloring that uses only two colors and supports identification in the limit. This is best possible in both dimensions discussed above: it uses only two colors, and (as a terminal coloring) it provides only one annotation per string. Essentially, what the result shows is that there is a powerful kind of positive, “non-uniform” counterpart to Gold’s classical impossibility theorem for identification in the limit: if we are allowed to annotate each string in each language with a single one-bit annotation, then identification in the limit becomes possible for every countable collection of infinite languages.2 1 As we discuss further in a later section, we can always convert a trace coloring using ℓ colors per symbol into a terminal coloring by taking the colors applied to each symbol of a string of length n and instead writing it as a single n-tuple of colors that annotates only the end of the string. This is a useful general conversion, but of course it does not fulfill the goal of using a fixed number of colors, since such an encoding requires an unbounded number of colors that grows with the length of the string: there are ℓn possible n-tuples of colors for a string of length n. 2 It is useful to note what is possible for language collections where some of the languages in the collection might be finite sets. What we can do in this case is to apply the terminal coloring to all the infinite languages in the collection, and use a distinct third color to annotate all the strings in all the finite languages. This means that as soon as the third color is seen, the algorithm knows it is working with a finite set, and it can use a standard algorithm to identify this language in the limit (in brief, by always guessing that the language consists of exactly the strings it has seen so far). In this way, a corollary of our main result is that when the collection can include languages of finite size, there is a terminal coloring using only three colors that supports identification in the limit.

3

We develop this result in several steps. First, we observe that there is a relatively direct construction of a terminal coloring with two colors if the colors assigned to a string w ∈ Li can depend not just on the language Li is belongs to but also the other languages Lj in the collection. Theorem 1 (Collection-dependent 2-coloring, see Proposition 4.1). Let C = {L1 , L2 , . . . } be any countable language collection, where every |Li | = ∞. There exists a set of 2-coloring functions {cL }L∈C that makes C identifiable in the limit. The above is a useful stepping-stone to our main result, but it is a much more limited type of a terminal coloring than what we will eventually be seeking, since the colors assigned to the strings in each language L in this first theorem are defined with knowledge of the collection C that L belongs to. We therefore think of this first result as a collection-dependent terminal coloring, since the coloring is defined with reference to the collection of languages. What we will obtain in the next stronger result is a collection-independent way to annotate the strings in each language L — using only knowledge of the single language L — such that when we subsequently assemble a countable collection of languages, the annotations of each language separately allow for identification in the limit. In other words, this collection-independent coloring is an annotation at the level of the language, not at the level of the collection of languages. This stronger definition accords with the intuition from practice, where annotations are generally providing assistance with the language in question, not with the contrast to infinite sets of other counterfactual languages that are not the language in question. The challenge we face in going from collection-dependent coloring of the first theorem to the collection-independent coloring (also with two colors) turns out to be fundamentally set-theoretic in nature. We are considering all possible infinite languages — i.e., all infinite subsets of a countable ground set (which we can take without loss of generality to be the natural numbers) — and we want to 2-color the elements of each in such a way that when we pull together any countable collection of these infinite sets, it is possible to achieve identification in the limit. We show that for this purpose, it is sufficient for the colorings of different subsets to satisfy a set of interdependent requirements that we define in later sections; and we use these requirements as part of a transfinite recursion that iterates through the uncountably many infinite languages and builds the 2-coloring of each language with reference to the 2-colorings that have been inductively defined for all earlier languages. Theorem 2 (Collection-independent 2-coloring, see Theorem 5). Let C be the collection of all infinite subsets of the universe. There exists a set of terminal 2-coloring functions {cL }L∈C , such that any countable subcollection C ′ ⊆ C is identifiable in the limit with terminal colors given by {cL }L∈C ′ . Note crucially how the construction of the coloring functions above is collection-independent: the terminal coloring used by any given language L is the same, regardless of the countable collection C ′ it is considered within. This is in contrast to the coloring functions from Theorem 1, where the terminal coloring used by a language L depends on the collection containing it. The inherently non-constructive nature of bounded terminal colorings. This is of course an extremely non-constructive way to define the terminal coloring, and a basic question that arises is whether this non-constructive aspect is necessary in every terminal 2-coloring — or more generally, in any bounded terminal coloring, where we are constrained to use a fixed number of colors. We show that it is, in a strong sense. First we need make precise what we mean by “constructive” versus “non-constructive” when the object being constructed — a 2-coloring of every infinite subset of the natural numbers — is uncountable in cardinality to begin with. 4

Constructive (Borel) Non-Borel

Collection-dependent 2 colors (Proposition 4.1) 2 colors (implied by Theorem 5)

Collection-independent infinite color set (Theorem 10) (provably necessary due to Theorem 9) 2 colors (Theorem 5)

Table 1: Summary of our results. The entries indicate the number of colors required by terminal coloring functions for language identification. Fortunately, there is a standard notion of constructiveness in this setting, which is based on the concept of a Borel map. A terminal k-coloring is simply a map J that sends infinite subsets L of the natural numbers to infinite strings over the finite alphabet {1, 2, 3, ..., k} (specifying the color assigned to each element of the set L). The standard topology on the domain D (all infinite subsets of the naturals), and the standard topology on the range R (all infinite strings over {1, 2, 3, ..., k}), both define the basic open sets as those sets where membership can be determined from the values on a finite prefix. The Borel sets are then all sets that can be formed from the basic open sets by iterated taking of unions, intersections, and complements (in other words, the σ-algebra generated by the basic open sets). Just as a map is continuous if J −1 (Y ) is open for every open set Y , a map is Borel if J −1 (Y ) is Borel for every Borel set Y . Finally, given that a k-coloring is just a map from the domain to the range as we have defined them, we say that a coloring is Borel if the map specifying it is a Borel map. Experience shows that essentially any function that can be defined using a “simple” or “closed-form” iterative construction is Borel, and all the colorings in previous work in this area are Borel. What we show is that for all finite k, if a terminal k-coloring supports identification in the limit, then it cannot be a Borel coloring. We do this via an infinitary Ramsey-theoretic argument, using the Galvin-Prikry Theorem [GP73]. Theorem 3 (No collection-independent finite Borel coloring, see Theorem 9). Let C be the collection of all infinite subsets of the universe, and let {cJL }L∈C be terminal coloring functions specified by a Borel map J that uses finitely many colors. There exists a countable subcollection C ′ ⊆ C such that C ′ is not identifiable in the limit with terminal colors given by {cJL }L∈C ′ . This is the deep sense in which our main result is a highly non-uniform positive counterpart to Gold’s Theorem: there is a way of annotating every string in every possible infinite language with a single bit (i.e. one of two colors) such that when any countable collection is assembled from these annotated languages, identification in the limit is possible. But every way of performing such an annotation is necessarily highly non-constructive, in that the annotation cannot be accomplished with a Borel map. This also forms a contrast with the earlier result of Charikar et al. (2026), which requires trace (rather than terminal) colorings and an unbounded set of colors (growing with alphabet size): in these quantitative respects, theirs is a weaker result, but it is also constructive in a way that our terminal 2-coloring cannot be.

2

Overview of Techniques

In this section, we give detailed proof sketches for all our main results.

5

2.1

Upper Bounds

Local 2-coloring functions. We start by describing a simple 2-coloring scheme that is collectiondependent, and satisfies the distinguishable coloring condition. Let C be any countable language collection, and suppose all the languages in C are infinite. Our strategy is to enumerate all the pairs in C one by one, and build the terminal coloring functions as we process them. Namely, whenever we encounter a pair (L, L′ ) for which L ⊊ L′ , we designate a special “sentinel” string x ∈ L which will be colored red in L (i.e.., cL (x) = red) but blue in L′ (i.e., cL′ (x) = blue). Furthermore, this sentinel string will be chosen to be longer than any sentinel string chosen so far; such a choice is possible since all languages are infinite, and ensures uniqueness of sentinel strings. Finally, for every language, all the strings that never get chosen as sentinels in this (infinite) process are colored blue. We can readily see that the terminal coloring functions thus constructed satisfy the distinguishable coloring condition; indeed, for any L, L′ ∈ C where L ⊊ L′ , we will have processed this pair at some finite time in the enumeration above, and hence designated some sentinel x ∈ L to be colored red in L but blue in L′ . Global 2-coloring functions. Notice that the 2-coloring functions constructed above are heavily collection-dependent. A string x ∈ L may be colored red if it gets chosen as a sentinel within a collection C, but may be colored blue within a different collection C ′ . We now describe how it is possible to obtain global 2-coloring functions for languages, such that the distinguishable coloring condition is satisfied with the same coloring functions irrespective of the collection in question. Notice that in order for this, it suffices to construct 2-coloring functions for the collection that comprises of all possible languages (i.e., all infinite subsets of the universe), since such a construction guarantees that, for every language L, and every possible proper superset L′ ⊋ L, there is a string x ∈ L that is colored differently in L and L′ . However, the collection of all infinite subsets of the universe is uncountable, which poses challenges in terms of building the coloring functions by enumerating pairs of languages as in the above. Therefore, we have to appeal to a highly non-constructive tool: transfinite recursion. For simplicity, and without loss of generality, assume that the universe is the natural numbers N, and let C be the set of all infinite subsets of N. Even if C is uncountable — i.e., has cardinality c, where c is the cardinality of the continuum —, by the axiom of choice, it is well-ordered, which means, by the well-ordering theorem, that it is order-isomorphic to a unique ordinal having cardinal c. So, consider the smallest ordinal κ having cardinality c. For such a κ, it holds that |α| < |κ| = c for every α < κ; we will crucially exploit this. Since C and κ have the same cardinality, let us put the ordinals α smaller than κ in bijection with the languages in C, i.e., C = {Lα : α < κ}. Since |α| < c for every α < κ, our strategy will be to associate an uncountable family Mα of infinite subsets of Lα with every Lα . The family Mα that we choose will have the special property of being almost-disjoint: namely, any two members of Mα will only have finite intersection. There are various ways in which such an almost-disjoint, uncountable family of infinite subsets of Lα may be built; we briefly describe one ahead; for now, let us assume the existence of such a family for every Lα . We proceed to sketch how we use transfinite recursion to conclude with the desired global 2-coloring functions satisfying the distinguishing coloring condition. For every α < κ, we will carefully choose a member Jα ∈ Mα , with a view to coloring all the elements in Jα as red, and all the elements in L \ Jα blue, and in a way that guarantees that the distinguishing coloring condition is not violated within the subcollection {Lβ }β<α . At a high level, such a choice is made possible since the number of ordinals β < α is at most |α| < |κ| = c, whereas there are uncountably many available candidates in Mα , leaving room for choosing Jα . 6

This is where the choice of κ as the initial ordinal having cardinality c, together with the almostdisjointedness property, is significant. To get a sense of how the almost-disjointedness property helps, consider any β < α for which Lβ ⊊ Lα . Then, in order for the distinguishable coloring condition to be satisfied, we wish for there to be a red-colored string in Lβ that is colored as blue in Lα . That is, we want that Jβ ̸= Jα ∩ Lβ . So, any X ∈ Mα that satisfies X ∩ Lβ = Jβ is invalidated as a candidate for being chosen as Jα . But crucially, since Mα is almost-disjoint, there cannot exist distinct X, Y ∈ Mα that both satisfy this property, since otherwise, Jβ ⊆ X ∩ Y , and |Jβ | = ∞. A similar argument holds in the case where Lβ ⊋ Lα . Thus, every β < α invalidates at most a single member of Mα . Since Mα is uncountable, we can therefore safely choose a Jα ∈ Mα to color red. Finally, we briefly describe one way to construct the required almost-disjoint family. Recall that we wish to construct an uncountable family Mα of infinite subsets of Lα such that every two members of the family have only a finite intersection. We will add a member Lα,r ⊆ Lα to Mα for every unique, infinite bit string r (of which there are uncountably many), where the elements of Lα,r are determined by all the finite prefixes of r. Since any two distinct bit strings r and s can agree on only finitely many prefixes, we can associate prefixes with elements within Lα , and construct the family Mα such that its members are almost-disjoint.

2.2

Lower Bounds

Finite-prefix coloring functions. We start by showing a lower bound for finite-prefix coloring functions, a simple but natural family of global coloring functions. A family of finite-prefix coloring functions is defined with respect to a function f that maps finite subsets of N to the palette, and the terminal coloring function cfL for a language L = {x0 , x1 , . . . } is defined to be cfL (xi ) = f ({x0 , x1 , . . . , xi }). We show that no family of finite-prefix coloring functions with any finite number of colors can globally suffice for language identification. For simplicity, we sketch the argument here for 2 colors; the argument extends naturally to k > 2 colors. First, let us see how finite-prefix 2-coloring functions do not satisfy the distinguishable coloring condition, which is only a sufficient condition for identification; later, we will extend the argument to rule out identification. For this, we must exhibit two infinite subsets A ⊊ B of the natural numbers satisfying that f (A≤x ) = f (B≤x ) for all x ∈ A (where A≤x comprises of all elements in A that are at most x). We attempt to build these sets greedily. That is, we start with E0 = {}, F0 = {1}, and aim to maintain growing set pairs (Ei , Fi ) for which it holds that f (Ei,≤x ) = f (Fi,≤x ) for all x ∈ Ei . Given (Ei , Fi ), we attempt to find a candidate finite set S of numbers strictly larger than all the numbers in Fi , with a view to append S to Fi but only the single element max(S) to Ei , such that the invariant f (Ei ∪ max(S)) = f (Fi ∪ S). is satisfied. If we can keep finding such sets S and grow our set pairs indefinitely, we can set A = ∪i≥0 Ei and B = ∪i≥0 Fi . Otherwise, we would halt at some finite set pair (En , Fn ); however, the halting condition implies that for any finite set S of numbers above all the numbers in Fn , it holds that f (Fn ∪S) ̸= f (En ∪max(S)). In particular, this means that for any number u > max(Fn ), and for any finite set S of numbers larger than max(Fn ) that has max(S) = u, the color f (Fn ∪ S) is pinned down to be either red or blue (i.e., the color not equal to f (En ∪ u)), solely as a function of u. We can thus set A = Fn ∪ C and B = Fn ∪ D for any infinite sets C, D ⊆ N>max Fn , where C ⊊ D. 7

We now extend the argument above to construct a countable collection C ′ for which not only the distinguishable coloring condition, but also identification is precluded. As in the above, we sketch the lower bound for 2 colors. By the characterization for identification with color traces in [CKP26] (see Theorem 4), the lower bound amounts to constructing a collection C ′ that contains a language L, such that for every finite, non-empty subset T ⊆ L, there exists a different language L′ ∈ C ′ for which T ⊆ L′ ⊊ L, and furthermore, f (L′≤x ) = f (L≤x ) for every x ∈ L′ . We will construct C ′ to comprise of a special language B, together with languages Ai for i ∈ N. Towards this, recall the situation above in the lower bound for the distinguishable coloring condition, where we were forced to halt in our infinite construction. Here, we had a finite set G which had the property that, for every u > max(G), and for any finite set S ⊆ N>max(G) satisfying max(S) = u, the color f (G ∪ S) is determined to be either red or blue solely as a function of u (a property that we denote later as “1-coherence”). Namely, if N>max(G) = {z0 , z1 , . . . }, we set B to be G ∪ N>max(G) , and Ai = G ∪ N>max(G) \ {zi }. We can readily see that every Ai ⊊ B, and that for every finite, non-empty T ⊆ B, there exists Ai satisfying T ⊆ Ai ⊊ B; furthermore, for such an Ai , the fact that f (Ai,≤x ) = f (B≤x ) for every x ∈ Ai follows simply from the constraint above on the set G. So, if we have a set G that is 1-coherent, our job is complete. Otherwise, our high-level strategy for constructing B, {Ai }i∈N is as follows: we attempt to construct an increasing sequence of finite sets H0 ⊊ H1 ⊊ . . . in steps. At each step s, we also maintain growing finite approximations of A0 , . . . , As . Denoting by Ai [s] the finite approximation of Ai maintained at step s, we maintain the invariant that for every i, Ai [s] ⊆ Hs , and furthermore, f (Ai [s]≤x ) = f (Hs,≤x ) for every x ∈ Ai [s]. We initialize H0 = A0 [0] = {1}. Then, at each step s, we will attempt to grow exactly one of the finite approximations A0 [s], . . . , As [s] by focusing on some i ≤ s. When we focus on Ai [s], we attempt to find some finite, non-empty set S ⊆ N>max(Hs ) such that, denoting u = max(S), it holds that f (Ai [s] ∪ {u}) = f (Hs ∪ S). If we are able to find such an S, we continue to the next step by setting Hs+1 = Hs ∪ S. We then initialize the finite approximation of As+1 as As+1 [s + 1] = Hs+1 , set Ai [s + 1] = Ai [s] ∪ {u}, and set Aj [s + 1] = Aj [s] for every j ̸= i, s + 1. It is then not too hard to see that if we had inductively maintained the required invariant up until step s, our update rule maintains the invariant at step s + 1. If this construction goes on indefinitely, we will set B = ∪s∈N Hs and Ai = ∪s≥i Ai [s] for every i. Since we want every Ai to eventually become infinite, we choose the index i that we focus on at step s in such a way that every index i gets focused on at infinitely many steps. Suppose then that the construction goes on indefinitely. Note that every Ai ⊊ B, since at infinitely many time steps, it is also the case that we do not focus on Ai . We then claim that for every finite, non-empty T ⊆ B, there exists Ai such that T ⊆ Ai ⊊ B, and furthermore, f (Ai,≤x ) = f (B≤x ) for every x ∈ Ai . Indeed, since B = ∪s∈N Hs , any such T is contained in some Hs , and note that As [s] is initialized to Hs , post which As only grows. Lastly, the property that f (As,≤x ) = f (B≤x ) follows by definition of the way that we extend both As and B. So, in the case that the construction goes on indefinitely, we have the desired lower bound. In the other case where the construction gets stuck at some step s, by definition of getting stuck, we have the property that, for every u > max(Hs ), and for any finite set S ⊆ N>max(Hs ) satisfying max(S) = u, it holds that f (Hs ∪ S) is necessarily not equal to f (Ai [s] ∪ {u}) for the particular i that we were focusing on at step s. In other words, f (Hs ∪ S) is pinned down solely as a function of max(S), which means that Hs is 1-coherent. We can thus fall back on our argument above to construct the required sets B, {Ai }i∈N . 8

Borel coloring functions. We now transfer the identification lower bound for finite-prefix coloring functions above to the much more expressive class of Borel coloring functions over a finite palette. This class includes essentially all natural, constructive notions of coloring functions. For example, the global coloring functions given by [CKP26], when naturally interpreted as terminal coloring functions, are Borel coloring functions (see Theorem 10), albeit over an infinite palette. These coloring functions satisfy the distinguishable coloring condition, and hence suffice for identification. Our lower bound thus shows that the use of an infinite palette by these functions is provably necessary. Moreover, this lower bound gives further evidence for the non-constructive nature of the transfinite-recursion based 2-coloring functions from our upper bounds above. To show a lower bound for Borel coloring functions, we show how we can translate a global family of Borel coloring functions that satisfy the characterizing condition of Theorem 4 to a global family of finite-prefix coloring functions satisfying this condition. This contradicts our lower bound above for finite-prefix coloring functions. At the core of our reduction is an application of the celebrated Ramsay-theoretic theorem of Galvin and Prikry [GP73], which shows that all Borel sets are Ramsay. We use this theorem, together with the assumption that the coloring function is Borel, to inductively construct an infinite subsequence of the natural numbers (Lemma 5.3), over which the application of the Borel coloring function behaves like a finite-prefix coloring function over a finite palette. Concretely, having constructed a finite portion of the required subsequence so far, we recursively thin the remaining tail of the subsequence, such that the application of the Borel map on any subsequence of the tail is color-homogenized. This recursive thinning/color homogenization is made possible by the Galvin-Prikry theorem. Once we have constructed this sequence, it is only a matter of identifying the entire domain of the natural numbers with this subsequence, which lets us transfer the tell-tales and coloring discrepancies as required by the characterizing condition of Theorem 4 from the Borel coloring function to the derived finite-prefix coloring function. This shows that the derived finite-prefix coloring function suffices for identifying every countable collection — a contradiction to the lower bound above. With this overview, we now proceed to formally establishing all the details of our results.

3

Preliminaries

A language in this paper is a subset of Σ∗ for a finite alphabet set Σ. Without loss of generality (i.e., by considering any suitable bijection), we will identify Σ∗ by the set of natural numbers N = {0, 1, 2, . . . }. A language L is then simply a subset of N, and a language collection is a (multi)set of subsets of N. Ordinal numbers will feature abundantly in our discussion; following convention, we will generally denote these by Greek alphabets. We will use the von Neumann definition of ordinal numbers: a set α is an ordinal, if and only if every element of α is a subset of α, and furthermore, α is (strictly) well-ordered by set-membership (∈). Namely, every non-empty subset β ⊆ α has a unique least element a such that a < b (i.e., a ∈ b) for every b ∈ β \ {a}. Observe that any ordinal α may be equivalently defined as α = {γ : γ < α}. For example, finite ordinals corresponding to the natural numbers are constructed as 0 = {}, 1 = {0}, 2 = {0, 1}, and so on. The first infinite ordinal ω consists of all the finite ordinals, and is hence equivalent to the set N = {0, 1, 2, . . . }. Thereafter, ω + 1 = {0, 1, 2, . . . , ω}, and so on. The central notion that an ordinal captures is its unique order type — informally, this is the shape of the order. For example, 2 has the shape 0 < 1, ω has the shape 0 < 1 < . . . with no largest

9

element, ω + 1 has the shape 0 < 1 < · · · < ω with ω being the largest element — each of these shapes are different. The cardinality of a set S, denoted |S|, is its size. Two sets S and S ′ have the same cardinality if there exists a bijection between them. For example, observe that |ω| = |ω + 1|. We will denote the cardinality of the set of real numbers R by c. In this paper, we will assume the Axiom of Choice. The axiom of choice is equivalent to the Well-ordering Theorem, which asserts that every set can be well-ordered. It is known that every well-ordered set (S, <) is order-isomorphic to a unique ordinal number α, meaning that there exists a bijection f between S and α, such that for any a, b ∈ S, a < b ⇐⇒ f (a) ∈ f (b). A terminal k-coloring function c maps N to P , where P is a palette of k colors. The following characterization of identification in the limit with terminal color traces essentially follows from Theorem 1 in [CKP26] — while the result in [CKP26] is stated for trace coloring functions, the argument for terminal coloring functions is identical. Theorem 4 (Characterization of Identification with Terminal Color Traces, essentially [CKP26]). Let C be a countable language collection. Then, C is identifiable in the limit with a terminal color trace given by the terminal coloring functions {cL }L∈C if and only if for every language L ∈ C, there exists a finite “tell-tale” subset TL ⊆ L, such that for every language L′ ∈ C that is a proper subset of L, either (1) L′ does not contain TL , or (2) there exists x ∈ L′ such that cL′ (x) ̸= cL (x). The condition (2) in the characterization above, which is a sufficient condition for identification with colors traces, is denoted in [CKP26] as the distinguishable coloring condition. Distinguishable coloring condition. A set of terminal k-coloring functions {cL }L∈C for a collection C = {L1 , L2 , . . . } satisfies the “distinguishable coloring condition” if for every L, L′ ∈ C satisfying L′ ⊊ L, there exists x ∈ L′ for which cL′ (x) ̸= cL (x).

4

Collection-independent 2-coloring

The simple proposition ahead shows, for every countable language collection, the existence of collection-dependent 2-coloring functions that satisfy the distinguishable coloring condition. Proposition 4.1. Let C = {L1 , L2 , . . . } be any countable language collection, where every |Li | = ∞. There exists a set of terminal 2-coloring functions {cL }L∈C that satisfies the distinguishable coloring condition, and hence makes C identifiable in the limit. Proof. Let us enumerate all the pairs (Li , Lj ) where i < j as (Li1 , Lj1 ), (Li2 , Lj2 ), . . . . We will initialize a size variable s0 = 1, and process these pairs in order. At step n (where n = 1, 2, . . . ), we will first check if either Lin ⊊ Ljn or Ljn ⊊ Lin ; if so, assume without loss of generality that Lin ⊊ Ljn . We will now find a string xn ∈ Lin that has size at least sn−1 , and mark this string as “special”. Such a special string necessarily exists in Lin since we assume every language is infinite, and the alphabet is finite. Then, we set cLin (xn ) = red, cLjn (xn ) = blue, and update sn = |xn | + 1. Otherwise, if neither Lin ⊊ Ljn nor Ljn ⊊ Lin , we set sn = sn−1 , and proceed to the next pair. For every language L ∈ C, and for every x ∈ Σ∗ that was never chosen to be special at any time in the process above, we set cL (x) = blue. This completes the specification of the terminal 2-coloring functions {cL }L∈C . Observe that since we always strictly increase the size of special strings, a string xn chosen to be special at step n is never chosen to be special at any other step. Thus, at no point do we ever overwrite colors.

10

It remains to argue that the distinguishable coloring condition is satisfied. Fix any L, L′ ∈ C satisfying L ⊊ L′ . These languages must exist as some pair (Lin , Ljn ) in our enumeration above; assume without loss of generality that Lin = L, Ljn = L′ . Then, the construction above would have found a special xn ∈ Lin and set cLin (xn ) = red, cLjn (xn ) = blue. Because we never overwrite colors, these are the final colors assigned to xn by cLin and cLjn . Thus, the distinguishable coloring condition is satisfied. Remark 1 (Finite Languages I). If the collection C also comprises of finite languages, the argument above is easily modified to work with 3 colors. Let C1 comprise of all the finite languages in C, and let C2 = C \C1 comprise of all the infinite languages. Since C is countable, both C1 and C2 are countable. We construct terminal coloring functions {cL }L∈C2 that use the colors red and blue, and satisfy the distinguishable coloring condition within C2 , as in the above. For the finite languages in C1 , we use terminal coloring functions {cL }L∈C1 that are constant functions mapping to the color green. In this case, if the input comprises of either red or blue traces, the learning algorithm knows that the target language is in C2 , and hence operates only within C2 ; since the traces satisfy the distinguishable coloring condition within C2 , identification is successful. Otherwise, if the terminal traces are green, the target language is determined to be a finite language from C1 . Since all languages in C1 are finite, the collection is identifiable [Gol67]. In particular, the input will eventually comprise of all the finitely many strings from the target language, and hence the algorithm can simply output the language in C1 that is equal to the observed set of strings. The terminal 2-coloring function cL for a language L above depends on the specific collection C that the language L is considered within. One can ask: does there exist a universal terminal 2-coloring function cL that can be used for language L uniformly across all countable collections C that contain L? This amounts to asking: does there exist a set of terminal 2-coloring functions {cL }L∈C that satisfies the distinguishable coloring condition, where C contains all infinite subsets of Σ∗ ? Theorem 5. Let C be the collection of all infinite subsets of N. There exists a set of terminal 2-coloring functions {cL }L∈C that satisfies the distinguishable coloring condition. Proof. Since the set of all infinite subsets of N is uncountable, note that |C| = c, where c is the cardinality of the continuum. By the well-ordering theorem, C can be well-ordered. This implies that C is order-isomorphic to a unique ordinal having cardinality c. Let κ be the initial ordinal having this cardinality. That is, |κ| = c, and furthermore |α| < |κ| for every ordinal α < κ. Since C and κ have the same cardinality, choose a bijection e : κ → C, where we define Lα := e(α) for every α < κ. We thus have that C = {Lα : α < κ}.

(1)

We will now associate every language Lα with a family of infinite subsets of it, where this family will have size c. Furthermore, the family will be almost-disjoint, meaning that any two members within it have a finite intersection. These two properties will ensure the existence of at least a single infinite subset within the family, such that if the terminal coloring function cLα colors all the elements of this subset red, and all the rest of the elements of Lα blue, the distinguishable coloring condition is satisfied. Towards building such families for every Lα , let us begin with a building block. Let Z denote the set of all infinite bit strings; note that |Z| = c. Additionally, fix any bijection b that maps the set of all finite bit strings to N. Then, for any infinite bit string r ∈ Z, define Mr to comprise of

11

all b(r≤i ) values for i ≥ 0, where r≤i is the finite prefix r0 , . . . , ri of r. Concretely, Mr := {b(r≤i ) : i ≥ 0}.

(2)

Note that |Mr | = |ω|. We now claim that |Mr ∩ Ms | < ∞ for any r ̸= s. To see this, fix some r ̸= s, and let i ≥ 0 be the leftmost index at which ri ̸= si . Then, observe that for any j ≥ i, r≤j ̸= s≤j , and hence r≤j ∈ / Ms , s≤j ∈ / Mr . Thus, |Mr ∩ Ms | = |{b(r≤j ) : j < i}| < ∞ as desired. Now fix any α < κ, and let Lα = {ℓα0 < ℓα1 < . . . } under the usual ordering of the natural numbers. Since |Lα | = |ω|, consider the bijection πα mapping ω to Lα , where πα (n) = ℓαn ,

n ≥ 0.

Then, for each r ∈ Z, define Lα,r := πα (Mr ) = {πα (n) : n ∈ Mr } = {ℓαn : n ∈ Mr }, where Mr is as defined above. Observe that |Lα,r | = |Mr | = |ω| and Lα,r ⊆ Lα ; furthermore, for any r ̸= s, |Lα,r ∩ Lα,s | = |{ℓαn : n ∈ Mr ∩ Ms }| < ∞, which also implies that every Lα,r is distinct. So, we define the family Mα as Mα = {Lα,r : r ∈ Z}. Since |Z| = c, we have that |Mα | = c. We will now use transfinite recursion to define a sequence {Jα }α<κ , where every Jα ∈ Mα , Jα ̸= ∅, and for every β < α, if Lβ ⊊ Lα , then Jα ∩ Lβ ̸= Jβ , and if Lβ ⊋ Lα , then Jβ ∩ Lα ̸= Jα . As the base case, define J0 to be an arbitrary element of M0 . Now fix any ordinal α < κ. and assume that Jβ satisfying the required condition for every β < α has been defined. We will now specify how Jα is defined. For every β < α, define a subfamily Fα,β ⊆ Mα of forbidden candidates as follows. Case 1: Lβ ⊊ Lα .

In this case, define Fα,β = {X : X ∈ Mα , X ∩ Lβ = Jβ }.

We claim that |Fα,β | ≤ 1. To see this, suppose X, Y ∈ Fα,β and X ̸= Y . Then, X ∩ Lβ = Jβ , and also, Y ∩ Lβ = Jβ . This implies that Jβ ⊆ X ∩ Y , meaning that |X ∩ Y | = ∞, which contradicts that the members of Mα are almost-disjoint. Case 2: Lβ ⊋ Lα .

In this case, define Fα,β = {X : X ∈ Mα , Jβ ∩ Lα = X}.

Note again that |Fα,β | ≤ 1, since Jβ ∩ Lα is some fixed set, and depending on whether it exists in Mα , Fα,β is either empty or singleton.

12

Case 3: Neither Lβ ⊊ Lα nor Lβ ⊋ Lα . In this case, define Fα,β = ∅. In all cases, it holds that |Fα,β | ≤ 1. Now define Fα :=

[

Fα,β .

β<α

We claim that |Fα | < |Mα |. Indeed, recall that |Mα | = c; furthermore, |α| < |κ| = c, since κ was chosen to be the initial ordinal having cardinality equal to c. Since every |Fα,β | ≤ 1, we get that |Fα | ≤ |α| < c = |Mα |. But since Fα ⊆ Mα , this implies that Mα \ Fα ̸= ∅. So, define Jα to be an arbitrary element from Mα \ Fα . Then, Jα ∈ Mα , Jα ̸= ∅. Furthermore, for every β < α, if Lβ ⊊ Lα , then we fall under Case 1 above, wherein any X ∈ Mα which satisfies X ∩ Lβ = Jβ would have been excluded as a candidate for Jα , ensuring that Jα ∩ Lβ ̸= Jβ . If Lβ ⊋ Lα , we fall under Case 2 above, wherein any X ∈ Mα that satisfies Jβ ∩ Lα = X would have been excluded as a candidate for Jα , ensuring that Jβ ∩ Lα ̸= Jα . Thus, Jα satisfies all the required conditions. By transfinite recursion, the sequence {Jα }α<κ is thus well-defined. Now, let α, β be any distinct ordinals. Since the ordinals are totally ordered by membership, either α < β or β < α. Thus, our construction above ensures that for any distinct ordinals α, β, if Lα ⊊ Lβ , it holds that Jβ ∩ Lα ̸= Jα . We now specify the terminal coloring functions. Recall from (1) above that the languages Lα for α < κ uniquely range over all of C. Then, for every α < κ, define ( red x ∈ Jα , cLα (x) = (3) blue otherwise. It remains to argue that these terminal coloring functions satisfy the distinguishable coloring condition. Fix any ordinals α, β where Lα ⊊ Lβ . We must show that there exists x ∈ Lα for which cLα (x) ̸= cLβ (x). Indeed, by our reasoning above, it holds that Jβ ∩ Lα ̸= Jα . This implies either the existence of some x ∈ Jα which does not belong to Jβ ∩ Lα , or the existence of some x ∈ Jβ ∩ Lα which does not belong to Jα . In the former case, since Jα ⊆ Lα , such an x satisfies that x ∈ / Jβ , meaning that cLα (x) = red, cLβ (x) = blue. In the latter case too, we obtain an x ∈ Lα satisfying x ∈ Jβ and x ∈ / Jα , meaning that cLα (x) = blue, cLβ (x) = red. Thus, in either case, we ensure the existence of an x ∈ Lα that satisfies cLα (x) ̸= cLβ (x), and the proof is complete. Remark 2 (Finite Languages II). As in Remark 1, we can extend C to also include all finite subsets of N, and construct collection-independent terminal coloring functions using 3 colors. For this, we can have C1 comprise of all the finite languages in C, and C2 = C \ C1 comprise of all the infinite languages. C2 is uncountable, whereas C1 is countable, since the collection of all finite finite subsets of N is countable. For C1 , we use terminal coloring functions {cL }L∈C1 that are constant functions mapping to the color green, and for C2 , we use the terminal coloring functions {cL }L∈C2 as given by the transfinite recursion argument above.

5

No collection-independent Borel finite-colorings

The terminal 2-coloring functions from the section above arise from a transfinite recursion argument. One can ask: is there a more constructive procedure for collection-independent 2-coloring functions? As a simpler target, how about a constructive procedure for k-coloring functions, for some finite k? Recall that the terminal coloring functions arising from the trace coloring functions in [CKP26] are collection-independent and constructive, but use infinitely many colors. 13

5.1

Finite-prefix coloring functions

As a starting point for “simple”, constructive but collection-independent terminal coloring functions, we begin by considering the family of finite-prefix coloring functions. Recall that we assume, without loss of generality, that a language L = {x0 , x1 , . . . , } is an infinite subset of N, listed in the natural increasing order of N. A finite-prefix coloring function cL assigns a color to xi solely as a function of {x0 , . . . , xi }. Definition 1 (Finite-prefix coloring functions). Let C be the collection of all infinite subsets of N, where every language L ∈ C is enumerated in its natural increasing order. A family of finite-prefix coloring functions {cfL }L∈C is specified by a function f that maps finite (ordered) subsets of N to the palette P , and which satisfies that, for any language L = {x0 , x1 , . . . } in its increasing enumeration, cfL (xi ) = f ({x0 , x1 , . . . , xi }). We will show that finite-prefix coloring functions, that are allowed to use an arbitrarily large but finite palette size, do not suffice globally for language identification. Namely, we can construct a collection, where it is impossible to identify the target language even with terminal colors given by the coloring functions. As a warm-up, we will first show that, for any given family of finite-prefix coloring functions that use a palette of size k, there exists a countable collection that does not satisfy the distinguishable coloring condition (recall, the distinguishable coloring condition is only a sufficient condition for language identification). We will later strengthen this argument to show that there exists a countable collection for which identification is impossible. Theorem 6. Let C be the collection of all infinite subsets of N, and let {cfL }L∈C be any family of finite-prefix coloring functions specified by the function f , and mapping to a finite palette P . There exists a countable collection C ′ such that {cfL }L∈C ′ does not satisfy the distinguishable coloring condition. In order to prove the theorem above, we will define the notion of a “t-coherent set”. For a set X ⊆ N, let X>a (respectively X<a ) denote all the natural numbers in X that are greater (respectively lesser) than a. For any finite G ⊆ N, let max(G) denote the largest number in G, with the convention that max(∅) = −1. Definition 2 (t-coherent set). Let G ⊆ N be a finite set with g = max(G). For any t ≥ 1, we say that G is t-coherent with respect to the function f if for every u > g, there exists a subset Pu ⊆ P of the palette of size at most t, such that for every finite S ⊆ N>g having max(S) = u, it holds that f (G ∪ S) ∈ Pu . In words, if we append finitely many elements to G, then the evaluation of f on the resulting set belongs to a set of t colors, where this set depends only on the largest element appended to G. We will use the convention that no set is 0-coherent with respect to f . Note that in order to prove Theorem 6, it suffices to construct two infinite sets A, B satisfying A ⊊ B, such that for every x ∈ A, cfA (x) = cfB (x); by the definition of finite-prefix coloring functions, this follows if f (A≤x ) = f (B≤x ) for every x ∈ A. We will now prove the following lemma by induction on the palette size. Lemma 5.1. Let G ⊆ N be a finite set, and suppose that G is t-coherent with respect to the function f , for t ≥ 1. Then, at least one of the following is true: (1) there exist infinite subsets A and B of N satisfying A ⊊ B such that f (A≤x ) = f (B≤x ) for every x ∈ A, (2) there exists finite G′ ⊇ G such that G′ is (t − 1)-coherent with respect to f . 14

Theorem 6 follows from the lemma above, since for any finite-prefix coloring functions specified by a function f , and that use a finite palette P of size k ≥ 1, it holds that every finite subset of N is k-coherent with respect to f , together with our convention that no finite set is 0-coherent with respect to f . Proof of Lemma 5.1. We will prove the lemma by induction on t. For the base case, let t = 1, and suppose that G is 1-coherent with respect to f . We will construct infinite sets A, B satisfying A ⊊ B such that f (A≤x ) = f (B≤x ) for every x ∈ A. Let g = max(G), and let C and D be any infinite subsets of N>g satisfying C ⊊ D. We will set A = G∪C and B = G∪D. It remains to argue that f (A≤x ) = f (B≤x ) for every x ∈ A. If x ∈ G, then A≤x = B≤x = G≤x , and the desired equality holds. Otherwise, x ∈ C, meaning also that x > g. In this case, defining S1 := C≤x and S2 := D≤x , we have that A≤x = G∪S1 and B≤x = G∪S2 , and furthermore, max(S1 ) = max(S2 ) = x. Then, by definition of G being 1-coherent, there exists a single color cx such that f (G ∪ S1 ) = f (G ∪ S2 ) = cx ; this immediately gives that f (A≤x ) = f (B≤x ) as desired. Suppose now that t > 1, and the lemma holds for all t′ < t. Let G be the given set that is t-coherent with respect to f , and let g = max(G). Set E0 = G, and F0 = G ∪ {g + 1}. Starting with (E0 , F0 ), we will attempt to construct an infinite chain (E0 , F0 ) → (E1 , F1 ) → . . . , where every Ei , Fi is finite, Ei ⊊ Ei+1 , Fi ⊊ Fi+1 , Ei ⊊ Fi , and furthermore, for any x ∈ Ei , it holds that f (Ei,≤x ) = f (Fi,≤x ). Observe first that (E0 , F0 ) already satisfies that E0 ⊊ F0 , and also that f (E0,≤x ) = f (F0,≤x ) for every x ∈ E0 . Now suppose that (Ei , Fi ) has been built, and let h = max(Fi ). Let S ⊆ N>h be any non-empty, finite set, for which, denoting max(S) = u, it holds that f (Ei ∪ {u}) = f (Fi ∪ S).

(4)

If such a set S exists, we set Ei+1 = Ei ∪ {u}, and Fi+1 = Fi ∪ S. Then, consider any x ∈ Ei+1 ; if x ∈ Ei , Ei+1,≤x = Ei,≤x and Fi+1,≤x = Fi,≤x , and f (Ei+1,≤x ) = f (Fi+1,≤x ) simply because f (Ei,≤x ) = f (Fi,≤x ). Otherwise, x = u; in this case, by construction Ei+1,≤x = Ei ∪ {u} and Fi+1,≤x = Fi ∪ S, and hence, f (Ei+1,≤x ) = f (Fi+1,≤x ) by (4). The other requirements, namely Ei ⊊ Ei+1 , Fi ⊊ Fi+1 and Ei+1 ⊊ Fi+1 , can also be readily verified. Now suppose that we are able to construct an infinite chain of (Ei , Fi ). In this case, we set A = ∪i≥0 Ei , B = ∪i≥0 Fi . Note that A and B thus constructed are both infinite sets, and satisfy that A ⊊ B. This is because the initial element g + 1 ∈ F0 \ E0 belongs to B, and is never later added to any Ei , since all later additions to Ei are above max(F0 ) = g + 1. Furthermore, any x ∈ A belongs to some Ei , and A≤x = Ei,≤x , B≤x = Fi,≤x , which also means that f (A≤x ) = f (B≤x ) by construction. Thus, in this case, the inductive step holds because we satisfy (1) in the lemma statement. Otherwise, the construction of the chain stops at (En , Fn ) for some finite n. Let h = max(Fn ); by definition of stopping, it must be the case that for every finite S ⊆ N>h , where we denote max(S) = u, it holds that f (Fn ∪ S) ̸= f (En ∪ {u}).

(5)

But now observe that Fn ∪ S = G ∪ T1 and En ∪ {u} = G ∪ T2 for some finite sets T1 , T2 ⊆ N>max(G) , which satisfy that max(T1 ) = max(T2 ) = u. Since G is t-coherent with respect to f , this means that both f (Fn ∪ S) and f (En ∪ {u}), belong to some palette Pu , where |Pu | ≤ t. Since f (Fn ∪ S) ̸= f (En ∪ {u}), we conclude that, for every u > h = max(Fn ), and for every finite S ⊆ N>h that satisfies that max(S) = u, f (Fn ∪ S) ∈ Pu′ , where |Pu′ | ≤ t − 1. Thus, setting G′ = Fn ⊇ G renders that G′ is (t − 1)-coherent with respect to f ; the induction is therefore complete. 15

Building up on the lower bound proof above, we will now show that for any given family of finite-prefix coloring functions that use a palette of size k, there exists a countable collection for which identification is impossible. Theorem 7. Let C be the collection of all infinite subsets of N, and let {cfL }L∈C be any family of finite-prefix coloring functions specified by the function f , and mapping to a finite palette P . There exists a countable collection C ′ such that C ′ is not identifiable in the limit with terminal color traces given by {cfL }L∈C ′ . By the characterizing condition in Theorem 4, it suffices to construct a countable collection C ′ which contains a language L, such that for any finite, non-empty subset T ⊆ L, there exists a different language L′ ∈ C ′ such that T ⊆ L′ ⊊ L, and furthermore, f (L′≤x ) = f (L≤x ) for every x ∈ L′ . Using our convention that every finite subset of N is k-coherent with respect to f when f uses a palette of size k, it suffices to prove the following lemma to establish Theorem 7. Lemma 5.2. Let G ⊆ N be a finite set, and suppose that G is t-coherent with respect to the function f , for t ≥ 1. Then, at least one of the following is true: (1) there exist infinite sets B, {Ai }i∈N that are subsets of N, such that for every finite, non-empty T ⊆ B, there exists i ∈ N such that T ⊆ Ai ⊊ B, and f (Ai,≤x ) = f (B≤x ) for every x ∈ Ai , (2) there exists finite G′ ⊇ G such that G′ is (t − 1)-coherent with respect to f . Proof. We will prove the lemma by induction on t. For the base case, let t = 1, and suppose that G is 1-coherent with respect to f . We will construct infinite sets B, {Ai }i∈N such that for every finite, non-empty T ⊆ B, there exists i ∈ N such that T ⊆ Ai ⊊ B and f (Ai,≤x ) = f (B≤x ) for every x ∈ Ai . Let g = max(G), and let D = {z0 < z1 < . . . } be any infinite subset of N>g . We will set B = G∪D, and Ai = G∪(D\{zi }). Fix any finite, non-empty T ⊆ B, and let s = max(T ). Consider any Ai , where zi > s; it is clear that T ⊆ Ai ⊊ B. It remains to argue that f (Ai,≤x ) = f (B≤x ) for every x ∈ Ai . If x ∈ G, then Ai,≤x = B≤x = G≤x , and the desired equality holds. Otherwise, x ∈ D \ {zi }, meaning also that x > g. In this case, defining S1 := (D \ {zi })≤x and S2 := D≤x , we have that Ai,≤x = G ∪ S1 and B≤x = G ∪ S2 , and furthermore, max(S1 ) = max(S2 ) = x. Then, by definition of G being 1-coherent, there exists a single color cx such that f (G ∪ S1 ) = f (G ∪ S2 ) = cx ; this immediately gives that f (Ai,≤x ) = f (B≤x ) as desired. Suppose now that t > 1, and the lemma holds for all t′ < t. Let G be the given set that is t-coherent with respect to f , and let g = max(G). We will attempt to construct an infinite chain of finite sets H0 ⊊ H1 ⊊ H2 · · · , starting with H0 = G. At step s, we will also maintain a family of finite sets Ai [s] for every i ≤ s. These sets will satisfy that: Ai [s] ⊆ Hs , and f (Ai [s]≤x ) = f (Hs,≤x ) for every x ∈ Ai [s], and for every i ≤ s.

(6)

The sets Ai [s] for s ≥ i are intended to be increasing finite approximations of the set Ai . We will incrementally S build up the sets Hs and Ai [s] for i ≤ s; if this process continues indefinitely, we will set Ai = s≥i Ai [s] for every i. At each step of the construction, we will focus on a particular Ai , and append an element to it; since we want each Ai to be infinite, we will have to focus on every Ai infinitely often. One way to do this is the following: at step s, focus on i = d(s), where d(s) is the element at index s in the sequence 0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4, . . . We begin by initializing H0 = G, A0 [0] = G. Note that property (6) is immediately satisfied for this initialization. Now suppose that Hs , Ai [s] for i ≤ s satisfying (6) have been built. Consider 16

the sets Ad(s) [s] and Hs , and let h = max(Hs ). Let S ⊆ N>h be any finite, non-empty set, for which, denoting max(S) = u, it holds that f (Ad(s) [s] ∪ {u}) = f (Hs ∪ S).

(7)

If such a set S exists, we will continue the construction as follows: we set Hs+1 = Hs ∪ S and As+1 [s + 1] = Hs+1 . For i < s + 1 where i ̸= d(s), we set Ai [s + 1] = Ai [s]. Finally, for i = d(s), we set Ai [s + 1] = Ai [s] ∪ {u}. Note that since As+1 [s + 1] = Hs+1 , the property (6) for i = s + 1 is immediately satisfied. Now consider i = d(s), for which Ai [s + 1] = Ai [s] ∪ {u}. Recall also that Hs+1 = Hs ∪ S, where S ⊆ N>max(Hs ) . Then, Ai [s + 1] ⊆ Hs+1 ; additionally, for any x ∈ Ai [s + 1], where x ̸= u, we have that f (Ai [s + 1]≤x ) = f (Ai [s]≤x ), which, by assumption, is equal to f (Hs,≤x ), which is furthermore equal to f (Hs+1,≤x ). As for x = u, we also have, by (7), that f (Ai [s + 1]≤x ) = f (Ai [s] ∪ {u}) = f (Hs ∪ S) = f (Hs+1,≤x ). Thus, property (6) holds for i = d(s). Finally, for i ̸= d(s), i ̸= s + 1, since Ai [s + 1] = Ai [s], and elements added to Hs are all above max(Hs ), property (6) holds simply by the previously maintained invariant. Thus, the construction validly proceeds forward. S Now consider the case that the construction goes on indefinitely. Then, we will set B = s∈N Hs , S and Ai = s≥i Ai [s]. Since at each step of the construction, we append at least an element to Hs , we have that B is infinite. Furthermore, since for every i, d(s) = i for infinitely many s, and we append an element to Ai [s] at each such s, we also have that Ai is infinite. We now argue that Ai ⊊ B for every i; to see this, observe that at infinitely many steps s of the construction, we do not focus on Ai . At each such step, we append an element to Hs (and hence to B), which can never later be added to Ai , since all later additions to Ai are larger than max(Hs ); thus, Ai ⊊ B. Now fix any finite, non-empty T ⊆ B. By construction, any such T must be contained in Hs for some s ≥ 0. Now recall that As [s] is initialized to Hs , and thereafter, As only grows. Thus, T ⊆ As ⊊ B. It remains to argue that for every x ∈ As , f (As,≤x ) = f (B≤x ). Observe that by virtue of the initialization As [s] = Hs , and the fact that every subsequent element added to both As and B is larger than max(Hs ), the desired equality holds for every x ∈ Hs . Now consider any element x > max(Hs ) in As — this element must have been added to As at some stage q, for which d(q) = s. Simultaneously, we would have incorporated a set S into B, where max(S) = x, and formed Hq+1 = Hq ∪ S. All subsequent additions to both As and B are entirely above x. Therefore, by the invariant maintained in (7), it is ensured that f (As,≤x ) = f (As [q] ∪ {x}) = f (Hq ∪ S) = f (B≤x ) as desired. We have thus argued that if the construction above goes on indefinitely, the inductive step in the proof of the lemma holds. Otherwise, the construction stops at some finite step s, by which time we will have built some finite set Hs ; let h = max(Hs ). Since the construction stopped, it must be the case that for any finite, non-empty S ⊆ N>h , denoting u = max(S), it holds that f (Ad(s) [s] ∪ {u}) ̸= f (Hs ∪ S). But now, observe that Ad(s) [s] ∪ {u} = G ∪ F1 and Hs ∪ S = G ∪ F2 for some finite sets F1 , F2 that satisfy max(F1 ) = max(F2 ) = u. Since G is t-coherent with respect to f , we have that both f (Ad(s) [s] ∪ {u}) and f (Hs ∪ S) belong to some common palette Pu , where |Pu | ≤ t. But since f (Ad(s) [s] ∪ {u}) ̸= f (Hs ∪ S), we conclude that for every u > h = max(Hs ), and for every finite S ⊆ N>h satisfying max(S) = u, it holds that f (Hs ∪ S) ∈ Pu′ , where |Pu′ | ≤ t − 1. Thus, we can set G′ = Hs ⊇ G, which renders G′ to be (t − 1)-coherent with respect to f , completing the inductive proof of the lemma.

17

5.2

Borel coloring functions

We now significantly generalize the class of coloring functions from finite-prefix coloring functions to Borel coloring functions. We will first precisely define the notion of Borel coloring functions that we consider. Let S be any discrete (finite or countably infinite) set, and let ZS denote the set of infinite strings whose characters belong to S, i.e., ZS = {(z0 , z1 , . . . ) : zi ∈ S ∀i ∈ N}. We will consider the standard product topology over ZS , where the basic open sets are given by finite prefixes p = (p0 , . . . , pn−1 ) ∈ S ∗ : Op = {X ∈ ZS : X0 = p0 , . . . , Xn−1 = pn−1 }.

(8)

That is, the open set Op comprises of all the strings in ZS that begin with p. Then, the Borel subsets of ZS are the elements of the σ-algebra generated by the open sets Op — namely, the smallest collection of subsets of ZS , which contains all the basic open sets Op for every p ∈ S ∗ , and is closed under complements, countable unions and countable intersections. We will now introduce some additional notation: for any S ⊆ N, where |S| = |ω|, let [S]ω = {L ⊆ S : |L| = |ω|}. Similar to the above, we will consider the standard product topology over [S]ω , whose basic open sets are given by the sets {x0 < x1 < · · · ∈ [S]ω | x0 = p0 , . . . , xn−1 = pn−1 }

(9)

for every finite prefix p0 < · · · < pn−1 . The Borel subsets of [S]ω are then the elements of the σ-algebra generated by these open sets. Note that a language is an element of [N]ω . We will be concerned with coloring functions that map the strings in a language to a sequence of colors in a “Borel” manner, i.e., as given by a Borel map J mapping [N]ω to ZP , where P is a finite palette having size k; for convenience, we will assume P = {1, 2, . . . , k}. That is, J has the property that J −1 (Y ) is Borel subset of [N]ω , for every Borel subset Y ⊆ ZP . We now formally define the family of Borel coloring functions: Definition 3 (Borel coloring functions). Let C = [N]ω . A family of Borel coloring functions {cJL }L∈C is specified by a Borel map J : [N]ω → ZP , which satisfies that, for any language L = {x0 < x1 < . . . }, cJL (xi ) = J(L)i . We will show that Borel coloring functions that use a finite palette do not suffice for identification. A key tool that we will use is the following famous result by Galvin and Prikry [GP73] which shows that every Borel set is Ramsey.3 Theorem 8 (Galvin-Prikry [GP73]). Let Z ∈ [N]ω , and let R ⊆ [Z]ω be a Borel subset of [Z]ω . Then, there exists Y ∈ [Z]ω such that either [Y ]ω ⊆ R or [Y ]ω ∩ R = ∅. We now show the following canonicalization lemma, which uses the Galvin-Prikry theorem above, and shows that Borel coloring functions, when restricted to particular languages in [N]ω , behave like finite-prefix coloring functions. 3

The result in [GP73] is originally stated for Z = N; the form that we state follows simply by identifying every element in N with an element in Z.

18

Lemma 5.3 (Canonicalization Lemma). Let C be the collection of all infinite subsets of N, and let {cJL }L∈C be a family of Borel coloring functions specified by a Borel map J over a finite palette P . There exists an infinite set X = {x0 < x1 < . . . } ∈ [N]ω and a finite-prefix function f that maps finite, non-empty subsets of X to the palette P , such that for every finite, non-empty S ⊆ X, where S = {xi0 < · · · < xim }, and every infinite tail T ∈ [X>xim ]ω , it holds that J(S ∪ T )m = f (S). In words, the lemma above identifies a special subsequence in [N]ω , such that, if we take take any finite subset S of the subsequence, and then append it with an infinite tail T above S, then the color assigned by the Borel coloring function J (which acts on all of S ∪ T ) to the largest member of S is independent of the tail T , and is specified completely by a finite-prefix function acting only on the set S. Proof. We will specify the elements of the set X inductively. At step n of the process, suppose we have constructed Xn = {x0 < x1 < · · · < xn−1 } and a “tail reservoir” Zn ∈ [N>xn−1 ]ω , such that for every non-empty subset S = {xi0 < · · · < xim } ⊆ Xn , f (S) has been defined, and satisfies that, for every infinite tail T ∈ [Zn ]ω , J(S ∪ T )m = f (S). For the base case n = 0, we simply have that X0 = {}, Z0 = N, and the claim holds vacuously, since there are no non-empty subsets of X0 . Now suppose that we have constructed Xn , Zn , and that f (S) has been defined for every nonempty subset S ⊆ Xn . We will set xn = min(Zn ), so that Xn+1 = {x0 < · · · < xn−1 < xn }. We must now define the tail reservoir Zn+1 , and also f (S) for every non-empty subset S ⊆ {x0 < · · · < xn } that contains xn , and thereafter verify that the required property is satisfied with respect to the updated tail reservoir Zn+1 . Let us enumerate all the finitely many non-empty subsets of Xn+1 that contain xn as S1 , . . . , Sℓ (where ℓ = 2n ), and let |Sj | = mj + 1 (recall: we use 0-indexing). We will process each Sj in order; furthermore, for each Sj , we will consider each color c ∈ {1, 2, . . . , k} in order. As we run through these, we will maintain a series of tail reservoirs Q1,0 , . . . , Q1,k−1 , Q2,0 , . . . , Q2,k−1 , . . . , Qℓ,0 , . . . , Qℓ,k−1 . These tail reservoirs will have the property that Qj,c+1 ⊆ Qj,c , and Qj+1,0 ⊆ Qj,k−1 . To begin with, let Q0,k−1 = Zn,>xn . We will now process S1 , . . . , Sℓ in order. (⋆) Suppose we begin to process Sj . We initialize Qj,0 = Qj−1,k−1 . Now, (⋆⋆) suppose we are processing color c ∈ {1, . . . , k} for Sj . Define the following subset of [Qj,c−1 ]ω : n o Rc,j := T ∈ [Qj,c−1 ]ω J(Sj ∪ T )mj = c . (10) Claim 5.4 at the end of the proof shows that Rc,j is a Borel subset of [Qj,c−1 ]ω . By the Galvin-Prikry theorem (Theorem 8), there exists Y ∈ [Qj,c−1 ]ω such that either [Y ]ω ⊆ Rc,j or [Y ]ω ∩ Rc,j = ∅. In the former case, we define f (Sj ) = c, set Qj,c = Qj,c+1 = · · · = Qj,k−1 = Y , and go back to (⋆) to process the next set Sj+1 . Note that this ensures: for every T ∈ [Qj,k−1 ]ω , J(Sj ∪ T )mj = c. In the latter case, we set Qj,c = Y ; we remain at the set Sj , but go back to (⋆⋆) to process the next color c + 1. Importantly, note that in this case, we have reduced a color: namely, every T ∈ [Qj,c ]ω satisfies that J(Sj ∪ T )mj ̸= c; so, if we have processed colors 1, . . . , c while remaining in this case, we have that J(Sj ∪ T )mj is restricted to exactly be one of the colors {c + 1, . . . , k}. This 19

means that if we continue to be in this case for each of c = 1, . . . , k − 1, when we begin processing c = k, we have the property that every T ∈ [Qj,k−1 ]ω satisfies the property that J(Sj ∪ T )mj = k. We then set f (Sj ) = k, and go back to (⋆) to process the next set Sj+1 . After we have processed each of S1 , . . . , Sℓ , we will have defined f (S) for every non-empty finite subset of Xn+1 . To finish up, we set Zn+1 = Qℓ,k−1 . To complete the inductive step, it remains to argue that for every non-empty, finite subset S ⊆ {x0 , . . . , xn } where |S| = m + 1, and for every tail T ∈ [Zn+1 ]ω , J(S ∪ T )m = f (S). If S ⊆ {x0 , . . . , xn−1 }, this holds simply by the inductive hypothesis, and the observation that Zn+1 ⊆ Zn . Otherwise, xn ∈ S; in this case, S = Sj for some Sj above. Then, observe that after we process Sj , f (Sj ) is set to be equal to precisely that c value for which it holds that J(Sj ∪ T )m = c for every T ∈ [Qj,k−1 ]ω ; since Zn+1 ⊆ Qj,k−1 , this property also holds for every T ∈ [Zn+1 ]ω . This completes the inductive construction of the elements in X, and also defines the function f at every finite, non-empty subset of X. Finally, we argue that for every finite, non-empty S ⊆ X, where S = {xi0 < · · · < xim }, and every T ∈ [X>xim ]ω , it holds that J(S ∪ T )m = f (S). To see this, let im = n. Then, at the time xn was added to X in the inductive construction above, we ensured that for every finite, non-empty subset S of {x0 , . . . , xn }, it holds that J(S ∪ T )|S|−1 = f (S) for every T ∈ [Zn+1 ]ω . In particular, this holds for S = {xi0 < · · · < xim }. The desired conclusion then follows by noting that X>xim = X>xn ⊆ Zn+1 . We now prove the promised claim that the sets Rc,j defined in (10) are Borel. Claim 5.4. The set Rc,j defined in (10) is a Borel subset of [Qj,c−1 ]ω . Proof. Recall that we defined Rc,j while processing the finite set Sj , where |Sj | = mj + 1. Consider the following subset of ZP : I = {C ∈ ZP

Cmj = c}.

Note that I is a finite union of open sets of the form in (8), and is hence an open set in the product topology over ZP . Since J : [N]ω → ZP is a Borel map, we have that J −1 (I) is a Borel subset of [N]ω . That is, A = J −1 (I) = {A ∈ [N]ω

J(A)mj = c}

is a Borel subset of [N]ω . Now consider the map φ : [Qj,c−1 ]ω → [N]ω ,

φ(Y ) = Sj ∪ Y.

Note that φ is continuous — for any basic open set Op = {X ∈ [N]ω : X0 = p0 , . . . , Xn−1 = pn−1 } corresponding to the finite prefix p = {p0 < · · · < pn−1 }, we have that φ−1 (Op ) is either equal to ∅, [Qj,c−1 ]ω or a basic open set in [Qj,c−1 ]ω , depending on the consistency of the prefix p with Sj . Finally, φ being continuous means that n o φ−1 (A) = T ∈ [Qj,c−1 ]ω J(Sj ∪ T )mj = c = Rc,j is a Borel subset of [Qj,c−1 ]ω as claimed. This concludes the proof of Lemma 5.3. Using the canonicalization lemma above, we now show that the class of Borel coloring functions do not suffice for identification with a finite palette. 20

Theorem 9. Let C be the collection of all infinite subsets of N, and let {cJL }L∈C be any universal family of Borel coloring functions specified by the Borel map J, and mapping to a finite palette P . There exists a countable collection C ′ such that C ′ is not identifiable in the limit, even with terminal colors given by {cJL }L∈C ′ . Proof. From Lemma 5.3, there exists an infinite set X = {x0 < x1 < . . . } ∈ [N]ω and a finite-prefix function f that maps finite, non-empty subsets of X to the palette P , such that for every finite, non-empty S ⊆ X, where S = {xi0 < · · · < xim }, and every infinite tail T ∈ [X>xim ]ω , it holds that J(S ∪ T )m = f (S).

(11)

Fix a bijection π : N → X satisfying that π(n) = xn . For any A ⊆ N, let us slightly abuse notation and use the shorthand π(A) := {π(a) : a ∈ A} = {xa : a ∈ A} ⊆ X. Now define the function g that maps finite (ordered) subsets of N to the palette P , where g(S) = f (π(S)). Consider now the universal family {cgL }L∈C of finite-prefix coloring functions, specified by the function g, which satisfies that, for any language L = {y0 < y1 < . . . } ∈ [N]ω , cgL (yi ) = g({y0 , . . . , yi }). Observe that cgL (yi ) = g({y0 , . . . , yi }) = f (π({y0 , . . . , yi })) = J({π(y0 ), . . . , π(yi )} ∪ {π(yi+1 ), π(yi+2 ), . . . })i = J(π(L))i .

(using (11)) (12)

Now assume for the sake of contradiction that for every countable collection C ′ comprising of languages from C, C ′ is identifiable in the limit with terminal colors given by the Borel coloring functions {cJL }L∈C ′ . We will then show that for every countable collection C ′ comprising of languages from C, C ′ is also identifiable in the limit with terminal colors given by the finite-prefix coloring functions {cgL }L∈C ′ , which will contradict Theorem 7. Towards this, fix any countable subcollection C ′ ⊆ C. We will show that for every L ∈ C ′ , there exist finite TL ⊆ L satisfying   ∀L′ ∈ C ′ if L′ ⊊ L then (TL ⊈ L′ ) ∨ (∃x ∈ L′ such that cgL′ (x) ̸= cgL (x)) . (13) From Theorem 4, this implies that C ′ is identifiable in the limit with terminal colors given by {cgL }L∈C ′ . In order to define the tell-tales TL , let us consider the collection C ′′ = {π(L)}L∈C ′ . By assumption, C ′′ is identifiable in the limit with terminal colors given by the Borel map J. From Theorem 4, this means that for every π(L) ∈ C ′′ , there exist finite Teπ(L) ⊆ π(L) satisfying h i ∀π(L′ ) ∈ C ′′ if π(L′ ) ⊊ π(L) then (Teπ(L) ⊈ π(L′ )) ∨ (∃z ∈ π(L′ ) such that cJπ(L′ ) (z) ̸= cJπ(L) (z)) . (14)

21

For any L ∈ C ′ , we now define TL ⊆ L as follows:   TL = π −1 Teπ(L) .

(15)

It remains to show that (13) holds true for TL defined as such. Towards this, consider any L′ ∈ C ′ that satisfies L′ ⊊ L. Now consider the languages π(L), π(L′ ) ∈ C ′′ . Since π is a bijection into X, L′ ⊊ L implies that π(L′ ) ⊊ π(L). From (14), this further means that (Teπ(L) ⊈ π(L′ )) ∨ (∃z ∈ π(L′ ) such that cJπ(L′ ) (z) ̸= cJπ(L) (z)) If Teπ(L) ⊈ π(L′ ), we have, using the definition of TL (15) and the fact that π is a bijection, that Teπ(L) ⊈ π(L′ ) =⇒ π(TL ) ⊈ π(L′ ) =⇒ TL ⊈ L′ . On the other hand, suppose ∃z ∈ π(L′ ) such that cJπ(L′ ) (z) ̸= cJπ(L) (z). Suppose that L′ = {y0′ < y1′ < . . . } ∈ [N]ω , so that π(L′ ) = {π(y0′ ) < π(y1′ ) < . . . }, and let z = π(yi′ ). Then, we have that cJπ(L′ ) (z) = cJπ(L′ ) (π(yi′ )) = J(π(L′ ))i = f (π({y0′ , . . . , yi′ })) = cgL′ (yi′ ).

(using (12)) (by definition of cgL′ )

Now suppose that L = {y0 < y1 < . . . } ∈ [N]ω , so that π(L) = {π(y0 ) < π(y1 ) < . . . }; since L′ ⊊ L, we have that π(L′ ) ⊊ π(L), and so, z ∈ π(L). Then, let z = π(yj ). Note that yj = yi′ = π −1 (z), since π is a bijection. By a similar chain of equalities as above, it holds that cJπ(L) (z) = cgL (yj ) = cgL (yi′ ). Therefore, since cJπ(L′ ) (z) ̸= cJπ(L) (z), we have that cgL′ (yi′ ) ̸= cgL (yi′ ). That is, we have shown the existence of x ∈ L′ such that cgL′ (x) ̸= cgL (x). Combining both the cases above establishes (13) for the tell-tales defined in (15). This implies that C ′ is identifiable in the limit with terminal colors given by {cgL }L∈C ′ . Since C ′ above was arbitrary, we have shown that for every countable collection C ′ comprising of languages from C, C ′ is identifiable in the limit with terminal colors given by the finite-prefix coloring functions {cgL }L∈C ′ . This contradicts Theorem 7, yielding the desired result. Remark 3 (Finite Languages III). Our lower bounds above rule out collection-independent Borel coloring functions and finite-prefix coloring functions that use a finite palette for identification of all countable language collections, where every language is infinite. The lower bound continues to hold when we additionally also include finite languages, since this only makes the problem harder.

5.3

Existence of Borel coloring functions that use an infinite palette

The previous subsection showed that no family of Borel coloring functions that uses a finite palette can work in a collection-independent manner for identification. We conclude this section by showing that there exists a family of Borel coloring functions that uses an infinite palette and suffices for identification collection-independently. Theorem 10. Let C be the collection of all infinite subsets of Σ∗ . There exists a family of Borel coloring functions {cJL }L∈C given by a Borel map J : C → ZN that satisfies the distinguishable coloring condition. 22

Proof. The coloring functions are based on the trace coloring functions given by [CKP26]: we show that the natural conversion of these trace coloring functions into terminal coloring functions — which uses an infinite palette — satisfies the Borel property, and also satisfies the distinguishable coloring condition. In more detail, the trace coloring functions of [CKP26] are defined as follows. For any L ⊆ Σ∗ , define the function fL : Σ∗ → {0, 1, . . . , |Σ| + 1} as X fL (y) = 1[y ∈ L] + 1[∃q ∈ Σ∗ such that yaq ∈ L]. (16) a∈Σ

Then, the trace coloring of any x = (s0 , . . . , sn ) ∈ L is the sequence (fL (ε), fL (s≤0 ), fL (s≤1 ), . . . , fL (s≤n )),

(17)

where s≤j = (s0 , . . . , sj ). We can naturally convert this trace coloring into a terminal coloring by introducing a bijection mapping finite, non-empty sequences over {0, 1, . . . , |Σ|+1} to N. Concretely, fix any bijection b : {0, 1, . . . , |Σ| + 1}>0 → N. Now define the terminal coloring function cL as cL (x) = b((fL (ε), fL (s≤0 ), fL (s≤1 ), . . . , fL (s≤n ))).

(18)

Note that this terminal coloring function uses an infinite palette. [CKP26] showed that the trace coloring functions given by (16), (17) satisfy the distinguishable coloring condition (over the collection C = [Σ∗ ]ω )4 , where instead of terminal colors, they consider trace colors. Since b induces a bijection between the two, whenever there is a discrepancy between the trace coloring of a string, there is a discrepancy between the terminal coloring as well. Summarily, it holds that the family of terminal colorings given in (18) satisfies the distinguishable coloring condition. Now, fix a canonical ordering of all the strings in Σ∗ , and suppose any L = {x0 , x1 , . . . } ∈ [Σ∗ ]ω is specified in this ordering. Consider the map J : [Σ∗ ]ω → ZN to be defined as J(L) = (cL (x0 ), cL (x1 ), . . . ). The following claim shows that this map is Borel, which completes the proof of Theorem 10. Claim 5.5. The terminal coloring functions defined in (18) induce a Borel map J. Proof. For any finite p ∈ Σ∗ , define Fp : [Σ∗ ]ω → {0, 1, . . . , |Σ| + 1} as X Fp (L) = 1[p ∈ L] + 1[∃q ∈ Σ∗ such that paq ∈ L]. a∈Σ

Namely, Fp is defined similarly to fL in (16), but swaps arguments. We will argue that Fp is a Borel map. Towards this, note first that the map L 7→ 1[p ∈ L] is a Borel map. This is because the set {L : p ∈ L}, which can be written as a countable union of open sets of the form given in (9), is a Borel subset of [Σ∗ ]ω . Next, we claim that for any a ∈ Σ, the map L 7→ 1[∃q ∈ Σ∗ such that paq ∈ L] is a Borel map. This follows since [ {L : ∃q ∈ Σ∗ such that paq ∈ L} = {L : paq ∈ L}, q∈Σ∗ ∗

In fact, [CKP26] show that distinguishable coloring condition holds for 2Σ , which includes finite subsets of Σ∗ as well. 4

23

and each {L : paq ∈P L} can be written as a countable union of open sets. Since Σ is finite, we get that the map L 7→ a∈Σ 1[∃q ∈ Σ∗ such that paq ∈ L] is Borel. In total, we conclude that Fp is Borel. Now consider the selector function Si : [Σ∗ ]ω → Σ∗ which selects the ith element in the enumeration of any language L = {x0 , x1 , . . . }, i.e., Si (L) = xi . We argue that Si is Borel. Towards this, consider any σm in the canonical ordering of Σ∗ = {σ0 , σ1 , . . . }. It suffices to show that Si−1 (σm ) is a Borel subset of [Σ∗ ]. Since all languages L are enumerated in an order consistent with the canonical ordering of Σ∗ , we have that o n [ Si−1 (σm ) = L = {x0 < x1 < . . . } ∈ [Σ∗ ]ω x0 = σj0 , . . . , xi−1 = σji−1 , xi = σm , j0 <j1 <···<ji−1 <m

which is a finite union of open subsets of [Σ∗ ]ω , and is hence Borel. We will now show that the coordinate-wise map Ji : [Σ∗ ]ω → N where Ji (L) = J(L)i is a Borel map. In order for this, it suffices to show that Ji−1 (n) for any given n ∈ N is a Borel set. To this end, recall that b is bijection mapping finite sequences over {0, 1, . . . , |Σ| + 1} to N, and consider b−1 (n) = (r0 , . . . , rℓ−1 ) ∈ {0, 1, . . . , |Σ| + 1}ℓ . Then, we have that Ji (L) = n if and only if L = {x0 < x1 < . . . } satisfies that |xi | = ℓ − 1, Fε (L) = r0 , and for every j = 0, . . . , ℓ − 2, Fxi,≤j (L) = rj+1 . Namely,  Ji−1 (n) =

[

S −1 (s) ∩ Fε−1 (r0 ) ∩ i

ℓ−2 \

 Fs−1 (rj+1 ) . ≤j

j=0

s∈Σℓ−1

The expression inside the (finite) union is a finite intersection of Borel sets (and is hence a Borel set), since we argued above that both Si and Fp are Borel maps. We conclude that Ji−1 (n) is a Borel subset of [Σ∗ ]ω ; since n was arbitrary, this implies that Ji is a Borel map. Finally, since ZN has the product Borel structure over N, this suffices to show that J : [Σ∗ ]ω → ZN is Borel, as desired.

AI Disclosure ChatGPT was routinely used to help in developing and understanding the technical ideas used in the paper. In particular, it pointed us to the connection with the Galvin-Prikry theorem used in our lower bounds.

Acknowledgements This work was supported by Moses Charikar’s and Gregory Valiant’s Simons Investigator Awards, a Google PhD Fellowship, a Simons Collaboration grant and a grant from the MacArthur Foundation.

References [Ang80] Dana Angluin. Inductive inference of formal languages from positive data. Information and control, 45(2):117–135, 1980. 1 [BHK26] Satwik Bhattamishra, Michael Hahn, and Varun Kanade. Automata learning and identification of the support of language models. In The Fourteenth International Conference on Learning Representations, 2026. 1 24

[CKP26] Moses Charikar, Jon Kleinberg, and Chirag Pabbaraju. Language identification with succinct machine-independent traces. In Steve Hanneke and Tor Lattimore, editors, Proceedings of Thirty Ninth Conference on Learning Theory, volume 336 of Proceedings of Machine Learning Research, pages 1054–1074. PMLR, 29 Jun–03 Jul 2026. 1, 2.2, 2.2, 3, 4, 3, 5, 5.3, 5.3, 4 [Gol67] E Mark Gold. Language identification in the limit. Information and control, 10(5):447– 474, 1967. 1, 1 [GP73] Fred Galvin and Karel Prikry. Borel sets and ramsey’s theorem. The Journal of Symbolic Logic, 38(2):193–198, 1973. 1, 2.2, 5.2, 8, 3 [PF25] Hristo Papazov and Nicolas Flammarion. Learning algorithms in the limit. In Nika Haghtalab and Ankur Moitra, editors, Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 4486– 4510. PMLR, 30 Jun–04 Jul 2025. 1 [PSV26] Binghui Peng, Amin Saberi, and Grigoris Velegkas. Language identification in the limit with computational trace. In The Fourteenth International Conference on Learning Representations, 2026. 1 [WWS+ 22] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022. 1

25