Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarch

What it claims

The paper gives a full characterization of language generation in the limit (producing valid unseen elements from every exhaustive positive presentation of an unknown infinite language) for arbitrary families over a countable universe. Generation is possible exactly when each target can be assigned a finite positive witness such that the targets activated by any finite sample have an infinite common intersection. On top of the yes/no characterization, it grades families by how large those witnesses must be.

How it works

The necessary direction comes from a universal normalization: a search through unconfirmed histories converts any successful generator into one that depends only on the observed set (not order or repetition). This is what lets the witness condition be extracted from an arbitrary generator.

The grading is a three-level positive separation width hierarchy:

• a smallest uniform size bound on compatible witnesses (finite width);
• unbounded but finite witnesses (no uniform bound);
• no compatible finite-witness assignment at all.

The paper shows every level is inhabited:

• countable families admit singleton witnesses;
• explicit families realize every finite width;
• a union of two families with infinite common cores requires unbounded finite witnesses.

It also proves countable-support and finite-profile obstructions, arguing that local combinatorial data cannot by itself determine whether generation in the limit is achievable — a negative result about what invariants can decide the question.

Evidence

The characterization, the full width hierarchy, and the level-separation constructions are machine-checked in Lean, including the simplified normalization lemma and a direct diagonal capture lemma. The Lean development is maintained at a linked repository (URL not resolved in the fetched text).

Limits

This is a theory paper: the fetched page is abstract-only, so the actual construction details, the Lean repository URL, and any complexity or effectiveness bounds on the generators are not visible here. The results concern existence of generators over countable universes; the abstract states nothing about computational efficiency, sample complexity, or applicability to concrete learning systems. Note the title as indexed truncates "Hierarch[y]". Two versions exist (v1 26 KB, 9 Sep 2026; v2 44 KB, 10 Sep 2026) — the analysis above reflects v1's abstract.