Is there a name for a family of finite sequences that block all infinite sequences? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T10:21:06Z http://mathoverflow.net/feeds/question/29676 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29676/is-there-a-name-for-a-family-of-finite-sequences-that-block-all-infinite-sequence Is there a name for a family of finite sequences that block all infinite sequences? Terry Tao 2010-06-27T05:39:21Z 2010-06-27T06:34:19Z <p>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 <em>blocking set</em> 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.)</p> <p>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</p> <ol> <li>All sequences $N_1,\ldots,N_m$ of length $m=10$.</li> <li>All sequences $N_1,\ldots,N_m$ in which $m = N_1 + 1$.</li> <li>All sequences $N_1,\ldots,N_m$ in which $m = N_{N_1+1}+1$.</li> </ol> <p>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</p> <blockquote> <p>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$.</p> </blockquote> <p>is equivalent to</p> <blockquote> <p>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.</p> </blockquote> <p>(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.)</p> <p>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.)</p> http://mathoverflow.net/questions/29676/is-there-a-name-for-a-family-of-finite-sequences-that-block-all-infinite-sequence/29681#29681 Answer by Péter Komjáth for Is there a name for a family of finite sequences that block all infinite sequences? Péter Komjáth 2010-06-27T06:24:44Z 2010-06-27T06:24:44Z <p>If you assume that no element of the family is an initial segment of the other, it is called a <i>barrier</i> in wqo (well quasi order) theory. See mostly Nash-Williams. </p> http://mathoverflow.net/questions/29676/is-there-a-name-for-a-family-of-finite-sequences-that-block-all-infinite-sequence/29682#29682 Answer by Andreas Blass for Is there a name for a family of finite sequences that block all infinite sequences? Andreas Blass 2010-06-27T06:34:19Z 2010-06-27T06:34:19Z <p>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.) </p> <p>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). </p>