27
$\begingroup$

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

$\endgroup$

2 Answers 2

33
$\begingroup$

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

$\endgroup$
14
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.