# Math4225 Homework 2

2.4.2 (1) If d(f, g) < ε and max0≤t≤1 f = f(t0), then g(t0) > f(t0) - ε, so that M(g) > M(f) - ε. Switching the roles of f and g, we also have M(f) > M(g) - ε. Therefore |M(f) - M(g)| < ε. This shows that M is continuous with respect to the L-metric.

On the other hand, M is not continuous with respect to the L1-metric. This can be seen easily by constructing g so that has the area between f and g is very small area, but g is significantly bigger than max0≤t≤1 f somewhere.

(2) We have |I(f) - I(g)| ≤ ∫ |f(t) - g(t)| dt = d1(f, g). Therefore d1(f, g) < ε implies |I(f) - I(g)| < ε. This implies that I is continuous with respect to the L1-metric.

By d1d, we have |I(f) - I(g)| ≤ d1(f, g) d(f, g). Therefore d(f, g) < ε implies |I(f) - I(g)| < ε. This implies that I is continuous with respect to the L-metric.

(3) Take the metric on X x Y to be d((x, y), (x', y')) = dX(x, x') + dY(y, y').

For the L-metric, we have d(σ(f + g), σ(f' + g')) = max0≤t≤1 |f(t) + g(t) - f'(t) - g'(t)| ≤ max0≤t≤1|f(t) - f'(t)| + max0≤t≤1|g(t) - g'(t)| = d(f, g) + d(f', g') = d((f, f'), (g, g')), where the right side is the product L-metric on C[0, 1]2. The inequality shows that σ is continuous with respect to the L-metric.

For the L-metric, we have d1(σ(f + g), σ(f' + g')) = ∫|f(t) + g(t) - f'(t) - g'(t)|dt ≤ ∫|f(t) - f'(t)|dt + ∫|g(t) - g'(t)|dt = d1(f, g) + d1(f', g') = d1((f, f'), (g, g')), where the right side is the product L1-metric on C[0, 1]2. The inequality shows that σ is continuous with respect to the L1-metric.

2.4.3 By d1d, we have d1(id(f), id(g)) ≤ d(f, g). This implies that the identity map is continuous from the L-metric to the L1-metric. The converse is not true because we could have very small d1(f, g) and very big d(f, g) at the same time.

2.4.4 Let (x0, y0) be rational numbers and ε > 0. The subsequent argument will be for the case both x0 and y0 are nonzero. The case at least one of them is zero is simpler and will be omitted.

Since both x0 and y0 are nonzero, we may write x0 = (m0/n0)pa0 and y0 = (k0/l0)pb0 in the usual way. Then we assume x - x0 = (m/n)pa and y - y0 = (k/l)pb in the usual way, with dp-adic(x, x0) = p-a < δ and dp-adic(y, y0) = p-b < δ, where δ > 0 is to be determined. Our goal is to determine δ so that dp-adic(xy, x0y0) < ε. Note that

xy - x0y0
= (x - x0)[(y - y0) + y0] + x0(y - y0)
= (m/n)pa[(k/l)pb + (k0/l0)pb0] + (m0/n0)pa0(k/l)pb
= [(m/n)pa+b-c + (mk0/nl0)pa+b0-c + (m0k/n0l)pa0+b-c]pc,

where c = min{a + b0, a + b, a0 + b}. The sum in the bracket is of the form (r/s)pd, where r and s are integers not divisible by p, and d is a non-negative integer. Thus we have dp-adic(xy, x0y0) = p-c-dp-c. The problem is now reduced to the choice of δ so that p-a < δ and p-b < δ implies p-c < ε. Since this is equivalent to p-a0δ ≤ ε, p-b0δ ≤ ε, δ2 ≤ ε, we should choose d = min{pa0ε, pb0ε, √ε}.

2.4.5 By AE - BEA - B and BE - AEB - A, we have (AE - BE) ∪ (BE - AE) ⊂ (A - B)∪(B - A). By taking minimum (note: XY ⇒ minX ≥ minY) and reciprocal, we conclude that d(AE, BE) ≤ d(A,B). Then it follows from Exercise 2.4.8 that union with E is a continuous map.

We also have AE - BEA - B. Then by the similar argument as before, we may prove d(AE, BE) ≤ d(A,B), which implies that intersection with E is a continuous map.

