Math4225 Homework 3

Home > Math323 > Homework Lecture Note Syllabus

3.3.1 The proof of Theorem 3.3.1 include the following conclusion: If G is a connected graph, then either G has a vertex V of degree 1, or there is a cycle C that does not "backtrack". In the first case, there is a unique edge E with V as one end, and deleting E (and together with V) from G will give us a connected graph. In the second case, deleting any edge from C from G will give us a connected graph.

3.4.1 The torus can be considered as obtained from a square with the opposite edges (the red and blue pairs in the pictures below) identified. Then we can embed K₅ and K_3,3 into the torus as in the picture. The black dots are the vertices, the dashed grey lines indicate the two ends of the grey line are the same points in the torus.

3.4.2 The graph embeded in the sphere has the special property that each edge E is shared by exactly two faces F and F'. Therefore in the sum Σdeg(F), each edge E contribute 1 to deg(F) and another 1 to deg(F'), and there are no other contributions. In other words, the sum Σdeg(F) counts each edge exactly twice. Hence we conclude that Σdeg(F) = 2e.

3.4.3 The connected and planar conditions imply that v - e + f = 2, from which we see that f is determined by v and e. Thus the problem is reduced to the conditions that must be satisfied by v and e. Since f ≥ 1, we must have e ≥ v - 1. On the other hand, for any given e and v satisfying e ≥ v - 1, we construct a graph on the plane as follows.

The graph has v vertices, and the last two vertices are connected by e - v + 2 edges. The example shows that the consdition e ≥ v - 1 is also sufficeint for constructing a connected planar graph.

In conclusion, the conditions are precisely v - e + f = 2 and e ≥ v - 1, f ≥ 1.

3.4.4 Consider the summation ∑(number of edges around a face), where the sum is over all faces. Since each edge is around exactly two faces, it is counted exactly twice in the summation. Consequently, the sum is 2e. On the other hand, it has been assumed that the number of edges around a face is 3. Therefore the summation is also 3f. Thus we conclude that 2e = 3f. Combined with v - e + f = 2, we can solve e and f in terms of v. The solution is e = 3v - 6, f = 2v -4.

4.1.2 The following picture suggests us to choose ε = min { ε₁ - d(x, x₁), ε₂ - d(x, x₂) }. Note that ε > 0 by the given condition.

Now we verify the claim. Suppose d(x, y) < ε. Then d(x, y) < ε₁ - d(x, x₁) and d(x, y) < ε₂ - d(x, x₁). Therefore

d(y, x₁) ≤ d(x, y) + d(x, x₁) < ε₁.
d(y, x₂) ≤ d(x, y) + d(x, x₂) < ε₂.

4.1.3 1. Basis: For example, take B = {[a, b)} and B' = {(a, b]}. We have 1 ∈ (0, 1] ∩ [1, 2), with both (0, 1] and [1, 2) in B ∪ B'. However, there is no B ∈ B ∪ B' such that 1 ∈ B ⊂ (0, 1] ∩ [1, 2) (such B must be {1}).

2. Not basis: For example, if B and B are as above, then the intersection is empty (the first condition for topological basis is violated). The following is a less trivial example (the first condition is satisfied, but the second condition is violated)

3. Not basis: For example, B - B' may be empty, so the first condition for topological basis is violated. The following example satisfies the first condition but not the second: X = {1, 2, 3}, B is all subsets of X, B' = {{1}, {2}, {3}}. Then B - B' = {∅, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}} is not a topological basis.

4. Not basis: Take X = {1, 2, 3}, B = {{1, 2}, {1, 2, 3}}, B' = {{1, 3}, {1, 2 ,3}}. Then the unions form {{1, 2}, {1, 3}, {1, 2, 3}}, which is not a topological basis.

5. Basis:

First condition: x ∈ X
⇒ x ∈ B and x ∈ B' for some B ∈ B and B' ∈ B'
⇒ x ∈ B ∩ B' ∈ {B ∩ B': B ∈ B and B' ∈ B'}.

