Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to prove the Heine Borel theorem for compactness of the closed interval $[0,1]$ using Konig's lemma. This is what I have so far:

  1. I assume $[0,1]$ can be covered by $\{(a_i,b_i):i=0,1,2\cdots\}$.

  2. I construct a graph $G$ as follows: First let a vertex be labelled $[0,1]$ (the root). Then consider $[0,1]-(a_0,b_0)\cup(a_1,b_1)$. This consists of $n_1$ closed intervals where $n_1$ is finite. Adjoin the $[0,1]$ vertex with $n_1$ vertices labelled by these closed intervals (these vertices will be at level 1). Next consider $[0,1]-(a_0,b_0)\cup(a_1,b_1)\cup(a_2,b_2)$. This consists of $n_2$ closed intervals. Each of these closed intervals is a subset of exactly one the closed intervals considered in the previous step. Make $n_2$ vertices labelled by these closed intervals and adjoin them to that vertex created in the previous step of which it is a subset of (these vertices will be at level 2). Continue doing so for higher levels, each time obtaining the labels by considering the closed interval obtained from $[0,1]-(a_0,b_0)\cup(a_1,b_1)\cdots \cup(a_i,b_i)$.

  3. This yields a rooted tree $G$ where each level is finite.

  4. Suppose the tree contained an infinite path: $[0,1]\supset[\alpha_1,\beta_1]\supset[\alpha_2,\beta_2]\cdots$.

  5. Since a sequence of nested closed intervals is nonempty so there is an element $x$ in it. As $x\in [0,1]$ so $x\in(a_i,b_i)$ for some $i$. But then $x$ cannot exist in any interval which is at a level beyond $i$, yielding a contradiction to 4.

  6. So by the contrapositive form of Konig's lemma, $G$ cannot be infinite. It follows that for some $i$, $[0,1]-(a_0,b_0)\cup(a_1,b_1)\cdots \cup(a_i,b_i)$ is empty. Hence $[0,1]$ is covered by $(a_0,b_0)\cup(a_1,b_1)\cdots \cup(a_i,b_i)$.

My doubts are in the arguments presented in 2. and 6. Are they correct? In particular is this statement: "Each of these closed intervals is a subset of exactly one the closed intervals considered in the previous step." correct?

What is an upper bound for $n_k$?


share|cite|improve this question
up vote 3 down vote accepted

The argument is correct, but it can be cleaned up a bit. Here’s one possible way.

Without loss of generality assume that $0\in(a_0,b_0)$, $1\in(a_1,b_1)$, and $b_0\le a_1$. Construct a sequence of closed subsets of $[0,1]$ as follows: $C_0=[0,1]$, and $C_{n+1}=C_n\setminus(a_n,b_n)$ for $n\in\Bbb N$.

Claim: Each $C_n$ is the union of a finite family of pairwise disjoint closed intervals (which may be degenerate).

Proof: This is clearly true for $C_0,C_1=[b_0,1]$, and $C_2=[b_0,a_1]$. Suppose that it holds for $C_n$, where $n\ge 2$, and write $C_n=\bigcup_{k=1}^m[c_k,d_k]$, where $c_1\le d_1<c_2\le d_2<\dots<c_m\le d_m$. That is, $c_k\le d_k$ for $k=1,\dots,m$, and $d_k<c_{k+1}$ for $k=1,\dots,m-1$. Then $C_{n+1}$ is the disjoint union of the following closed intervals: the intervals $[c_k,d_k]$ such that $d_k\le a_n$ or $c_k>b_n$; the interval $[c_k,a_n]$ if $c_k\le a_n<d_k$; and the interval $[b_n,d_k]$ if $c_k<b_n\le d_k$. The result now follows by induction. $\dashv$

For $n\in\Bbb N$ let $\mathscr{C}_n$ be the set of pairwise disjoint closed intervals that are the connected components of $C_n$, and let $\mathscr{C}=\bigcup_{n\in\Bbb N}\mathscr{C}_n$. It’s clear that if $m\le n$ and $I\in\mathscr{C}_n$, there is a unique $J\in\mathscr{C}_m$ such that $I\subseteq J$. Thus, $\langle\mathscr{C},\supseteq\rangle$ is a tree of height $\omega$, and $\mathscr{C}_n=\operatorname{Lev}_n\mathscr{C}$ for each $n\in\Bbb N$, so $\mathscr{C}$ has finite levels. It follows from König’s theorem that there is a branch $\beta=\langle I_n:n\in\Bbb N\rangle$ through $\mathscr{C}$. Then $\beta$ is a nested sequence of closed intervals, so $\bigcap_{n\in\Bbb N}I_n\ne\varnothing$. Fix $x\in\bigcap_{n\in\Bbb N}I_n\ne\varnothing$. Then $x\in[0,1]$, but for each $n\in\Bbb N$ we have $x\in I_{n+1}\subseteq[0,1]\setminus(a_n,b_n)$, so $x\in[0,1]\setminus\bigcup_{n\in\Bbb N}(a_n,b_n)$, contradicting the assumption that $\{(a_n,b_n):n\in\Bbb N\}$ is a cover of $[0,1]$.

For completeness there are a couple of things that you ought to say first: you really should start with an arbitrary open cover $\mathscr{U}$ of $[0,1]$ and then justify replacing it by a countable cover by open intervals. How you do this depends on what tools you consider to be available.

To answer the final question, note that each step can increase the number of closed intervals by at most one: in my construction this happens exactly when there is a $k$ such that $c_k\le a_n<b_n\le d_k$. Since $|\mathscr{C}_n=1|$ for $n=0,1,2$, this means that $|\mathscr{C}_n|\le n-1$ for $n\ge 2$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.