Next: Reversal via Hahn-Banach Up: Separation and Weak König's Previous: Preliminaries

# Separation in

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

Theorem 3.1   The following is provable in . 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 replaced by .

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 . Let A and B be compact convex sets in Rn. If A and B are disjoint, then A and B can be strictly separated.

Proof. For we denote by the dot product of x and y. The norm on Rn is given by . We imitate the argument of Lemma 3.1 of [5].

Put . Then C is a compact convex set in Rn. Since , we have . The function is continuous on C, so it follows in that there exists of minimum norm, i.e., for all .

We claim that for all . Suppose not. Let be such that . Consider w=tz+(1-t)c where . Since C is convex, we have , hence . Expansion of gives

and from this it follows that . Now set

and note that . With this t we have

a contradiction. This proves our claim.

Define by . Since , we may fix and such that c=b-a. Using our claim, it is easy to show that for all and . 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 . Let X and K be complete separable metric spaces. Assume that K is compact. If is closed, then

is closed.

Proof. Reasoning in , put and

We shall prove that U is open.

Since V is open, there is a sequence of open balls B((am,bm),rm), , , , such that

Since K is compact, there is a sequence of points , , , such that for each n.

We claim that

 (1)

is a necessary and sufficient condition for . Obviously (1) is sufficient since it implies whence . For the necessity, let be given. Then . By Heine-Borel compactness of K in it follows that for some and finite sequence , , qm<rm. Let n be such that . Then for each there exists such that d((am,bm),(x,yni))<qm, hence d((am,bm),(x,yni))+1/2n<rm. This gives condition (1) and our claim is proved.

Since the condition (1) is , it follows by Lemma II.5.7 of [20] that is open. Therefore, the complementary set is closed. This proves our lemma.

Lemma 3.5   The following is provable in . Let X be a separable Banach space. Fix and let be the space of all finite sequences of elements of X of length . Then

is an open set in Y.

Proof. Consider the compact space where

Here the 's are real numbers. Note that is linearly dependent if and only if for some . 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 . Let K be a compact metric space, and let be a sequence of nonempty closed sets in K. Then there exists a sequence of points such that for all j.

Proof. Since K is compact, there is a sequence of points , , , such that for each . Let S be the bounded tree consisting of all finite sequences such that for all n< the length of . Construct a sequence of trees , , such that for each j there is a one-to-one correspondence between infinite paths g in Tj and points , the correspondence being given by . For details of the construction of the Tj's, see Section IV.1 of [20].

Let be a primitive recursive pairing function which is onto and monotone in both arguments. Let be the interleaved tree, defined by putting if and only if for all j, where . Note that T is a bounded tree, the bounding function being given by h((j,n))=kn+1. In order to show that T is infinite, we prove that for all m there exists of length m such that for all j and all length of , has at least one extension of length n in Tj. This statement is easily proved by induction on m, using the fact that each of the Tj's is infinite.

Since T is an infinite bounded tree, it follows by Bounded König's Lemma in (see Section IV.1 of [20]) that T has an infinite path, f. Then for each j we have an infinite path fj in Tj given by fj(n)=f((j,n)). Thus we obtain a sequence of points where is a point of Cj.

Lemma 3.7   The following is provable in . Let X be a separable Banach space, and let be a finite set of elements of X. Then there is a closed subspace consisting of all linear combinations of . Moreover, there exists a finite set

which is a basis of X', i.e., each element of X' is uniquely a linear combination of .

Proof. We first prove that X' has a basis. By lemma 3.5, the set of all linearly independent is open. By bounded comprehension in , it follows that

is a finite set of subsets of . Let be a maximal element of . Then clearly each of is a linear combination of . Moreover, we can apply Lemma 3.6 to obtain a double sequence of coefficients , , , such that

and

for each . Obviously so we may put to obtain

for each . With this it is clear that every linear combination of is uniquely a linear combination of .

It remains to prove that X' is a closed subspace of X. As a code for X' we may use Qn identifying with . 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 , 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

With this assumption, reasoning in , our goal will be to prove the existence of a bounded linear functional such that for all , and for all ; these properties easily imply that F(x)<1 for all . Observe also that any such F will necessarily have .

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

Note that any bounded linear functional with may be identified with a point of K in an obvious way, namely . Thus our goal may be expressed as follows: to prove that there exists a point satisfying the conditions
1.
for all ;
2.
for all ;
3.
for all and such that d=q1d1+q2d2.
Let be this countable set of conditions. By Heine-Borel compactness of K in , it suffices to show that each finite subset of is satisfied by some point of K.

Suppose we are given a finite set of conditions . Let be the elements of that are mentioned in . Let be the elements of S that are mentioned in . Let be the nonzero elements of D that are mentioned in . By Lemma 3.7, let X' be the finite-dimensional subspace of X spanned by . Let A' be the convex hull of . Let B' be the convex hull of . Note that and ; hence . Moreover A' and B' are compact. By Lemmas 3.7 and 3.3, there exists a bounded linear functional such that for all , and for all . In particular for all ; hence . Put for , and for . Then is a point of K which satisfies . This completes the proof.

Remark 3.8   Our proof of a separation theorem in (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.

Next: Reversal via Hahn-Banach Up: Separation and Weak König's Previous: Preliminaries
Stephen G Simpson
1998-10-25