Motivation to Lipschitz Trees

We overview some results of Todorčević with a goal to unravel the following, mysterious at first sight, definitions.
Recall that in the previous post we gave some definitions about trees.
Let $T$ be a tree and $t\in T$, suppose $\alpha\leq \mathop{\mathrm{ht}}(t)$ then we denote by $t\mathop{\mathrm{\restriction}}\alpha$ the $s\leq t$ in $T$ such that $\mathop{\mathrm{ht}}(s)=\alpha$.

A partial map $g$ from a tree $S$ into a tree $T$ is called Lipschitz is $g$ is level-preserving and $\Delta(g(x),g(y))\geq \Delta(x,y)$ for all $x,y\in \mathop{\mathrm{dom}}(g)$.

Definition. A Lipschitz tree is any Aronszajn tree $T$ with the property that every level-preserving map from an uncountable subset of $T$ into $T$ is Lipschitz on an uncountable subset of its domain.

The following are two useful Lemmas about Lipschitz trees that are worth mentioning although we will not need them for the rest of the post.
Lemma 1. Suppose $T$ is a Lipschitz tree, $0<n<\omega$ and that $A$ is an uncountable subset of the $n$-th power of $T$. Then there existsan uncountable $B\subseteq A$ such that $\Delta(a_i,b_i)= \Delta(a_j,b_j)$ for all $a\neq b$ in $B$ and $i,j<n$. It follows that the $n$-th power of $T$ is a Lipschitz tree as well.

Lemma 2. Every uncountable subset of a Lipschitz tree $T$ contains an uncountable antichain. More generally, every family $A$ if pairwise disjoint finite subset of $T$ contains an uncountable sub-family $B$ such that $\bigcup B$ is an antichain of $T$.

Theorem (Todorčević): (Theorem 4.2.4). Every special coherent tree $T$ is Lipschitz.

Proof. Let $(T,\subseteq)$ be a special coherent tree $T\subseteq {}^{<\omega_1}\omega$ where the nodes are functions from countable ordinals to $\omega$ and the tree is closed with respect to restrictions of nodes to countable ordinals.
By our assumption, the tree $T$ can be decomposed into countably many anti chains. So let $c:T\rightarrow \omega$ be fixed map such that $c(s)\neq c(t)$, whenever $s<_T t$ and such that $a$ is one-to-one on the levels of $T$.
For every $t,s\in T$ we have $\Delta(s,t)= \min\{\xi < \min(\mathop{\mathrm{ht}}(s),\mathop{\mathrm{ht}}(t)) \mid t(\xi)\neq s(\xi)\}$
Consider a partial level-preserving map $f$ from an uncountable subset $X$ of $T$ into $T$.
As the tree $T$ is special, we may refine and assume both the domain and the image of $f$ are ncountable anti-chains.
Moreover, we may assume that $X$ contains no two different nodes of the same height. For $t\in X$, set $D_t:=\{\xi <\mathop{\mathrm{ht}}(t)\mid t(\xi)\neq f(t)(\xi)\}$.
Let $p_t:D_t\rightarrow \omega$ and $q_t:D_t\rightarrow \omega$ be the functions defined by $p_t(\xi) = c(t\mathop{\mathrm{\restriction}}\xi) \text{ and }q_t(\xi)=c(f(t)\mathop{\mathrm{\restriction}}\xi).$
Applying the $\Delta$-system, pigeon-hole principle and shrinking $X$, we assume that $\langle D_t \mid t\in X \rangle$ forms a $\Delta$-system with root $R$ such that:

  • $D_s\setminus R < D_t \setminus R$ whenever $s,t\in X$ are such
    that $\mathop{\mathrm{ht}}(s)<\mathop{\mathrm{ht}}(t)$.

And for every $s,t\in X$ we have,
$s\mathop{\mathrm{\restriction}}D_s \cong t\mathop{\mathrm{\restriction}}D_t$, $f(s)\mathop{\mathrm{\restriction}}D_s \cong f(t)\mathop{\mathrm{\restriction}}D_t$, $p_s\mathop{\mathrm{\restriction}}D_s \cong p_t\mathop{\mathrm{\restriction}}D_t,$ and $q_s\mathop{\mathrm{\restriction}}D_s \cong q_t\mathop{\mathrm{\restriction}}D_t.$
Fix $s$ and $t$ in $X$, let us show that $\Delta(s,t)=\Delta(f(s),f(t))$.
Let us first establish the inequality

Let $\alpha=\Delta(s,t)$. Then $\alpha<\mathop{\mathrm{ht}}(t),\mathop{\mathrm{ht}}(s)$, since $s$ and $t$ are incomparable.
Let us show that $D_s\cap \alpha=D_t\cap \alpha$. Suppose $(D_s \cap \alpha) \setminus D_t$ is non-empty and contains $\beta$. Then by the properties of our parameters $s$ and $t$, $s\mathop{\mathrm{\restriction}}\beta = t\mathop{\mathrm{\restriction}}\beta$
and $c(s\mathop{\mathrm{\restriction}}\beta) = c(t\mathop{\mathrm{\restriction}}\gamma)$ for some $\gamma\neq \beta$ in $D_t$.
Notice that$s\mathop{\mathrm{\restriction}}\beta$ and $t\mathop{\mathrm{\restriction}}\gamma$ are comparable as they both restrictions of $t$ which is a contradiction to the assumption each homogeneous set of the coloring $c$ is an anti-chain. Similarly we can show that $(D_t \cap \alpha) \setminus D_s = \emptyset$.
By the properties of our parameters $s$ and $t$, we have that $D_s\cap \alpha=D_t\cap \alpha$ and that $f(s)$ and $f(t)$ agree on this set.
From the definition of $D_s$ and $D_t$, we conclude that $f(s)$ and $f(t)$ must agree below $\alpha$, and so $\Delta(f(s),f(t))\geq\alpha$.
A completely symmetric argument will give us the other inequality