Second condition: x ∈ C₁ ∩ C₂, with C₁, C₂ ∈ {B ∩ B': B ∈ B and B' ∈ B'}
⇒ x ∈ (B₁ ∩ B'₁) ∩ (B₂ ∩ B'₂), with B₁, B₂ ∈ B and B'₁, B'₂ ∈ B'
⇒ x ∈ B₁ ∩ B₂, with B₁, B₂ ∈ B and x ∈ B'₁ ∩ B'₂, with B'₁, B'₂ ∈ B
⇒ x ∈ B ⊂ B₁ ∩ B₂ for some B ∈ B and x ∈ B' ⊂ B'₁ ∩ B'₂ for some B' ∈ B'
⇒ x ∈ B ∩ B' ⊂ (B₁ ∩ B₂) ∩ (B'₁ ∩ B'₂) = C₁ ∩ C₂ for some C ∈ {B ∩ B': B ∈ B and B' ∈ B'}.

6. Not basis: For example, B - B' may be empty when B is smaller than B', so that the first condition for topological basis is violated. The following example satisfies the first condition but not the second: X = {1, 2, 3}, B = {X}, B' = {{1}, {2}, {3}}. Then taking differences gives us {{1, 2}, {1, 3}, {2, 3}}, which is not a topological basis.

4.1.4 1. f^-1(B) is a topological basis:

First condition: x ∈ X
⇒ f(x) ∈ Y
⇒ f(x) ∈ B for some B ∈ B (by B being a topological basis)
⇒ x ∈ f^-1(B), for some f^-1(B) ∈ f^-1(B).

Second condition: x ∈ f^-1(B₁) ∩ f^-1(B₂), with B₁ and B₂ ∈ B
⇒ f(x) ∈ B₁ ∩ B₂
⇒ f(x) ∈ B ⊂ B₁ ∩ B₂ for some B ∈ B (by B being a topological basis)
⇒ x ∈ f^-1(B) ⊂ f^-1(B₁) ∩ f^-1(B₂) for some f^-1(B) ∈ f^-1(B).

2. {B: f(B) ∈ B} may not be a topological basis: X = R, Y= [0, ∞), f(x) = x², B = {Y}. Then f(B) ∈ B means that {|x|: x ∈ B} = [0, ∞). Such subsets B do not form a topological basis.

4.1.5 1. f(B) may not be a topological basis: X = {a, b, -1, 1}, Y= {0, -1, 1}, f(a) = f(b) = 0, f(-1) = -1, f(1) = 1, B = {{a, -1}, {b, 1}}. Then f(B) = {{0, -1}, {0, 1}} is not a topological basis.

2. {B: f^-1(B) ∈ B} may not be a topological basis: X = {-1, 0, 1}, Y= {0, 1}, f(-1) = f(1) = 1, f(0) = 0, B = {{-1}, {0, 1}}. Then there is no B ⊂ Y satisfying f^-1(B) ∈ B.

4.1.7 The subbasis {(-∞, a)} ∪ {[a, ∞)} induces B₂. The subbasis {(-∞, a]} ∪ {(a, ∞)} induces B₃.

4.1.9 Given finitely many distinct primes p₁, …, p_n, we have

S_p1 ∩ … ∩ S_pn = {multiples of p₁, …, p_n} = {multiples of p₁…p_n} = S_p1…pn.

Note that repeating the same prime will not change the intersection. Thus the topological basis induced by S is B = {S_n: n has no square factors}.

4.2.1 1. {2, 3} is not open because there is no B ∈ B such that 2 ∈ B ⊂ {2, 3}.

{1, 2, 4} is open because 1 ∈ {1, 2} ⊂ {1, 2, 4}, 2 ∈ {1, 2} ⊂ {1, 2, 4}, 4 ∈ {4} ⊂ {1, 2, 4}.

{2, 3, 4} is not open because there is no B ∈ B such that 2 ∈ B ⊂ {2, 3, 4}.

2. [0, 1] is open in B₁₀ but not in other topological bases: The openness in B₁₀ follows from the previous exercise. It is not open in B₁, B₂, B₄, …, B₉ because we cannot find B ∈ B such that 1 ∈ B ⊂ [0, 1]. It is not open in B₃ because there is no B ∈ B₃ satisfying 0 ∈ B ⊂ [0, 1].

