502 – König’s lemma

(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.)

1. Notation

We begin by describing some notation and conventions we will need throughout the course.

{{\mathbb N}=\{0,1,\dots\}}. In set theory, it is customary to denote {{\mathbb N}} by {\omega.}

A sequence is a function whose domain is either {{\mathbb N}} or an initial segment of {{\mathbb N}} (possibly empty).

We identify natural numbers with their set of predecessors. So, if we say, for example, that a sequence has domain {n\in{\mathbb N}}, what we mean is that its domain is {\{0,1,\dots,n-1\}.} If we say that {i\in k} what we mean is that {i<k}.

The length of a sequence is its domain if it is finite, and {\infty} if it is {{\mathbb N}}.

We usually represent sequences as ordered tuples. Thus if {s} is a sequence with domain {k,} we will write

\displaystyle (s(0),s(1),\dots,s(k-1))

for {s}. We will usually write {s_i} rather than {s(i),} and omit parentheses and commas if there is no danger of ambiguity, so the sequence above can also be written as

\displaystyle s_0s_1\dots s_{k-1}.

The concatenation of two sequences {s} and {t,} where {s} is finite, is the sequence {s{}^\frown t} defined as follows: Let {n={\rm dom}(s)} and {M={\rm dom}(t)}. Then {s^\frown t} is the sequence {l} that has domain {n+M} (if {M={\mathbb N}} then this is just {{\mathbb N}}) and is given by:

  • {l(i)=s(i)} for {i<n}.
  • {l(i)=t(i-n)} for {n\le i,} {i\in n+M}.

We may write {st} for {s{}^\frown t} and {si} for {s{}^\frown(i)} if {s} and {t} are sequences and {i} is some object.

A tree {{\mathcal T}} is a set of finite sequences with the property that whenever {s\in{\mathcal T}} and {n<{\rm lh}(s)}, then {s\upharpoonright n \in{\mathcal T}.}

The typical example of a tree is the (full) binary tree, also called the Cantor tree, {2^{<{\mathbb N}},} consisting of all finite sequences of 0s and 1s.

Trees are partially ordered in a natural way: Given sequences {s,t,} write {s\sqsubseteq t} to indicate that {s} is an initial segment of {t.} The root of a tree is the empty sequence, {\emptyset,} which is an initial segment of any element (node) of the tree. If {s\sqsubseteq t} but {s\ne t,} we write {s\sqsubset t.}

Typically, I will imagine trees as growing downward:

If {s\in{\mathcal T},} the successors of {s} are those {t\in{\mathcal T}} such that {s\sqsubset t.} Its predecessors are those {t} such that {t\sqsubset s;} these are just the sequences {s\upharpoonright n} for {n<{\rm lh}(s).} The immediate successors of {s} are the successors of {s} of length {1+{\rm lh}(s).}

We can assign a stratification by levels to the tree {{\mathcal T}} in a natural way; namely, the nodes of tree of length {n} form the {n}-th level of {{\mathcal T}.} An infinite branch through a tree {{\mathcal T}} is an infinite sequence {s} such that for all {n,} {s\upharpoonright n\in{\mathcal T}.} Intuitively, branches are paths through {{\mathcal T}.} We denote by {[{\mathcal T}]} the set of all infinite branches through {{\mathcal T}.} Thus

\displaystyle [2^{<{\mathbb N}}]=2^{\mathbb N}

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 {[0,1].} In fact, this identification is a homeomorphism, when we give {\{0,1\}} the discrete topology and {\{0,1\}^{\mathbb N}} the product topology. Recall that in this topology a basic open set is one of the form

\displaystyle N_s=\{x\in 2^{\mathbb N}\mid s\sqsubset x\}

for {s\in 2^{<{\mathbb N}}.}

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.

Lemma 1 Let {{\mathcal T}} be an infinite, finite branching tree. Then {[{\mathcal T}]\ne\emptyset.}

Proof: By induction, we will identify for each {n\in{\mathbb N}} a node {s_n} in level {n} of {{\mathcal T}} in such a way that

  1. {n<m} implies that {s_n\sqsubset s_m}, and
  2. The set of successors of {s_n} is infinite.

Condition (1) above allows us to form the infinite sequence

\displaystyle s=\bigcup_n s_n.

By construction, {s\in[{\mathcal T}],} 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 {s_0=\emptyset.} By hypothesis, {{\mathcal T}} is infinite, so condition (2) is satisfied.

Suppose {s_n} has been defined. Let {t^0,\dots,t^k} list all the immediate successors of {s_n.} There are finitely many of them since {{\mathcal T}} is finite branching. Note also that a successor of {s_n} is either a {t^i} or a successor of {t^i.} It follows that for some {i\le k,} {t^i} has infinitely many successors. Let such {t^i} be {s_{n+1}.} This completes the induction. \Box

Exercise 1 Show that König’s lemma is false if we omit the assumption that {{\mathcal T}} is finite branching, even if we require that all levels of {{\mathcal T}} be nonempty.

Here is an application: Define a domino system to be a finite set {D} of domino types, i.e., unit squares (parallel to the axes) whose sides have been labeled. Note that we require that {D} is finite as part of the definition.

For example, {D} could consist of the following domino types:

A tiling by {D} of the plane, or of a finite or infinite subset {S} of the plane, consist of a filling-in of the set {S} by dominoes of type in {D} so that adjacent dominoes have matching labels (no rotations are allowed).

For example, the set {D} above can tile the plane by periodically repeating the pattern below:

Theorem 2 For any domino system {D,} the following are equivalent:

  1. {D} can tile the plane.
  2. {D} can tile the upper right quadrant.
  3. For each {n=1,2,\dots,} {D} can tile the {n\times n} square.

Proof: Clearly, (1) implies (2), and (2) implies (3).

We prove that (3) implies (1). Consider a system {D} that can tile all finite squares. Define a tree {{\mathcal T}} as follows: At level {0} we have the empty sequence. At level {n>0,} we have all tilings {D} of the {(2n-1)\times(2n-1)} square. Such a tiling is an immediate successor of a tiling of the {(2n-3)\times(2n-3)} 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 {{\mathcal T}} is infinite (by assumption (3)) and finite branching (since {D} is finite). By König’s lemma, {[{\mathcal T}]\ne\emptyset,} 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. \Box

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.


One Response to 502 – König’s lemma

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: