Thank you for your reply, and for suggesting a fix to your earlier incorrect argument. We'd like to start by pointing out that your new proposed proof is also incorrect. The problem is in the step where you claim that "Since $L_z$ is consistent with $S_t$ for every $t$, we have that for any $t\geq z$, there is at least one simply-critical language." Here is an example that shows there might be no simply-critical language at certain steps where $t \geq z$, contradicting this claim. For the example, let the languages be subsets of the natural numbers, let $L_1$ consist of all multiples of 6, $L_2$ consist of all multiples of 10, and $L_3$ consist of all multiples of 15. (It will not be important for this example what $L_4, L_5, ...$ are.) Let $L_3$ be the true language; i.e. $z = 3$. Suppose that the adversary's first three examples are 60, 120, and 180, so at $t = 3$, the set $S_t$ is {60,120,180}.
For this value $t = 3$, which satisfies $t \geq z$, each of $L_1$, $L_2$, and $L_3$ is consistent with $S_t$, but none is a subset of any of the others, so there is no simply-critical language for $t = 3$. (Note that in comparison, there is a language in this example that is critical under our definition, since as noted in the paper, the first consistent language is always critical.)
Since the author response period is closing today and we may not get a chance to respond further, we would like to make a few further points based on the above.
(i) First, it would be possible to modify your proof to get to a correct proof, but the ways we see to do it would involve incorporating the remaining ideas from the proof in our paper. In particular, defining criticality has to be done carefully, as the problem with your incorrect argument introducing simple-criticality makes clear. Moreover, and crucially, even with our notion of criticality, the true language $L_z$ does not necessarily become critical as soon as $t \geq z$ (as you were attempting to achieve with simple-criticality). Rather, we may have to wait until a potentially later step in the enumeration; our paper accomplishes this in (4.3) via the analysis of the step $t^+$. If you make all these changes, then you would fix the problems with your current proposed proof, but you would also be gradually arriving at all the steps in our current proof.
(ii) You argue that our explanations have unnecessary length. Given that full proof in our paper is only a few pages, we do not think it is particularly long in an absolute sense, even with complete explanations included. Moreover, given that your reviews have now contained two incorrect attempts at a proof, we would suggest that this indicates how getting the details of the proof right is fairly subtle, and it is easy to inadvertently set things up in a way that leads to errors. That is exactly the kind of situation that we typically think of as calling for complete arguments and explanations rather than abbreviated ones. For example, your later suggested description that "The inclusion queries in Item 1 can be replaced by membership tests (as done by the authors) simply by considering slices of the languages up to $L_t$ containing only strings up to a certain length" is indeed correct at a high level, but it is essentially equivalent to Section 5 of our paper, just with all the details suppressed. Given the subtlety of these arguments, and the ease with which errors can arise, we think it is important for these details to be present; and if you were to fill in these details, you would get back to something essentially equivalent to Section 5.
On your remaining points, we believe that the feasibility of language generation is a question of fundamental interest, and given that NeurIPS has tracks for theoretical work on the inherent limits to learning, we also believe it is clearly in scope for the conference. The paper discusses on pages 2-3 and again on page 9 some of the potential connections to current issues in language modeling; we agree there are many open questions that can be considered here, and we find the presence of these open questions a benefit of the current direction.
On the point about the languages $L_i$ being infinite, as noted earlier, we agree that the question becomes technically more complicated when some languages can be finite, and we can indeed discuss this point in a revision. As we also discussed earlier, we think that these added complications arising from finiteness detract from the underlying motivation rather than adding to it. In particular, we'd reiterate the point from our earlier response that the challenge in real language generation problems is not the concern that the training data might have exhausted all possible valid utterances; it is generally understood, both intuitively and on more technical grounds, that there will always be further valid utterances that have not yet been seen. This is exactly the reason to assume that the candidate languages $L_i$ are infinite.