(0, 1] is open in B₃ and B₁₀ but not in other topological bases: The openness in B₃ follows from the previous exercise. It is open in B₁₀ because for any x ∈ [0, 1] we have x ∈ [x, x] ⊂ [0, 1]. It is not open in other topological bases because we cannot find B ∈ B such that 1 ∈ B ⊂ (0, 1].

(0, +∞) is not open in B₆, B₉ but is open in all other topological bases: For any x ∈ (0, +∞), there is no B in either B₆ or B₉ satisfying x ∈ B ⊂ (0, +∞). Therefore (0,+∞) is not open in either basis. The openness in other topological bases is easy to verify.

3. {f: f(0) > f(1)} is open: If f(0) > f(1), let ε = (f(0) - f(1))/2. Then for g ∈ B(f(0), f(1), 0, 1, ε), we have |g(0) - f(0)| < ε, |g(1) - f(1)| < ε, so that g(0) - g(1) > (f(0) - ε) - (f(1) + ε) = f(0) - f(1) - 2ε = 0.

{f: ∫₀¹f(t)dt < 1} and {f: ∫₀^1/2f(t)dt > ∫_1/2¹f(t)dt} are not open: Given any I, J and any finitely many conditions |g(t_i) - a_i| < ε, i = 1, 2, …, n, we can easily construct a continuous function g satisfying the conditions and ∫₀¹g(t)dt = I + J, ∫₀^1/2g(t)dt = I, ∫_1/2¹g(t)dt = J.

4. The first disk is open with respect to all the topological bases.

The second disk is open only with respect to B₄.

The third and the fourth disks are not open with respect to all the bases.

4.2.2 By Exercise 4.1.9, the smallest subset in the topological basis that contains a = p₁^n₁…p_k^n_k is bN, where b = p₁…p_n. Therefore if an open subset contains a, then it must also contain bm = p₁…p_nm for any m.

4.2.3 B is a topological basis because mN ∩ nN = lN, where l is the least common multiple of m and n.

U ⊂ N is open if and only if n ∈ U implies mn ∈ U for any natural number m.

4.2.4 First condition: An element of X ∪ Y must be either in X or in Y. For x ∈ X, because B_X is a topological basis of X, we have B ∈ B_X (⊂ B_X ∪ B_Y), satisfying x ∈ B. The argument is similar for y ∈ Y. This verifies the first condition.

Second condition: Suppose x ∈ B₁ ∩ B₂, with B₁ and B₂ ⊂ B_X ∪ B_Y. If x ∈ X, then we necessarily have B₁ and B₂ ⊂ B_X. Since B_X is a topological basis of X, we have B ∈ B_X (⊂ B_X ∪ B_Y), satisfying x ∈ B ⊂ B₁ ∩ B₂. The argument is similar for y ∈ Y. This verifies the second condition.

4.3.1 1, 2. Not topology: {1, 2} and {2, 3} are in T. But their intersection is not in T.

Also not basis for the similar reason.

3. Topology: If subsets do not contain odd numbers, then the unions and intersections also do not contain odd numbers.

4. Not topology: 2N ∪ 3N is not of the form nN.

The collection is a basis. See Exercise 4.2.3.

5. Topology: ∪ 2^n_iN = 2^max{n_i}N and 2^mN ∩ 2ⁿN = 2^{max{m, n}}N.

4.3.2 1. Topology: ∪ (a_i, ∞) = (mina_i, ∞), (a, ∞) ∩ (b, ∞) = (max{a, b}, ∞).

2. Not topology: (-∞, 1) ∩ (-1, ∞) are in T. But (-∞, 1) ∩ (-1, ∞) = (-1, 1) is not in T.

Also not basis for the similar reason.

3. Topology: ∪ (-a_i, 2a_i) = (-a, 2a) with a = supa_i, (-a, 2a) ∩ (-b, 2b) = (-max{a, b}, 2max{a, b}).

