While preparing a lecture on dynamic programming principle in optimal stochastic control after the book of Touzi, I discovered a gap in the proof of DPP (page 28 of the book).

Here I simplify the relevant place to give a brief idea where the gap lies. The author defines a family of sets $$ B(s,y) = \{(t,x)\in \mathbf{S}=[0,T)\times \mathbb{R}^d: t\in (s-r(s,y),s), |x-y|<r(s,y)\}, $$ where $(s,y) \in \mathbf{S}$, and $r(s,y)>0$ are some numbers. Further, the author writes, "Clearly, $\{B(s,y): (s,y) \in \mathbf{S}\}$ forms an open covering of $\mathbf{S}$", and then appeals to Lindelöf's theorem to show that there is a countable subcover. However, the fact that $\{B(s,y)\}$ is a cover is false in general.

I've managed to find a workaround. Instead of considering the open cylinders $B(s,y)$, one needs to consider half-open cylinders $$ D(s,y;r) = \{(t,x)\in \mathbf{S}: t\in (s-r,s], |x-y|<r\} $$ (note that $t=s$ is now included to the set). Then we need the following.

Fact 1 Let, for each $r(s,y)$, $(s,y) \in \mathbf{S}$, be arbitrary positive numbers. Then there is a countable family $\{(s_n,y_n),n\ge 1\}$ such that $$ \mathbf{S}= \bigcup_{n\ge 1} D(s_n,y_n; r(s_n,y_n)). $$

The proof is as follows. Obviously, $\mathsf{D} = \{D(s,y,r(s,y)),(s,y) \in \mathbf{S}\}$ is a cover of $\mathbf{S}$. The sets $D(s,y;r)$ are open in the topology of the product space $[0,T)\times \mathbb{R}^d$, where the interval $[0,T)$ is equipped with the left half-open interval topology, and $\mathbb{R}^d$ is equipped with the usual topology. Since this space is a product of a Lindelöf space and a $\sigma$-compact space, it is Lindelöf itself. Therefore, there exists a countable subcover of $\mathsf{D}$.

I don't like this argument too much, since it involves some topological references I would like to avoid. Therefore, the question:

Is there a simpler/direct argument of Fact 1?

  • $\begingroup$ Actually the formula in Fact 1 should read $$\mathbf{S}\subset \bigcup_{n\ge 1} D(s_n,y_n; r(s_n,y_n)) . $$ $\endgroup$ Nov 10, 2015 at 22:43
  • $\begingroup$ @PietroMajer, actually not. Read the definition of $D(s,y;r)$. $\endgroup$
    – zhoraster
    Nov 11, 2015 at 3:55
  • $\begingroup$ Sorry, am I missing something? It seems to me, points $(0,x)$ in S should belong to cylinders that also include points $(-\epsilon,x)$. $\endgroup$ Nov 11, 2015 at 6:33
  • $\begingroup$ @PietroMajer, I defined $D(s,y;r)$ as a subset of $\mathbf{S}$. This does not matter, of course. $\endgroup$
    – zhoraster
    Nov 11, 2015 at 10:55

1 Answer 1


Let $B_r$ denote the closed ball of radius $r$ centered at $0$ in $\mathbb{R}^d$.

Claim: for any $r>0$ and $\tau <T$ there is a countable subfamily of $D$ that covers $[0,\tau] \times B_r$.

To prove the claim, consider the set $I$ of all $t\in [-\infty, \tau]$ such that $(t, \tau] \times B_r$ is covered by some countable subfamily of $\mathsf{D}$. The set $I$ is not empty (trivially, $\tau$ is in $I$); it is closed, for if $t_j$ is a sequence in $I$ converging to $t$, then also $(t,\tau] \times B_r$ is covered by a countable subfamily of $\mathsf{D}$ (namely, by the countable union of the countable families that covers the sets $(t_j,\tau] \times B_r$, for $j$ in $\mathbb{N}$). Next, we show that $\min I < 0$, which implies the claim.

Notice that for any $0 \le t \le \tau$ there is a finite subfamily of $\mathsf{D}$ which covers the set $\{t \}\times B_r$. Indeed, the traces of the cylinders $D \in \mathsf{D}$ on the compact subspace $\{t \}\times B_r$ are an open ball covering of it. Also note that this finite family of balls also covers $(t',t]\times B_r$ for some $t'<t$. Therefore it can't be the case that $\min I \ge 0 $.

Since for any rational $r>0$ and $\tau<T$ there is a countable subfamily of $D$ that covers of $[0,\tau] \times B_r$, the union of these is a countable covering of $[0,T) \times \mathbb{R}^d$.

  • $\begingroup$ A minor correction was needed: the sentence after "Notice that" is not true for $t=T$, because $\{T\}\times B_r$ is not contained in $\mathbf{S}$ and shouldn't be covered by $\mathsf{D}$. I slightly modified the argument correspondingly. $\endgroup$ Nov 11, 2015 at 6:41
  • 1
    $\begingroup$ I think there was no problem with the former argument, as $T$ belonged to $I$ obviously: the set $(t,T)\times B_r$ is empty for $t=T$. $\endgroup$
    – zhoraster
    Nov 11, 2015 at 11:01
  • $\begingroup$ Yes, that's ok, but as it was stated, in the case $t=T$ we couldn't deduce that a finite family of balls covers $(t',t] \times B_r$ for some $t'<t$ (it should only be true "countable"). $\endgroup$ Nov 11, 2015 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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