Separation in $\mathsf{WKL}_0$

The purpose of this section is to prove the following theorem.

Theorem 3.1   The following is provable in $\mathsf{WKL}_0$. Let X be a separable Banach space. Let A be an open convex set in X, and let B be a separably closed convex set in X. If A and B are disjoint, then A and B can be separated.

Remark 3.2   Theorem 3.1 verifies a conjecture that appeared in [11], page 61. A special case of this result had been conjectured earlier in [12], page 4246. Corollary 5.1.2 of [11] (see also Lemma 4.10 of [12]) is essentially our present Theorem 3.1 with $\mathsf{WKL}_0$ replaced by $\mathsf{ACA}_0$.

Toward the proof of Theorem 3.1, we first prove a separation result for finite-dimensional Euclidean spaces.

Lemma 3.3   The following is provable in $\mathsf{WKL}_0$. Let A and B be compact convex sets in Rⁿ. If A and B are disjoint, then A and B can be strictly separated.

Proof. For $x,y\in{\mathbf{R}}^n$ we denote by $x\cdot y$ the dot product of x and y. The norm on Rⁿ is given by $\Vert x\Vert^2=x\cdot x$. We imitate the argument of Lemma 3.1 of [5].

Put $C=B-A=\{y-x\mid x\in A,\,y\in B\}$. Then C is a compact convex set in Rⁿ. Since $A\cap B=\emptyset$, we have $0\notin C$. The function $z\mapsto\Vert z\Vert$ is continuous on C, so it follows in $\mathsf{WKL}_0$ that there exists $c\in C$ of minimum norm, i.e., $0<\Vert c\Vert\le\Vert z\Vert$ for all $z\in C$.

We claim that $\Vert c\Vert^2\le c\cdot z$ for all $z\in C$. Suppose not. Let $z\in C$ be such that $\Vert c\Vert^2-c\cdot z=\varepsilon>0$. Consider w=tz+(1-t)c where $0<t\le1$. Since C is convex, we have $w\in C$, hence $0<\Vert c\Vert\le\Vert w\Vert$. Expansion of $\Vert w\Vert^2=w\cdot w$ gives

$$\Vert w\Vert^2\,\,=\,\,\Vert c\Vert^2+t^2(\Vert z\Vert^2-\Vert c\Vert^2)-2t(1-t)\varepsilon$$

and from this it follows that $t(\Vert z\Vert^2-\Vert c\Vert^2)\ge 2(1-t)\varepsilon$. Now set

$$t\,=\,\frac\varepsilon{\Vert z\Vert^2-\Vert c\Vert^2+2\varepsilon}$$

and note that $0<t\le1/2$. With this t we have

$$t(\Vert z\Vert^2-\Vert c\Vert^2)\,\,=\,\,\varepsilon-2\vareps... ...\,<\,\,2\varepsilon-2\varepsilon t\,\,=\,\,2(1-t)\varepsilon\,,$$

a contradiction. This proves our claim.

Define $F:{\mathbf{R}}^n\to{\mathbf{R}}$ by $F(z)=c\cdot z$. Since $c\in C=B-A$, we may fix $a\in A$ and $b\in B$ such that c=b-a. Using our claim, it is easy to show that $F(x)\le F(a)<F(b)\le F(y)$ for all $x\in A$ and $y\in B$. Thus A and B are strictly separated.

In order to reduce Theorem 3.1 to the finite-dimensional Euclidean case, we need some technical lemmas.

Lemma 3.4   The following is provable in $\mathsf{WKL}_0$. Let X and K be complete separable metric spaces. Assume that K is compact. If $C\subseteq X\times K$ is closed, then

$$\{x\in X\mid(x,y)\in C\mbox{\textnormal{ for some }}y\in K\}$$

is closed.

Proof. Reasoning in $\mathsf{WKL}_0$, put $V=(X\times K)\setminus C$ and

$$U\,=\,\{x\in X\mid(x,y)\in V\mbox{ for all }y\in K\}\,.$$

We shall prove that U is open.

Since V is open, there is a sequence of open balls B((a_m,b_m),r_m), $(a_m,b_m)\in X\times K$, $r_m\in{\mathbf{Q}}$, $m\in{\mathbf{N}}$, such that

