Cheap Set-valued Analysis

1. The All-or-Nothing Filter

Most of the time when we want to prove something about inequalities we make use of the trick of ‘worsening the estimates’: we may know that, say, x lies in A and y lies in B, but we drop this in favour of weaker facts, x ∈ A′ and y ∈ B′, for a certain A′ ⊃ A and a certain B′ ⊃ B; with these new conditions some calculations become easier to do, and, after maybe a series of steps like these we get to the conclusion that we desire, that is something like f(x, y) ∈ W (think in A, B, A′, B′ and W as being intervals to get a good mental picture). Here we’ll show how a technique very close to the one in section ... lets us do all calculations with the variables assuming many values at the same time (they’ll be “set-valued”), while still retaining all the properties of the familiar, “point-valued” situation.

As in the previous section, we’ll start with a simple example and then proceed to translate it into the usual language. Everything in this example will be happening over the reals.

Suppose that we have p(x) := x^{4}+a(x)x^{3}+b(x)x^{2}+c(x)x+d(x), where each of the functions a, b, c and d is bounded, and that we want to show formally that for all |x| sufficiently large (i.e., ∀x |x| > R) the sign of p(x) is the same as the sign of its leading term, x^{4}; moreover, suppose that we want to obtain an estimate for R. Then we can reason like this, if we are allowed to use set-valued variables:

(start indentation...)

take a value k such that ∀x |a(x)| ≤ k, …, |d(x)| ≤ k; without loss of generality we can take k ≥ 1. We’ll show that R can be taken as 2k. Let’s denote by s a variable that assumes exactly the values in the interval [−1, 1], and by u the “unsigned” version of s, that assumes all values in the interval [0, 1]. We’ll “worsen” a(x) by replacing it by ku, and we’ll do the same for b, c and d; then we’ll show that for any x such that |x| ≥ 2k all values assumed by ksx^{3} + ksx^{2} + ksx + ks have module smaller than |x^{4}|.

Fix an x with |x| ≥ 2k, and define h := \frac{x}{2}. Then ks “fits into” hs, in the sense the set of values that ks assume is contained in the set of values of hs. It is easy to check that

a(x)x^{3} + b(x)x^{2} + c(x)x + d(x) fits into

ksx^{3} + ksx^{2} + ksx + ks that fits into

hsx^{3} + hsx^{2} + hsx + hs that fits into, and is equal to

hs(2h)^{3} + hs(2h)^{2} + hs(2h) + hs that fits into, and is equal to 8h^{4}s + 4h^{3}s + 2h^{2}s + hs that fits into, and is equal to 8h^{4}s + 4h^{4}s + 2h^{4}s + h^{4}s that fits into, and is equal to 15h^{4}s,

but all the values that |15h^{4}s| take are less than |16h^{4}| = |(2h)^{4}| = |x^{4}|, and so we’re done: a(x)x^{3} + b(x)x^{2} + c(x)x + d(x) ∈ (−|x^{4}|, |x^{4}|).

(...end indentation).

The trick to translate this argument to standard terms is to consider each s as being a point-valued function of 𝕚; the value of each s becomes a set when we “forget at which 𝕚 we were looking at” and we move on to the full image of 𝕀 by the function s. However, each s is a different function of 𝕚, and to get the right interpretation for

f(s, s)  fits into  g(s, s)

we have to translate it to

f(s_{1}, s_{2})  =  g(s_{3}, s_{4}),

where we omit the parameters 𝕚 from s_{1}(𝕚), s_{2}(𝕚), s_{3}(𝕚), s_{4}(𝕚); to convey the right meaning we have to choose a function 𝕚 → (s_{1}, s_{2}) whose image is exactly [−1, 1]^{2}, and the affirmative “f(s, s) fits into g(s, s)” is then equivalent to “∀𝕚 ∃(s_{3}, s_{4}) … ”, or, equivalently, “∀(s_{1}, s_{2}) ∃(s_{3}, s_{4}) … ”.

There are universal ways to choose an index set and its projections into the ‘s’s; for the case f(s_{1}, s_{2}) = g(s_{3}, s_{4}) we may take E_{𝕚} = { (s_{1}, s_{2}, s_{3}, s_{4}) | f(s_{1}, s_{2}) = g(s_{3}, s_{4}) }; if then the natural projection 𝕚 → (s_{1}, s_{2}) does not cover all of the [−1, 1]^{2} that will mean that there are pairs (s_{1}, s_{2}) for which no good corresponding (s_{3}, s_{4}) exist, and so “f(s, s) fits into g(s, s)” is false. For the big example about p(x) and |x^{4}| for all of the steps we have more obvious ways to choose the new ‘s’s: in “a(x)x^{3} +b(x)x^{2} +c(x)x+d(x) fits into ks_{1}x^{3} +ks_{2}x^{2} +ks_{3}x+ks_{4}” we can take s_{1} = \frac{a(x)}{k}, …, s_{4} = \frac{d(x)}{k}; for “ks_{1}x^{3} + ks_{2}x^{2} + ks_{3}x + ks_{4} fits into hs_{5}x^{3} + hs_{6}x^{2} + hs_{7}x + hs_{8}” we can take s_{5} = \frac{k}{h}s_{1}, …, s_{8} = \frac{k}{h}s_{4}, and so on, and this will be enough to prove that there’s an adequate s_{21} such that a(x)x^{3} + b(x)x^{2} + c(x)x + d(x) = 15h^{4}s_{21}.

2. Corsets and Continuity

Still on the context of functions from the reals to the reals let’s define what we’ll call a corset. Take any non-decreasing function h : [0, ∞) → [0, ∞] whose limit when its parameter goes to zero is zero; the symmetric corset generated by h is the set { (x, y) | |y| ≤ h(x) }, and we say that a subset of ℝ^{2} is a symmetric corset when there is a function h satisfying the conditions above that generates it. Some examples of symmetric corsets are the horizontal line, the set { (x, y) | |y| ≤ x } and sets like the one drawn below:

It is trivial but boring to define corsets without the symmetry requirement; they’ll be generated by four monotonic functions. We can also define a corset over (x_{0}, y_{0}) as being a set that becomes a corset when translated by −(x_{0}, y_{0}), a Lipschitz corset as a corset whose h is of the form αx for some α ∈ [0, ∞), a xo(x) corset as one in which h(x) = xo(x) for some function o(x) from [0, ∞) to [0, ∞] that goes to zero when its parameter goes to zero, and so on; note that every corsets (without further attributes) is a o(x)-corsets and vice-versa.

A function f : ℝ → ℝ that has f(0) = 0 is continuous at 0 iff its graph is contained in a corset; a function f : ℝ → ℝ is continuous iff for every x its graph is contained in a corset over (x, f(x)); it is Lipschitz iff for every x its graph is inside a Lipschitz corset over (x, f(x)), and it is uniformly continuous iff there’s a single corset C such that for every x the graph of f is inside C + (x, f(x)), that is C translated to make it into a (x, f(x))-corset.