Finally, substracting E is the same as intersecting N - E. Therefore the substraction is also continuous.

2.4.6 For aX and ε > 0, we need to find δ > 0, such that d(x, a) < δ implies |f(x) + g(x) - f(a) - g(a)| < ε.

Note that in order for the final conclusion to hold, it suffices to have |f(x) - f(a)| < ε/2 and |g(x) - g(a)| < ε/2. Based on this observation, we come up with the following argument: For the given a and ε, by the continuity of f, we have δ1 > 0, such that d(x, a) < δ1 implies |f(x) - f(a)| < ε/2. Similarly, by the continuity of g, we have δ2 > 0, such that d(x, a) < δ2 implies |g(x) - g(a)| < ε/2. Choose δ = min{δ12}. Then d(x, a)< δ implies

|f(x) + g(x) - f(a) - g(a)| ≤ |f(x) - f(a)| + |g(x) - g(a)| < ε/2 + ε/2 = ε.

Now let us prove the continuity of fg. The conclusion we would like to reach is |f(x)g(x) - f(a)g(a)| < ε. The key observation is the inequality

|f(x)g(x) - f(a)g(a)|
= |f(x)g(x) - f(a)g(x) + f(a)g(x) - f(a)g(a)|
≤ |f(x) - f(a)| |g(x)| + |f(a)| |g(x) - g(a)|.

Because the inequality is more complicated than the summation case, it is a little bit more complicated to predict how small |f(x) - f(a)| and |g(x) - g(a)| should be. Thus we will simply assume |f(x) - f(a)| < ε' and carry out the argument. The size of ε' will become clear near the end.

Based on the analysis above, we come up with the following argument: For the given a and ε, we will postulate a small number ε' > 0, which will depend only on the given data (f, g, a, ε) and will be determined at the end. By the continuity of f, we have δ1 > 0, such that d(x, a) < δ1 implies |f(x) - f(a)|< ε'. Similarly, by the continuity of g, we have δ2 > 0, such that d(x, a)< δ2 implies |g(x) - g(a)| < ε'. Choose δ = min{δ12}. Then d(x, a) < δ implies

|f(x)g(x) - f(a)g(a)|
≤ |f(x) - f(a)| |g(x)| + |f(a)| |g(x) - g(a)|
< ε'(|g(x) - g(a)| + |g(a)|) + |f(a)|ε'
< ε'(ε' + |g(a)|) + |f(a)|ε',

which will be ε as long as ε' satisfies

ε'2 + |g(a)|ε' + |f(a)|ε' < ε.

This suggests us that we could use ε' = (1 + |f(a)| + |g(a)|)-1 at the beginning of our arguement.

2.4.8 For any aX and ε > 0, we take δ = ε/c. Then dX(x, a) < δ implies dY(f(x), f(a)) < c dX(x, a) < c δ = ε.

2.4.10 For any bX (I choose b because a has been used) and ε > 0, we take δ = ε. Then d(x, b) < δ implies |f(x) - f(b)| = |d(x, a) - d(b, a)| ≤ d(x, b) < ε, where ≤ follows from Exercise 2.1.6.

2.4.11 For any (a, b) ∈ X×X and ε > 0, we take δ = ε/2. Then d((x, y), (a, b)) < δ implies d(x, a) < δ and d(y, b) < δ. Then it follows from Exercise 2.1.6 that |d(x, y) - d(a, b)| ≤ |d(x, a)| + |d(y, b)| < 2δ = ε.

2.4.12 Suppose f is continuous and lim an = x. For this x and any ε > 0, there is δ > 0, such that

d(y, x) < δ ⇒ d(f(y), f(x)) < ε.

By lim an = x, for this δ > 0, there is N, such that

n > Nd(an, x) < ε.

Combining thwe two implicaitons together, we get

n > Nd(f(an), f(x)) < ε.

This proves that lim f(an) = f(x).

On the other hand, if f is not continuous, then there is x and ε > 0, such that for any δ > 0, there is a satisfying d(a, x) < δ, yet d(f(a), f(x)) ≥ ε. By choosing δ = 1/n, we get an satisfying d(an, x) < 1/n, yet d(f(an), f(x)) ≥ ε. Therefore we have lim an = x, yet lim f(an) ≠ f(x). This proves the other direction.