$$V\,=\,\bigcup_{m=0}^\infty B((a_m,b_m),r_m)\,.$$

Since K is compact, there is a sequence of points $y_{ni}\in K$, $i\le k_n$, $n\in{\mathbf{N}}$, such that $K=\bigcup_{i\le k_n}B(y_{i,n},1/2^n)$ for each n.

We claim that

$$\exists n\,\,\,\forall i\le k_n\,\,\,\exists m\,\,\, d((a_m,b_m),(x,y_{ni}))+1/2^n\,<\,r_m$$ (1)

is a necessary and sufficient condition for $x\in U$. Obviously (1) is sufficient since it implies $\{x\}\times K\subseteq\bigcup_{i\le k_n}B((x,y_{ni}),1/2^n)\subseteq V$ whence $x\in U$. For the necessity, let $x\in U$ be given. Then $\{x\}\times K\subseteq\bigcup_{m=0}^\infty B((a_m,b_m),r_m)$. By Heine-Borel compactness of K in $\mathsf{WKL}_0$ it follows that $\{x\}\times K\subseteq\bigcup_{m=0}^k B((a_m,b_m),q_m)$ for some $k\in{\mathbf{N}}$ and finite sequence $q_m\in{\mathbf{Q}}$, $m\le k$, q_m<r_m. Let n be such that $1/2^n<\min_{m\le k}(r_m-q_m)$. Then for each $i\le k_n$ there exists $m\le k$ such that d((a_m,b_m),(x,y_ni))<q_m, hence d((a_m,b_m),(x,y_ni))+1/2ⁿ<r_m. This gives condition (1) and our claim is proved.

Since the condition (1) is $\Sigma^0_1$, it follows by Lemma II.5.7 of [20] that $U\subseteq X$ is open. Therefore, the complementary set is closed. This proves our lemma.

Lemma 3.5   The following is provable in $\mathsf{WKL}_0$. Let X be a separable Banach space. Fix $n\ge1$ and let $Y=\bigcup_{m=1}^n X^m$ be the space of all finite sequences of elements of X of length $\le n$. Then

$$\{s\in Y\mid s\mbox{\textnormal{ is linearly independent}}\}$$

is an open set in Y.

Proof. Consider the compact space $K=\bigcup_{m=1}^n K_m$ where

$$K_m=\{\left\langle\alpha_1,\dots,\alpha_m\right\rangle\mid \vert\alpha_1\vert+\dots+\vert\alpha_m\vert=1\}\,.$$

Here the $\alpha_i$'s are real numbers. Note that $s=\left\langle x_1,\dots,x_m\right\rangle\in Y$ is linearly dependent if and only if $\alpha_1 x_1+\dots+\alpha_m x_m=0$ for some $\left\langle\alpha_1,\dots,\alpha_m\right\rangle\in K$. Hence by Lemma 3.4 the set of all such s is closed. It follows that the complementary set is open.

Lemma 3.6   The following is provable in $\mathsf{WKL}_0$. Let K be a compact metric space, and let $\left\langle C_j\right\rangle_{j\in{\mathbf{N}}}$ be a sequence of nonempty closed sets in K. Then there exists a sequence of points $\left\langle x_j\right\rangle_{j\in{\mathbf{N}}}$ such that $x_j\in C_j$ for all j.

Proof. Since K is compact, there is a sequence of points $x_{ni}\in K$, $i\le k_n$, $n\in{\mathbf{N}}$, such that $K=\bigcup_{i\le k_n}B(x_{in},1/2^n)$ for each $n\in{\mathbf{N}}$. Let S be the bounded tree consisting of all finite sequences $\sigma\in{\mathbf{N}}^{<{\mathbf{N}}}$ such that $\sigma(n)\le k_n$ for all n< the length of $\sigma$. Construct a sequence of trees $T_j\subseteq S$, $j\in{\mathbf{N}}$, such that for each j there is a one-to-one correspondence between infinite paths g in T_j and points $x\in C_j$, the correspondence being given by $x=\lim_nx_{ng(n)}$. For details of the construction of the T_j's, see Section IV.1 of [20].

