DEFINABLE VERSIONS OF THEOREMS BY KIRSZBRAUN AND HELLY

MATTHIAS ASCHENBRENNER AND ANDREAS FISCHER

Abstract. Kirszbraun’s Theorem states that every Lipschitz map S → ℝ^{n}, where S ⊆ ℝ^{m}, has an extension to a Lipschitz map ℝ^{m} → ℝ^{n} with the same Lipschitz constant. Its proof relies on Helly’s Theorem: every family of compact subsets of ℝ^{n}, having the property that each of its subfamilies consisting of at most n + 1 sets share a common point, has a non-empty intersection. We prove versions of these theorems valid for definable maps and sets in arbitrary definably complete expansions of ordered fields.

Introduction

Let L be a non-negative real number and let f: S → ℝ^{n}, S ⊆ ℝ^{m}, be an L-Lipschitz map, i.e., ||f(x) − f(y)|| ≤ L ||x − y|| for all x, y ∈ S. It was noted by McShane and Whitney independently (1934) that if n = 1, then f extends to an L-Lipschitz function ℝ^{m} → ℝ. This immediately implies that for general n, there always exists a \sqrt{n} L-Lipschitz map F: ℝ^{m} → ℝ^{n} with F |S = f. A seminal result proved by Kirszbraun (1934) shows that in fact, the multiplicative constant \sqrt{n} is redundant: there is an L-Lipschitz map F: ℝ^{m} → ℝ^{n} such that F |S = f. This theorem plays an important role in geometric measure theory (see [13]) and has been generalized in many ways, e.g., to more general moduli of continuity and arbitrary Hilbert spaces (see [3, Theorem 1.12]). The usual proofs of theorems of this kind in the literature employ, in some form or other, the Axiom of Choice. (See, e.g., [3, 5, 13, 15, 20].) This prompted Chris Miller to ask: suppose f as before is semialgebraic; is there a semialgebraic L-Lipschitz map ℝ^{m} → ℝ^{n} extending f? More generally:

Let ℜ be an o-minimal expansion of a real closed ordered field R, and let f: S → R^{n}, S ⊆ R^{m}, be definable in ℜ and L-Lipschitz (where L ∈ R, L ≥ 0). Does f admit an extension to an L-Lipschitz map R^{m} → R^{n} which is definable in ℜ?

Here and below, “definable” means “definable, possibly with parameters.” Questions like these are of interest since many (but not all [22]) properties familiar from real analysis and topology hold for sets and functions definable in o-minimal structures, even if the underlying ordered set is different from the real line. See [8] for this, and basic definitions concerning o-minimal structures.

It is easy to see that the question above has a positive answer in the case n = 1 by the McShane-Whitney construction alluded to above (see Proposition 5.3 below) and also if the domain S of f is convex (see Proposition 5.4). In this paper we answer Miller’s question positively in general. In fact, o-minimality may be replaced by a weaker assumption. For the rest of this introduction, we fix an expansion ℜ = (R, 0, 1, +, · , <, …) of a real closed ordered field, and “definable” means “definable in ℜ.” One says that ℜ is definably complete if every non-empty definable subset of R which is bounded from above has a least upper bound in R. (See Section 1.1 below for more on this notion.) Our first main result is the following:

Date: June 2009.

Theorem A. Suppose ℜ is definably complete. Let L ∈ R, L ≥ 0, and let f: S → R^{n}, where S ⊆ R^{m}, be a definable L-Lipschitz map. Then there exists a definable L-Lipschitz map F: R^{m} → R^{n} such that F |S = f.

It turns out that definable completeness is indeed necessary for the conclusion of Theorem A to hold, see Proposition 5.2 below. The extension F of f in the theorem can additionally be chosen to depend uniformly on parameters, see Corollary 5.13.

The proof of Theorem A is based on a recent constructive approach to Kirszbraun’s Theorem due to Bauschke and Wang [1, 2] using the proximal average of convex functions. This is the culmination of a long train of thought (going back at least to Minty [28]) relating Lipschitz maps to monotone set-valued maps. It is remarkable that the arguments of loc. cit. may be transferred in a straightforward way to the setting of definable complete expansions of ordered fields, with the exception of an interesting property of definable families: In general, a family C of closed balls in R^{n} with the finite intersection property may have empty intersection; however (and perhaps, somewhat surprisingly), if ℜ is definably complete and the family C is definable, then ⋂ C ≠ ∅. More precisely, we have the following result:

Theorem B. Suppose ℜ is definably complete. Let C be a definable family of closed bounded convex subsets of R^{n}. If any collection of at most n + 1 sets from C has a non-empty intersection, then C has a non-empty intersection.

This theorem is a definable analogue of a classical theorem of Helly (1913) on families of compact convex subsets of ℝ^{n}. In the standard proofs of this theorem (e.g., as given in [39]), one first reduces to the case of a finite family by a topological compactness argument, which is unavailable in the more general context considered here. Thus we were forced to find a different proof which adapts to infinite definable families. (See [5, 11] for the history and numerous variants of Helly’s Theorem.)

Note that the theorem fails trivially if the assumptions “closed” or “bounded” are dropped, as suitable definable families of intervals in R show. Definable completeness of ℜ is also necessary in this case: if ℜ has the property that every infinite definable family of closed bounded convex subsets of R with empty intersection contains two disjoint members, then ℜ is definably complete. It may also be worth noting that the natural definable analogue of the Heine-Borel Theorem (a definable set S ⊆ R^{n} is closed and bounded if and only if every definable family of closed subsets of S with the finite intersection property has a non-empty intersection) fails if the ordered field R is non-archimedean. (See Section 3.2.)

Organization of the paper. Many of the basic properties of convex sets in ℝ^{n} (as presented in, say, [34, 39]) hold in the setting of a definably complete expansion of an ordered field, provided attention is restricted to definable convex sets. After a preliminary Section 1, we develop some of these properties in Section 2, restricting ourselves to what is necessary for the proof of Theorems A and B. We give the proof of Theorem B and some applications of this theorem in Section 3. In Section 3.2 we also present another proof of Theorem B valid in the case where ℜ is o-minimal, due to S. Starchenko (and based on results by Dolich and Peterzil-Pillay). In Section 4 we establish a few basic results of convex analysis in the definably complete setting, and in Section 5 we prove Theorem A. In Section 6 we discuss some variants of Theorem A: a weak version of Kirszbraun’s Theorem for Lipschitz maps which are locally definable in expansions of the ordered field of real numbers, and the extension problem for uniformly continuous definable maps.

Acknowledgments. We thank Chris Miller for many discussions around the topics of this paper, and Sergei Starchenko for permission to include the argument in Section 3.2. This paper was partially written while both authors were participating in the thematic program on O-minimal Structures and Real Analytic Geometry at the Fields Institute in Toronto in 2009. The support of this institution is gratefully acknowledged. The first author was also partially supported by a grant from the National Science Foundation.

Conventions and notations. We let k, m, n, range over the set ℕ = {0, 1, 2, … } of natural numbers. “Definable” means “definable, possibly with parameters.”

Let R be a real closed ordered field. We equip R with the order topology, and each R^{n} with the corresponding product topology. Given a subset S of R^{n} we write int(S) for the interior, cl(S) for the closure, and bd(S) = cl(S) \ int(S) for the boundary of S. We write the dot product of x = (x_{1}, …, x_{n}) ∈ R^{n} and y = (y_{1}, …, y_{n}) ∈ R^{n} as

⟨x, y⟩ = x_{1}y_{1} + ⋯ + x_{n}y_{n},

and we set ||x|| := \sqrt{⟨x, x⟩}. For ϱ > 0 and x ∈ R^{n} we write

B_{ϱ}(x) := \{y ∈ R^{n} : ||x − y|| < ϱ\}, \overline{B}_{ϱ}(x) := \{y ∈ R^{n} : ||x − y|| ≤ ϱ\}

for the open respectively closed ball in R^{n} with radius ϱ and center x. A set S ⊆ R^{n} is said to be bounded if S ⊆ B_{ϱ}(0) for some ϱ > 0.

For a, b ∈ R we put [a, b] := {x ∈ R : a ≤ x ≤ b}. For S ⊆ R and a ∈ R we set S^{>a} := {r ∈ S : r > a} and similarly with other inequality symbols in place of “>.” We extend the linear ordering of R to a linear ordering of R_{±∞} = R ∪ {−∞, +∞} such that −∞ < R < +∞. We assume the usual rules for addition and multiplication with ±∞. We also set R_{∞} = R∪{+∞}. We say that a function f: S → R_{±∞} (where S ⊆ R^{n}) is finite at x ∈ S if f(x) ∈ R, and we simply say that f is finite if it is finite at every x ∈ S.

1. Preliminaries

This section contains material which is fundamental for the following sections. In Sections 1.1 and 1.2 we collect basic properties of definably complete expansions of ordered fields. In Section 1.4 we discuss Lipschitz maps, and Section 1.5 contains a useful fact about Minkowski sums of closed sets.

1.1. Definable completeness. Let ℜ be an expansion of an ordered field R. One says that ℜ is definably complete if every non-empty definable subset of R which is bounded from above has a least upper bound in R. Clearly then every non-empty definable subset of R which is bounded from below has a greatest lower bound in R. Moreover, if ℜ is definably complete, then the field R is necessarily real closed. For a proof of this fact see [26], where further basic properties of definably complete structures were developed. In particular, the following characterization of definable completeness is proved in [26, Corollary 1.5].

Proposition 1.1. The following are equivalent:

(1) ℜ is definably complete.

(2) Every continuous definable function f: [a, b] → R has the intermediate value property: for each y ∈ R between f(a) and f(b) there is some x ∈ [a, b] with y = f(x).

(3) Intervals in R are definably connected.

(4) R is definably connected.

(Recall that a set S ⊆ R^{n} is said to be definably connected if for all definable open sets U, V ⊆ R^{n} with S = (S ∩ U) ∪ (S ∩ V) and S ∩ U ∩ V = ∅, we have S ⊆ U or S ⊆ V.)

The notion of definable completeness is intended to capture the first-order content of Dedekind completeness: indeed, every expansion of the ordered field of real numbers is definably complete, and every structure elementarily equivalent to a definably complete structure is definably complete [26, Section 3]. Definable completeness is connected to o-minimality: If ℜ is o-minimal, then ℜ is definably complete. (In fact, it is enough to require that the open core ℜ^{∘} of ℜ is o-minimal.) If ℜ is o-minimal, and R′ is a proper dense subset of R which is the underlying set of an elementary substructure of ℜ, then (ℜ, R′) is definably complete, by [9]. However, definable completeness is sufficiently far removed from o-minimality to warrant independent interest: by results in [7, 27], ℜ is o-minimal if and only if ℜ is definably complete, every definable subset of R is constructible (i.e., a finite boolean combination of open sets), and there is no definable subset of R which is both infinite and discrete.

In the rest of this section we assume that ℜ is definably complete.

Notation. We say that A ⊆ R_{±∞} is definable if A ∩ R is definable. With this convention, every non-empty definable subset A of R_{±∞} has a least upper bound in R_{±∞}, which we denote by sup A, and A has a greatest lower bound in R_{±∞}, denoted by inf A. We also set sup ∅ := −∞ and inf ∅ := +∞.

We have a weak version of definable choice [26, Proposition 1.8]:

Lemma 1.2. Let C = {C_{a}}_{a∈A}, where A ⊆ R^{n}, be a definable family of non-empty closed and bounded subsets of R^{m}. Then there is a definable map f: A → R^{m} such that f(a) ∈ C_{a} for every a ∈ A.

Many facts familiar from set-theoretic topology in ℝ continue to hold for ℜ, provided attention is restricted to the definable category. In the following we collect some of those properties. The first one [26, Lemma 1.9] (which follows from Lemma 1.2) captures a crucial feature of compact subsets of ℝ^{n}:

Lemma 1.3. Let C = {C_{a}}_{a∈A}, where A ⊆ R, be a definable family of non-empty closed bounded subsets of R^{n} which is monotone, i.e., either C_{a} ⊆ C_{b} for all a, b ∈ A with a ≤ b, or C_{a} ⊇ C_{b} for all a, b ∈ A with a ≤ b. Then ⋂ C ≠ ∅.

Note that this lemma implies a special case of Theorem B for monotone definable families of closed bounded sets (without the assumption of convexity).

Proposition 1.4. Let f: S → R^{n} be definable and continuous, where S ⊆ R^{m}. If S is closed and bounded, then so is f(S).

This is [26, Proposition 1.10]. As an immediate consequence, one has:

Corollary 1.5. Let f: S → R be definable and continuous, where S ⊆ R^{m} is closed and bounded. Then f achieves a minimum and a maximum on S.

1.2. Definable Bolzano-Weierstrass Theorem. For our investigations it is useful to have a counterpart of the Bolzano-Weierstrass Theorem from classical analysis, concerning infinite sequences in compact subsets of ℝ^{n}. In o-minimal geometry, this counterpart is described by the Curve Selection Lemma, which is not available in the definably complete situation.

Definition. Let γ: I → R^{n} be a definable function, where I ⊆ R^{>0} is unbounded. We call such a function γ a sequence-function. A sequence-function γ′: I′ → R^{n} is said to be a subsequence-function of γ if I′ ⊆ I and γ′ = γ|I′. We say that γ converges if a = lim_{t→∞, t∈I} γ(t) exists, and in this case, we say that γ converges to

a. An element a of R^{n} such that there is a subsequence function γ′ of γ converging to a is called an accumulation point of γ.

Proposition 1.6 (Definable Bolzano-Weierstrass Theorem). Let S ⊆ R^{n} be a closed and bounded definable set. Then every sequence-function γ: I → S has an accumulation point in S.

Proof. Let γ: I → S be a sequence-function. In the following let ε, ε′ and t range over R^{>0}. For every t put S_{t} := cl(γ(I^{>t})), a closed and bounded non-empty definable subset of S. By Lemma 1.3 we have ⋂_{t} S_{t} ≠ ∅. Let a ∈ ⋂_{t} S_{t}; we claim that a is an accumulation point of γ. To see this, note that by choice of a, for every ε the definable set

I_{ε} := {t ∈ I : ∥γ(t) − a∥ < ε}

is unbounded, hence I_{ε} ∩ R^{≥1/ε} ≠ ∅. For each ε put

t_{ε} := inf (I_{ε} ∩ R^{≥1/ε}) ∈ R^{>0}, s_{ε} := t_{ε} + 1.

So for every ε there exists t ∈ I_{ε} with 1/ε ≤ t ≤ s_{ε}, hence the definable subset

I′ := {t : ∃ε (t ∈ I_{ε} & t ≤ s_{ε})}

of I is unbounded. Moreover, if ε′ ≤ ε then s_{ε′} ≥ s_{ε}. Let ε be given, and let t ∈ I′ with t > s_{ε}. Then there is some ε′ with t ∈ I_{ε′} and t ≤ s_{ε′}. Then ε > ε′ and hence t ∈ I_{ε}. This shows that a = lim_{t→∞, t∈I′} γ(t). □

1.3. Moduli of continuity. Let f: S → R^{n} be a definable map, where S ⊆ R^{m} is non-empty. Then the modulus of continuity ω_{f}: R^{≥0} → R_{∞} of f is given by

ω_{f}(t) := sup {||f(x) − f(y)|| : x, y ∈ S, ||x − y|| ≤ t}.

The function ω_{f} is definable and increasing with ω_{f} ≥ 0, and f is uniformly continuous if and only if ω_{f}(t) → 0 as t → 0^{+}. If f is bounded, then ω_{f} is finite.

Lemma 1.7. Suppose f is uniformly continuous. Then f extends uniquely to a continuous map F: cl(S) → R^{n}. This extension is again definable, with

ω_{f}(t) ≤ ω_{F} (t) ≤ inf_{t′>0} ω_{f}(t′ + t) for all t > 0.

In particular, F remains uniformly continuous.

Proof. Uniqueness is easy to see (and only needs continuity of f). For existence, take δ > 0 such that the restriction of ω_{f} to the interval A := (0, δ) is finite. Let x_{0} ∈ cl(S); we introduce a definable family C = C(x_{0}) as follows: For t ∈ A let

C_{t} := ⋂_{x∈\overline{B}_{t}(x_{0})∩S} \overline{B}_{ω_{f} (t)}(f(x));

then C = {C_{t}}_{t∈A} is a decreasing definable family of non-empty closed bounded subsets of R^{m}. By Lemma 1.3, we have ⋂ C ≠ ∅. Note that this intersection is a singleton: if y ≠ y′ are both in C, take t ∈ A such that ω_{f}(t) < \frac{1}{2}||y − y′||; then for every x ∈ \overline{B}_{t}(x_{0}) ∩ S we have ||y − f(x)|| ≤ ω_{f}(t) and ||y′ − f(x)|| ≤ ω_{f}(t), hence ||y − y′|| ≤ 2ω_{f}(t), a contradiction. Therefore we have a definable map F: cl(S) → R^{m} which sends x_{0} ∈ cl(S) to the unique element in ⋂ C(x_{0}). Clearly the map F extends f, and hence ω_{f} ≤ ω_{F}. Let t > 0 and x_{0}, x_{1} ∈ cl(S) with ||x_{0} − x_{1}|| ≤ t be given. For every t′ with 0 < t′ < δ − t we find y_{0}, y_{1} ∈ S with ||x_{0} − y_{0}|| ≤ t′/2 and ||x_{1} − y_{1}|| ≤ t′/2, and so ||y_{0} − y_{1}|| ≤ t + t′; then

||F (x_{0}) − F (x_{1})|| ≤ ||F (x_{0}) − f(y_{0})|| + ||f(y_{0}) − f(y_{1})|| + ||F (x_{1}) − f(y_{1})||
≤ ω_{f}(t′) + ω_{f}(t′ + t) + ω_{f}(t′).

The inequality for the moduli of continuity now follows by letting t′ → 0. □

As over ℝ we have uniform continuity of definable continuous maps with closed and bounded domain, as shown in the next lemma. (The classical proof of this fact uses the finite subcover property of compact sets.) Notice that by Corollary 1.5, definable, closed and bounded non-empty subsets D and E of R^{m} have a common point if and only if d(D, E) = 0, where d(D, E) := inf { ∥x − y∥ : x ∈ D, y ∈ E} is the distance between D and E.

Lemma 1.8. Suppose S is closed and bounded, and f is continuous. Then f is uniformly continuous.

Proof. Note that ω_{f} is finite since f is bounded, cf. Proposition 1.4. We shall show that ω_{f}(t) → 0 as t → 0^{+}. Assume, for a contradiction, that ε > 0 is such that ω_{f}(t) ≥ ε for arbitrarily small positive t. Then D := {(x, y) ∈ S × S : ∥f(x) − f(y)∥ ≥ ε} and E := {(x, x) : x ∈ S} are disjoint definable closed and bounded non-empty sets with d(D, E) = 0, a contradiction. □

We say that a function ω: R^{≥0} → R_{∞} is a modulus of continuity of f if ω_{f} ≤ ω. The following is easy to show; we skip the proof:

Lemma 1.9. Let ω: R^{≥0} → R^{≥0} be definable, and let {f_{a}}_{a∈A} be a definable family of functions f_{a}: S → R with modulus of continuity ω. If the function

x ↦ inf_{a∈A} f_{a}(x): S → R ∪ {−∞}

is finite at one point of S, then it is finite with modulus of continuity ω. Similarly, if the function

x ↦ sup_{a∈A} f_{a}(x): S → R ∪ {+∞}

is finite at one point of S, then it is finite with modulus of continuity ω.

1.4. Lipschitz maps. Let f: S → R^{n} be a definable map, where S ⊆ R^{m} is nonempty. Given L ∈ R^{≥0}, we say that f is L-Lipschitz if ||f(x) − f(y)|| ≤ L||x − y|| for all x, y ∈ S. We call f Lipschitz if f is L-Lipschitz for some L ∈ R^{≥0}. Every Lipschitz map is uniformly continuous; in fact, given L ∈ R^{≥0}, f is L-Lipschitz if and only if t ↦ Lt is a modulus of continuity of f. Consequently, if f is L-Lipschitz, then f extends uniquely to a continuous map cl(S) → R^{n}, and this map is also L-Lipschitz, by Lemma 1.7.

We use non-expansive synonymously for 1-Lipschitz. By the triangle inequality, for every y ∈ R^{n} the function

x ↦ d(x, y) := ||x − y||: R^{n} → R

is non-expansive. From Lemma 1.9 we therefore obtain:

Corollary 1.10. For every definable subset S of R^{n}, the distance function

x ↦ d(x, S) := inf {d(x, y) : y ∈ S}: R^{n} → R

is non-expansive.

The set S in the previous corollary was not assumed to be closed. However, in this context one may often reduce to the case of a closed set, since d(x, S) = d(x, cl(S)) for every definable set S ⊆ R^{n} and every x ∈ R^{n}. For closed sets we have, as a consequence of Corollary 1.5:

Corollary 1.11. Suppose S is closed and definable. Then for every x ∈ R^{n} there is a nearest point of S to x, that is, a point y_{0} ∈ S such that d(x, y_{0}) = d(x, S).

Proof. Let x ∈ R^{n}. Choose ϱ > 0 such that the closed and bounded definable set S ∩ \overline{B}_{ϱ}(x) is non-empty. By Corollary 1.5 the function y ↦ d(x, y) attains a minimum on this set, say at y_{0}; then y_{0} is a nearest point of S to x. □

The following concept plays an important role in the proof of Theorem A below.

Definition. A map f: S → R^{n}, where S ⊆ R^{n}, is called firmly non-expansive if

∥f(x) − f(y)∥^{2} ≤ ⟨f(x) − f(y), x − y⟩ for all x, y ∈ S.

The Cauchy-Schwarz Inequality implies that every firmly non-expansive map is non-expansive. We also have the following fact, well-known in classical convex analysis (see, e.g., [15, Theorem 12.1]):

Proposition 1.12. Let S ⊆ R^{n}. Then f ↦ \frac{1}{2}(f + id) is a bijection from the set of non-expansive maps S → R^{n} to the set of firmly non-expansive maps S → R^{n}.

Proof. For x, y ∈ S consider

a(x, y) := \frac{1}{4} ∥x − y∥^{2} + \frac{1}{2}⟨f(x) − f(y), x − y⟩ + \frac{1}{4} ∥f(x) − f(y)∥^{2}
= ∥\frac{1}{2}(x + f(x)) − \frac{1}{2}(y + f(y))∥^{2}

and

b(x, y) := \frac{1}{2} ∥x − y∥^{2} + \frac{1}{2} ⟨f(x) − f(y), x − y⟩
= ⟨\frac{1}{2}(x + f(x)) − \frac{1}{2}(y + f(y)), x − y⟩ .

Then x ↦ \frac{1}{2}(x + f(x)) is firmly non-expansive if and only if a(x, y) ≤ b(x, y) for all x, y ∈ S. Moreover, for given x, y ∈ S, the inequality a(x, y) ≤ b(x, y) holds if and only if ∥f(x) − f(y)∥ ≤ ∥x − y∥. □

1.5. Minkowski sum. Let A and B be subsets of R^{n}. We denote the (Minkowski) sum of A and B by

A + B = {a + b : a ∈ A, b ∈ B}.

If both A and B are closed, then A + B is not necessarily closed, as the example

A = {0} × R, B = {(x, y) ∈ R^{2} : xy ≥ 1, x ≥ 0}

shows. The following fact is used in Section 3.1.

Lemma 1.13. Let A, B ⊆ R^{n} be definable, and suppose A is closed, and B is closed and bounded. Then A + B is closed.

Proof. Let z ∈ cl(A + B). Then for every ε > 0 the definable closed set

C_{ε} := {(a, b) ∈ A × B : ||a + b − z|| ≤ ε}

is non-empty. Note that each C_{ε} is bounded: if (a, b) ∈ C_{ε} then ||a|| ≤ ||a+b−z||+ ||b − z|| ≤ ε + ϱ + ||z|| where ϱ > 0 is such that B ⊆ B_{ϱ}(0). Hence by Lemma 1.3 we have ⋂_{ε>0} C_{ε} ≠ ∅, showing that z ∈ A + B. □

2. Basic Properties of Convex Sets

In this section, ℜ is an expansion of an ordered field R. Recall: A ⊆ R^{n} is convex if for all x, y ∈ A we have [x, y] ⊆ A. Here and below, for x, y ∈ R^{n} we write

[x, y] = {λx + (1 − λ)y : 0 ≤ λ ≤ 1}

for the line segment in R^{n} connecting x and y. (We also use analogous notation for the half-open line segments (x, y] and [x, y).) If A, B are convex, then so are A + B and λA = {λa : a ∈ A}, where λ ∈ R.

2.1. Theorems of Carathéodory, Radon, and Helly. The intersection of an arbitrary family of convex subsets of R^{n} is convex. In particular, the intersection of all convex subsets of R^{n} which contain a given set A ⊆ R^{n} is a convex set containing A, called the convex hull conv(A) of A. As in the case R = ℝ (cf., e.g., [39, Theorem 2.2.2]), one shows that conv(A) is the set of convex combinations of elements of A, that is, the set of x ∈ R^{n} for which there are x_{1}, …, x_{k} ∈ R^{n} and λ_{1}, …, λ_{k} ∈ R^{≥0} such that x = ∑_{i} λ_{i}x_{i} and ∑_{i} λ_{i} = 1. In fact, only convex combinations of n + 1 elements of A need to be considered:

Lemma 2.1 (Carathéodory’s Theorem). Let A be a subset of R^{n}, and let x ∈ conv(A). Then x is a convex combination of affinely independent points in A. In particular, x is a convex combination of at most n + 1 points in A.

This is also shown just as for R = ℝ, cf. [39, Theorem 2.2.4]. We record some consequences of this lemma. First, an obvious yet important observation:

Corollary 2.2. The convex hull of every definable subset of R^{n} is definable.

Clearly the convex hull of a bounded subset of R^{n} is bounded. The union of a line and a point not on it shows that the convex hull of a closed definable set need not be closed. However, we have:

Corollary 2.3. Let A ⊆ R^{n}. Then conv(cl(A)) ⊆ cl(conv(A)). Moreover, if ℜ is definably complete and A is definable and bounded, then conv(cl(A)) = cl(conv(A)); in particular, the convex hull of every closed and bounded definable set is closed.

Proof. It is easy to see that the closure of a convex set is convex; this yields conv(cl(A)) ⊆ cl(conv(A)). Now suppose ℜ is definably complete and A is definable and bounded. Then the set

C := {(λ_{1}, …, λ_{n+1}, x_{1}, …, x_{n+1}) : λ_{i} ≥ 0, x_{i} ∈ cl(A), ∑_{i=1}^{n+1} λ_{i} = 1}

of R^{(n+1)^{2}} is definable, closed, and bounded. Hence by Proposition 1.4 its image under the definable continuous map

(λ_{1}, …, λ_{n+1}, x_{1}, …, x_{n+1}) ↦ ∑_{i=1}^{n+1} λ_{i}x_{i} ∈ R^{n}

is also closed and bounded. By Carathéodory’s Theorem, this image is equal to conv(cl(A)). Thus cl(conv(A)) ⊆ cl(conv(cl(A)) = conv(cl(A)). □

The next fact is also shown as in the case R = ℝ; cf. [39, Theorem 2.2.5].

Lemma 2.4 (Radon’s Lemma). Each finite set of affinely dependent points in R^{n} is a union of two disjoint sets whose convex hulls have a common point.

As for R = ℝ, Radon’s Lemma implies Theorem B in the case of a finite family of convex sets; see [39, Theorem 7.1.1] for a proof. Given a family F = {F_{i}}_{i∈I} of sets, we say that F has the n-intersection property if F_{i_{1}} ∩ ⋯ ∩ F_{i_{n}} ≠ ∅ for all i_{1}, …, i_{n} ∈ I, and we say that F has the finite intersection property if F has the n-intersection property for some n.

Corollary 2.5 (Helly’s Theorem for finite families). Let A_{1}, …, A_{k} ⊆ R^{n} be convex. If {A_{i}}_{i=1,...,k} has the (n + 1)-intersection property, then A_{1} ∩ ⋯ ∩ A_{k} ≠ ∅.

The following consequence for arbitrary families of convex sets is perhaps wellknown, but we could not locate it in the literature:

Corollary 2.6. Let C = {C_{a}}_{a∈A} be a family of convex subsets of R^{n}, and suppose p_{1}, …, p_{k} ∈ R^{n} have the property that for all a_{1}, …, a_{n+1} ∈ A there is some i ∈ {1, …, k} such that p_{i} ∈ C_{a_{1}} ∩ ⋯ ∩ C_{a_{n+1}}. Then ⋂ C ≠ ∅.

Proof. Let P = {p_{1}, …, p_{k}}. Then P = {conv(C_{a} ∩ P)}_{a∈A} is a family of convex subsets of R^{n} with only finitely many distinct members, and by assumption, P has the (n + 1)-intersection property. Hence ∅ ≠ ⋂ P ⊆ ⋂ C by Corollary 2.5. □

2.2. Convex functions. Let f: S → R_{±∞}, where S ⊆ R^{n}. The epigraph of f is the set

epi(f) = {(x, t) ∈ R^{n} × R : x ∈ S, t ≥ f(x)}.

We say that f is convex if epi(f) is a convex subset of R^{n+1}, and we say that f is concave if −f is convex. Clearly if f is convex, then its domain

dom(f) = {x ∈ S : f(x) < +∞}

is a convex subset of R^{n}, since dom(f) = π(epi(f)) where π: R^{n+1} → R^{n} is the natural projection onto the first n coordinates. We say that f is proper if epi(f) is non-empty and contains no vertical lines, i.e., f(x) < +∞ for some x ∈ S and f(x) > −∞ for all x ∈ S. Otherwise, f is called improper.

Example 2.7. Suppose S is a convex subset of R^{n} and f(x) > −∞ for all x ∈ S. Then f is convex if and only if for all x, y ∈ S and λ ∈ [0, 1] we have

f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y) for all λ ∈ [0, 1],

where this inequality is interpreted in R_{∞}. If f is finite and convex, then extending f by setting f(x) := +∞ for x ∈ R^{n} \ S yields a convex function R^{n} → R_{∞} (and every proper convex function R^{n} → R_{∞} arises in this way from the restriction to its domain). For example, the constant function 0 on S extends to a convex function δ_{S}: R^{n} → R_{∞} with δ_{S}|(R^{n} \ S) ≡ +∞, called the indicator function of S.

We say that f is definable if the restriction of f to the set f^{−1}(R) of points at which f is finite is definable (as function f^{−1}(R) → R). Similarly, a family {f_{a}}_{a∈A} of functions f_{a}: S_{a} → R_{±∞} (where A ⊆ R^{m} and S_{a} ⊆ R^{n} for every a ∈ A) is called definable if the family {f_{a}|f_{a}^{−1}(R)}_{a∈A} is definable.

2.3. Constructing convex functions. Throughout the rest of this section, we assume that ℜ is definably complete. The following lemma (which is easy to verify) shows in particular that the pointwise supremum of a definable family of convex functions is convex:

Lemma 2.8. Let f: R^{n} → R_{±∞}, and let {f_{a}}_{a∈A} be a definable family of functions f_{a}: R^{n} → R_{±∞}. Then

f = sup_{a∈A} f_{a} ⟺ epi(f) = ⋂_{a∈A} epi(f_{a}).

The next lemma is also easily proved; it allows the construction of convex functions from fibers of definable convex sets:

Lemma 2.9. Let C be a convex definable subset of R^{n+1}. Then f: R^{n} → R_{±∞} defined by f(x) = inf C_{x} is convex with domain π(C), where π: R^{n+1} → R^{n} is the projection onto the first n coordinates.

Let now f: R^{n} → R_{±∞} be definable, and let A: R^{n} → R^{m} be R-linear. We denote the definable function

x ↦ inf {f(y) : A(y) = x}: R^{m} → R_{±∞}

by Af. Applying the lemma above to C = (A × id)(epi(f)) yields:

Lemma 2.10. Suppose f is convex. Then Af is convex with domain A(dom(f)).

Let f, g: R^{n} → R_{∞} be definable. The (infimal) convolution f □ g: R^{n} → R_{±∞} of f and g is defined by

(f □ g)(x) := inf_{y∈R^{n}} (f(y) + g(x − y)) for x ∈ R^{n}.

By the previous lemma, if f and g are convex, then f □ g is convex, with domain dom(f) + dom(g). (However, if f and g are proper, f □ g may fail to be proper, as the example f = id_{R}, g = − id_{R} shows.) Note that for every x ∈ R^{n},

(f □ g)(x) = inf {s + t : (y, s) ∈ epi(f), (z, t) ∈ epi(g), y + z = x}

and hence

(2.1)  epi(f) + epi(g) ⊆ epi(f □ g) ⊆ cl(epi(f) + epi(g)).

2.4. The distance function and the metric projection. After this digression on convex functions, we return to the study of convex sets. For the rest of this section we fix a non-empty convex closed definable subset C of R^{n}. Recall that the distance from x ∈ R^{n} to C is defined by

d(x, C) = inf {||x − c|| : c ∈ C}.

We have:

Lemma 2.11. The function x ↦ d(x, C): R^{n} → R is convex.

Proof. The function d( · , C) may be expressed as the convolution of the Euclidean norm and the indicator function of C. □

Lemma 2.12. For every x ∈ R^{n}, there is a unique element of C of smallest distance to x.

Proof. We have existence by Corollary 1.11. For uniqueness, let x ∈ R^{n}, and suppose y_{1}, y_{2} ∈ C are both nearest points of C to x. Then z := \frac{1}{2}(y_{1} + y_{2}) ∈ C and ||x − z|| < ||x − y_{1}|| except if y_{1} = y_{2}. □

Given x ∈ R^{n}, we denote the unique nearest point to x in C by p(x, C). The map x ↦ p(x, C): R^{n} → S is called the (metric) projection of C. Note that

d(x, C) = ||x − p(x, C)|| = min {||x − y|| : y ∈ C}.

Lemma 2.13. For all x ∈ R^{n} and z ∈ C we have

⟨x − p(x, C), z − p(x, C)⟩ ≤ 0.

Proof. Let x ∈ R^{n}, z ∈ C, and put p := p(x, C). For 0 < λ ≤ 1 set z_{λ} := λ z + (1 − λ) p. Then z_{λ} ∈ C and hence

∥x − p∥^{2} ≤ ∥x − z_{λ}∥^{2} = ∥(x − p) + λ(z − p)∥^{2} .

Subtracting ∥x − p∥^{2} yields 0 ≤ λ^{2} ∥z − p∥^{2} − 2λ⟨x − p, z − p⟩. Dividing by λ and taking λ → 0 yields the lemma. □

Corollary 2.14. The projection p( · , C) is firmly non-expansive.

Proof. Let x, y ∈ R^{n}; we need to show that

⟨x − y, p(x, C) − p(y, C)⟩ ≥ ∥p(x, C) − p(y, C)∥^{2} .

To see this apply Lemma 2.13 to (x, p(y, C)) and (y, p(x, C)) in place of (x, z), respectively, and add the resulting inequalities. □

The following lemma is used in the proof of Theorem B in the next section:

Lemma 2.15. Suppose C is bounded, and let x ∈ R^{n} \ C, p = p(x, C), and z ∈ (x, p]. Then there is a δ > 0 such that ||z − c|| ≤ ||x − c|| − δ for every c ∈ C.

Proof. Suppose not. Then for every δ > 0 the set

C_{δ} := {c ∈ C : ||z − c|| ≥ ||x − c|| − δ}

is non-empty, and so we have a decreasing definable family {C_{δ}}_{δ>0} of closed and bounded non-empty sets. Hence by Lemma 1.3 there is some c ∈ C with ||z − c|| ≥ ||x − c||. Let a be the point of smallest distance to c on the line through x and p. Then Pythagoras yields ||a − z|| ≥ ||a − x||, a contradiction to x ≠ z. □

2.5. Supporting hyperplanes. Given p, u ∈ R^{n}, u ≠ 0, and α ∈ R we write

H_{u,p} = {y ∈ R^{n} : ⟨y, u⟩ = ⟨p, u⟩}

for the hyperplane in R^{n} through p orthogonal to u. Note that if ⟨p, u⟩ = ⟨p′, u⟩ then H_{u,p} = H_{u,p′}, and we sometimes write H_{u,α} for H_{u,p}, where α = ⟨p, u⟩. Given a hyperplane H = H_{u,α}, we write

H^{+} = {y ∈ R^{n} : ⟨y, u⟩ ≥ α}, H^{−} = {y ∈ R^{n} : ⟨y, u⟩ ≤ α}

for the two closed halfspaces bounded by H.

Let S ⊆ R^{n}. Given a hyperplane H = H_{u,α} and a point x ∈ R^{n}, we say that H supports S at x if x ∈ S ∩ H and S ⊆ H^{+} or S ⊆ H^{−}. (In this case necessarily x ∈ bd(S).)

Lemma 2.16. Let x ∈ R^{n} \ C. The hyperplane H = H_{u,p} through p = p(x, C) orthogonal to u = x − p supports C at p, and C is contained in the halfspace H^{−} bounded by H which does not contain x.

Proof. By Lemma 2.13 and since x ≠ p, for every y ∈ C we have ⟨y, x − p⟩ ≤ ⟨x − p, p⟩ < ⟨x, x − p⟩, and this yields the lemma. □

In particular, the previous lemma implies that if C ≠ R^{n}, then C is the intersection of all closed halfspaces which contain C.

Corollary 2.17. For each p ∈ bd(C) there exists some y ∈ bd(B_{1}(p)) with p = p(y, C). Hence for every p ∈ bd(C) there is a hyperplane that supports C at p.

Proof. Let p ∈ bd(C). For every ε with 0 < ε < 1 there is some x ∈ \overline{B}_{ε}(p) \ C; then ||p − p(x, C)|| ≤ ||p − x|| < ε by Corollary 2.14, and since the distinct points x and p(x, C) are in B_{1}(p), there is a (unique) y on the sphere S := bd(B_{1}(p)) with x ∈ [p(x, C), y]. By Lemma 2.16 we have p(x, C) = p(y, C). This means that for every ε > 0 the definable set

S_{ε} := \{y ∈ S : \overline{B}_{ε}(p) ∩ [p(y, C), y] ≠ ∅\}

is non-empty. It is easily verified that each S_{ε} is closed and bounded. By Lemma 1.3 take y ∈ ⋂_{ε>0} S_{ε}. Then for every ε > 0 there is some x ∈ [p(y, C), y] with ||x−p|| ≤ ε; hence ||p(y, C) − p|| = ||p(x, C) − p|| ≤ ||x − p|| ≤ ε. Thus p = p(y, C). □

Remark. The existence of a supporting hyperplane through every boundary point characterizes convex sets among definable closed subsets of R^{n} with non-empty interior; this can be shown as in the case R = ℝ, see, e.g., [34, Theorem 1.3.3].

2.6. Separating hyperplanes. Let A, B ⊆ R^{n} and let H = H_{u,α} be a hyperplane. We say that H separates A and B if A ⊆ H^{−} and B ⊆ H^{+}, or vice versa. If there is a hyperplane separating A and B, we say that A and B can be separated.

Proposition 2.18. Let S ⊆ R^{n} be definable and non-empty, and let x ∈ R^{n} \ S. Suppose S is closed, or S is open. Then S and {x} can be separated.

To see this we use:

Lemma 2.19. Let A ⊆ R^{n} be convex with non-empty interior. Then int(cl(A)) = int(A) and hence bd(A) = bd(cl(A)).

Proof. The inclusion int(A) ⊆ int(cl(A)) is trivial. Conversely, let z ∈ int(cl(A)). Take an arbitrary x ∈ int(A). Then there exists y ∈ cl(A) such that z ∈ [x, y). As in the case R = ℝ (cf. [34, Lemma 1.1.8]) one shows that this implies z ∈ int(A). □

Proof (Proposition 2.18). Suppose first that S is closed, and set p = p(x, S), u = x − p. Then the hyperplane which is parallel to the supporting hyperplane H_{u,p} of S at p and passes through (p + x)/2 separates S and {x}. If S is not closed and x ∉ cl(S), then every hyperplane separating cl(S) and {x} also separates S and {x}. If S is open and x ∈ cl(S), then x ∈ bd(cl(S)), so by Corollary 2.17 there is a supporting hyperplane H to cl(S) through x, and H separates S and {x}. □

We obtain a definable version of a special case of the separation theorem for convex sets [39, Theorem 2.4.10]:

Corollary 2.20. Let A, B ⊆ R^{n} be definable non-empty convex sets with A∩B = ∅. If A is open, or if A is closed and B is closed and bounded, then A and B can be separated.

Proof. The convex set S := A − B does not contain the origin 0 of R^{n}. If A is open, then so is S, and if A is closed and B is closed and bounded, then S is closed (Lemma 1.13). Hence S and {0} can be separated by Proposition 2.18. It is easy to see that this yields that A and B can be separated. □

3. Proof of Theorem B

Suppose that ℜ is a definably complete expansion of an ordered field, and let C = {C_{a}}_{a∈A} be a definable family of closed bounded convex subsets of R^{n}, with A ≠ ∅. Assume C has the (n + 1)-intersection property; we need to show ⋂ C ≠ ∅. Fix an arbitrary a_{0} ∈ A. By Helly’s Theorem for finite families (Corollary 2.5), the definable family C′ = {C_{a} ∩ C_{a_{0}}}_{a∈A} of closed bounded convex subsets of R^{n} also has the (n + 1)-intersection property. Hence, after replacing C by C′ if necessary, we may assume that ⋃_{a∈A} C_{a} is bounded. In particular, for each x ∈ R^{n}, the set of distances d(x, C_{a}) (where a ranges over A) is bounded from above, and we obtain a definable function d: R^{n} → R given by

d(x) := sup_{a∈A} d(x, C_{a}).

The function d is convex and non-expansive. (Lemmas 1.9 and 2.8, and Corollary 1.10.) In particular, for ϱ > 0 such that B_{ϱ/2}(0) ⊇ ⋃_{a∈A} C_{a}, the restriction of d to \overline{B}_{ϱ}(0) has a minimum. (Corollary 1.5.) This minimum must be attained in B_{ϱ}(0), and is indeed a global minimum of d. Let x_{0} ∈ R^{n} such that d(x_{0}) = min_{x∈R^{n}} d(x). If d(x_{0}) = 0 then x_{0} ∈ ⋂_{a∈A} C_{a}, and we are done. So assume d(x_{0}) > 0. We obtain a definable map

a ↦ x_{a} := p(x_{0}, C_{a}): A → ⋃_{a} C_{a}.

We have ||x_{0} − x_{a}|| = d(x_{0}, C_{a}) for each a ∈ A. Let ε > 0 be given. The definable set

A_{ε} := {a ∈ A : d(x_{0}) − ε ≤ d(x_{0}, C_{a})}

is non-empty. We let H be the image of A_{ε} under a ↦ x_{a}, and put C := cl(conv(H)). (There is no reason to believe that conv(H) is closed, unless, for example, A_{ε} is finite.)

Claim. x_{0} ∈ C.

Proof. Suppose for a contradiction that x_{0} ∉ C. Let p = p(x_{0}, C), and let z ∈ [x_{0}, p] such that ||x_{0} − z|| = ε/2. We show that d(z) < d(x_{0}); this will contradict the minimality of d(x_{0}). If a ∉ A_{ε}, then d(x_{0}) − ε > d(x_{0}, C_{a}), and since d( · , C_{a}) is non-expansive, we have

d(z, C_{a}) − d(x_{0}, C_{a}) ≤ ||z − x_{0}|| = ε/2

and hence

d(z, C_{a}) ≤ ε/2 + (d(x_{0}) − ε) = d(x_{0}) − ε/2.

Let δ > 0 be as in Lemma 2.15 applied to x = x_{0}. Then for all a ∈ A_{ε} we have

d(z, C_{a}) ≤ ||z − x_{a}|| ≤ ||x_{0} − x_{a}|| − δ = d(x_{0}, C_{a}) − δ ≤ d(x_{0}) − δ.

Hence d(z) ≤ d(x_{0}) − min(ε/2, δ). □

By the claim and Carathéodory’s theorem there are elements a_{1}, …, a_{n+1} ∈ A_{ε} and non-negative λ_{1}, …, λ_{n+1} ∈ R with ∑_{i} λ_{i} = 1 and ||x_{0} − ∑_{i} λ_{i}x_{a_{i}}|| < ε^{2}. By Lemma 2.16, for y ∈ C_{a_{i}} we have

⟨y − x_{0}, x_{a_{i}} − x_{0}⟩ ≥ ||x_{a_{i}} − x_{0}||^{2},

and since

||x_{a_{i}} − x_{0}|| = d(x_{0}, C_{a_{i}}) ≥ d(x_{0}) − ε,

we obtain

(3.1)  ⟨y − x_{0}, x_{a_{i}} − x_{0}⟩ ≥ (d(x_{0}) − ε)^{2}.

Take y with y ∈ C_{a_{i}} for all i. (Such y exists by the assumption of the theorem.) Then using (3.1) and the Cauchy-Schwarz Inequality we get

(d(x_{0}) − ε)^{2} ≤ ∑_{i} λ_{i}⟨y − x_{0}, x_{a_{i}} − x_{0}⟩