4. Not topology: Let a_i be a strictly increasing seqeunce converging to 1. Then ∪[-a_i, 2a_i) = (-1, 2) is not in T.

The collection is a basis because [-a, 2a) ∩ [-b, 2b) = [-max{a, b}, 2max{a, b}).

5. Topology: same reason as (1).

4.3.4 Since any subset is a union of single point subsets, by the second property of open subsets, (any single point is open implies) any subset is open. This is the discrete topology.

4.3.5 Suppose A is open. For any x ∈ A, we may choose U = A. Then U is open and x ∈ U ⊂ A.

Conversely, suppose for each x ∈ A, we can find an open subset U_x, such that x ∈ U_x ⊂ A. Then for all x ∈ A, we find such U_x and conclude that

A = ∪_x∈A{x} ⊂ ∪_x∈AU_x ⊂ A.

This implies that A = ∪_x∈AU_x, a union of open subsets. Then by Theorem 4.4, A is open.

4.3.7 1. Not topology: Take X = {1, 2, 3}, T = { ∅, {1}, X }, T' = { ∅, {2}, X }. Then T ∪ T' = { ∅, {1}, {2}, X }, which does not satisfy the third condition for topology.

2. Topology: Since ∅, X ∈ T and T', we get ∅, X ∈ T ∩ T'.

If U_i ∈ T ∩ T', then U_i ∈ T ⇒ ∪ U_i ∈ T by the second property of T. By the same reason, ∪ U_i ∈ T'. Therefore ∪ U_i ∈ T ∩ T'.

If U, V ∈ T ∩ T', then U, V ∈ T ⇒ U ∩ V ∈ T by the third property of T. By the same reason, U ∩ V ∈ T'. Therefore U ∩ V ∈ T ∩ T'.

3. Not topology: T - T' does not contain ∅ and X.

4. Not topology: Take X = {1, 2, 3}, T = { ∅, {1, 2}, X }, T' = { ∅, {1, 3}, X }. Then the unions form the collection = { ∅, {1, 2}, {1, 3}, X }. However, the collection does not contain {1, 2} ∩ {1, 3}.

5. Not topology: Take X = {1, 2, 3}, T = { ∅, {1}, X }, T' = { ∅, {2}, X }. Then the intersections form the collection = { ∅, {1}, {2}, X }. However, the collection does not contain {1} ∪ {2}.

6. Not topology: Take X = R, T = { ∅, X }, T' = usual topology. Then the subtractions produces the closed subsets in the topology. We know the usual closed subsets in R do not form a topology.

4.3.8 1. f^-1(T) is a topology:

First condition: ∅ ∈ T ⇒ ∅ = f^-1(∅) ∈ f^-1(T), Y ∈ T ⇒ X = f^-1(Y) ∈ f^-1(T).

Second condition: U_i ∈ f^-1(T)
⇒ U_i = f^-1(V_i) with V_i ∈ T
⇒ ∪ V_i ∈ T (T satisfies the second condition)
⇒ ∪ U_i = ∪ f^-1(U_i) = f^-1(∪ U_i) ∈ f^-1(T).

Third condition: U₁, U₂ ∈ f^-1(T)
⇒ U₁ = f^-1(V₁), U₂ = f^-1(V₂) ∈ T
⇒ V₁∩V₂ ∈ T (T satisfies the third condition)
⇒ V₁∩V₂ = f^-1(U₁)∩f^-1(U₂) = f^-1(U₁∩U₂) ∈ f^-1(T).

2. T' = {U: f(U) ∈ T} is not a topology: X = {-1, 0, 1}, Y = {0, 1}, f(-1) = f(1) = 1, f(0) = 0, T = { ∅, Y }. We have {-1, 0}, {0, 1} ∈ T' and {-1, 0} ∩ {0, 1} ∉ T'.

4.3.9 1. f(T) is not a topology: X = {a, b, -1, 1}, Y= {0, -1, 1}, f(a) = f(b) = 0, f(-1) = -1, f(1) = 1, T = {∅, {a, -1}, {b, 1}, X}. Then f(T) = {∅, {0, -1}, {0, 1}, Y} is not a topology.