2.4.14 If Y has the discrete metric, then the continuity of f: XY means that f-1(U) is open for any subset U of Y. This is often not true. For a concrete example, we consider

f(x) = x: (R, usual metric) → (R, discrete metric)

The subset U = {0} is open in (R, discrete metric). However, f-1(U) = U is not open in (R, usual metric). Therefore f is not continuous.

2.4.15 Denote f(x) = d(x, A). The following picture suggests that |f(x) - f(y)| ≤ d(x, y).

To rigorously prove |f(x) - f(y)| ≤ d(x, y), we note that we have

f(y) ≤ d(y, a) ≤ d(x, a) + d(x, y),

for any aA, where the first ≤ comes from the definition of f(y), and the second ≤ comes from triangle inequality. Since the left side of the inequality is independent of a, we we take the inf of the right side for all aA, and get

f(y) ≤ f(x) + d(x, y).

By exchanging the roles of x and y, we can similarly prove

f(x) ≤ f(y) + d(x, y).

Thus we conclude that |f(x) - f(y)| ≤ d(x, y).

The inequality implies the continuity of f at yX in the following way: For any yX and ε > 0, we choose δ = ε. Then we have

d(x, y) < δ ⇒ |f(x) - f(y)| ≤ d(x, y) < δ = ε,

which verifies the definition of the continuity.

Finally, we have

Aε = {xX: d(x, a)< ε for some aA} = {xX: f(x) < ε} = f-1(-∞,ε).

Since f is continuous and (-∞,ε) is open, we conclude that Aε is open.

2.5.1

Exercise 2.3.5

(1) The limit points in L-metric are f satisfying f(0) ≥ 0. The limit points in L1-metric are all functions.

(2) The limit points in L-metric are f satisfying f(0) ≥ 0. The limit points in L1-metric are all functions.

(3) The limit points in L-metric are f satisfying f(0) ≥ f(1). The limit points in L1-metric are all functions.

(4) The limit points in L-metric are f satisfying t + 1 ≥ f(t) ≥ t2. The limit points in L1-metric are the same.

(5) The limit points in L-metric are f satisfying t + 1 ≥ f(t) ≥ t2. The limit points in L1-metric are the same.

(6) The limit points in L-metric are f satisfying ∫01f(t)dt ≥ 0. The limit points in L1-metric are the same.

(7) The limit points in L-metric are f satisfying ∫01f(t)dt ≥ 0. The limit points in L1-metric are the same.

(8) The limit points in L-metric are f satisfying ∫01/2f(t)dt ≥ ∫1/21f(t)dt. The limit points in L1-metric are the same.

Exercise 2.3.6 Note that the 2-adic metric is an ultrametric: d(x, y) ≤ max{d(x, z), d(z, y)}.

(1) Suppose x ≠ 0 is a limit of integers. By the ultrametric property, d(x, 0) ≤ max{d(x, n), d(n, 0)}. By chosing integer n so that d(x, n) < ε = d(x, 0), we find d(x, 0) ≤ d(n, 0) ≤ 1. Therefore the denominator of x is an odd number.

Conversely, suppose b is an odd number such that there is an integer k ≥ 1 satisfying 2k = 1 modulo b. Then we get 2kn = 1 + bm for any n and some integer m. This implies 2kn/b = 1/b + m, so that d(1/b, m) = 2-kn can be as small as possible. This proves that 1/b is a limit point of all integers.

Now we claim that any odd number b has the property. The reason comes from the group theory. Since the number 2 is coprime to b, it is an invertible element in the group (Z/bZ)* of multiplicatively invertible elements in the ring Z/bZ. The group is finite with order k (actually denoted φ(b) and called the Euler function). From theory of finite groups, 2k is the identity element in the group (Z/bZ)*, which means 2k = 1 modulo b.

It is not difficult to prove that if x and y are limit points of integers, then x + y and -x are also limit points. Therefore if 1/b is a limit point, then a/b is also a limit point. In particular, by taking a to be multiples of b, integers are limit points. We conclude that the limit points are those with odd numbers as denominator (including 1 as denominator).