= ⟨y − x_{0}, ∑_{i} λ_{i}x_{a_{i}} − x_{0}⟩

≤ ||y − x_{0}|| · ε^{2} ≤ r · ε^{2},

where r > 0 is such that conv(⋃_{a∈A} C_{a}) ⊆ \overline{B}_{r}(x_{0}). Hence (\frac{d(x_{0})}{ε} − 1)^{2} ≤ r, and this is a contradiction for sufficiently small ε > 0. □

Remark. The proof of Theorem B given above exploits a certain duality between the intersection properties of convex sets and the representation of elements in the convex hull. After a first version of this manuscript was completed, we became aware of Sandgren’s proof of Helly’s Theorem [33] (in the exposition of Valentine [38]) in which this duality is made more explicit. This proof may probably be adapted to give another proof of Theorem B above.

3.1. Applications. In this subsection we give some applications of Theorem B. Throughout we assume that ℜ is a definably complete expansion of an ordered field. By a translate of A ⊆ R^{n} we mean a set of the form x+A, for some x ∈ R^{n}. The following generalizes Theorem B (which corresponds to the case where K is a singleton):

Corollary 3.1. Let C = {C_{a}}_{a∈A} be a definable family of closed bounded convex subsets of R^{n}, and let K ⊆ R^{n} be definable, closed, bounded and convex. If any n + 1 elements of C intersect some translate of K non-trivially, then there is a translate of K intersecting every element of C non-trivially.

Proof. Recall Lemma 1.13 and apply Theorem B to the family {K − C_{a}}_{a∈A}. □

Combining Helly’s Theorem for finite families (Corollary 2.5) with Theorem B yields another slight variant:

Corollary 3.2. Suppose C is a definable family of closed convex subsets of R^{n}, each n + 1 of which intersect non-trivially, and assume some intersection C of finitely many members of C is bounded. Then ⋂ C ≠ ∅.

By taking complements, Theorem B about intersections of closed sets immediately gives rise to a result about coverings by open sets:

Corollary 3.3. Let F = {F_{a}}_{a∈A} be a definable family of open subsets of R^{n} with the property that for every a ∈ A, the complement R^{n} \ F_{a} is convex. Let C be a closed bounded convex definable subset of R^{n} with C ⊆ ⋃ F. Then there are n + 1 members F_{a_{1}}, …, F_{a_{n+1}} of F with C ⊆ F_{a_{1}} ∪ ⋯ ∪ F_{a_{n+1}}.

The hypotheses on F are satisfied, e.g., by the family of open halfspaces in R^{n}.

Corollary 3.4 (Jung’s Theorem). Let A be a definable subset of R^{n} of diameter at most 1 (i.e., ||a − b|| ≤ 1 for all a, b ∈ A). Then there is a closed ball of radius ϱ = \sqrt{n/(2(n + 1))} containing A.

Proof. If A has at most n+1 elements, this may be shown as for R = ℝ, cf. [39, Theorem 7.1.6]. Hence for arbitrary A, by Theorem B there is some x ∈ ⋂_{a∈A} \overline{B}_{ϱ}(a), and then A ⊆ \overline{B}_{ϱ}(x). □

Given a subset A of R^{n}, a family {C_{a}}_{a∈A} of subsets of A is called a Knaster-Kuratowski-Mazurkiewicz family (KKM family for short) if for every finite subset F of A,

conv(F) ⊆ ⋃_{a∈F} C_{a}.

The KKM Theorem (see [17, 16]) states that if A is a non-empty compact convex subset of ℝ^{n}, then every KKM family consisting of closed subsets of A has a nonempty intersection. From Theorem B we obtain:

Corollary 3.5 (KKM Theorem for definable families of convex sets). Let A be a closed and bounded non-empty subset of R^{n} and let C = {C_{a}}_{a∈A} be a KKM family where each C_{a} is closed and convex. Then ⋂ C ≠ ∅.

Proof. The argument in the proof of [17, Théorème 1] for the case R = ℝ shows that C has the finite intersection property. Hence ⋂ C ≠ ∅ by Theorem B. □

The KKM Theorem for convex sets has numerous consequences (minimax theorems etc.), whose proofs go through for definable objects; cf. [17, 16]. Other applications of Helly’s Theorem, some of which may also be transferred into the present context, can be found in [5, 11]. Our last application of Theorem B is used in the proof of Theorem A in the next sections:

Corollary 3.6. Let f: A → R^{n}, A ⊆ R^{n}, be a definable non-expansive map, and let x ∈ R^{n} \ A. Then f extends to a non-expansive map A ∪ {x} → R^{n}.

Proof. We have to show that the set

B := ⋂_{a∈A} {y ∈ R^{n} : ∥y − f(a)∥ ≤ ∥x − a∥}

is non-empty, because if y ∈ B, then we obtain an extension of f to a non-expansive map A ∪ {x} → R^{n} by x ↦ y.

Claim. Let x_{1}, …, x_{k} ∈ R^{m} and y_{1}, …, y_{k} ∈ R^{n} for which the inequalities

∥y_{i} − y_{j}∥ ≤ ∥x_{i} − x_{j}∥ (1 ≤ i, j ≤ k)

hold, and let r_{1}, …, r_{k} ∈ R^{>0}. If

\overline{B}_{r_{1}}(x_{1}) ∩ ⋯ ∩ \overline{B}_{r_{k}}(x_{k}) ≠ ∅,

then

\overline{B}_{r_{1}}(y_{1}) ∩ ⋯ ∩ \overline{B}_{r_{k}}(y_{k}) ≠ ∅.

(To see this, repeat the proof for the case R = ℝ given in [20, Lemma 2.7], or use the fact that the claim can be expressed as a sentence in the language of ordered rings, and apply Tarski’s Transfer Principle and loc. cit. A stronger version of the claim for R = ℝ can be found in [18].)

Consider the definable family B = (B_{a})_{a∈A} of closed balls in R^{n} given by

B_{a} := \overline{B}_{||x−a||}(f(a)) = \{y ∈ R^{n} : ∥y − f(a)∥ ≤ ∥x − a∥ \}.

Let a_{1}, …, a_{n+1} ∈ A. Then y_{i} := f(a_{i}) and x_{i} := x−a_{i} satisfy the conditions of the claim, hence B_{a_{1}} ∩ ⋯ ∩ B_{a_{n+1}} ≠ ∅. Thus by Theorem B we have B = ⋂ B ≠ ∅. □

Remark. In the context of the previous corollary, suppose that f is firmly nonexpansive. Then there exists an extension of f to a firmly non-expansive map A ∪ {x} → R^{n}, by the corollary and Proposition 1.12.

3.2. A related result. Let S be a set and let F be a family of subsets of S. A subset T of S is called a transversal of F if every member of F intersects T nontrivially. The following was shown by Peterzil and Pillay [30], as an application of a result implicit in work of Dolich [6]:

Theorem 3.7. Let ℜ be an o-minimal structure with definable choice function, and let F = {F_{a}}_{a∈A} be a definable family of closed and bounded subsets of R^{n} parametrized by a subset A of R^{m}. If F has the N(m, n)-intersection property where

N(m, n) = (1 + 2^{m}) · (1 + 2^{2^{m}}) ⋯ (n factors),

then F has a finite transversal.

This theorem gives rise to another proof of Theorem B, kindly communicated to us by S. Starchenko, in the case where ℜ is an o-minimal expansion of an ordered field. Suppose ℜ is such an expansion, and let C = {C_{a}}_{a∈A} be a definable family of closed bounded convex subsets of R^{n}, with A ≠ ∅, having the (n + 1)- intersection property. By Helly’s theorem for finite families (Corollary 2.5), the (definable) family whose members are the intersections of n + 1 members of C has the finite intersection property, and hence has a finite transversal by Theorem 3.7.

That is, there are p_{1}, …, p_{k} ∈ R^{n} such that for all a_{1}, …, a_{n+1} ∈ A we have p_{i} ∈ C_{a_{1}} ∩ ⋯ ∩ C_{a_{n+1}} for some i. Now Corollary 2.6 yields ⋂ C ≠ ∅. □

We finish with an example to show that the natural analogue of the Heine-Borel Theorem fails in the definable category:

Example 3.8. Suppose ℜ is a non-archimedean real closed field, and let ε ∈ R be a positive infinitesimal. Then the definable family F = {F_{a}}_{a∈A} of closed and bounded subsets of A = [0, 1] given by F_{a} = [0, 1] \ (a − ε, a + ε) for a ∈ A has the finite intersection property, but ⋂ F = ∅. However, any two distinct elements of A ∩ ℚ form a transversal of F. (This is a simplification of an example in [30].)

4. Basic Convex Analysis

In this section we develop a few fundamental results from convex analysis required for the proof of Theorem A. See [4, 21, 32] for this material in the classical case.

4.1. Lower semicontinuous functions. In this subsection we let f: R^{n} → R_{±∞} be a function. One says that f is lower semicontinuous (l.s.c.) if for each x ∈ R^{n} and δ > 0, there exists ε > 0 such that f(y) ≥ f(x) − δ for all y ∈ B_{ε}(x). A continuous function R^{n} → R is clearly l.s.c. Lower semicontinuity may be characterized geometrically:

Lemma 4.1. The following are equivalent:

(1) f is l.s.c.;

(2) epi(f) is closed;

(3) for every r ∈ R, the sublevel set f^{−1}(R^{≤r}) = {x ∈ R^{n} : f(x) ≤ r} of f is closed.

Proof. Suppose f is l.s.c., and let (x, r) ∈ cl(epi(f)). Let δ > 0 be given, and choose ε with 0 < ε ≤ δ as in the definition of l.s.c. above. There exists (y, t) ∈ epi(f) with ||x − y|| < ε and ||r − t|| < ε. Hence

r + δ > t ≥ f(y) ≥ f(x) − δ.

Since this inequality holds for all δ > 0, we obtain r ≥ f(x), that is, (x, r) ∈ epi(f). This shows (1) ⇒ (2). The implication (2) ⇒ (3) follows from the identity

f^{−1}(R^{≤r}) × {r} = epi(f) ∩ (R^{n} × {r}).

Suppose all sublevel sets of f are closed, and let x ∈ R^{n} and δ > 0 be given. Then x ∉ f^{−1}(R^{≤r}), where r := f(x) − δ if f(x) < ∞ and r := 0 otherwise. Hence there exists ε > 0 such that y ∉ f^{−1}(R^{≤r}) for all y ∈ B_{ε}(x). Thus f is l.s.c. □

For proper convex functions R^{n} → R_{∞}, we use closed synonymously with l.s.c., and we also declare the constant functions +∞ and −∞ to be closed. Note that if f, g: R^{n} → R_{∞} are closed convex, then so is λf + μg, for each λ, μ ∈ R^{≥0}.

The following proposition is an analogue for definable convex functions of the supporting hyperplane lemma (Lemma 2.16). It is proved similar to the case R = ℝ, see [21, Proposition IV.1.2.8] or [32, Theorem 12.1]. A function φ: R^{n} → R of the form x ↦ ⟨x, u⟩ − α (where u ∈ R^{n}, α ∈ R) is called affine. Alternatively, φ is affine if and only if φ is both convex and concave. The epigraph of an affine function R^{n} → R is a closed halfspace in R^{n+1}. Below we let φ (possibly with subscripts) range over all affine functions R^{n} → R.

Proposition 4.2. Suppose f is definable. The following are equivalent: (1) f is closed convex;

(2) f = sup {φ : φ ≤ f};

(3) f = sup_{a∈A} φ_{a} for some definable family of affine functions {φ_{a}}_{a∈A}.

Proof. The implication (2) ⇒ (3) is trivial, and (3) ⇒ (1) follows from Lemma 2.8. To show (1) ⇒ (2), suppose f is closed convex. We may assume that f is proper, so epi(f) is a proper non-empty closed convex definable subset of R^{n+1}. Hence epi(f) is the intersection of all closed halfspaces containing epi(f). (Lemma 2.16.) As in the case R = ℝ one now shows that only the hyperplanes corresponding to epigraphs of affine functions are required in this intersection; cf. proof of [21, Proposition IV.1.2.8]. (The reference to [21, Proposition 1.2.1] in that proof is superfluous.) □

4.2. Conjugates. Let f: R^{n} → R_{±∞} be definable. The (Fenchel) conjugate of f is the definable function f^{∗}: R^{n} → R_{±∞} given by

f^{∗}(x^{∗}) := sup_{x∈R^{n}} (⟨x, x^{∗}⟩ − f(x)).

Note that if there is x_{0} ∈ R^{n} with f(x_{0}) = −∞, then f^{∗} ≡ +∞, whereas if f ≡ +∞ then f^{∗} ≡ −∞. Clearly if g: R^{n} → R_{±∞} is another definable function and f ≤ g, then f^{∗} ≥ g^{∗}. We summarize further properties of conjugates in the next lemma:

Lemma 4.3. Let f: R^{n} → R_{±∞} be definable. Then:

(1) The function f^{∗} is closed convex.

(2) We have f^{∗∗} := (f^{∗})^{∗} ≤ f, with equality if and only if f is closed convex.

(3) If f is proper closed convex, then f^{∗} is proper, and ⟨x, x^{∗}⟩ ≤ f(x) + f^{∗}(x^{∗}) for all x, x^{∗} ∈ R^{n}. (Fenchel-Young Inequality.)

Proof. Clearly f^{∗} is closed convex, being the supremum of a definable family of affine functions. This shows (1), and also that f is closed convex if f^{∗∗} = f. It is easy to check that f^{∗∗} ≤ f, with equality if f is an affine function R^{n} → R. Hence if f is closed convex, then for every affine function φ: R^{n} → R with φ ≤ f we have φ = φ^{∗∗} ≤ f^{∗∗} ≤ f. Thus f^{∗∗} = f by Proposition 4.2. This shows (2). Note that (2) implies that if f is proper closed convex, then f^{∗} is proper, since the only improper closed convex functions are +∞ and −∞, which are conjugate to each other. The Fenchel-Young Inequality is now immediate. □

Given λ ∈ R^{>0} we define

λ ∗ f: R^{n} → R_{±∞}, (λ ∗ f)(x) = λf(x/λ) for x ∈ R^{n}.

Note that if f and g: R^{n} → R_{∞} are definable and proper, then λ ∗ (f □ g) = (λ ∗ f) □ (λ ∗ g). The formulas in the following lemma are useful for computing conjugates.

Lemma 4.4. Let f, g: R^{n} → R_{∞} be definable and convex.

(1) For all λ > 0, we have (λf)^{∗} = λ ∗ f^{∗} and (λ ∗ f)^{∗} = λf^{∗}.

(2) Let A: R^{n} → R^{m} be R-linear. Then (Af)^{∗} = f^{∗} ∘A^{∗}, where A^{∗}: R^{m} → R^{n} is the adjoint of A. In particular, (f □ g)^{∗} = f^{∗} + g^{∗}.

(3) Suppose

f(x) = g(x − a) + ⟨x, a^{∗}⟩ + α for all x ∈ R^{n},

where a, a^{∗} ∈ R^{n} and α ∈ R. Then

f^{∗}(x^{∗}) = g^{∗}(x^{∗} − a^{∗}) + ⟨x^{∗}, a⟩ + α^{∗} for all x^{∗} ∈ R^{n},