2. T' = {V: f^-1(V) ∈ T} is a topology:

First condition: f^-1(∅) = ∅ ∈ T ⇒ ∅ ∈ T', f^-1(Y) = X ∈ T ⇒ Y ∈ T'.

Second condition: V_i ∈ T'
⇒ f^-1(V_i) ∈ T
⇒ f^-1(∪ V_i) = ∪ f^-1(V_i) ∈ T (T satisfies the second condition)
⇒ ∪ V_i ∈ T'.

Third condition: V₁, V₂ ∈ T'
⇒ f^-1(V₁), f^-1(V₂) ∈ T
⇒ f^-1(V₁ ∩ V₂) = f^-1(V₁) ∩ f^-1(V₂) ∈ T (T satisfies the third condition)
⇒ V₁ ∩ V₂ ∈ T'.

4.3.10 T_X × T_Y is not a topology. Take X = Y = R with T_X and T_Y being the usual topology. Then the squares (0, 1) × (0, 1), (1, 2) × (1, 2) ∈ T_X × T_Y. However, the union of the two squares is not of the form U × V. Therefore the union is not in T_X × T_Y.

4.4.1 By B_d(a, ε) = B_√d(a, √ε), the collection of d-balls and the collection of √d-balls are the same.

B_min{1,d}(a, ε) = B_d(a, ε) in case ε ≤ 1. It is easy to see that if B_d'(a, ε) = B_d(a, ε) for small ε, then d and d' induce the same topology.

4.4.2 1. By x ∈ (a, b) ⇒ x ∈ [x, b) ⊂ (a, b), T₂ is finer than T₁. On the other hand, x ∈ [x, b), but there is no (a', b'), such that x ∈ (a', b') ⊂ [x, b). Therefore T₁ is not finer than T₂. We conclude that T₂ is strictly finer than T₁.

Similarly, T₃ is strictly finer than T₁.

We have x ∈ [x, b), but there is no (a', b'], such that x ∈ (a', b'] ⊂ [x, b). Thus T₃ is not finer than T₂. Similarly, T₂ is not finer than T₃. We conclude that T₂ and T₃ are not comparable.

B₂ ⊂ B₄ ⇒ T₄ is finer than T₂. On the other hand, if x ∈ B for some B ∈ B₄, then we have two cases:

1. B ∈ B₁. In this case, we have x ∈ B = (a, b). Then x ∈ [x, a) ⊂ B, with [x, a) ∈ B₂.
2. B ∈ B₂.

In either case, we have x ∈ B' ⊂ B for some B' ∈ B₂. Thus T₂ is finer than T₄. We conclude that T₂ is the same as T₄.

B₅ ⊂ B₁ ⇒ T₁ is finer than T₅. On the other hand, x ∈ (x - 1, x + 1), but there is no (a, ∞), such that x ∈ (a, ∞) ⊂ (x - 1, x + 1). Therefore T₁ is not finer than T₅. We conclude that T₁ is strictly finer than T₅.

Similarly, T₁ is strictly finer than T₆.

We have x ∈ (x - 1, ∞), but there is no (-∞, a), such that x ∈ (-∞, a) ⊂ (x - 1, ∞). Thus T₆ is not finer than T₅. Similarly, T₅ is not finer than T₆. We conclude that T₅ and T₆ are not comparable.

B₇ ⊂ B₁ ⇒ T₁ is finer than T₇. On the other hand, for any x ∈ (a, b), we can always find rational r, s, such that x ∈ (r, s) ⊂ (a, b). Thus T₇ is finer than T₁. We conclude that T₁ is the same as T₇.

B₈ ⊂ B₂ ⇒ T₂ is finer than T₈. On the other hand, √2 ∈ [√2, 2), but there is no rational a, b, such that √2 ∈ (a, b) ⊂ [√2, 2). Therefore T₈ is not finer than T₂. We conclude that T₂ is strictly finer than T₈.

The reason similar to the comparison between T₁ and T₂ shows that T₈ is strictly finer than T₇.

