The scalar product of and is defined as . Here, we have
2.
The scalar product of and is
3.
The scalar product is defined only for vectors of the same set , i.e. on the cartesian product of a set with itself. Hence, the scalar product of and does not exist.
(ii) An important property of real number multiplication is distributivity over addition: for any , it holds that . Does this hold for the scalar product as well? Justify your answer with a formal argument.
The property is true for the scalar product. Consider arbitrary vectors , where is some set of real vectors. Then,
b. Metrics
(i) Verify that the so-called French Railway Metric on ,
is indeed a metric, i.e. show that it satisfies the three properties that define a metric function. (Hint: use case distinctions for whether or not is true; the regular and inverse triangle inequality of the norm may be helpful at several instances.)
The three properties that we need to establish are: (a) non-negativity, (b) symmetry, and (c) triangle-inequality. (a) Non-negativity. This property has two parts: first, the function must always be weakly positive, and second, it must be equal to zero if and only if the arguments coincide – formally, (a.i) and (a.ii) . (a.i) is straightforward from non-negativity of the Euclidean norm. For (a.ii), if , then either and , or and . The latter case can be disregarded: If , then by non-negativity of the norm, , and , so that this case never occurs. In the former, , and by non-negativity of the norm, , i.e. . Hence, satisfies non-negativity.
(b) Symmetry. If , by absolute homogeneity of the norm,
Otherwise,
Hence, , i.e. is symmetric.
(c) Triangle inequality. Recall that intuitively, if , the path between and is “direct” and shorter than the other case. This also holds formally:
where the second step follows from the triangle inequality and the second from absolute homogeneity of the Euclidean norm. Hence, it holds that
(1)
Let . If , then, using the triangle inequality and absolute homogeneity of the Euclidean norm,
If instead, , then either, or , because otherwise, , and there exists for which . Without loss of generality, assume that there exists no (otherwise, re-label and ). Then,
With the inverse triangle inequality,
Hence, , i.e. satisfies the triangle inequality.
(ii) Consider a strictly monotonically increasing function , i.e. satisfies , for which . Further, consider a metric that measures the distance of vectors in . Can you find a sufficient condition that imposes one additional property on such that the monotonic transformation of induced by , i.e. for which , is guaranteed to be a metric?
When using a monotonic transformation, symmetry is guaranteed to be preserved: for any ,
by symmetry of .
Non-negativity is not problematic as well: for any , and thus , and
Lastly, for the triangle inequality, it is always true that
by strict monotonicity of and the triangle inequality of . However, to guarantee that this expression is weakly smaller than , an additional assumption must be imposed: for the range of , , if , then the triangle inequality is guaranteed. Intuitively, this means that satisfies a triangle inequality itself, which is the case when does not increase “too fast” with increasing arguments, we must e.g. have that so that , and increases faster in the argument than in the value, i.e. doubling the argument less than doubles the value.
In conclusion, the sufficient condition we were looking for is
(iii) Using the result of (ii), is a metric on , where is the metric induced by the Euclidean norm? (Hint: for all .)
The setup corresponds precisely to the scenario we investigated in (ii): for the metric induced by the Euclidean norm. Hence, the function we consider is . Because the natural logarithm function is strictly monotonically increasing on , so is on . Further, . The range of is (the distance of two vectors in can get infinitely large; as extends towards along any of its dimensions). By the result of (ii), we know that is a metric on if
For arbitrary ,
where the second equality follows from the logarithm rule given in the hint, and the fourth follows because . Hence, satisfies the sufficient condition found in (ii), and is indeed a metric on .
c. Norms
(i) The course discusses the most common examples of norm functions as used in practice. However, there are of course a variety of other functions that are norms. One such example is the following function on :
Verify that this function constitutes a norm according to our definition by establishing the three norm properties for .
The three properties that we need to establish are: (a) non-negativity, (b) triangle-inequality, and (c) absolute homogeneity. (a) Non-negativity. This property has two parts: weak positivity and equality to zero only at the origin. Weak positivity is trivial given that the absolute value is weakly positive. For the latter,
which is in turn equivalent to , i.e. . Hence, satisfies non-negativity. (b) Triangle-inequality. Note first that for any , by the triangle inequality of the absolute value,
Therefore, for any , using again the triangle inequality of the absolute value,
Hence, satisfies the triangle inequality. (c) Absolute homogeneity. For any and any ,
Hence, satisfies absolute homogeneity.
(ii) A key concept related to norms that the course does not discuss is norm equivalence. You may recall that we said that a function may be continuous in one metric space but not in the other, depending on the metric chosen. Similarly, convergence of sequences may depend on the metric chosen. A further appealing aspect of norm-induced metrics over general metrics is that at least in metric spaces over with finite , all of our usual p-norms are equivalent, which means that if a function satisfies continuity or a sequence converges with respect to one norm, they do so with respect to the other as well.
It turns out to be sufficient for norm equivalence that we can reduce the differences in two norms to some constants that matter little in the -arguments we use to investigate convergence, continuity and related concepts. Formally, two norms and on are said to be equivalent if there exist constants such that
Show that all p-norms are equivalent on any , i.e. that , is equivalent to on for any . (Hint: this is easiest done in two steps: (1) show that any -norm is equivalent to the maximum norm, and (2) show that if a – and -norm are both equivalent to the maximum norm, the – and -norm are also equivalent to each other.)
Let and .
Following the hint, we first show that is equivalent to :
Let , and , i.e. so that . Then,
and
Hence, we obtain
which meets the definition of norm equivalence with and .
Now for the second step: take . By the first step, we know that
Therefore,
and
so taken together
which meets the definition of norm equivalence with and .
Exercise 2: Testing for Set Properties
For the following sets, investigate whether they are open, closed, compact and/or convex. Throughout the exercise, consider the natural metric of or the Euclidean norm of the . Note that there always are quite a number of ways to establish the set properties. It may well be that the solution sketches do not always cover your approach, even if it is correct – you should, however, always arrive at the same set properties as the solutions. The solution of 2.a is relatively verbose and also gives some review here and there, so it may be a good idea to start with this exercise.
a. A subset of the real line.
Let . Is this set open, closed, compact and/or convex?
Closedness and Openness
First, it is instructive to simplify the expression for . Noting that , we can re-write
You may know that closed intervals on the real line are, in fact, closed and not open, which makes this case trivial. However, this exercise provides a good opportunity to get some practice with the formal concepts using a manageable example, hence let us not rely on this fact in the following. This solution outlines the “direct” approach via the definitions and then gives the “sequence approach to closedness” as an alternative solution.
The closure of is every point “inside or touching” , i.e.
Clearly, this applies to any . Further, for , we can choose small enough so that the -open ball around does not overlap with : set e.g. . Then,
Because , , and . Hence, it does not hold that . Thus, is not a closure point of .
Similarly, for any fixed , we can set . Then,
and because , , and . As above, is not a closure point of .
The reasoning suggests that any point for which either or is not a closure point of . Hence:
that is, is equal to its closure, and by definition of the closed set, is closed.
Recall that closedness was the scenario where all boundary points are contained in the set, whereas openness was that none of them are. Hence, once we know that the set is closed, to disprove openness, it suffices to show that the set indeed has boundary points. Recall that boundary points where those elements of the set that are not in the interior, i.e. points for which there does not exist an -open ball around that is contained in (). Intuitively, it should be pretty clear that and are such points, because any -ball around them will contain elements outside . Formally:
Consider . Let . Then, but . Hence, is no subset of . Because was chosen arbitrarily, there exists no such that , and is not an interior point of . Hence, it is a boundary point.
Because is closed and has at least one boundary point, is not open.
Alternatively, you can use the sequence approach to establish closedness with relative ease:
To apply the sequence method, we (1) define an arbitrary sequence over the set in question and assume only that it converges to some limit point (potentially outside the set), (2) show that the limit point is indeed contained in the set, and (3) argue that because the convergent sequence was chosen arbitrarily, any convergent sequence over the set will have its limit in the set as well — which is what we need to show for the proposition we intend to use. So, let’s do this:
(1) Let be a sequence over , i.e. , and assume that the sequence converges to a limit .
(2) By the definition of convergence,
If were not an element of , because all the are, there would exist a small so that : , which violates the definition of convergence. Hence, must be an element of .
(3) Because we only imposed convergence for and nothing else, any convergent sequence over will have .
Compactness and Convexity
Compactness
By Heine-Borel’s theorem, because we already know that is closed, it suffices to investigate boundedness for compactness. From the chapter, we know that it is sufficient to show that the norm that induces our metric is bounded on , i.e. . The norm that induces the natural metric of the is the absolute value, so that we must find for which . Clearly, for any , this is satisfied, such that the we are looking for exists! Hence, is also bounded, and thus compact.
Convexity
For convexity, the course has argued that intervals on the real line are convex. If you want to show convexity here explicitly, you can either refer to the line-intuition or the formal definition.
For the line, if you pick any two points , , the collection of points on the line connecting them is , and as , , i.e. the line is fully contained in . By the arbitrary choice of and , is convex.
For the definition, if you pick any two points and , you have
and
and thus . By the arbitrary choice of and and , is convex.
b. A complement.
Let . Is this set open, closed, compact and/or convex?
The complement of is .
Closedness and Openness
As the complement of a closed set (see the solution of Ex. 2.a), is open. is not closed: to establish this, we show that there exist boundary points that are not contained in . Again, a natural candidate is . This is indeed a boundary point: for any contains points in and thus points in (e.g. ). Hence, is not closed.
Compactness
Because is not closed, by Heine-Borel, it can not be compact. Moreover, is unbounded below and above, as it extends indefinitely towards and , and one may show that is also not bounded. As it is sufficient that is not closed, however, the unboundedness argument is not given here formally.
Convexity is not convex: consider and , . Then, .
c. Two dimensions.
Let . Is this set open, closed, compact and/or convex?
Closedness and Openness
The set is closed and not open.
Closedness can be shown from openness of the complement: . For any , , and for , for any ,
Therefore, it especially holds that , and
Hence, . So, there exists such that , and is an interior point of . Because was chosen arbitrarily, it results that , i.e. is open. Thus, is closed.
To disprove openness, we need to find a boundary point. Intuitively, any with will have points with in its neighborhood that are not contained in , and therefore constitute a non-interior, i.e. boundary point. Formally:
Let . Then, . For any , for , it holds that
so that . Accordingly, . Because , is a boundary point. Hence, is not open.
Compactness is not bounded. Intuitively, the -dimension is entirely unrestricted, and the -dimension is also restricted only above, such that the set can expand indefinitely into three directions. Formally:
For two points ,
Hence, for any , we can pick with and (and the first dimension chosen in any way that ensures ) so that
and there exists no so that for all . Thus, is not bounded.
Convexity is convex: Let and . Then,
and .
d. A set defined by functional equality.
Let . Is this set open, closed, compact and/or convex? You can use that is a continuous function.
Closedness and Openness is closed and not open. Perhaps, the easiest way to establish this is the sequence method (see the solution of Ex. 2.a for the step-by-step recipe):
Let be a sequence over , i.e. , and assume that the sequence converges to a limit . Then, with as defined in the setup,
and thus, . Hence, is closed.
To disprove openness, we need to find a boundary point of . Indeed, every point is a boundary point: for any , for any , and (this works as because ). Hence, is not open.
Compactness is not bounded and hence not compact: consider and . Note that for any , , and moreover
Hence, for , , and in particular, for any , there exists such that and
Thus, there exists no such that for all , , and is not bounded.
Convexity
You can see formally that only very particular combinations of and satisfy . To disprove convexity, it is sufficient to find one such example, such that you don’t need to dig into the formal investigation. Consider e.g. and , and . Then, for which . Hence, is not convex.
e. The graph of a univariate real-valued function.
Let , i.e. the graph of a function . Is this set open, closed, compact and/or convex?
You may assume that . Your answers may depend on whether is (a) continuous and (b) linear. Hint: As we will see in Exercise 3, the limit of vectors can be applied element-wise, so that if is a convergent sequence, we have .
Note that is a subset of ; hence, we use the Euclidean norm.
Closedness and Openness
Perhaps, the easiest way to investigate closedness is the sequence method (see the solution of Ex. 2.a for the step-by-step recipe):
Let be a sequence over , i.e. , and assume that the sequence converges to a limit . For simplicity and because , we write elements in the sequence as in the following.
We have
Note that if and only if , which is the case if and only if , i.e. is a continuous function. Hence, if is continuous, is closed. Otherwise, is not closed.
On the other hand, is never open: for any , for any , since
but ; i.e. any is a boundary point and not an interior point. Hence, is not open.
Compactness is not bounded because the set of arguments is unbounded; , which is allowed to diverge to . More formally, one would fix either or and argue that and thus diverges as the other variable tends to , and thus, the bound required by the definition of boundedness can not exist (cf. the previous exercises).
If the domain were bounded, the graph might still be unbounded, namely the range of is unbounded; an example is , where . Then, apply the logic of above using . However, if both domain and range of are bounded, then the graph is bounded as well. Formally, if are bounds so that and for any where is the domain of (which exist if and only if domain and range of are bounded), then for any ,
such that bounds the distances of objects in the graph.
Convexity is convex if and only if for any and , , which is the case if and only if . This is precisely the characterization of a linear function, i.e. a function for which there exist such that for all , . Hence, is convex if and only if is a linear function.
Exercise 3: Element-wise Applicability of the Multivariate Limit
The course discussed the multivariate limit concept for general metric spaces. However, just from the definition, it is not too obvious how we should use it. Here, we turn to a rather powerful result, namely that the limit can be applied element-wise in metric spaces where the metric is -norm induced.
Fact 1. In any normed space , where is a p-norm, , is the limit of the sequence over with for all if and only if all component sequences , , are convergent, and .
Prove Fact 1. Hint 1: This is an equivalence proof, which typically means that you must show two directions separately. Hint 2: Recall Exercise 1: all -norms are equivalent! Hence, it is sufficient to pick any one -norm and show that Fact 1 holds for this specific case; convenient choices may be the -norm or the -norm; the solution given here uses the norm.
As per hint 2, let us choose the -norm as the p-norm we consider.
First, the perhaps more intuitive direction: we show that if all component sequences converge and , then is the limit of . It needs to be established that
(2)
Now, fix an arbitrary . By convergence of the component sequences, for any , there exists . Hence, there exists such that
which is equivalent to
Since , and by the arbitrary choice of , this establishes (2).
Now, the other direction: we need to show that if is the limit of , then all component sequences converge and . While this sounds a bit more intimidating, the logic is very similar to what we did so far.
Because is the limit of , it holds that
Plugging in , one obtains
Now, fix an arbitrary . Let so that . Because for any , , it also holds that
Hence, by the arbitrary choice of , for any , it holds that
This is precisely the definition of the univariate limit, which allows to conclude that for any , the component sequence converges with limit . Hence, .
As a take-away of this exercise, you can memorize:
When you want to compute a multivariate limit, you can pull the limit operator into the individual entries.