Let $(-,-):{\mathbf{N}}\times{\mathbf{N}}\to{\mathbf{N}}$ be a primitive recursive pairing function which is onto and monotone in both arguments. Let $T=\bigoplus_{j\in{\mathbf{N}}}T_j$ be the interleaved tree, defined by putting $\tau\in T$ if and only if $\tau_j\in T_j$ for all j, where $\tau_j(n)=\tau((j,n))$. Note that T is a bounded tree, the bounding function $h:{\mathbf{N}}\to{\mathbf{N}}$ being given by h((j,n))=k_n+1. In order to show that T is infinite, we prove that for all m there exists $\tau\in T$ of length m such that for all j and all $n\ge$ length of $\tau_j$, $\tau_j$ has at least one extension of length n in T_j. This $\Pi^0_1$ statement is easily proved by $\Pi^0_1$ induction on m, using the fact that each of the T_j's is infinite.

Since T is an infinite bounded tree, it follows by Bounded König's Lemma in $\mathsf{WKL}_0$ (see Section IV.1 of [20]) that T has an infinite path, f. Then for each j we have an infinite path f_j in T_j given by f_j(n)=f((j,n)). Thus we obtain a sequence of points $\left\langle x_j\right\rangle_{j\in{\mathbf{N}}}$ where $x_j=\lim_n x_{nf_j(n)}$ is a point of C_j.

Lemma 3.7   The following is provable in $\mathsf{WKL}_0$. Let X be a separable Banach space, and let $x_1,\dots,x_n$ be a finite set of elements of X. Then there is a closed subspace $X'=\mbox{\textnormal{span}}(x_1,\dots,x_n)\subseteq X$ consisting of all linear combinations of $x_1,\dots,x_n$. Moreover, there exists a finite set

$$x_{i_1},\dots,x_{i_m}\,,\quad 1\le i_1<\dots<i_m\le n\,,$$

which is a basis of X', i.e., each element of X' is uniquely a linear combination of $x_{i_1},\dots,x_{i_m}$.

Proof. We first prove that X' has a basis. By lemma 3.5, the set of all linearly independent $s\in\bigcup_{m=0}^n X^m$ is open. By bounded $\Sigma^0_1$ comprehension in $\mathsf{WKL}_0$, it follows that

$$\mathcal{I}\,=\,\{I\subseteq\{1,\dots,n\}\mid\{x_i\mid i\in I\}\mbox{ is linearly independent}\}$$

is a finite set of subsets of $\{1,\dots,n\}$. Let $M=\{i_1,\dots,i_m\}$ be a maximal element of $\mathcal{I}$. Then clearly each of $x_1,\dots,x_n$ is a linear combination of $x_{i_1},\dots,x_{i_m}$. Moreover, we can apply Lemma 3.6 to obtain a double sequence of coefficients $\alpha_{ij}$, $i=1,\dots,n$, $j=0,1,\dots,m$, such that

$$\vert\alpha_{i0}\vert+\vert\alpha_{i1}\vert+\dots+\vert\alpha_{im}\vert\,=\,1$$

and

$$\alpha_{i0}x_i+\alpha_{i1}x_{i_1}+\dots+\alpha_{im}x_{i_m}\,=\,0$$

for each $i=1,\dots,n$. Obviously $\alpha_{i0}\ne0$ so we may put $\beta_{ij}=-\alpha_{ij}/\alpha_{i0}$ to obtain

$$x_i\,=\,\beta_{i1}x_{i_1}+\dots+\beta_{im}x_{i_m}$$

for each $i=1,\dots,n$. With this it is clear that every linear combination of $x_1,\dots,x_n$ is uniquely a linear combination of $x_{i_1},\dots,x_{i_m}$.

It remains to prove that X' is a closed subspace of X. As a code for X' we may use Qⁿ identifying $\left\langle q_1,\dots,q_n\right\rangle\in{\mathbf{Q}}^n$ with $q_1x_1+\dots+q_nx_n\in X$. Thus X' is a subspace of X. The fact that X' is closed follows easily from Lemma 3.5.