(2) The set is obtained by multiplying 2 to all the points in the set in (1). By d(2x, 2y) = d(x, y)/2, it is easy to see that the limit points are obtained by multiplying 2 to the limit points in (1). In other words, the limit points are of the form even/odd.

(3) Suppose x ≠ 0 is a limit of odd/even. By the ultrametric property, d(r, 0) ≤ max{d(r, x), d(x, 0)}. By chosing r = odd/even so that d(x, r) < ε = d(x, 0), we find d(x, 0) ≥ d(r, 0) ≥ 2. Therefore x is also of the form odd/even.

Conversely, assume x is of the form = odd/even. Then x + 2k is also of the form = odd/even and d(x, x + 2k) = 2-k. This shows that x is a limit point.

(4) Suppose x ≠ 0 is a limit of even/odd. By the ultrametric property, d(x, 0) ≤ max{d(x, r), d(r, 0)}. By chosing r = even/odd so that d(x, r) < ε = d(x, 0), we find d(x, 0) ≤ d(r, 0) ≤ 1/2. Therefore x is also of the form even/odd.

Conversely, assume x is of the form = even/odd. Then x + 2k is also of the form = even/odd and d(x, x + 2k) = 2-k. This shows that x is a limit point.

(5) By an argument similar to (3), a limit point must has odd numerator. Conversely, assume x = a/b, with a odd. Then for any k, a is a generator in the cyclic additive group Z/2kZ. This implies that na = b modulo 2k for some integer n. Dividing nb, we get x - 1/n = 2km/n. If k is bigger than the number of 2-factors in b, then the number of 2-factors in n must be the same as the number in b. Therefore the number of 2-factors in 2km/n is getting bigger as k gets bigger. In other words, d(x, 1/n) can become as small as we want. We conclude that the limit points are those with odd numerator.

(6) For any rational number x = a/b, we have x - x/(2n+1) = a2n/b(2n+1). This implies that d(x, x/(2n+1)) can become as small as we want as n gets bigger. Since x/(2n+1) has small absolute value as n gets bigger, we conclude that any rational number is a limit.

Exercise 2.3.7

(1) All subsets with numbers bigger than 10.

(2) No limit points.

(3) All subsets of even numbers.

(4) All subsets that does not contain 100.

(5) All subsets.

(6) All single subsets and empty set.

2.5.2 Suppose xA is a limit point of A. Then there is aA, such that d(a, x) < ε/2. If there is another bA that also satisfies d(b, x) < ε/2. Then d(a, b) < ε, contradicting to the assumption about the distance between the elements of A. Therefore a is the only element of A satisfying d(a, x) < ε/2. Then for δ = d(a, x) > 0 (xa because xA), there is no bA satisfying d(b, x) < δ. This shows that x is not a limit point of A.

Now consider xA. Then by the assumption, there is no aA satisfying ax and d(a, x) < ε. Therefore x is not a limit point of A.

2.5.3 Let d'(x, y) < c d(x, y). Then Bd(x, ε) ⊂ Bd'(x, cε), which implies (A - x) ∩ Bd(x, ε) ⊂ (A - x) ∩ Bd'(x, cε). Therefore (A - x) ∩ Bd(x, ε) is nonempty for arbitrary ε > 0 implies (A - x) ∩ Bd'(x, cε) is nonempty for arbitrary ε > 0 (ε is arbitrary is equivalent to cε is arbitrary). In other words, the limit points of A in metric d must be limit points of A in metric d'.

2.5.4 1. (A - x) ∩ Bd(x, ε) ≠ ∅ implies (B - x) ∩ Bd(x, ε) ≠ ∅.

2. Since A and B are contained in AB, by part 1 we conclude that A'B' ⊂ (A B)'.

