(The material on mathematical logic is covered in the textbook starting with Chapter 5; however, for the first few lectures, I will be providing some required background topics and will not be following the book. There are several references that you may find useful. For example,
- Kaye, Richard. The mathematics of logic, Cambridge University Press (2007).
I am also making use of a set of notes originally developed by Alexander Kechris for the course Math 6c at Caltech.)
We begin by describing some notation and conventions we will need throughout the course.
. In set theory, it is customary to denote by
A sequence is a function whose domain is either or an initial segment of (possibly empty).
We identify natural numbers with their set of predecessors. So, if we say, for example, that a sequence has domain , what we mean is that its domain is If we say that what we mean is that .
The length of a sequence is its domain if it is finite, and if it is .
We usually represent sequences as ordered tuples. Thus if is a sequence with domain we will write
for . We will usually write rather than and omit parentheses and commas if there is no danger of ambiguity, so the sequence above can also be written as
The concatenation of two sequences and where is finite, is the sequence defined as follows: Let and . Then is the sequence that has domain (if then this is just ) and is given by:
- for .
- for .
We may write for and for if and are sequences and is some object.
A tree is a set of finite sequences with the property that whenever and , then
The typical example of a tree is the (full) binary tree, also called the Cantor tree, consisting of all finite sequences of 0s and 1s.
Trees are partially ordered in a natural way: Given sequences write to indicate that is an initial segment of The root of a tree is the empty sequence, which is an initial segment of any element (node) of the tree. If but we write
Typically, I will imagine trees as growing downward:
If the successors of are those such that Its predecessors are those such that these are just the sequences for The immediate successors of are the successors of of length
We can assign a stratification by levels to the tree in a natural way; namely, the nodes of tree of length form the -th level of An infinite branch through a tree is an infinite sequence such that for all Intuitively, branches are paths through We denote by the set of all infinite branches through Thus
is the set of all infinite sequences of 0s and 1s. This is usually called the Cantor set, since it can be naturally identified with Cantor’s ternary subset of In fact, this identification is a homeomorphism, when we give the discrete topology and the product topology. Recall that in this topology a basic open set is one of the form
2. König’s lemma
A tree is infinite iff it has infinitely many nodes. It is finite branching iff each node has only finitely many immediate successors.
König’s lemma is a very powerful tool that allows us to relate infinite and finite combinatorics, and we will use it frequently throughout the course. Its proof is remarkably simple.
Proof: By induction, we will identify for each a node in level of in such a way that
- implies that , and
- The set of successors of is infinite.
Condition (1) above allows us to form the infinite sequence
By construction, and this will give us the result we want. Condition (2) is used to ensure that we can keep the induction going.
At stage 0 we simply set By hypothesis, is infinite, so condition (2) is satisfied.
Suppose has been defined. Let list all the immediate successors of There are finitely many of them since is finite branching. Note also that a successor of is either a or a successor of It follows that for some has infinitely many successors. Let such be This completes the induction.
Exercise 1 Show that König’s lemma is false if we omit the assumption that is finite branching, even if we require that all levels of be nonempty.
Here is an application: Define a domino system to be a finite set of domino types, i.e., unit squares (parallel to the axes) whose sides have been labeled. Note that we require that is finite as part of the definition.
For example, could consist of the following domino types:
A tiling by of the plane, or of a finite or infinite subset of the plane, consist of a filling-in of the set by dominoes of type in so that adjacent dominoes have matching labels (no rotations are allowed).
For example, the set above can tile the plane by periodically repeating the pattern below:
Theorem 2 For any domino system the following are equivalent:
- can tile the plane.
- can tile the upper right quadrant.
- For each can tile the square.
Proof: Clearly, (1) implies (2), and (2) implies (3).
We prove that (3) implies (1). Consider a system that can tile all finite squares. Define a tree as follows: At level we have the empty sequence. At level we have all tilings of the square. Such a tiling is an immediate successor of a tiling of the square iff this smaller tiling occupies the center of the larger one.
(It is straightforward to transform this labeling of nodes into a tree according to our conventions.)
Note that is infinite (by assumption (3)) and finite branching (since is finite). By König’s lemma, i.e., we can tile the odd-length squares in such a way that we can keep extending the tiling, thus covering the whole plane. This completes the proof.
The above is a typical application of König’s lemma. It allows us to replace an infinite problem (tiling the plane) with a series of finite, in principle, more approachable, problems. Other applications do the opposite: They allow us to extract information about finite combinatorics from result about infinite objects. We will see a few more examples next time, and throughout the course.
Typeset using LaTeX2WP. Here is a printable version of this post.