Is there a name for a family of finite sequences that block all infinite sequences? - MathOverflow

Is there a name for a family of finite sequences that block all infinite sequences?

2010-06-27T05:39:21Z

Let ${\bf N}^\omega = \bigcup_{m=1}^\infty {\bf N}^m$ denote the space of all finite sequences $(N_1,\ldots,N_m)$ of natural numbers. For want of a better name, let me call a family ${\mathcal T} \subset {\bf N}^\omega$ a blocking set if every infinite sequence $N_1,N_2,N_3,N_4,\ldots$ of natural numbers must necessarily contain a blocking set $(N_1,\ldots,N_m)$ as an initial segment. (For the application I have in mind, one might also require that no element of a blocking set is an initial segment of any other element, but this is not the most essential property of these sets.)

One can think of a blocking set as describing a machine that takes a sequence of natural number inputs, but always halts in finite time; one can also think of a blocking set as defining a subtree of the rooted tree ${\bf N}^\omega$ in which there are no infinite paths. Examples of blocking sets include

All sequences $N_1,\ldots,N_m$ of length $m=10$.
All sequences $N_1,\ldots,N_m$ in which $m = N_1 + 1$.
All sequences $N_1,\ldots,N_m$ in which $m = N_{N_1+1}+1$.

The reason I happened across this concept is that such sets can be used to pseudo-finitise a certain class of infinitary statements. Indeed, given any sequence $P_m(N_1,\ldots,N_m)$ of $m$-ary properties, it is easy to see that the assertion

There exists an infinite sequence $N_1, N_2, \ldots$ of natural numbers such that $P_m(N_1,\ldots,N_m)$ is true for all $m$.

is equivalent to

For every blocking set ${\mathcal T}$, there exists a finite sequence $(N_1,\ldots,N_m)$ in ${\mathcal T}$ such that $P_m(N_1,\ldots,N_m)$ holds.

(Indeed, the former statement trivially implies the latter, and if the former statement fails, then a counterexample to the latter can be constructed by setting the blocking set ${\mathcal T}$ to be those finite sequences $(N_1,\ldots,N_m)$ for which $P_m(N_1,\ldots,N_m)$ fails.)

Anyway, this concept seems like one that must have been studied before, and with a standard name. (I only used "blocking set" because I didn't know the existing name in the literature.) So my question is: what is the correct name for this concept, and are there some references regarding the structure of such families of finite sequences? (For instance, if we replace the natural numbers ${\bf N}$ here by a finite set, then by Konig's lemma, a family is blocking if and only if there are only finitely many finite sequences that don't contain a blocking initial segment; but I was unable to find a similar characterisation in the countable case.)

Answer by Péter Komjáth for Is there a name for a family of finite sequences that block all infinite sequences?

2010-06-27T06:24:44Z

If you assume that no element of the family is an initial segment of the other, it is called a barrier in wqo (well quasi order) theory. See mostly Nash-Williams.

Answer by Andreas Blass for Is there a name for a family of finite sequences that block all infinite sequences?

2010-06-27T06:34:19Z

Intuitionists use the name "bar" for what you called a blocking set. The relevant context is "bar induction," the principle saying that, if (1) a property has been proved for all elements of a bar and (2) it propagates in the sense that, whenever it holds for all the one-term extensions of a finite sequence s then it holds for s itself, then this property holds of the empty sequence. (I'm omitting some technicalities here that distinguish different versions of bar induction.)

There's also a closely related notion in infinite combinatorics, called a "barrier"; this is a collection $B$ of finite subsets of $\mathbf N$ such that no member of $B$ is included in another and every infinite subset of $\mathbf N$ has an initial segment in $B$. This is the subject of a partition theorem due to Nash-Williams: If a barrier is partitioned into two pieces, then there is an infinite $H\subseteq\mathbf N$ such that one of the pieces includes a barrier for $H$ (meaning that every infinite subset of $H$ has an initial segment in that piece).