Finitistic trees, level products, density, and matrices

A finitistic tree is a partially ordered set $(T,{\le }_T)$ with a root $r_T$ such that, for every $t\in T$, the strict predecessor set $\{s:s{<}_{T}t\}$ is finite and linearly ordered by ${\le }_T$. Its cardinality is the height ${\mathrm{ht}}_T(t)$ of $t$, and

$T(n)=\{t\in T:{\mathrm{ht}}_T(t)=n\}$

is its $n$th level. We require every level to be finite and every node to have a strict extension. Thus every node extends to every greater finite height: given $t$ and $m<\omega$, finite recursion chooses one successor at a time to obtain an extension on level $\mathrm{ht}(t)+m$. This is only a finite sequence of existential instantiations, not a choice function on an infinite family.

For $A\subseteq T$, say that $A$ dominates $t$ if $t{\le }_{T}a$ for some $a\in A$. Given $h,k<\omega$, $A$ is $(h,k)$-dense if there is an $x\in T(h)$ such that $A$ dominates every $t\in T(h+k)$ above $x$. It is $k$-dense when it is $(0,k)$-dense. At $k=0$, $(h,0)$-density says exactly that $A$ dominates some node of $T(h)$; at $h=k=0$, this is equivalent to $A\mathrm{\ne }\mathrm{\varnothing }$. The empty set is never $(h,k)$-dense.

Fix a positive integer $d$ and finitistic trees $T_1,\dots ,T_d$. Their full product is

${\prod }_{i=1}^d{T}_i,$

whose coordinates may have different heights. Their level product is

${\bigcup }_{n<\omega }{\prod }_{i=1}^d{T}_i(n),$

whose coordinates have one common height. If each $A_i\subseteq T_i$ is $(h,k)$-dense, then ${\prod }_{i=1}^d{A}_i$ is an $(h,k)$-matrix. A $k$-matrix is a $(0,k)$-matrix. A matrix is a subset of the full product; it need not lie in the level product. The convention excludes $d=0$; for $d=1$ a matrix is simply a dense coordinate set.

Two elementary consequences will be used below. First, if $A$ is $(h,p-h)$-dense above $x\in T(h)$ and $h\le h^{\mathrm{\prime }}\le p$, then any extension $x^{\mathrm{\prime }}\in T(h^{\mathrm{\prime }})$ of $x$ witnesses that

$A\cap \{a:x^{\mathrm{\prime }}{\le }_{T}a\}$

is $(h^{\mathrm{\prime }},p-h^{\mathrm{\prime }})$-dense. Indeed, every height-$p$ extension of $x^{\mathrm{\prime }}$ is already a height-$p$ extension of $x$. Second, for finitely many roots $x_i$ of possibly different heights $n_i$, putting $h={\max }_i{n}_i$ and extending each $x_i$ to some $x_i^{\mathrm{\prime }}\in T_i(h)$ makes the preceding restriction available with one common height. Only finitely many extensions are selected.