where α^{∗} = −α − ⟨a, a^{∗}⟩.

Proof. Part (1) is easily verified by direct computation. For (2) see [40, Theorem 2.3.1, (ix)], and for (3) see [32, Theorem 12.3]. □

If g: R^{n} → R_{±∞} is definable and concave (so −g is convex), then the conjugate of g is the definable function g^{∗}: R^{n} → R_{±∞} given by

g^{∗}(x^{∗}) := inf_{x∈R^{n}} (⟨x, x^{∗}⟩ − g(x)) = −(−g)^{∗}(−x^{∗}).

Next we show a definable version of the Fenchel Duality Theorem [32, Theorem 31.1] in a special case:

Proposition 4.5. Let f: R^{n} → R_{∞} be definable proper convex, and let g: R^{n} → R be definable continuous concave. Then

inf_{x∈R^{n}} (f(x) − g(x)) = max_{x^{∗}∈R^{n}} (g^{∗}(x^{∗}) − f^{∗}(x^{∗})).

Proof. For all x, x^{∗} ∈ R^{n} we have

f(x) + f^{∗}(x^{∗}) ≥ ⟨x, x^{∗}⟩ ≥ g(x) + g^{∗}(x^{∗})

by Fenchel-Young, hence inf_{x} (f(x) − g(x)) ≥ sup_{x^{∗}} (g^{∗}(x^{∗}) − f^{∗}(x^{∗})). Set α := inf_{x} (f(x) − g(x)); we may assume α > −∞. It now suffices to show that there exists x^{∗} ∈ R^{n} such that g^{∗}(x^{∗}) − f^{∗}(x^{∗}) ≥ α. Consider the non-empty definable convex sets

A := epi(f), B := {(x, t) ∈ R^{n+1} : t < g(x) + α}.

Then B is open, and A ∩ B = ∅. Hence by Corollary 2.20 there exists a hyperplane H in R^{n+1} separating A and B. If H were vertical, i.e., of the form H = H′ × R for some hyperplane H′ in R^{n}, then H′ would separate dom(f) and R^{n}, which is impossible. Therefore H is the graph of an affine function x ↦ ⟨x, x^{∗}⟩ − α^{∗} (x^{∗} ∈ R^{n}, α^{∗} ∈ R). Then for all x ∈ R^{n} we have

f(x) ≥ ⟨x, x^{∗}⟩ − α^{∗} ≥ g(x) + α.

This yields α = (α^{∗} + α) − α ≤ g^{∗}(x^{∗}) − f^{∗}(x^{∗}) as required. □

4.3. Examples of conjugates. The functions discussed in the following examples will be of constant use below.

Example 4.6. The function x ↦ q(x) := \frac{1}{2} ∥x∥^{2} : R^{n} → R is the only definable closed convex function R^{n} → R_{∞} such that q^{∗} = q.

Proof. To see that q is convex use the identity

∥λx + μy∥^{2} = λ ∥x∥^{2} + μ ∥y∥^{2} − λμ ∥x − y∥^{2}

which holds for all x, y ∈ R^{n} and λ, μ ∈ R^{≥0} with λ + μ = 1. Since q is continuous, q is closed. Let f: R^{n} → R_{∞} be definable closed convex such that f^{∗} = f. Then f is proper, and by Fenchel’s Inequality ⟨x, x⟩ ≤ f(x) + f^{∗}(x) = 2f(x), thus f ≥ q and hence f = f^{∗} ≤ q^{∗} = q, so f = q. □

Example 4.7. The conjugate of the convex function κ: R^{n} × R^{n} → R given by κ(x, y) := q(x − y) is the function κ^{∗}: R^{n} × R^{n} → R_{∞} given by

κ^{∗}(x^{∗}, y^{∗}) = \begin{cases}q(x^{∗}), & if x^{∗} = −y^{∗}, \\ +∞, & otherwise. \end{cases}

Proof. Suppose that x^{∗} ≠ −y^{∗}. Then ∥x^{∗} + y^{∗}∥ > 0, hence

κ^{∗}(x^{∗}, y^{∗}) = sup_{(x,y)} (⟨(x^{∗}, y^{∗}), (x, y)⟩ − \frac{1}{2} ∥x − y∥^{2})

\underbrace{≥}_{x=y=t(x^{∗}+y^{∗})} sup_{t} ⟨(x^{∗}, y^{∗}), t(x^{∗} + y^{∗}, x^{∗} + y^{∗})⟩ = sup_{t} t ∥x^{∗} + y^{∗}∥^{2} = ∞.

We also have

\frac{1}{2} ∥x^{∗}∥^{2} = ⟨(x^{∗}, −x^{∗}), (x^{∗}, 0)⟩ − \frac{1}{2} ∥x^{∗} − 0∥^{2} ≤ κ^{∗}(x^{∗}, −x^{∗})

and

κ^{∗}(x^{∗}, −x^{∗}) = sup_{(x,y)} (⟨(x^{∗}, −x^{∗}), (x, y)⟩ − \frac{1}{2} ∥x − y∥^{2})

= sup_{(x,y)} (⟨x^{∗}, x − y⟩ − \frac{1}{2} ∥x − y∥^{2})

≤ sup_{(x,y)} (∥x^{∗}∥ ∥x − y∥ − \frac{1}{2} ∥x − y∥^{2})

\underbrace{=}_{∥x−y∥=t∥x^{∗}∥} sup_{t} ∥x^{∗}∥^{2} (t − \frac{t^{2}}{2} ) = \frac{1}{2} ∥x^{∗}∥^{2} ,

hence κ^{∗}(x^{∗}, −x^{∗}) = \frac{1}{2} ∥x^{∗}∥^{2}. □

Example 4.8. The function Δ: R^{n}×R^{n} → R given by Δ(x, y) := q(x+y) = κ(x, −y) is convex and continuous. Note that Δ satisfies the useful identity

Δ(x, y) = \frac{1}{2} ∥x∥^{2} + ⟨x, y⟩ + \frac{1}{2} ∥y∥^{2} .

Fix (a, b) ∈ R^{n} × R^{n} and define δ: R^{n} × R^{n} → R by

δ(x, y) := Δ(a − x, b − y) − ⟨x, y⟩.

Let (x^{∗}, y^{∗}) ∈ R^{n} × R^{n}. Then

δ^{∗}(x^{∗}, y^{∗}) = δ(−y^{∗}, −x^{∗}).

Proof. We have

δ(x, y) = q((x, y) − (a, b)) − ⟨(x, y), (b, a)⟩ + ⟨a, b⟩

and hence by Lemma 4.4, (3):

δ^{∗}(x^{∗}, y^{∗}) = q^{∗}((x^{∗}, y^{∗}) + (b, a)) + ⟨(x^{∗}, y^{∗}), (a, b)⟩ + ⟨a, b⟩

= q((−y^{∗}, −x^{∗}) − (a, b)) − ⟨(−y^{∗}, −x^{∗}), (b, a)⟩ + ⟨a, b⟩ = δ(−y^{∗}, −x^{∗}).

□

The following observations about κ are used in the next subsection:

Lemma 4.9. Let g: R^{n} → R_{∞} be definable proper closed convex, and let λ ∈ R^{>0} and x ∈ R^{n}. Then

inf_{y} g(y) + κ(x, λy) = min_{y} g(y) + κ(x, λy).

Proof. By Proposition 4.2, there is an affine function φ: R^{n} → R such that φ ≤ g. So the definable function h: R^{n} → R_{∞}, h(y) := g(y) + κ(x, λy) is closed convex such that lim_{∥y∥→+∞} h(y) = +∞. Take some z ∈ R^{n} with g(z) < ∞. Then B := {y ∈ R^{n} : h(y) ≤ h(z)} is closed and bounded, and the continuous definable function y ↦ φ(y) + κ(x, y) attains a minimum on B. (Corollary 1.5.) Hence the definable set

epi(h) ∩ {(y, t) ∈ R^{n} × R : t ≤ h(z)} = {(y, t) ∈ R^{n} × R : h(y) ≤ t ≤ h(z)}

is non-empty, closed, and bounded. So is its projection on the last coordinate. (Proposition 1.4.) Hence h attains its infimum. □

Lemma 4.10. Let g: R^{n} × R^{n} → R_{∞} be definable and proper closed convex. Then g □ κ^{∗} is proper closed convex.

Proof. For (x, x^{∗}) ∈ R^{n} × R^{n}, we have

(g □ κ^{∗})(x, x^{∗}) = inf_{y∈R^{n}} g(x − y, x^{∗} + y) + q(y),

and by the previous lemma, the infimum is attained, so −∞ < g □ κ^{∗} ≤ g, showing that g □ κ^{∗} is proper. Set C := epi(g) × epi(κ^{∗}) ⊆ R^{m}, where m = 2(2n + 1). By (2.1), it remains to show that the definable convex set

epi(g) + epi(κ^{∗}) = {y + z : (y, z) ∈ C}

is closed. (Recall from Section 1.5 that the sum of two closed convex sets is not closed in general.) Let x ∈ cl(epi(g) + epi(κ^{∗})) and ε > 0. The definable set

C_{ε} := {(y, z) ∈ C : ∥x − (y + z)∥ ≤ ε}

is closed, convex, and non-empty.

Claim. C_{ε} is bounded.

Proof of the claim. For t > 0 let S^{m}(t) := {x ∈ R^{m} : ∥x∥ = t}. Assume for a contradiction that C_{ε} is unbounded. Take an arbitrary p = (y, z) ∈ C_{ε}. Then there is a definable unbounded subset I ⊆ R^{>0} such that (p + S^{m}(t)) ∩ C_{ε} ≠ ∅ for each t ∈ I. By weak definable choice (Lemma 1.2), there is a definable function γ̃: I → C_{ε} with γ̃(t) ∈ (p + S^{m}(t)) ∩ C_{ε} for all t ∈ I. Consider γ: I → S^{m}(1) defined by γ(t) := \frac{1}{t}(γ̃(t) − p). By Proposition 1.6, after replacing I by a suitable unbounded definable subset, we may assume that γ converges. Let p′ = (y′, z′) := lim_{I∋t→∞} γ(t) ∈ S^{m}(1).

Then for every λ ≥ 0, we have p + λp′ ∈ C_{ε}. Indeed, observe that for every t ∈ I we have [p, p + tγ(t)] ⊆ C_{ε}. Suppose for a contradiction that λ > 0 satisfies

(4.1)  δ := d(p + λp′, C_{ε}) > 0.

Take t ∈ I such that t ≥ λ and ∥γ(t) − p′∥ < δ/λ. Then

d(p + λp′, C_{ε}) ≤ ∥p + λp′ − (p + λγ(t))∥ = λ ∥p′ − γ(t)∥ < δ,

which contradicts (4.1).

So we have ∥x − y − z − λ(y′ + z′)∥ ≤ ε for every choice of λ ≥ 0. Hence, y′ = −z′. Moreover, y +λy′ ∈ epi(g) and z +λz′ ∈ epi(κ^{∗}) for every λ ≥ 0. But the only possible z′ is z′ = (0, …, 0, t) for some t > 0. Therefore, y′ = (0, …, 0, −t), which implies that epi(g) contains a vertical line. This contradicts that g is proper. □

By the claim, {C_{ε}}_{ε>0} is a monotone definable family of non-empty closed and bounded sets, so ⋂_{ε>0} C_{ε} ≠ ∅ by Lemma 1.3. Hence there is (y, z) ∈ ⋂_{ε>0} C_{ε} ⊆ C such that y + z = x. □

4.4. Proximal average. Let f, g: R^{n} → R_{∞} be definable. The definable function ψ = ψ(f, g): R^{n} → R_{±∞} given by

ψ(x) := inf_{y+z=x}(\frac{1}{2} ∗ f)(y) + (\frac{1}{2} ∗ g)(z) + κ(y, z)

is called the proximal average of f and g. This construction (cf. [1, 2]) plays a key role in extending monotone set-valued maps in the next section.

Lemma 4.11. Suppose f and g are proper closed convex. Then ψ(f, g) is proper convex, with conjugate (ψ(f, g))^{∗} = ψ(f^{∗}, g^{∗}).

Proof. Define A: R^{n} × R^{n} → R^{n} by A(y, z) = y + z; then A^{∗}: R^{n} → R^{n} × R^{n} is given by A^{∗}(x^{∗}) = (x^{∗}, x^{∗}). Also define the proper closed convex functions F, G: R^{n} × R^{n} → R_{∞} by

G(y, z) = (\frac{1}{2} ∗ f)(y) + (\frac{1}{2} ∗ g)(z), F (y, z) = G(y, z) + κ(y, z).

So for each x ∈ R^{n} we have

ψ(x) = (AF)(x) = inf_{y} G(y, x − y) + κ(x, 2y).

Hence ψ is convex, and by Lemma 4.9 the infimum is attained, so ψ is proper. By Lemma 4.10, the definable convex function G^{∗} □ κ^{∗} is closed, hence

F^{∗} = (G + κ)^{∗} = (G^{∗∗} + κ^{∗∗})^{∗} = (G^{∗} □ κ^{∗})^{∗∗} = G^{∗} □ κ^{∗}.

Now for all y^{∗}, z^{∗} ∈ R^{n},

G^{∗}(y^{∗}, z^{∗}) = \frac{1}{2}f^{∗}(y^{∗}) + \frac{1}{2}g^{∗}(z^{∗}).

Hence for all x^{∗} ∈ R^{n},

(ψ(f, g))^{∗}(x^{∗}) = (AF)^{∗}(x^{∗})

= F^{∗}(A^{∗}(x^{∗}))

= (G^{∗} □ κ^{∗}) (x^{∗}, x^{∗})

= inf_{(y^{∗},z^{∗})} (G^{∗}(y^{∗}, z^{∗}) + κ^{∗} (x^{∗} − y^{∗}, x^{∗} − z^{∗}) )

= inf_{y^{∗}+z^{∗}=2x^{∗}} (\frac{1}{2}f^{∗}(y^{∗}) + \frac{1}{2}g^{∗}(z^{∗}) + q(\frac{1}{2}(y^{∗} − z^{∗})))

= (ψ(f^{∗}, g^{∗}))(x^{∗}).

□

Let f: R^{n} × R^{n} → R_{±∞} be definable. We define the transpose f^{t} of f by f^{t}(x, x^{∗}) := f(x^{∗}, x) for all (x, x^{∗}) ∈ R^{n} × R^{n}. We say that f is autoconjugate if f^{∗} = f^{t}. Note that if f is autoconjugate, then f = f^{∗t} is closed convex.

Proposition 4.12. Let f: R^{n} ×R^{n} → R_{∞} be definable proper closed convex. Then the proximal average ψ(f, f^{∗t}): R^{n} × R^{n} → R_{∞} of f and f^{∗t} is autoconjugate.

Proof. Note that f^{∗t} = f^{t∗} and hence f^{∗t∗} = f^{t}. So by the previous lemma,

(ψ(f, f^{∗t}))^{∗} = ψ(f^{∗}, f^{∗t∗}) = ψ(f^{∗}, f^{t}) = ψ(f^{t}, f^{∗}) = ψ(f^{t}, f^{∗tt}) = (ψ(f, f^{∗t}))^{t}.