To prove the inclusion in another direction, we assume x is not in A'B'. Then we have (A - x) ∩ Bd(x, ε) = ∅ and (B - x) ∩ Bd(x, ε') = ∅ for some ε, ε' > 0. This implies (AB - x) ∩ Bd(x, min{ε, ε'}) ⊂ ((A - x) ∩ Bd(x, ε)) ∪ ((B - x) ∩ Bd(x, ε')) = ∅. Therefore x is not in (A B)'.

The following argument for (AB)' to be contained in A'B' is wrong:

Let x be a limit point of AB. Then (AB - x) ∩ Bd(x, ε) ≠ ∅ for any ε > 0. Since (AB - x) ∩ Bd(x, ε) = ((A - x) ∩ Bd(x, ε)) ∪ ((B - x) ∩ Bd(x, ε)), we have (A - x) ∩ Bd(x, ε) ≠ ∅ ot (B - x) ∩ Bd(x, ε) ≠ ∅.

The subtle point is that the reasoning here only shows that for ONE ε, we find one a in A (or in B). It does not exclude the possibility that for ANOTHER ε, we find b in B instead of A. On the other hand, we are required to make up our mind on whether x is a limit point of A or not BRFORE the choice of ε. In other words, we cannot change our mind for different choices of ε.

3. By part 1 it is easy to see that (AB)' ⊂ A'B'. However, the containment other way around is not true.

Consider X = R with the usual metric. Take A = (-1, 0), B = (0, 1). Then AB is empty and so is (AB)'. On the other hand, A'B' = [-1, 0] ∩ [0, 1] = {0} is not empty.

4. Let xA''. Then for any ε > 0, we have a', such that

1) a'A', 2) a'x, 3) d(a', x) < ε.

Since a'A', for ε' = min{d(a', x), ε - d(a', x)} > 0, we have a, such that

1) aA, 2) aa', 3) d(a, a') < ε'.

Then d(a, a') < ε' ≤ d(a', x) implies ax. Moreover, we have

d(a, x) ≤ d(a', x) + d(a, a') < d(a', x) + ε' ≤ d(a', x) + (ε - d(a', x)) = ε.

Thus we conclude that

1) aA, 2) a x, 3) d(a, x) < ε,

and xA'.

2.5.5 Suppose there is such a sequence. Since aiaj for ij, we have at most one an equal to x. By deleting this an if necessary, we may assume all anx. Now for any ε > 0, we have some an, such that d(an, x) < ε. Thus we have

1) anA, 2) anx, 3) d(an, x) < ε.

This shows that x is a limit point of A.

Conversely, assume x is a limit point of A. Then we can find a sequence of points as follows

1) a1A, 2) a1x, 3) d(a1, x) < 1,

2) a2A, 2) a2x, 3) d(a2, x) < min{d(a1, x), 1/2},

3) a3A, 2) a3x, 3) d(a3, x) < min{d(a2, x), 1/3},

n) anA, 2) anx, 3) d(an, x) < min{d(an-1, x), 1/n},

This sequence {an} is a non-repetitive sequence in A with limn→∞d(an, x) = 0.

2.5.8 Since xU and U is open, we have B(x, δ) ⊂ U for some δ > 0. Now for any ε satisfying δ ≥ ε > 0, since x is a limit point of A, the intersection (A - x) ∩ B(x, ε) ≠ ∅. By B(x, ε) ⊂ B(x, δ) ⊂ U, this implies (AU - x) ∩ B(x, ε) = (A - x) ∩ UB(x, ε) = (A - x) ∩ B(x, ε) ≠ ∅.

We have proved (AU - x) ∩ B(x, ε) ≠ ∅ for any δ ≥ ε > 0. Now for ε ≥ δ, (AU - x) ∩ B(x, ε) is even bigger and should still be nonempty. Thus we have shown x is a limit point of AU.

The fact that AU is infinite follows from Exercise 2.5.2 and the existence of limit points for AU.

2.5.9 Not true. If f is a constant map, then f(A) conatined only one point and has no limit points.

2.5.10 We clearly have d(x, A) = 0 for xA. On the other hand, let x be a limit point of A. Then for any ε > 0, there is a, such that

1) aA, 2) ax, 3) d(a, x) < ε.

In particular, we have d(x, A) ≤ d(a, x) < ε. Since ε can be arbitarily small, and d(x, A) does not depend on ε, we conclude that d(x, A) = 0.

Conversely, we need to show that d(x, A) = 0 and aA implies a is a limit point of A. Since d(x, A) = 0, for any ε > 0, we can find aA, such that d(a, x) < ε. Thus the first and the third conditions are satisfied. Moreover, since aA and xA, we have ax. Thus the second condition is also satisfied. In conclusion, x is a limit point of A.

