being explicit with recursion in a basic proof

Question

related: induction (vs recursion) in proof

I want to be explicit with this principle (PCR):

Principle of Countable Recursion. Let $T$ be a set, and let $p$ be some map­ping from $\{$finite sequences in T$\}$ into $T$. Then there exists a unique sequence $(t_1,t_2, t_3,\dots)$ in $T$ that satisfies $t_n= p(t_1 , t_2 ,\dots, t_{n - 1})$ for all $n$.

in the proof for "every interval $[a,b]$ is compact". Here's the relevant part of the proof:

Suppose for a contradiction that our interval $I_1=[a,b]$ is not compact. Let $T$ be the set of intervals $[x,y]\subseteq I_1$ such that $[x,y]$ is not compact. Let $S=\{$finite sequences in $T\}$. I define a sequence $(I_n:n\in\mathbb{N})$ in $T$ using PCR.

Let $f:S\rightarrow T$. When $s$ is the empty sequence, define $f(s)=I_1$. Let $s=(I_1,\dots,I_{k-1})$ (for $k=2,3,\dots)$ where each $I_i\in T$. $I_{k-1}$ is not compact. We have an interval $I_k$ such that $I_k\subseteq I_{k-1}$, $I_k$ is not compact, and diam${I_k}=\frac{1}{2^{k-1}}(b-a)$. Define $f(s)=I_k$. By PCR, there exists a unique sequence $(I_n:n\in\mathbb{N})$ such that $I_n=f(I_1,I_2,\dots,I_{n-1})$ for every $n\in\mathbb{N}$.

Here's what I'm wondering: does my "mapping" $f:S\rightarrow T$ have to be defined for all sequences in $S$? Right now it isn't. It's only defined for sequences starting with $I_1$.

Phrased another way: is it sufficient to define $f$ for a subset of $S$? The wording of PCR makes me think that I have to define $f$ for every $s\in S$.

Thanks

Answer 1

Let me outline an approach that works, using this alternative formulation of PCR:

If $T$ is a set, $f:T\to T$ a function, and $t_1\in T,$ then there is a unique sequence $\langle t_n\rangle_{n\in\Bbb N}$ of elements of $T$ such that $t_{n+1}=f(t_n)$ for all $n\in\Bbb N.$

You should justify each step.

• Since $I_1=[a,b]$ is non-compact by assumption, then there is an open cover $\mathcal U$ of $I_1$ having no finite subcover.
• Let $T$ be the set of non-degenerate closed subintervals of $I_1$--that is, intervals of the form $[c,d]$ with $a\le c<d\le b$--that cannot be covered by a finite subset of $\mathcal U.$
• Given $I\in T,$ say with $I=[c,d],$ at least one of the intervals $\left[c,\frac{c+d}2\right],$ $\left[\frac{c+d}2,d\right]$ cannot be covered by any finite subset of $\mathcal U.$ If one of these two intervals can be covered by some finite subset of $\mathcal U,$ then let $f(I)$ be the other one. Otherwise, let $f(I)=\left[c,\frac{c+d}2\right].$
• In this fashion, we define $f:T\to T,$ so since $I_1\in T$ by assumption, then there is a unique sequence $\langle I_n\rangle_{n\in\Bbb N}$ of $T$-intervals such that $I_{n+1}=f(I_n)$ for all $n\in\Bbb N.$
• For all $n\in\Bbb N,$ we have $I_{n+1}\subseteq I_n$ and the length of $I_{n+1}$ is half the length of $I_n.$
• By Nested Interval Theorem, $\bigcap_{n\in\Bbb N}I_n$ is non-empty.
• Given $x,y\in\bigcap_{n\in\Bbb N}I_n,$ we have $x=y.$
• Hence, $\bigcap_{n\in\Bbb N}I_n=\{x_0\}$ for some $x_0\in I_1.$
• Since $\mathcal U$ is an open cover of $I_1,$ then there is some $U_0\in\mathcal U$ such that $x_0\in U_0.$
• Since $U_0$ is open and $x_0\in U_0\cap I_n$ for all $n\in\Bbb N,$ then there is some $k\in\Bbb N$ such that $I_k\subseteq U_0.$
• Since $I_k\in T,$ then $\{U_0\}$ does not cover $I_k.$
• We have reached a contradiction.