□

Remark. In the proof of the result analogous to Proposition 4.12 in [1], appeals to more general results replace our use of the elementary Lemmas 4.9 and 4.10 above.

5. Proof of Theorem A

Let ℜ be an expansion of a real closed ordered field. In this section we prove Theorem A, which we state here again for the convenience of the reader, in a slightly strengthened form:

Theorem 5.1. Suppose ℜ is definably complete. Let L ∈ R^{>0} and let f: A → B, where A ⊆ R^{m}, B ⊆ R^{n}, be a definable L-Lipschitz map. There exists a definable L-Lipschitz map F: R^{m} → cl(conv(B)) such that F |A = f.

In fact, the extra condition F (R^{m}) ⊆ cl(conv(B)) is easy to achieve once we have a definable L-Lipschitz map F′: R^{m} → R^{n} with F′|A = f: simply take F := p ∘ F′ where p = p(−, cl(conv(B))), and recall that p is non-expansive by Corollary 2.14.

Naturally, the question arises whether the hypothesis of definable completeness in this theorem is necessary. This question is affirmatively answered by the following proposition.

Proposition 5.2. Suppose ℜ is not definably complete. Then there exists a definable non-expansive function f: A → R, where A ⊆ R is closed, which cannot be extended to a non-expansive function R → R.

Proof. Since ℜ is not definable complete, there exists a closed non-empty definable set S ⊆ R which is bounded from above and which does not have a least upper bound in R. We let

A_{1} := {a ∈ R : a ≤ x for some x ∈ S}, A_{2} := R \ (1 + A_{1}).

We have S ⊆ A_{1} ⊆ 1 + A_{1} < A_{2}. Both A_{1} and A_{2} are closed, hence A := A_{1} ∪ A_{2} is a closed definable subset of R. After passing from S to a suitable affine image a + bS (a, b ∈ R), we may assume that 1 + A_{1} ⊈ A_{1} and so A ≠ R.

Let f: A → R be defined by f(x) := 1 if x ∈ A_{1} and f(x) := 0 if x ∈ A_{2}. Clearly, f is definable and non-expansive. Assume for a contradiction that there is a non-expansive F: R → R which extends f. Fix an arbitrary x ∈ R \ A; then x is an upper bound for A_{1} and a lower bound for A_{2}. Hence, for all y ∈ A_{1} and z ∈ A_{2}, we have

1 + y − x = f(y) − |y − x| ≤ F (x) ≤ f(z) + |z − x| = z − x.

So ζ := F (x) + x is an upper bound for 1 + A_{1} and a lower bound for A_{2}. Thus ζ ∉ 1 + A_{1} since 1 + A_{1} has no least upper bound in R, and ζ ∉ A_{2} since A_{2} has no largest lower bound in R, contradicting R = (1 + A_{1}) ∪ A_{2}. □

In the rest of this section we assume that ℜ is definably complete.

We prove Theorem 5.1 at the end of this section. In the rest of this subsection we mention two special cases of this theorem that are not hard to show directly. We let f: A → B be a definable map, where A is a non-empty subset of R^{m} and B ⊆ R^{n}. First, Lemma 1.9 yields Theorem A for a 1-dimensional target space. More generally, we have the following result; here and below, a function ω: R^{≥0} → R is said to be subadditive if ω(s + t) ≤ ω(s) + ω(t) for all s, t ∈ R^{≥0}. For example, it is easy to see that if A is convex, then the modulus of continuity ω_{f} of f is subadditive.

Proposition 5.3 (McShane-Whitney). Suppose n = 1 and f has a definable increasing subadditive modulus of continuity ω. Then

x ↦ inf_{a∈A} (f(a) + ω(||x − a||)), x ↦ sup_{a∈A} (f(a) − ω(||x − a||))

are definable functions R^{n} → R extending f with modulus of continuity ω.

To prove this, by Lemma 1.9 one only needs to show that given ω as in the proposition, for each a ∈ A, the function x ↦ ω(||x−a||) has modulus of continuity ω, and this follows by a straightforward computation.

Theorem 5.1 for Lipschitz maps with convex domain is also easy to show:

Proposition 5.4. Suppose A is convex, and f is uniformly continuous (L-Lip-schitz, where L ∈ R^{≥0}). Then there exists a definable map F: R^{m} → cl(B) with F |A = f which is uniformly continuous (L-Lipschitz, respectively). If f is convex, then F can additionally be chosen to be convex.

This is an immediate consequence of Lemma 1.7 and the following lemma:

Lemma 5.5. Suppose A is closed and convex. Then there exists a definable map F: R^{m} → B with F |A = f and ω_{f} = ω_{F}.

Proof. For x ∈ R^{m} put F (x) := f(p(x, A)). Then the map F: R^{m} → B agrees with f on A. Moreover, let δ > 0. Then for x_{1}, x_{2} ∈ R^{m} with ∥x_{1} − x_{2}∥ ≤ δ, setting y_{i} = p(x_{i}, A) for i = 1, 2, we have ∥y_{1} − y_{2}∥ ≤ δ by Corollary 2.14 and hence ∥F (x_{1}) − F (x_{2})∥ = ∥f(y_{1}) − f(y_{2})∥ ≤ ω_{f}(δ). This yields ω_{F} (δ) ≤ ω_{f}(δ), and the inequality ω_{F} (δ) ≥ ω_{f}(δ) is immediate. □

5.1. Monotone set-valued maps. The crucial technique in proving Theorem A is to transfer the extension problem to definable monotone set-valued maps. As we will prove, these maps stay in one-to-one correspondence with firmly non-expansive maps. (See [31] for a useful survey on the theory of monotone set-valued maps in the context of Banach spaces.)

We begin by introducing (definable) set-valued maps as an alternative language for talking about (definable) families of sets. We use the notation T: R^{m} ⇉ R^{n} to denote a map T: R^{m} → 2^{R^{n}}, and call such T a set-valued map. Such a set-valued map T is trivial if T (x) = ∅ for all x ∈ R^{m}. The inverse of a set-valued map T: R^{m} ⇉ R^{n} is the set-valued map T^{−1} : R^{n} ⇉ R^{m} given by

T^{−1}(x^{∗}) = {x ∈ R^{m} : x^{∗} ∈ T (x)} for x^{∗} ∈ R^{n}.

Given set-valued maps S, T: R^{m} ⇉ R^{n} and λ ∈ R, the set-valued maps S + T, λ S: R^{m} ⇉ R^{n} are defined by (S + T)(x) = S(x) + T (x) and (λ S)(x) = λ S(x) for x ∈ R^{m}.

Let T = (T_{x})_{x∈X} be a family of subsets of R^{n}, where X ⊆ R^{m}. Then T gives rise to a set-valued map T: R^{m} ⇉ R^{n} by setting T (x) := T_{x} for x ∈ X and T (x) := ∅ for x ∈ R^{m} \ X. A set-valued map R^{m} ⇉ R^{n} arising in this way from a definable family T = (T_{x})_{x∈X} of subsets of R^{n} with X ⊆ R^{m} is said to be definable.

Let T: R^{m} ⇉ R^{n} be a set-valued map. The graph of T is the subset

graph(T) := {(x, x^{∗}) ∈ R^{m} × R^{n} : x^{∗} ∈ T (x)}

of R^{m} × R^{n}. Note that every map f: X → R^{n}, X ⊆ R^{m}, gives rise to a set-valued map R^{m} ⇉ R^{n}, whose graph is the graph of the map f. We continue to denote the set-valued map associated to f by the same symbol. Given S: R^{m} ⇉ R^{n}, we say that T extends S if graph(S) ⊆ graph(T), and we say that T properly extends S if graph(S) ⊊ graph(T).

Definition. Let T: R^{n} ⇉ R^{n}. An element (x, x^{∗}) ∈ R^{n} × R^{n} is said to be monotonically related to T if

⟨x − y, x^{∗} − y^{∗}⟩ ≥ 0 for all (y, y^{∗}) ∈ graph(T).

We say that T is monotone if every (x, x^{∗}) ∈ graph(T) is monotonically related to T, and T is called maximal monotone if T is monotone, and no (x, x^{∗}) ∉ graph(T) is monotonically related to T. (Equivalently, T is maximal monotone if T is monotone but every proper extension of T fails to be monotone).

Clearly T is monotone (maximal monotone) if and only if T^{−1} is monotone (maximal monotone, respectively). It is easy to show that if T: R^{n} ⇉ R^{n} is maximal monotone, then T (x) is a convex subset of R^{n}, for each x ∈ R^{n}.

Example 5.6. Let f: X → R, where X ⊆ R^{n}. If f is firmly non-expansive, then (the set-valued map associated to) f is monotone. If n = 1, then f is monotone if and only if f is increasing: x ≤ y ⇒ f(x) ≤ f(y), for all x, y ∈ X.

Example 5.7. Let T: R^{n} → R^{n} be R-linear. Then T is monotone if and only if T is positive (i.e., ⟨T (x), x⟩ ≥ 0 for all x ∈ R^{n}), and in this case, T is maximal monotone. (See [31, Example 1.5 (b)].)

Our interest in definable set-valued maps is motivated by the following fact; compare with [12]. Its proof makes crucial use of Theorem B (the definable version of Helly’s Theorem).

Proposition 5.8. Let T: R^{n} ⇉ R^{n}, and let f := (T + id)^{−1}. Then

(1) T is monotone if and only if f is the graph of a firmly non-expansive map X → R^{n}, for some X ⊆ R^{n};

(2) if f is the graph of a firmly non-expansive map R^{n} → R^{n}, then T is maximal monotone;

(3) if T is definable and maximal monotone, then f is the graph of a firmly non-expansive map R^{n} → R^{n}.

Proof. We first note that the linear map (x, x^{∗}) ↦ (x+x^{∗}, x) restricts to a bijection graph(T) → graph(f) with inverse (y, y^{∗}) ↦ (y^{∗}, y − y^{∗}). So if T is monotone and (x, x_{i}^{∗}) ∈ graph(f), where i = 1, 2, then (x_{i}^{∗}, x − x_{i}^{∗}) ∈ graph(T) and hence

0 ≤ ⟨x_{1}^{∗} − x_{2}^{∗}, (x − x_{1}^{∗}) − (x − x_{2}^{∗})⟩ = − ∥x_{1}^{∗} − x_{2}^{∗}∥^{2}

by monotonicity of T, so x_{1}^{∗} = x_{2}^{∗}. Hence f is the graph of a function X → R^{n}, where X ⊆ R^{n}. Now (1) is a consequence of this observation and the following identity, valid for all (x, x^{∗}), (y, y^{∗}) ∈ graph(T):

⟨f(x + x^{∗}) − f(y + y^{∗}), (x + x^{∗}) − (y + y^{∗})⟩ − ∥f(x + x^{∗}) − f(y + y^{∗})∥^{2}
= ⟨x − y, (x + x^{∗}) − (y + y^{∗})⟩ − ∥x − y∥^{2} = ⟨x − y, x^{∗} − y^{∗}⟩.

For (2), suppose f is the graph of a firmly non-expansive map R^{n} → R^{n}, and S: R^{n} ⇉ R^{n} is a monotone set-valued extending T. Then (S + id)^{−1} is the graph of a function extending f = (T + id)^{−1}, hence S = T. For (3), suppose that T is definable and monotone, and X ≠ R^{n}. Let x ∈ R^{n} \ X. Then f extends to a firmly non-expansive map A ∪ {x} → R^{n} by Corollary 3.6 and the remark following it. Hence T can be properly extended to a monotone set-valued map R^{n} ⇉ R^{n}, so T is not maximal. □

Let f: R^{n} × R^{n} → R_{∞}. The set-valued map T: R^{n} ⇉ R^{n} with

graph(T) = {(x, x^{∗}) ∈ R^{n} × R^{n} : f(x, x^{∗}) = ⟨x, x^{∗}⟩}

is called the set-valued map represented by f. If f is definable proper convex and autoconjugate, then the Fenchel-Young Inequality implies f(x, x^{∗}) ≥ ⟨x, x^{∗}⟩ and f^{∗}(x, x^{∗}) ≥ ⟨x, x^{∗}⟩ for all x, x^{∗} ∈ R^{n}. Together with the next proposition (due to [37] in the classical case), this yields that autoconjugate functions represent maximal monotone maps:

Proposition 5.9. Let f: R^{n} × R^{n} → R_{∞} be definable proper convex, and let T: R^{n} ⇉ R^{n} be the set-valued map represented by f. If f(x, x^{∗}) ≥ ⟨x, x^{∗}⟩ for all x, x^{∗} ∈ R^{n}, then T is monotone, and if in addition f^{∗}(x, x^{∗}) ≥ ⟨x, x^{∗}⟩ for all x, x^{∗} ∈ R^{n}, then T is maximal monotone.

Proof. Suppose f(x, x^{∗}) ≥ ⟨x, x^{∗}⟩ for all x, x^{∗} ∈ R^{n}. Then for (x, x^{∗}), (y, y^{∗}) ∈ graph(T), using the convexity of f:

\frac{1}{2}⟨x, x^{∗}⟩ + \frac{1}{2}⟨y, y^{∗}⟩ = \frac{1}{2}f(x, x^{∗}) + \frac{1}{2}f(y, y^{∗}) ≥

f (\frac{1}{2}x + \frac{1}{2}y, \frac{1}{2}x^{∗} + \frac{1}{2}y^{∗}) ≥ ⟨\frac{1}{2}x + \frac{1}{2}y, \frac{1}{2}x^{∗} + \frac{1}{2}y^{∗}⟩ ,

and this yields ⟨x − y, x^{∗} − y^{∗}⟩ ≥ 0. Now assume f^{∗}(x, x^{∗}) ≥ ⟨x, x^{∗}⟩ for all x, x^{∗} ∈ R^{n}, and let (y, y^{∗}) ∈ R^{n} × R^{n} be monotonically related to T, i.e., ⟨y − x, y^{∗} − x^{∗}⟩ ≥ 0 for all (x, x^{∗}) ∈ graph(T). From Example 4.8 recall the notation Δ(x, y) = \frac{1}{2} ∥x + y∥^{2} for x, y ∈ R^{n}. By assumption and since Δ ≥ 0, with g := (f^{∗})^{t} we have

g(x, x^{∗}) − ⟨x, x^{∗}⟩ + Δ(y − x, y^{∗} − x^{∗}) ≥ 0 for all (x, x^{∗}) ∈ graph(T_{f}).

Hence by Proposition 4.5 and Example 4.8 there exists (x, x^{∗}) ∈ R^{n} ×R^{n} such that

g^{∗}(x^{∗}, x) − ⟨x, x^{∗}⟩ + Δ(y − x, y^{∗} − x^{∗}) ≤ 0.

Since g^{∗}(x^{∗}, x) = f^{∗}(x, x^{∗}) therefore

⟨x, x^{∗}⟩ ≤ f^{∗}(x, x^{∗}) ≤ ⟨x, x^{∗}⟩ − Δ(y − x, y^{∗} − x^{∗}).

Hence (x, x^{∗}) ∈ graph(T), thus ⟨y − x, y^{∗} − x^{∗}⟩ ≥ 0, and