2.6.1 In discrete topology, any subset is open and closed. In Rusual, (0, 1) is open but not closed, [0, 1] is closed but not open, and [0, 1) is neither closed nor open.

Let A be an open subset of Rusual, and A ≠ ∅ or R. Then A is a nonempty disjoint union of open intervals. Let (a, b) be one such open interval. Then one of a, b must be finite (because (a, b) cannot be the whole R), and this one is not in A. Without loss of generality, we may assume a is finite and not in A. Then a is a limit point of (a, b), which implies a is a limit point of A. Since aA, we see that A is not closed.

2.6.2 By Exercise 2.5.3, if d'(x, y) < c d(x, y), then d'-closed implies d-closed.

2.6.3 By Exercise 2.5.10, A is closed if and only if d(x, A) = 0 implies xA.

2.6.5 Let x be a limit point of a ball B(a, ε) in an ultrametric space. Then for any δ > 0, the intersection (B(a, ε) - x) ∩ B(x, δ) ≠ ∅. Let y be a point in the intersection. Then by yB(a, ε) and Exercise 2.19, B(a, ε) = B(y, ε). Moreover, by yB(x, δ) and Exercise 2.19, B(x, δ) = B(y, δ). By choosing δ = ε, we conclude that xB(x, δ) = B(y, δ) = B(y, ε) = B(a, ε). Thus we have proved that B(a, ε) contains all its limit points.

Alternative proof: We prove that the complement X - B(a, ε) is open. Suppose xB(a, ε). Then we claim that B(x, ε) ∩ B(a, ε) = ∅. The claim would imply that B(x, ε) is still contained in X - B(a, ε), and the openness of X - B(a, ε) follows by definition.

Suppose B(x, ε) ∩ B(a, ε) ≠ ∅. Let y be in the intersection. Then by yB(x, ε) and Exercise 2.19, B(x, ε) = B(y, ε). Moreover, by yB(a, ε) and Exercise 2.19, B(a, ε)= B(y, ε). Therefore B(x, ε) = B(y, ε) = B(a, ε). This implies xB(a, ε), contradicting to original assumption.

2.6.6 If x is a limit point of the closed ball, then for any δ > 0, there is y in the closed ball, such that d(x, y) < δ. Since y in the closed ball, we have d(y, a) ≤ ε. Therefore d(x, a) < δ + ε for any δ > 0. This implies d(y, a) ≤ ε. In other words, x is also in the closed ball.

2.6.7 If A contains all the limits of convergent sequences in A, then by Exercise 2.5.5, A contains all its limt points and is therefore closed. Conversely, suppose A is closed and anA is a sequence converging to x. Then either an are distinct for sufficiently big n, or there is a constant subsequence. In the first case, the limit x is, by Exercise 2.5.5, a limit point of A. Since A is closed, we get xA. In the second case, the constant sequence is the same as the limit point x repeating itself again and again. Since the subsequence lies in A, we get xA.

2.6.8 [1/n, 1] is closed. But ∪n [1/n, 1] = (0, 1] is not closed.

2.6.9 1. Not closed: 0 is a limit point of (0, 1] in A. But 0 is not contained in (0,1].

2. Closed: The trouble point 0 in the prwvious example is no longer included in B. Once may either see the closedness by considering the limit points of (0, 1] in B (which is (0, 1] itself). Or one can use the fact that the complement (1, ∞) is open in B.

3. Not closed: The trouble is the same as in 1.

4. Closed: The whole space is always closed.

5. Not closed: Same trouble as in 1.

6. Closed: Same reason as in 2.

2.6.10 A subset A has limit point x if and only if A is infinite and x = 0. Therefore the closed subsets are the finite subsets and the infinite subsets that contain 0.

2.6.11 1. closed: It is the product of closed subsets {0} and (-∞, 5] (see Exercise 2.6.15)

2. closed: It is the product of closed subsets {positive integers} and {integers} (see Exercise 2.6.3)

3. not closed: (0,1) is a limit point but is not in the subset.

4. closed: It is the preimage of the single point {0} under the continuous map y - x2: R2R.

2.6.12 1. The map f(x, y, z) = x3 - y3 + 2z2 - xy - 2yz + 3zx: R3usualRusual is continuous. The subset is f-1[-1, 3].

