Exercises and examples from Chapter 1

By a direct modification of the argument given in Theorem 1.10.

Suppose $T\subseteq {\mathbb{N}}^{<\omega }$ is an infinite tree where ${\mathbb{N}}^{<\omega }$ is the set of all sequences of naturals of finite length. Suppose for each $s\in T$ there is a bound $B_s\in \mathbb{N}$ such that $sk\in T$ implies $k<B_s$. Definfe, for each such $s$ the tree $T_s$ as in the proof of Theorem 1.10. We define a sequence $s\left(n\right)$ of elements of $T$ such that for each $n$ $T_{s\left(n\right)}$ is infinite. Let $s\left(0\right)$ be the root so $T=T_{s\left(0\right)}$ and this is infinite by hypothesis. Now suppose $s\left(n\right)$ is defined and $T_{s\left(n\right)}$ is infinite. then for $k=B_s-1$

So since the set of nodes on the left hand side is infinite and there are finitely many sets on the right hand side, one of these sets is infinite. Let $s\left(n\mathrm{+1}\right)=s\left(n\right)i$ where $i$ is least such that $T_{s\left(n\right)i}$ is infinite. This constructs $s\left(n\right)$ for all $n$ and it is easy to check that $\left\{s\left(n\right):n\in \mathbb{N}\right\}$ is an infinite path.

Define a translation of a sequence $s=s_0{s}_1\dots s_k$ of natural numbers to be the sequence obtained by replacing each number $n$ by the string $1^{n}0=11\dots 10$ ($n$ $1$s). For example the translation of $2103$ is $1101001110$.

Suppose $T\subseteq {\mathbb{N}}^{<\omega }$ is an infinite tree and consider the set of translations of sequences in $T$. This isn't a tree, but if we close it under restrictions we can make a tree $T\prime$ of sequences of the digits $0,1$. For example if $2103\in T$ we will need to have $1$, $11$, $110$, $1101$, $11010$, $110100$, $1101001$, $11010011$, $110100111$ and $1101001110$ in the tree $T\prime$.

Now $T$ is infinite, hence $T\prime$ is too, so $T\prime$ has an infinite path $P$ defining an infinite sequence of $0$s and $1$s. We can translate this path $P$ back to a path of $T$ provided that $P$ is not eventually the constant sequece $1111\dots$. But this cannot happen, for if $t=1^{n_1}01^{n_1}0\dots 1^{n_k}0$ is an initial part of this path, this corresponds to the sequence $s=n_1{n}_2\dots n_k\in T$ and $l=B_s$ is finite so the only sucessors to $1^{n_1}01^{n_1}0\dots 1^{n_k}0$ in $T\prime$ are amongst $1^{n_1}01^{n_1}0\dots 1^{n_k}01^{r}0$ and its retrictions and successors, for $0⩽r<B_s$, so that $t$ can be followed by a string of $1s$ of length at most $B_s$, and not by an infinite sequence of $1$s.

The set consisting of the empty string together with the set of sequences $0,1,2,3,\dots$ (each of length one) forms an infinite tree in ${\mathbb{N}}^{<\omega }$ with no path of length greater than one. There are infinitely many nodes and no infinite path, and the root has infinite valency.

When reading this example, please note that the fact that the sequence it constructs converges to an element of $[0,1]$ requires a proof, which is omitted in the text. This proof is easy, but it is the place that the argument breaks down for the open interval $(0,1)$ for example. The interval $(0,1)$ is not sequentially compact as the sequence $1/2,1/4,1/8,\dots$ does not have any subsequence with a limit in $(0,1)$.

(a) by going through all the cases you should be able to chech that the only $x^2$-free 2-sequences are the empty string, $0,1,01,10,010$ and $101$.

(b) Let $T$ be the set of $x^3$-free 2-sequences. Then $T$ is a tree. $T$ is infinite if there are arbitrarily long finite $x^3$-free 2-sequences and $T$ has an infinite path if and only if there is an infnite $x^3$-free 2-sequence. By König's lemma these statements are equivalent.

Note that the argument in the last paragraph does not say how to construct an infinite $x^3$-free 2-sequence, since it is not obvious if for example $0110$ is the initial part of such a sequence. (In fact it is, see below.) Similarly there are infinite $x^2$-free 3-sequences but $1213121$ is not an initial part of any such sequence.