0 = Δ(y − x, y^{∗} − x^{∗}) = \frac{1}{2} ∥y − x∥^{2} + ⟨y − x, y^{∗} − x^{∗}⟩ + \frac{1}{2} ∥y^{∗} − x^{∗}∥^{2} ,

therefore (y, y^{∗}) = (x, x^{∗}) ∈ graph(T). □

5.2. The Fitzpatrick function. Let T: R^{n} ⇉ R^{n} be a non-trivial definable setvalued map. The function Φ_{T} : R^{n} × R^{n} → R_{∞} given by

Φ_{T} (x, x^{∗}) := sup_{(a,a^{∗})∈graph(T)} (⟨x, a^{∗}⟩ + ⟨a, x^{∗}⟩ − ⟨a, a^{∗}⟩)

is the Fitzpatrick function of T. (This concept was introduced in [14].) The function Φ_{T} is the pointwise supremum of a definable family of affine functions, hence Φ_{T} is definable and closed convex. For (x, x^{∗}) ∈ R^{n} × R^{n} we have

Φ_{T} (x, x^{∗}) = ⟨x, x^{∗}⟩ − inf_{(a,a^{∗})∈graph(T)}⟨x − a, x^{∗} − a^{∗}⟩.

Hence if T is monotone, then Φ_{T} (x, x^{∗}) = ⟨x, x^{∗}⟩ for all (x, x^{∗}) ∈ graph(T), in particular, Φ_{T} is proper; and if T is maximal monotone, then Φ_{T} represents T.

From now on until the end of this subsection we assume that T is monotone. Then the set-valued map represented by Φ_{T}^{∗} also extends T:

Lemma 5.10. For all (y, y^{∗}) ∈ graph(T) we have Φ_{T}^{∗} (y^{∗}, y) = ⟨y^{∗}, y⟩.

In the following we use tildes to denote elements of R^{n} ×R^{n}. Given x̃ ∈ R^{n} ×R^{n}, we write x̃ = (x, x^{∗}) where x, x^{∗} ∈ R^{n}, and we put x̃^{t} = (x^{∗}, x). Below we will often use the identity

⟨x, x^{∗}⟩ = \frac{1}{2}⟨x̃, x̃^{t}⟩ (x̃ = (x, x^{∗}) ∈ R^{n} × R^{n}).

For x̃ ∈ R^{n} × R^{n} we have

Φ_{T} (x̃) = sup_{ã∈graph(T)}⟨x̃, ã^{t}⟩ − \frac{1}{2}⟨ã, ã^{t}⟩

and hence, for ỹ ∈ R^{n} × R^{n}:

Φ_{T}^{∗} (ỹ) = sup_{x̃} (⟨x̃, ỹ⟩ − Φ_{T} (x̃)) = sup_{x̃} inf_{ã∈graph(T)} (⟨ỹ − ã^{t}, x̃⟩ + \frac{1}{2}⟨ã, ã^{t}⟩) .

Proof of Lemma 5.10. Let ỹ ∈ graph(T). Then Φ_{T} (ỹ) = \frac{1}{2}⟨ỹ^{t}, ỹ⟩, so the Fenchel-Young Inequality applied to Φ_{T} yields Φ_{T}^{∗} (ỹ^{t}) ≥ \frac{1}{2}⟨ỹ^{t}, ỹ⟩. We also have

Φ_{T}^{∗} (ỹ^{t}) = sup_{x̃} inf_{ã∈graph(T)} (⟨ỹ^{t} − ã^{t}, x̃⟩ + \frac{1}{2}⟨ã, ã^{t}⟩) ≤ sup_{x̃} \frac{1}{2}⟨ỹ, ỹ^{t}⟩ = \frac{1}{2}⟨ỹ, ỹ^{t}⟩.

Hence, Φ_{T}^{∗} (ỹ^{t}) = \frac{1}{2}⟨ỹ^{t}, ỹ⟩. □

Let Ψ_{T} : R^{n} × R^{n} → R be the proximal average of Φ_{T} and Φ_{T}^{∗}, that is,

Ψ_{T} (x̃) = inf_{ỹ+z̃=2x̃} (\frac{1}{2}Φ_{T} (ỹ) + \frac{1}{2}Φ_{T}^{∗} (z̃^{t}) + \frac{1}{4}κ(ỹ, z̃)) for x̃ ∈ R^{n} × R^{n}.

By Proposition 4.12, the definable function Ψ_{T} is proper convex and autoconjugate.

Lemma 5.11. Let x̃ ∈ graph(T). Then Φ_{T} (x̃) = Ψ_{T} (x̃).

Proof. By the Fenchel-Young Inequality, we have on the one hand

2Ψ_{T} (x̃) = Ψ_{T}^{∗t}(x̃) + Ψ_{T} (x̃) ≥ ⟨x̃, x̃^{t}⟩.

On the other hand

2Ψ_{T} (x̃) ≤ Φ_{T} (x̃) + Φ_{T}^{∗} (x̃^{t}) = ⟨x̃, x̃^{t}⟩.

So Ψ_{T} (x̃) = \frac{1}{2}⟨x̃, x̃^{t}⟩ = Φ_{T} (x̃). □

By Proposition 5.9 and the previous lemma, we have the following adaptation of [2, Theorem 5.7]:

Proposition 5.12. The set-valued map \overline{T}: R^{n} ⇉ R^{n} represented by Ψ_{T} is a definable maximal monotone extension of T.

We are now able to prove the definable version of the Kirszbraun Theorem.

5.3. Proof of Theorem 5.1. Let A ⊆ R^{m} be non-empty, and let f: A → R^{n} be a definable L-Lipschitz function, where L ∈ R^{>0}. If m < n, then let f_{1} : A×R^{n−m} → R^{n} be given by f_{1}(x_{1}, …, x_{n}) := f(x_{1}, …, x_{m}). If n ≤ m, then set f_{1}(x) := (f(x), 0, …, 0) ∈ R^{m}. Note that f extends to a definable L-Lipschitz map R^{m} → R^{n} if and only if f_{1} extends to a definable L-Lipschitz map R^{k} → R^{k}, where k = max{m, n}. So after replacing f by f_{1}, we may assume that m = n. Replacing f by f/L, we may also assume that f is non-expansive. By Proposition 1.12 the definable map g := \frac{1}{2}(id +f) is firmly non-expansive, and it suffices to show that g admits an extension to a definable firmly non-expansive map R^{n} → R^{n}. The definable set-valued map T := g^{−1} − id: R^{n} ⇉ R^{n} is monotone by Proposition 5.8, (1). By Proposition 5.12 there is a definable maximal monotone \overline{T}: R^{n} ⇉ R^{n} extending T. By Proposition 5.8, (3), G := (\overline{T} + id)^{−1} is the graph of a definable firmly non-expansive map R^{n} → R^{n} extending g as required. □

Inspection of the proof of Theorem 5.1 given above exhibits a certain uniformity in the construction:

Corollary 5.13. Let a ↦ L_{a}: A → R^{≥0} be a definable function. Let {f_{a}}_{a∈A} be a definable family of maps f_{a}: S_{a} → R^{n}, where S_{a} ⊆ R^{m}, such that each f_{a} is L_{a}-Lipschitz. There exists a definable family {F_{a}}_{a∈A} of maps R^{m} → R^{n}, each F_{a} being L_{a}-Lipschitz and extending f_{a}.

We finish this section with a question related to Theorem A, to which we do not know the answer. For a definable set S ⊆ R^{n}, let L_{m}(S) be the R-linear space of all definable Lipschitz maps S → R^{m}, equipped with the seminorm

f ↦ |f| = sup_{x≠y} \frac{∥f(x) − f(y)∥}{∥x − y∥}.

Theorem A shows the existence of a map E: L_{m}(S) → L_{m}(R^{n}) such that for all f ∈ L_{m}(S), the map E(f) extends f, and |E(f)| ≤ |f|.

Question 5.14. Is there an R-linear map E: L_{m}(S) → L_{m}(R^{n}) and some C ∈ R such that for all f ∈ L_{m}(S), E(f) extends f, and |E(f)| ≤ C |f|?

Note that since we do not require C ≤ 1 (unlike in Theorem A), it is enough to consider the case m = 1. For R = ℝ and o-minimal ℜ, the answer to this question is positive, as shown in [29].

6. Some Variants

In this section we discuss a variant of Kirszbraun’s Theorem for locally definable maps, and the problem of definably extending uniformly continuous maps, which is related to (but easier than) the problem of definably extending Lipschitz maps.

6.1. Kirszbraun’s Theorem for locally definable maps. Let ℜ be an expansion of the ordered field of real numbers. A set S ⊆ ℝ^{n} is said to be locally definable (in ℜ) if for every x ∈ ℝ^{n} there exists an open ball B with center x such that B ∩S is definable. A map S → ℝ^{m}, where S ⊆ ℝ^{n}, is called locally definable if its graph is locally definable. This notion encompasses both the subanalytic setting and Shiota’s notion [36] of 𝔛 families with axiom (v):

Examples 6.1.

(1) A set S ⊆ ℝ^{n} is locally definable in the expansion ℝ_{an} of the ordered field of real numbers by all restricted analytic functions if and only if S is subanalytic (cf. [10, p. 507]).

(2) Each 𝔛 family satisfying axiom (v) gives rise to an o-minimal expansion of the ordered field of reals with the property that the sets locally definable in this structure are precisely the sets in the given 𝔛 family (cf. [35]).

Many of the techniques used to prove the definable version of the Kirszbraun Theorem in the previous sections cannot be applied to locally definable maps and sets. In particular, the intersection or union of a locally definable family of sets is not locally definable anymore in general, and the pointwise infimum of a locally definable family of functions is also not necessarily locally definable. However:

Lemma 6.2. Suppose for each ℓ ∈ ℕ we are given a locally definable map f_{ℓ}: A_{ℓ} → ℝ^{n}, where A_{ℓ} ⊆ ℝ^{m}, such that B_{ℓ}(0) ⊆ A_{ℓ} ⊆ A_{ℓ+1} and f_{ℓ} = f_{ℓ+1}|A_{ℓ} for every ℓ. Then the map F: ℝ^{m} → ℝ^{n} given by F (x) = f_{ℓ}(x), where ℓ is such that x ∈ A_{ℓ}, is locally definable. Moreover, if each f_{ℓ} is L-Lipschitz, where L ∈ ℝ^{≥0}, then F is L-Lipschitz.

This observation together with Theorem 5.1 does yield locally definable variants of the Kirszbraun Theorem. For this, we fix a locally definable L-Lipschitz map f: A → ℝ^{n}, where L > 0 and A ⊆ ℝ^{m} is non-empty.

Corollary 6.3. Suppoe f is bounded. Then f extends to a bounded locally definable L-Lipschitz map ℝ^{m} → ℝ^{n}.

Proof. By considering x ↦ C·f(x+a) (for suitable C ∈ ℝ^{>0} and arbitrary a ∈ A) in place of f, we may assume L = 1, f is bounded by 1, and 0 ∈ A. For every ℓ ∈ ℕ we construct a locally definable non-expansive map f_{ℓ}: A_{ℓ} := \overline{B}_{ℓ}(0) ∪ A → \overline{B}_{1}(0) such that for each ℓ we have f_{ℓ+1} = f_{ℓ} on B_{ℓ}(0) and f_{ℓ} = f on A. Set f_{0} := f. Suppose now that ℓ > 0 and the map f_{ℓ−1} has been constructed already. By Theorem 5.1, there is a definable non-expansive function g_{ℓ}: ℝ^{m} → \overline{B}_{1}(0) such that g_{ℓ} = f_{ℓ−1} on A_{ℓ−1} ∩ \overline{B}_{ℓ+2}(0). For x ∈ A_{ℓ}, set

f_{ℓ}(x) = \begin{cases}g_{ℓ}(x) & if ∥x∥ ≤ ℓ, \\ f(x) & if ∥x∥ > ℓ. \end{cases}

We claim that f_{ℓ} is non-expansive. Suppose x, y ∈ A_{ℓ}. If ∥x∥ , ∥y∥ ≤ ℓ or ∥x∥ , ∥y∥ > ℓ, then clearly ∥f_{ℓ}(x) − f_{ℓ}(y)∥ ≤ ∥x − y∥. Assume now that ∥x∥ ≤ ℓ and ∥y∥ > ℓ. If ∥y∥ ≤ ℓ + 2, then

∥f_{ℓ}(x) − f_{ℓ}(y)∥ = ∥g_{ℓ}(x) − g_{ℓ}(y)∥ ≤ ∥x − y∥ .

If ∥y∥ > ℓ + 2, then ∥x − y∥ > 2. Since ∥f_{ℓ}∥ ≤ 1, we have

∥f_{ℓ}(x) − f_{ℓ}(y)∥ ≤ ∥f_{ℓ}(x)∥ + ∥f_{ℓ}(y)∥ ≤ 1 + 1 < ∥x − y∥ .

Hence f_{ℓ} is non-expansive. Now apply Lemma 6.2. □

An enhancement of the previous proof leads to the following corollary.

Corollary 6.4. Let ε > 0. Then f extends to a locally definable (L + ε)-Lipschitz map ℝ^{m} → ℝ^{n}.

Proof. After replacing f by x ↦ \frac{1}{L}(f(x + a) − f(a)), where a ∈ A is arbitrary, we may assume that L = 1 and f(0) = 0. Let (ε_{ℓ})_{ℓ∈ℕ} be a strictly decreasing sequence of positive real numbers such that ∑_{ℓ} ε_{ℓ} < ε. For each ℓ ∈ ℕ let

L_{ℓ} := 1 + ∑_{p=0}^{ℓ} ε_{p}.

We construct for every ℓ ∈ ℕ a locally definable L_{ℓ}-Lipschitz function f_{ℓ}: A_{ℓ} := \overline{B}_{ℓ}(0) ∪ A → ℝ^{n} such that for each ℓ we have f_{ℓ+1} = f_{ℓ} on \overline{B}_{ℓ}(0) and f_{ℓ} = f on A ∩ B_{ℓ}(0). Set f_{0} := f. Suppose ℓ > 0 and f_{ℓ−1} has been constructed already. Let

M_{ℓ} = sup { ∥f_{ℓ−1}(x)∥ : x ∈ A_{ℓ−1}, ∥x∥ ≤ ℓ}.

Select r_{ℓ} > ℓ so big such that ε_{ℓ}r_{ℓ} ≥ M_{ℓ} +ℓL_{ℓ}. By Theorem 5.1, there is a definable L_{ℓ−1}-Lipschitz map g_{ℓ}: ℝ^{m} → ℝ^{n} such that g_{ℓ} = f_{ℓ−1} on A_{ℓ} ∩ \overline{B}_{r_{ℓ}}(0). Define f_{ℓ}: A_{ℓ} → ℝ^{n} by

f_{ℓ}(x) = \begin{cases}g_{ℓ}(x) & if ∥x∥ ≤ ℓ, \\ f(x) & if ∥x∥ > ℓ. \end{cases}

We claim that f_{ℓ} is L_{ℓ}-Lipschitz. Suppose x, y ∈ A_{ℓ}. If ∥x∥ , ∥y∥ ≤ ℓ or ∥x∥ , ∥y∥ > ℓ, then ∥f_{ℓ}(x) − f_{ℓ}(y)∥ ≤ L_{ℓ} ∥x − y∥ is evident. Assume now that ∥x∥ ≤ ℓ and ∥y∥ > ℓ. If ∥y∥ ≤ r_{ℓ}, then

