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

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

1. All sequences $N_1,\ldots,N_m$ of length $m=10$.
2. All sequences $N_1,\ldots,N_m$ in which $m = N_1 + 1$.
3. 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.)

-

## 2 Answers

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).

-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 33, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9512479901313782, "perplexity_flag": "head"}