We are now ready to prove Theorem 3.1.

Proof. [Proof of Theorem 3.1] Reasoning within $\mathsf{WKL}_0$, let X, A, B be as in the hypotheses of Theorem 3.1. We need to prove that A and B can be separated. Since A is open, we may safely assume that

$$\{x\in X\mid\Vert x\Vert\le1\}\subseteq A\,.$$

With this assumption, reasoning in $\mathsf{WKL}_0$, our goal will be to prove the existence of a bounded linear functional $F:X\to{\mathbf{R}}$ such that $F(x)\le1$ for all $x\in A$, and $F(x)\ge1$ for all $x\in B$; these properties easily imply that F(x)<1 for all $x\in A$. Observe also that any such F will necessarily have $\Vert F\Vert\le1$.

Since X is a separable Banach space, there exists a countable vector space D over the rational field Q such that $D\subseteq X$ and D is dense in X. Since B is separably closed, there exists a countable sequence $S\subseteq B$ such that S is dense in B. We may safely assume that $S\subseteq D$. With this assumption, consider the compact product space

$$K\,\,=\,\,\prod_{d\in D}\,\,[-\Vert d\Vert,\Vert d\Vert\,]\,\,.$$

Note that any bounded linear functional $F:X\to{\mathbf{R}}$ with $\Vert F\Vert\le1$ may be identified with a point of K in an obvious way, namely $F=\left\langle F(d)\right\rangle_{d\in D}$. Thus our goal may be expressed as follows: to prove that there exists a point $\left\langle\alpha_d\right\rangle_{d\in D}\in K$ satisfying the conditions

1.

$\alpha_d\le1$ for all $d\in D\cap A$;

2.

$\alpha_d\ge1$ for all $d\in S$;

3.

$\alpha_d=q_1\alpha_{d_1}+q_2\alpha_{d_2}$ for all $d,d_1,d_2\in D$ and $q_1,q_2\in{\mathbf{Q}}$ such that d=q₁d₁+q₂d₂.

Let $\Phi$ be this countable set of $\Pi^0_1$ conditions. By Heine-Borel compactness of K in $\mathsf{WKL}_0$, it suffices to show that each finite subset of $\Phi$ is satisfied by some point of K.

Suppose we are given a finite set of conditions $\Phi'\subseteq\Phi$. Let $a_1,\dots,a_m$ be the elements of $D\cap A$ that are mentioned in $\Phi'$. Let $b_1,\dots,b_n$ be the elements of S that are mentioned in $\Phi'$. Let $d_1,\dots,d_k$ be the nonzero elements of D that are mentioned in $\Phi'$. By Lemma 3.7, let X' be the finite-dimensional subspace of X spanned by $d_1,\dots,d_k$. Let A' be the convex hull of $a_1,\dots,a_m,\pm d_1/\Vert d_1\Vert,\dots,\pm d_k/\Vert d_k\Vert$. Let B' be the convex hull of $b_1,\dots,b_n$. Note that $A'\subseteq A\cap X'$ and $B'\subseteq B\cap X'$; hence $A'\cap B'=\emptyset$. Moreover A' and B' are compact. By Lemmas 3.7 and 3.3, there exists a bounded linear functional $F':X'\to{\mathbf{R}}$ such that $F'(x)\le1$ for all $x\in A'$, and $F'(x)\ge1$ for all $x\in B'$. In particular $F'(\pm d_i/\Vert d_i\Vert)\le1$ for all $i=1,\dots,k$; hence $\vert F'(d_i)\vert\le\Vert d_i\Vert$. Put $\alpha'_d=F'(d)$ for $d=d_1,\dots,d_k$, and $\alpha'_d=0$ for $d\in D\setminus\{d_1,\dots,d_k\}$. Then $\left\langle\alpha'_d\right\rangle_{d\in D}$ is a point of K which satisfies $\Phi'$. This completes the proof.

Remark 3.8   Our proof of a separation theorem in $\mathsf{WKL}_0$ (Theorem 3.1) was accomplished by means of a reduction to the finite-dimensional Euclidean case using a compactness argument. This proof technique is not entirely new (see [13]) but does not seem to be widely known.