This web page provides answers, or hints and clues, to exercises
from Chapter 1 of
The Mathematics of Logic and also some additional
information on some of the examples.
By a direct modification of the argument given in Theorem 1.10.
Suppose is an infinite tree where is the set of all sequences of naturals of finite length. Suppose for each there is a bound such that implies . Definfe, for each such the tree as in the proof of Theorem 1.10. We define a sequence of elements of such that for each is infinite. Let be the root so and this is infinite by hypothesis. Now suppose is defined and is infinite. then for
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 where is least such that is infinite. This constructs for all and it is easy to check that is an infinite path.
translation of a sequence
of natural numbers to be the sequence obtained by replacing each number
by the string (
For example the translation of is .
Suppose is an infinite tree and consider the set of translations of sequences in . This isn't a tree, but if we close it under restrictions we can make a tree of sequences of the digits . For example if we will need to have , , , , , , , , and in the tree .
Now is infinite, hence is too, so has an infinite path defining an infinite sequence of s and s. We can translate this path back to a path of provided that is not eventually the constant sequece . But this cannot happen, for if is an initial part of this path, this corresponds to the sequence and is finite so the only sucessors to in are amongst and its retrictions and successors, for , so that can be followed by a string of of length at most , and not by an infinite sequence of s.
The set consisting of the empty string together with the set of
(each of length one) forms an infinite tree in
with no path of length greater than one.
There are infinitely many nodes and no infinite path, and the root has infinite
When reading this example, please note that the fact that the sequence it constructs converges to an element of 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 for example. The interval is not sequentially compact as the sequence does not have any subsequence with a limit in .
(a) by going through all the cases you should be able to chech that the only -free 2-sequences are the empty string, and .
(b) Let be the set of -free 2-sequences. Then is a tree. is infinite if there are arbitrarily long finite -free 2-sequences and has an infinite path if and only if there is an infnite -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 -free 2-sequence, since it is not obvious if for example is the initial part of such a sequence. (In fact it is, see below.) Similarly there are infinite -free 3-sequences but is not an initial part of any such sequence.
(c) To show that is -free
is a bit more tricky. we sketch a proof here that goes by induction
on , providing most but not all details.
The base cases can be checked by calculating ,
, , etc. Now consider
is -free. Suppose we have an
instance of the word in for some
string . There are four cases, depending on whether is
aligned in , meaning the first digit in the
fist occurs at an even index in , or
not, and whether the length of is odd or even.
The easy case is the aligned even case. In this case every pair of digits in corresponds to a single digit in . And therefore the string in shows there is a string in constradicting the induction hypothesis.
Now suppose the string has even length but no first digit of any occurrence of these threes s is aligned. Then the last digit of the first is paired with the first digit of the second , and so on. That means that the first digit of is and the last digit is or vice versa. Assuming for some (the other case being symmetrical) we observe the digit after the last of the three s is also . That means there is an aligned occurrence of where , and this reduces us to the argument in the previous paragraph.
The other two cases, where 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 is aligned on pairs, and without loss of generality assume that this is digit is . Then the last digit of the first is paired with the first digit of the next , so the last digit of is . Similarly the second digit of is paired with the first digit, so . The second digit of the second is paired with the third digit of this , so this third digit is . Continuing in this way we must have giving a contradiction because contains no sequence of three or more consecutive digits.
It turns out that is an initial part of and so these define a path, an infinite -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 , , , and showing is -free for all by similar arguments. The cases are where a substring falls with relation to the alignments at positions congruent to mod and the length of mod .
It is probably easiest to use a version of König's lemma similar to that in Exercise 1.12. For each enumerate all -colourings of the subgraph induced on (i.e. with all edges between these vertices that are in the original graph) as colourings . Note that there are only finitely many such colourings for each . Make a tree with as nodes all such that this corresponds to a valid colouring and edges joining if and only if the colouing extends that of . Then the tree is finite if and only if there are nodes for all , i.e. if any finite subgraph is -colourable, and if this is the case then the tree has an infinite path, which defines a -colouring of the whole graph.
Similar to the previous, except that a node in the tree corresponds to a possible way of tiling the 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.
Finally, as another way to indicate that König's lemma is doing interesting mathematical work, one can note that the definition of the infinite path constructed in the proof of the lemma is comparitively difficult to write down. The following precise version of this observation is suggested for ambitious students with some basic knowledge of computability theory, which may have to be adapted (in the most natural way possible) to the context here.
Show that there is an infinite recursive binary tree such that every infinite path in is nonrecursive.