2. The map f(x, y, z, w) = (x4 + y4 - z4 - w4, x3 + y3 - z3 - w3): R4usualR2usual is continuous. The subset is f-1(0,0), the preimage of the single origin point.

3. The map F(M) = MtM: Matrix(n×n) → Matrix(n×n) is continuous (for n = 2, write F explicitly as a map from R4 to R4 and convince yourself that F is continuous). The subset is F-1(I), the preimage of the identity matrix.

4. The characteristic polynomial F(M) = det(tI - M): Matrix(n×n) → Pn is a continuous map, where the space Pn of degree n polynomials may be identified with Rn+1. The subset is F-1((t - 1)n), the preimage of the single polynomial (t - 1)n.

2.6.13 In a square matrix M = (aij)1≤i,jn, the k-th principal submatrix M(k) = (aij)1≤i,jk is formed by the entries in row 1 through k and columns 1 through k. The coefficients in a quadratic form form a symmetric matrix M. The quadratic form is semi-positive definite if and only if in the corresponding symmetric matrix, the determinants of all principal submatrices are non-negative. In other words, the semi-positive definite symmetric matrices are exactly F-1( [0, ∞)×…×[0, ∞) ), where F(M) = (detM(1), detM(2), …, detM(n)) = (a11, a11a22 - a12a21, …): SymmetricMatrix(n×n) → Rn is continuous. Since [0, ∞)×…×[0, ∞) is a closed subset of Rn, we see that all semi-positive definite symmetric matrices form a closed subset.

2.6.14 By Exercise 2.5.1, 2.3.5(2, 3, 6, 7) are L- closed, 2.3.5(6, 7) are L1- closed, 2.3.6(3, 4) are closed, 2.3.7(1, 2, 3) are closed.

The others are not closed.

2.6.15 We have X × Y - A × B = (X - A) × YX × (Y - B). Since A and B are closed, we see that X - A and Y - B are open. Since Y and X are open, by Exercise 2.36, (X - A) × Y and X × (Y - B) are open. Then by Theorem 2.4, the union (X - A) × YX × (Y - B) is open. This implies that A × B is closed.

2.6.17 Suppose y is in the closure of A. We wish to show B(y, ε) ⊂ A. Take any zB(y, ε). Then δ = ε - d(y, z) > 0 and there is xA satisfying d(x, y) < δ. This implies d(x, z) ≤ d(x, y) + d(y, z) < δ + d(y, z) = ε. By xA, we have zB(z, ε) ⊂ A. This completes the proof of B(y, ε) ⊂ A.

3.1.1 By Theorem 3.1.3, the number of vertices with odd degrees must be an even number. Therefore the second and third combinations are impossible. The following graphs realize the first and the fifth combinations.

In general, the condition for a list of numbers to be the degrees of some graph is that the number of odd numbers in the list is even. Specifically, let 2a1, 2a2, …, 2am, 2b1 + 1, 2b2 + 1, …, 2b2n + 1 be such a list. Then we may start with m + 2n vertices V1, V2, …, Vm, W1, W2, .., W2n. We draw ai loops at Vi, bi loops at Wi. Then we draw one edge between each pair W2i, W2i+1. The result is a graph with given list as degrees.

The condition for a list of numbers 1, 1, …, 1, 2, 2, …, 2, a1, a2, …, an (where the number of 1 is k, the number of 2 is l, and ai > 2) to be the degrees of a connected graph is the evenness of the number of odd numbers and

a1 + a2 + … + an - 2n + 2 ≥ k.

The key for proving this is the following fact: Suppose A is a collection of natural numbers, and a, bA, a > 2, b ≥ 2. Suppose B is obtained by replacing a and b in A by a - 1 and b + 1. Then A can be realized by a connected graph if and only if B can be realized by a graph.

To prove the fact, let G be a graph whose degrees is A. Let V and W be vertices in G such that degG(V) = a, degG(W) = b. Since G is connected, we can find a path α connecting V to W. If α comes back to V before reaching W, then α is broken into two paths, the first part β starts and ends at V, and the second part γ connecting V to W. By (repeatedly, if necessary) using γ in place of α, we may assume that α actually does not come back to V. Thus we are in the situation like the left of the picture below, in which the path α is painted red, and there is only one red edge at V.