∥f_{ℓ}(x) − f_{ℓ}(y)∥ = ∥g_{ℓ}(x) − g_{ℓ}(y)∥ ≤ L_{ℓ} ∥x − y∥ .

If ∥y∥ > r_{ℓ}, then we have

∥f_{ℓ}(x) − f_{ℓ}(y)∥ ≤ ∥f_{ℓ}(x)∥ + ∥f_{ℓ}(y)∥
≤ M_{ℓ} + L_{ℓ−1} ∥y∥
< ε_{ℓ} ∥y∥ − ℓL_{ℓ} + L_{ℓ−1} ∥y∥
= L_{ℓ} ∥y∥ − ℓL_{ℓ}
≤ L_{ℓ} ∥y∥ − ∥x∥ L_{ℓ}
≤ L_{ℓ} ∥x − y∥ .

Hence f_{ℓ} is L_{ℓ}-Lipschitz. Now apply Lemma 6.2. □

The previous two corollaries raise the following question, the answer to which we do not know:

Question 6.5. Does the Kirszbraun Theorem hold for locally definable maps, i.e.: given a locally definable L-Lipschitz map f: A → ℝ^{n}, where A ⊆ ℝ^{m}, does f extend to a locally definable L-Lipschitz map ℝ^{m} → ℝ^{n}?

6.2. Extending uniformly continuous maps. In this subsection we let ℜ be a definably complete expansion of an ordered field. Every Lipschitz map is uniformly continuous, so in light of Theorem 5.1 it is natural to ask: when does a definable uniformly continuous map A → R^{n}, where A ⊆ R^{m}, extend to a uniformly continuous map R^{m} → R^{n}? The aim of this subsection is to give a complete answer to this question (see Proposition 6.7), following [19], where this question was treated for R = ℝ without definability requirements.

For this, let f: A → B be a definable map, where A ⊆ R^{m} is non-empty and and B ⊆ R^{n}. We also assume that A is closed. (Recall from Lemma 1.7 that a definable uniformly continuous map always extends to a definable uniformly continuous map on the closure of its domain.) Note that f is uniformly continuous if and only if each of the n coordinate functions of f is uniformly continuous, and similarly with “continuous” in place of “uniformly continuous.” Hence, in order to study the extendability of f to a uniformly continuous (or merely continuous) map R^{m} → R^{n}, we may further assume that n = 1, which we do from now on.

Before we study uniformly continuous extensions, it is perhaps worth noting that if f is continuous, then f always extends to a definable continuous function on R^{m}:

Lemma 6.6 (Definable Tietze Extension Theorem). Suppose f is continuous. Then there exists a definable continuous function F: R^{m} → R with F |A = f.

Proof. First assume B = (1, 2). In this case one simply verifies that the definable function F: R^{m} → B with F |A = f and

F (x) := inf_{a∈A} f(a) · \frac{d(x, a)}{d(x, A)} for x ∈ R^{m} \ A

is continuous. This well-known formula is due to Riesz (1923), and related to similar extension formulas by Hausdorff (1919) and Tietze (1915). For the general case, let τ be a definable homeomorphism R → (1, 2), such as

t ↦ \frac{3}{2} + \frac{t}{2\sqrt{1 + t^{2}}} ,

and note that if F: R^{m} → (1, 2) extends τ ∘ f, then τ^{−1} ∘ F extends f. □

(The proof of the definable version of Tietze Extension above is shorter and more elementary than the one in [8, Chapter 8], which is only valid for o-minimal ℜ and uses triangulations.)

The classical counterpart of the following fact was proved in [19]:

Proposition 6.7. Suppose f is uniformly continuous. The following are equivalent: (1) f extends to a definable uniformly continuous function R^{m} → R;

(2) f has a definable subadditive modulus of continuity ω such that ω(t) → 0 as t → 0^{+};

(3) f has an affine modulus of continuity;

(4) f has a definable concave modulus of continuity ω with ω(t) → 0 as t → 0^{+}.

The implication (1) ⇒ (2) is clear. The implications (2) ⇒ (3) and (3) ⇒ (4) follow from the next two lemmas, for which we fix a definable function ω: R^{≥0} → R^{≥0}. The classical proof of the first lemma (as given in [19]) uses the archimedean property of ℝ.

Lemma 6.8. Suppose ω is subadditive and ω(t) → 0 as t → 0^{+}. Then there is an affine function ω_{1} : R → R with ω_{1} ≥ ω.

Proof. There is δ > 0 such that ω(t) < 1 for all t ∈ [0, δ], hence ω(t) ≤ 2 for t ∈ [0, 2δ] by subadditivity. We claim that ω_{1} : R → R given by ω_{1}(t) := 2 + \frac{1}{δ}t majorizes ω. Assume for a contradiction that the subset B := {ω > ω_{1}} of R^{≥0} is non-empty, and put b := inf B. Evidently, we have b ≥ 2δ. Let s ∈ [b, b + δ). Then

ω(s) = ω(s − δ + δ) ≤ ω(s − δ) + ω(δ)
< ω_{1}(s − δ) + 1 = 2 + \frac{1}{δ}(s − δ) + 1 = ω_{1}(s).

Hence B ∩ [b, b + δ) = ∅, a contradiction. □

Lemma 6.9 (McShane). Suppose there exists an affine function ω_{1} with ω_{1} ≥ ω. Then there exists a definable concave function ω_{2} with ω_{2} ≥ ω; if ω(t) → 0 as t → 0^{+}, then ω_{2} can be chosen so that moreover ω_{2}(t) → 0 as t → 0^{+}.

Proof. For a, b ∈ R let ω_{a,b}(t) = a + bt, and let a_{0}, b_{0} ∈ R with ω_{1} = ω_{a_{0},b_{0}}. Then

ω_{2}(t) := inf {ω_{a,b}(t) : a, b ∈ R, ω ≤ ω_{a,b}}

is a definable concave function with ω_{2} ≥ ω. Assume now that lim_{t→0^{+}} ω(t) = 0.

To see that lim_{t→0^{+}} ω_{2}(t) = 0, let ε > 0 be given. Take δ > 0 such that ω(t) ≤ ε

for 0 ≤ t ≤ δ. Take some b > 0 such that ω_{ε,b}(t) > ω_{a_{0},b_{0}}(t) for t > δ. Then ω(t) ≤ ω_{ε,b}(t) for all t ≥ 0, so ω_{2}(t) ≤ ω_{ε,b}(t) for all t ≥ 0. Also, ω_{ε,b}(t) → ε as t → 0^{+}. This yields the claim. □

The implication (4) ⇒ (1) in Proposition 6.7 is a consequence of Proposition 5.3 and the next lemma:

Lemma 6.10. Let ω: R^{≥0} → R^{≥0} be a concave function. Then ω is increasing, and if in addition ω(0) = 0, then ω is subadditive.

Proof. Suppose that s, t are positive elements of R such that s < t and ω(s) > ω(t). Put Δ := t − s, and choose λ with 0 < λ < 1 and (1 − λ)ω(s) > ω(t). Then we have, by concavity of ω:

ω(t) = ω(s + Δ) ≥ λω (s + \frac{1}{λ}Δ) + (1 − λ)ω(s)

and hence

ω (s + \frac{1}{λ}Δ) ≤ \frac{1}{λ} (ω(t) − (1 − λ)ω(s)) < 0,

a contradiction. Hence ω is subadditive. If ω(0) = 0, note that for s, t > 0, by concavity ω(s) ≥ \frac{s}{s+t}ω(s + t), and similarly for t in place of s; now add. □

Corollary 6.11. If f is bounded and uniformly continuous, then there is a definable uniformly continuous function on R^{m} extending f. In particular, if A is bounded and f is continuous, then f extends to a definable uniformly continuous function on R^{m}.

Proof. If M ∈ R is such that ∥f∥ ≤ M, then ω_{f} ≤ 2M. Hence the first statement follows from (3) ⇒ (1) in Proposition 6.7. The second statement now follows from the first by Lemma 1.8. □

Remarks. Suppose f is uniformly continuous.

(1) If B = [1, 2], then the extension F of f to a function on R^{m} defined as in the proof of Lemma 6.6 is also uniformly continuous. (This is shown for R = ℝ in [25], and the proof given there goes through in general.)

(2) If A is convex, then f extends to a definable uniformly continuous function on R^{m} with the same modulus of continuity, cf. Lemma 5.5. In [24] it is shown that given a closed subset S of ℝ^{m}, each uniformly continuous function on S has an extension to a function on ℝ^{m} with the same modulus of continuity if and only if S is convex.

References

1. H. H. Bauschke and X. Wang, Firmly nonexpansive and Kirszbraun-Valentine extensions: a constructive approach via monotone operator theory, in: Nonlinear Analysis and Optimization (Haifa 2008 ), Contemp. Math., Amer. Math. Soc., to appear.

2. , The kernel average for two convex functions and its applications to the extension and representation of monotone operators, Trans. Amer. Math. Soc., to appear.

3. Y. Benyamini and J. Lindenstrauss, Geometric Nonlinear Functional Analysis, Vol. 1, Amer. Math. Soc. Colloquium Publications, vol. 48, Amer. Math. Soc., Providence, RI, 2000.

4. J. M. Borwein and A. S. Lewis, Convex Analysis and Nonlinear Optimization, 2nd ed., CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, vol. 3, Springer-Verlag, New York, 2006.

5. L. Danzer, B. Grünbaum, and V. Klee, Helly’s theorem and its relatives, in: [23], 101–180.

6. A. Dolich, Forking and independence in o-minimal theories, J. Symbolic Logic 69 (2004), no. 1, 215–240.

7. R. Dougherty and C. Miller, Definable Boolean combinations of open sets are Boolean combinations of open definable sets, Illinois J. Math. 45 (2001), no. 4, 1347–1350.

8. L. van den Dries, Tame Topology and O-minimal Structures, London Mathematical Society Lecture Note Series, vol. 248, Cambridge University Press, Cambridge, 1998.

9. , Dense pairs of o-minimal structures, Fund. Math. 157 (1998), no. 1, 61–78.

10. L. van den Dries and C. Miller, Geometric categories and o-minimal structures, Duke Math. J. 84 (1996), no. 2, 497–540.

11. J. Eckhoff, Helly, Radon, and Carathéodory type theorems, in: P. M. Gruber and J. M. Wills (eds.), Handbook of Convex Geometry, Vol. A, 389–448, North-Holland Publishing Co., Amsterdam, 1993.

12. J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Programming 55 (1992), no. 3, Ser. A, 293–318.

13. H. Federer, Geometric Measure Theory, Die Grundlehren der mathematischen Wissenschaften, vol. 153, Springer-Verlag, New York, 1969.

14. S. Fitzpatrick, Representing monotone operators by convex functions, in: S. Fitzpatrick and J. Giles (eds.), Workshop/Miniconference on Functional Analysis and Optimization (Canberra, 1988 ), 59–65, Proceedings of the Centre for Mathematical Analysis, Australian National University, vol. 20, Australian National University, Centre for Mathematical Analysis, Canberra, 1988.

15. K. Goebel and W.A. Kirk, Topics in Metric Fixed Point Theory, Cambridge Studies in Advanced Mathematics, vol. 28, Cambridge University Press, Cambridge, 1990.

16. A. Granas and J. Dugundji, Fixed Point Theory, Springer Monographs in Mathematics, Springer-Verlag, New York, 2003.

17. A. Granas and M. Lassonde, Sur un principe géométrique en analyse convexe, Studia Math. 101 (1991), no. 1, 1–18.

18. M. Gromov, Monotonicity of the volume of intersection of balls, in: J. Lindenstrauss and V. D. Milman (eds.), Geometrical Aspects of Functional Analysis, 1–4, Lecture Notes in Mathematics, vol. 1267, Springer-Verlag, Berlin, 1987.

19. F. Grünbaum and E. H. Zarantonello, On the extension of uniformly continuous mappings. Michigan Math. J. 15 (1968), 65–74.

20. J. Heinonen, Lectures on Lipschitz Analysis, University of Jyväskylä Department of Mathematics and Statistics Report, vol. 100, University of Jyväskylä, Jyväskylä, 2005.

21. J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms. I. Fundamentals, Grundlehren der Mathematischen Wissenschaften, vol. 305, Springer-Verlag, Berlin, 1993.

22. E. Hrushovski and Y. Peterzil, A question of van den Dries and a theorem of Lipshitz and Robinson; not everything is standard, J. Symbolic Logic 72 (2007), no. 1, 119–122.

23. V. Klee (ed.), Convexity (Seattle, 1961 ), Proc. Sympos. Pure Math., vol. VII, Amer. Math. Soc., Providence, RI, 1963.

24. G. Kleiner, Convex sets and the modulus of continuity, Zeszyty Nauk. Uniw. Jagiello. Prace Mat. Zeszyt 13 (1969), 41–44.

25. M. Mandelkern, On the uniform continuity of Tietze extensions, Arch. Math. (Basel) 55 (1990), no. 4, 387–388.

26. C. Miller, Expansions of dense linear orders with the intermediate value property, J. Symbolic Logic 66 (2001), no. 4, 1783–1790.

27. C. Miller and P. Speissegger, Expansions of the real line by open sets: o-minimality and open cores, Fund. Math. 162 (1999), no. 3, 193–208.

28. G. Minty, Monotone (nonlinear) operators in Hilbert space, Duke Math. J. 29 (1962), 341– 346.

29. W. Pawłucki, A linear extension operator for Whitney fields on closed o-minimal sets, Ann. Inst. Fourier (Grenoble) 58 (2008), no. 2, 383–404.

30. Y. Peterzil and A. Pillay, Generic sets in definably compact groups, Fund. Math. 193 (2007), 153–170.

31. R. R. Phelps, Lectures on maximal monotone operators, Extracta Math. 12 (1997), no. 3, 193–230.

32. R. T. Rockafellar, Convex Analysis, Princeton Mathematical Series, vol. 28, Princeton University Press, Princeton, N. J., 1970.

33. L. Sandgren, On convex cones, Math. Scand. 2 (1954), 19–28.

34. R. Schneider, Convex Bodies: The Brunn-Minkowski Theory, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press, Cambridge, 1993.

35. J. Schürmann, On the comparison of different notions of geometric categories, preprint (2002).

36. M. Shiota, Geometry of Subanalytic and Semialgebraic Sets, Progress in Mathematics, vol. 150, Birkhäuser Boston, Inc., Boston, MA, 1997.

37. S. Simons and C. Zălinescu, Fenchel duality, Fitzpatrick functions and maximal monotonicity, J. Nonlinear Convex Anal. 6 (2005), no. 1, 1–22.

38. F. A. Valentine, The dual cone and Helly type theorems, in [23], 473–493.

39. R. Webster, Convexity, Oxford Science Publications, Oxford University Press, New York, 1994.

40. C. Zălinescu, Convex Analysis in General Vector Spaces, World Scientific Publishing Co., Inc., River Edge, NJ, 2002.

University of California, Los Angeles, California, USA

   E-mail address: matthias@math.ucla.edu

The Fields Institute, Toronto, Ontario, Canada

   E-mail address: afischer@fields.utoronto.ca