Bases for Aronszajn Trees

We overview some results by Baumgartner.
Recall that a poset $\mathbf T=(T,{<_T})$ is a $\kappa$-tree iff all of the following hold:

  • $|T|=\kappa$;
  • for every $x\in T$, $(x_\downarrow,<_T)$ is well-ordered.

For every $x\in T$, denote $\mathop{\mathrm{ht}}(x):=\mathop{\mathrm{otp}}(x_\downarrow,<_T)$.
For every $A\subseteq\kappa$, let $T\restriction A:=\{ x\in T\mid \mathop{\mathrm{ht}}(x)\in A\}$.
Note that, for every $\alpha<\kappa$, $T_\alpha:=\{ x\in T\mid \mathop{\mathrm{ht}}(x)=\alpha\}$ and $T\restriction\alpha$ have size ${<}\kappa$.
A maximal linearly ordered subset of $T$ is called a branch.

A $\kappa$-Aronszajn tree is a $\kappa$-tree with no chains of size $\kappa$.

A $\kappa$-Souslin tree is a $\kappa$-tree with no chains or anti-chains of size $\kappa$.

A $\kappa$-Kurepa tree is a $\kappa$-tree with at least $\kappa^+$ branches.

An $\aleph_1$-tree $T$ is special if there is a function $f:T\rightarrow \omega$ such that whenever $s<_T t$ we have $f(t)\neq f(s)$.

The next well-known lemma shows that Souslin trees are similar to Luzin spaces in the sense that every large subset of a Souslin tree is somewhere dense.

Lemma (folklore). Suppose $\mathbf T=(T,{<_T})$ is a $\kappa$-Souslin tree and $B\subseteq T$ is a subset with $|B|=\kappa$. Then there exists $w\in T$ such that $w^\uparrow\cap B$ is cofinal in $w^\uparrow$.

Definition. Let $(T,<_T)$ be a normal $\omega_1$-tree, a sub-tree of $T$ is a subset $S$ which is a normal $\omega_1$-tree and $S$ is downward closed under $<_T$ (i.e., if $t\in S$ and $s<_T t$ then $s\in S$).

A base for $T$ is a set $\mathcal B$ of sub-trees such that for every sub-tree $S$ of $T$ there is $A\in \mathcal B$ with $A\subseteq S$.

Remark. Let us observe that any $\kappa$-Souslin tree $T$ has a basis of size $\kappa$. Define for every $t\in T$ the set $T_t:=\{s\in T \mid s\leq_T t\text{ or }t\leq_T s\}$, then by the Lemma the set $\{ T_t \mid t\in T \}$ is a base for $T$.

Theorem (Todorčević): Suppose there is an $\aleph_1$-Kurepa tree with at least $\kappa$-branches. Then there is a special $\aleph_1$-Aronszajn tree for which every base has cardinality greater equal to $\kappa$.

Proof. Let $(K,\leq_K)$ be an $\aleph_1$-Kurepa tree with $\kappa$ branches and let $T$ be a special $\aleph_1$-Aronszajn tree. Let $S=K\otimes T :=\{ (k,t) \mid k\in K, t\in T\text{ and }\mathop{\mathrm{ht}}(k)=\mathop{\mathrm{ht}}(t) \}$ with the coordinatewwise ordering, i.e. $(k,t)< (a,b) \iff k<_K a \wedge t<_T b$. Then $S$ is clearly an $\aleph_1$-Aronszajn tree, for $S_\alpha = K_\alpha\times T_\alpha$ for all $\alpha<\omega_1$ and if $B\subseteq S$ is an uncountable branch then $\{t\in T \mid \exists k[(k,t)\in B]\}$ would be an uncountable branch through $T$, which is impossible.

If $f:T\rightarrow \omega$ is a witnesses that $T$ is special then we define the function $g:S\rightarrow \omega$ by $g(k,t)=f(t)$, this clearly witnesses that $S$ is also special.

Finally, let $\langle b_\xi \mid \xi<\kappa \rangle$ be a sequence of disjoint uncountable branches through $K$. Let $A_\xi := \{ (k,t)\in S \mid k\in b_\xi\}$ then it is easily to see that
for every $\xi\neq \eta$ in $\kappa$, we have $b_\xi\cap b_\eta$ is countable, hence $A_\xi \cap A_\eta$ is also countable, and it is clear that $A_\xi$ is a subtree of $S$.

Suppose we have a basis $\mathcal B$ of cardinality less than $\kappa$, but this is impossible since for every $\xi<\kappa$ there must exists some $B\in \mathcal B$ such that $B\subseteq A_\xi$. ◻