Since a > 2, there are other edges at V not belonging to α. Let one such edge be E, connecting V to U. Then by deleting E and adding an edge between U and W, we get a new graph G' on the right. Because of α, G' is still connected. Moreover, the only changes of degree in going from G to G' are: degG'(V) = a - 1, degG'(W) = b + 1. Thus G' is a connected graph with B as degrees.

Having proved the fact, we can now go back to our original question. Suppose A = {1, 1, …, 1, 2, 2, …, 2, a1, a2, …, an} is the degrees of a connected graph. By taking a = a1 and b = a2 in the fact, we see that B = {1, 1, …, 1, 2, 2, …, 2, a1-1, a2 + 1, …, an} is also the degrees of another connected graph. Continuing the process, we eventually modify a1, a2, …, an into 2, 2, …, 2, b, where

b = (a1 - 2) + (a2 - 2) + … + (an-1 - 2) + an = a1 + a2 + … + an - 2n + 2.

Eventually A becomes a set R = {1, 1, …, 1, 2, 2, …, 2, b}, where the number of 1 is k, th number of 2 is l + n -1. The degree 2 points are "removable". For the graph to be connected, the degree 1 points must all be connected to the degree b point. This implies bk.

3.2.1 The second picture contains four points of degree 3, so that the path cannot be found. A path can be found for the the other pictures.

3.2.2 All four vertices of the Königsberg graph have odd degree. If we add an edge between any of the two vertices, then the two vertices will have even orders and the remaining two still have odd orders. Therefore Euler's problem can be solved for the new graph. Practially, this means that Euler's problem can be solved if we build one bridge between any two parts of the four parts of Königsberg.

3.2.3 Suppose the number of vertices with odd degrees is N. Then by Theorem 3.1.3, N is an even number. If we connect two such points by a new edge, then the number is decreased to N - 2. Therefore if N > 2, then we may add (N - 2)/2 number of edges to get a connected graph with only two vertices of odd degrees, for which Euler's problem has solution. Therefore we conclude the following

• If N = 0 or 2, then no need to add edges.
• If N > 2, then we need to add (N - 2)/2 edges.

3.2.4 By a proof similar to the necessary part of Theorem 3.1.2, if we can traverse the graph G in two trips, then G has at most two connected components, the number of odd order degree vertices must be N = 0, 2 or 4, and we must be in one of the following situation

• G is connected and N = 0 or 2, then one trip is enough.
• G is connected and N = 4, then two trips are enough, and the the trips begin and end at odd degree vertices.
• G has two connected components and N = 0 or 2, then the odd order vertices are in the same component, and two trips (one in each component) is enough.
• G has two connected components and N = 4, then each component has two odd order vertices, and two trips (one in each component) is enough.

Next we prove the situations described above are sufficient for two trips. Again this can be done by inducting on the number of edges. By the sufficient part of Theorem 3.1.2, we can traverse the graph in no more than two trips in the all except the second case. So only the second case needs to be proved.

Assume G is connected and has 4 vertices of odd degree. Similar to the proof of the sufficient part of Theorem 3.1.2, let V be one of the odd degree vertex and let E be one edge with V as one end. If deleting E from G gives us a connected graph G', then by counting the degree of vertices in G', we see that G' is in either the first or the second situation described above, and the proof can be finished by induction. If deleting E from G gives us a non-connected graph, then the new graph must have two connected components G1 and G2, and we may assume V lies in G1. Since the numbers of odd order vertices in G1 and G2 are even, by simple computations of degrees, we find there are two possibilities

• G1 has no vertices of odd order, G2 has either 2 or 4 vertices of odd order.
• G1 has 2 vertices of odd order, G2 has either 0 or 2 vertices of odd order. In case G2 has 2 vertices of odd order, one such vertex is the other end of the edge E.

In the first case, we can replace E by another edge E' in G that has V as one end. Then by Lemma 3.2.1, deleting E' from G gives us a connected graph, and induction can still be used. In the second case, we can traverse G1 and G2 by one trip each, with end points being vertices of odd degree or the trip being a cycle. From the two trips, it is very easy to construct two trips traversing the whole G.