Since R - F are open in T₁, we see that T₉ is finer than T₁. On the other hand, x ∈ (x - 1, x + 1), but there is no finite F, such that x ∈ R - F ⊂ (x - 1, x + 1). Therefore T₁ is strictly finer than T₉.

The single points sets are included in B₁₀. This shows that B₁₀ induces the discrete topology. Therefore B₁₀ is strictly finer than any other.

One may similarly complete all the other comparisons. The following are all the results, with > for strictly finer, and = for equivalent.

T₁₀ > T₂ = T₄ > T₈ > T₁ = T₇ > T₅, T₆, T₉,
T₁₀ > T₃ > T₁ = T₇ > T₅, T₆, T₉.

Finally, we note that T_i > T_j > T_k implies T_i > T_k.

2. We compare

T₁: induced by topological subbasis {pN: p prime} and basis {nN: n has no square factor} (see Exercise 4.1.9)
T₂: a subset is open if it contains no odd numbers
T₃: open subsets are 2ⁿN
T₄: induced by 2-adic metric. The balls are given by B(a, ε) = (a + 2ⁿZ) ∩ N = {a + k2ⁿ: k ∈ Z} ∩ N, where 2^-n < ε ≤ 2^-n+1.

3N is T₁-open but obvious not T₂-open and not T₃-open. Since for any a and n, there is k, such that a + k2ⁿ = a + k(-1)ⁿ ≠ 0 modulo 3, we see that 3N never contain subsets of the form (a + 2ⁿZ) ∩ N. Therefore 3N is not T₄-open.

The single point is {2} T₂-open but not open in the other topologies, because the open subsets in the other topologies are infinite.

T₃-open clearly implies T₂-open and T₄-open (T₃-open subsets are T₄-balls). However, 4N is T₃-open but not T₁-open.

(1 + 2Z) ∩ N = {all odd numbers} is T₄-open because it is a T₄-ball. It is clearly not open in the other topologies.

We conclude that T₃ is strictly coarser than T₂ and T₄. Moreover, there is not other comparison.

4.4.4 The subset U = {f: f(0) > 1} is open in the pointwise convergence topology but not L₁-open. Therefore the pointwise convergence topology is not coarser than the L₁-topology.

The ball B_L1(0, 1) = {f: |∫₀¹f(t)dt| < 1} is L₁-open. On the other hand, for any subset B = B(a₁, …, a_n, t₁, …, t_n, ε) containing 0, we can easily find a function g ∈ B with ∫₀¹g(t)dt to be any number we want. Thus B_L1(0, 1) is not pointwise convergence open. Therefore the pointwise convergence topology and the L_∞-topology are not comparable.

4.4.6 Let T_A = {U ∪ B: U ∈ T, B ⊂ A}. Let T' be a topology such that any open subset in T is open and any single of A is open. Since any subset of A is a union of single points in A, we get T_A ⊂ T'. On the other hand, T_A is already a topology:

U_i ∈ T and B_i ⊂ A ⇒ ∪ U_i ∈ T, ∪ B_i ⊂ A ⇒ ∪ (U_i ∪ B_i) = (∪ U_i) ∪ (∪ B_i) ∈ T_A

U, U' ∈ T and B, B' ⊂ A ⇒ U ∩ U' ∈ T and U ∩ B', B ∩ U', B ∩ B' ⊂ A ⇒ (U ∪ B) ∩ (U' ∪ B') = (U ∩ U') ∪ [ (U ∩ B') ∪ (B ∩ U') ∪ (B ∩ B') ] ∈ T_A

Thus we conclude that T_A is the coarsest topology such that any open subset in T is open and any single point of A is open.

4.4.9 Denote by S' the topological basis B considered as a subbasis (the same collection but coinsidered as used fordifferent purpose). Then B' consists of finite intersections of subsets in S' and induces a topology T'.

By S' = B ⊂ T and Lemma 4.8, we get T' ⊂ T. On the other hand, by B = S' ⊂ T' and Lemma 4.8 again, we get T ⊂ T'. Thus we conclude T = T'.