(c) To show that ${\sigma }^n\left(0\right)$ is $x^3$-free is a bit more tricky. we sketch a proof here that goes by induction on $n$, providing most but not all details. The base cases can be checked by calculating ${\sigma }^2\left(0\right)$, ${\sigma }^3\left(0\right)$, ${\sigma }^4\left(0\right)$, etc. Now consider ${\sigma }^{n+1}\left(0\right)$ and suppose ${\sigma }^n\left(0\right)$ is $x^3$-free. Suppose we have an instance of the word $xxx$ in ${\sigma }^{n+1}\left(0\right)$ for some string $x$. There are four cases, depending on whether $x$ is aligned in ${\sigma }^{n+1}\left(0\right)$, meaning the first digit in the fist $x$ occurs at an even index in ${\sigma }^{n+1}\left(0\right)$, or not, and whether the length of $x$ is odd or even.

The easy case is the aligned even case. In this case every pair of digits in $x$ corresponds to a single digit in ${\sigma }^n\left(0\right)$. And therefore the string $xxx$ in ${\sigma }^{n+1}\left(0\right)$ shows there is a string $yyy$ in ${\sigma }^n\left(0\right)$ constradicting the induction hypothesis.

Now suppose the string $x$ has even length but no first digit of any occurrence of these threes $x$s is aligned. Then the last digit of the first $x$ is paired with the first digit of the second $x$, and so on. That means that the first digit of $x$ is $0$ and the last digit is $1$ or vice versa. Assuming $x=0u1$ for some $u$ (the other case being symmetrical) we observe the digit after the last of the three $x$s is also $0$. That means there is an aligned occurrence of $yyy$ where $y=u10$, and this reduces us to the argument in the previous paragraph.

The other two cases, where $x$ has odd length with the dirst digit either aligned or not are similar, and we shall do one of these only. Suppose the first digit of the first $x$ is aligned on pairs, and without loss of generality assume that this is digit is $0$. Then the last digit of the first $x$ is paired with the first digit of the next $x$, so the last digit of $x$ is $1$. Similarly the second digit of $x$ is paired with the first digit, so $x=01u1$. The second digit of the second $x$ is paired with the third digit of this $x$, so this third digit is $0$. Continuing in this way we must have $x=010101\dots$ giving a contradiction because ${\sigma }^n\left(0\right)$ contains no sequence of three or more consecutive digits.

It turns out that ${\sigma }^n\left(0\right)$ is an initial part of ${\sigma }^{n+1}\left(0\right)$ and so these define a path, an infinite $x^3$-free 2-sequence which is remarkably regular. This sequence is known as the Morse-Thue sequence.

(d) I suggest applying a similar argument to that in (c), looking at $\sigma \left(0\right)=0102$, $\sigma \left(1\right)=1210$, $\sigma \left(2\right)=2021$, and showing ${\sigma }^n\left(0\right)$ is $x^2$-free for all $n$ by similar arguments. The cases are where a substring $x$ falls with relation to the alignments at positions congruent to $0$ mod $4$ and the length of $x$ mod $4$.

It is probably easiest to use a version of König's lemma similar to that in Exercise 1.12. For each $n\in \mathbb{N}$ enumerate all $k$-colourings of the subgraph induced on $v_0,\dots ,v_{n-1}$ (i.e. with all edges between these vertices that are in the original graph) as colourings $⟨n,0⟩,\dots ,⟨n,m⟩$. Note that there are only finitely many such colourings for each $n$. Make a tree with as nodes all $⟨n,l⟩$ such that this corresponds to a valid colouring and edges joining $⟨n,l⟩,\dots ,⟨n+1,m⟩$ if and only if the colouing $⟨n+1,m⟩$ extends that of $⟨n,l⟩$. Then the tree is finite if and only if there are nodes $⟨n,l⟩$ for all $n$, i.e. if any finite subgraph is $k$-colourable, and if this is the case then the tree has an infinite path, which defines a $k$-colouring of the whole graph.

Similar to the previous, except that a node in the tree corresponds to a possible way of tiling the $2n+1\times 2n+1$ square centred on the origin and an edge in the tree is added when one tiling extends the next.

In the proof of König's lemma we have to select at each stage one of possibly finitely many daughter nodes of the current node withthe property that the tree below it is infinite. If the nodes are labelled with naturaly numbers we can do this by choosing the node with the least label. But without such labels it is more difficult (or impossible) to specify which choice is to be made, especially as there are potentially infinitely many choices to be made. A new set theoretical pronciple (a weak form of the axiom of choice) is in general required.

Show that there is an infinite recursive binary tree $T$ such that every infinite path in $T$ is nonrecursive.