Math4225 Homework 3

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 K5 and K3,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 ev - 1. On the other hand, for any given e and v satisfying ev - 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 ev - 1 is also sufficeint for constructing a connected planar graph.

In conclusion, the conditions are precisely v - e + f = 2 and ev - 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 { ε1 - d(x, x1), ε2 - d(x, x2) }. Note that ε > 0 by the given condition.

Now we verify the claim. Suppose d(x, y) < ε. Then d(x, y) < ε1 - d(x, x1) and d(x, y) < ε2 - d(x, x1). Therefore

d(y, x1) ≤ d(x, y) + d(x, x1) < ε1.
d(y, x2) ≤ d(x, y) + d(x, x2) < ε2.

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 BB'. However, there is no BBB' 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: xX
xB and xB' for some BB and B'B'
xBB' ∈ {BB': BB and B'B'}.

Second condition: xC1C2, with C1, C2 ∈ {BB': BB and B'B'}
x ∈ (B1B'1) ∩ (B2B'2), with B1, B2B and B'1, B'2B'
xB1B2, with B1, B2B and xB'1B'2, with B'1, B'2B
xBB1B2 for some BB and xB'B'1B'2 for some B'B'
xBB' ⊂ (B1B2) ∩ (B'1B'2) = C1C2 for some C ∈ {BB': BB 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: xX
f(x) ∈ Y
f(x) ∈ B for some BB (by B being a topological basis)
xf-1(B), for some f-1(B) ∈ f-1(B).

Second condition: xf-1(B1) ∩ f-1(B2), with B1 and B2B
f(x) ∈ B1B2
f(x) ∈ BB1B2 for some BB (by B being a topological basis)
xf-1(B) ⊂ f-1(B1) ∩ f-1(B2) 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) = x2, B = {Y}. Then f(B) ∈ B means that {|x|: xB} = [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 BY satisfying f-1(B) ∈ B.

4.1.7 The subbasis {(-∞, a)} ∪ {[a, ∞)} induces B2. The subbasis {(-∞, a]} ∪ {(a, ∞)} induces B3.

4.1.9 Given finitely many distinct primes p1, …, pn, we have

Sp1 ∩ … ∩ Spn = {multiples of p1, …, pn} = {multiples of p1pn} = Sp1pn.

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

4.2.1 1. {2, 3} is not open because there is no BB 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 BB such that 2 ∈ B ⊂ {2, 3, 4}.

2. [0, 1] is open in B10 but not in other topological bases: The openness in B10 follows from the previous exercise. It is not open in B1, B2, B4, …, B9 because we cannot find BB such that 1 ∈ B ⊂ [0, 1]. It is not open in B3 because there is no BB3 satisfying 0 ∈ B ⊂ [0, 1].

(0, 1] is open in B3 and B10 but not in other topological bases: The openness in B3 follows from the previous exercise. It is open in B10 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 BB such that 1 ∈ B ⊂ (0, 1].

(0, +∞) is not open in B6, B9 but is open in all other topological bases: For any x ∈ (0, +∞), there is no B in either B6 or B9 satisfying xB ⊂ (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 gB(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: ∫01f(t)dt < 1} and {f: ∫01/2f(t)dt > ∫1/21f(t)dt} are not open: Given any I, J and any finitely many conditions |g(ti) - ai| < ε, i = 1, 2, …, n, we can easily construct a continuous function g satisfying the conditions and ∫01g(t)dt = I + J, ∫01/2g(t)dt = I, ∫1/21g(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 B4.

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 = p1n1pknk is bN, where b = p1pn. Therefore if an open subset contains a, then it must also contain bm = p1pnm for any m.

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

UN is open if and only if nU implies mnU for any natural number m.

4.2.4 First condition: An element of XY must be either in X or in Y. For xX, because BX is a topological basis of X, we have BBX (⊂ BXBY), satisfying xB. The argument is similar for yY. This verifies the first condition.

Second condition: Suppose xB1B2, with B1 and B2BXBY. If xX, then we necessarily have B1 and B2BX. Since BX is a topological basis of X, we have BBX (⊂ BXBY), satisfying xBB1B2. The argument is similar for yY. 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: ∪ 2niN = 2max{ni}N and 2mN ∩ 2nN = 2max{m, n}N.

4.3.2 1. Topology: ∪ (ai, ∞) = (minai, ∞), (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: ∪ (-ai, 2ai) = (-a, 2a) with a = supai, (-a, 2a) ∩ (-b, 2b) = (-max{a, b}, 2max{a, b}).

4. Not topology: Let ai be a strictly increasing seqeunce converging to 1. Then ∪[-ai, 2ai) = (-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 xA, we may choose U = A. Then U is open and xUA.

Conversely, suppose for each xA, we can find an open subset Ux, such that xUxA. Then for all xA, we find such Ux and conclude that

A = ∪xA{x} ⊂ ∪xAUxA.

This implies that A = ∪xAUx, 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 TT' = { ∅, {1}, {2}, X }, which does not satisfy the third condition for topology.

2. Topology: Since ∅, XT and T', we get ∅, XTT'.

If UiTT', then UiT ⇒ ∪ UiT by the second property of T. By the same reason, ∪ UiT'. Therefore ∪ UiTT'.

If U, VTT', then U, VTUVT by the third property of T. By the same reason, UVT'. Therefore UVTT'.

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), YTX = f-1(Y) ∈ f-1(T).

Second condition: Uif-1(T)
Ui = f-1(Vi) with ViT
⇒ ∪ ViT (T satisfies the second condition)
⇒ ∪ Ui = ∪ f-1(Ui) = f-1(∪ Ui) ∈ f-1(T).

Third condition: U1, U2f-1(T)
U1 = f-1(V1), U2 = f-1(V2) ∈ T
V1V2T (T satisfies the third condition)
V1V2 = f-1(U1)∩f-1(U2) = f-1(U1U2) ∈ 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) = XTYT'.

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

Third condition: V1, V2T'
f-1(V1), f-1(V2) ∈ T
f-1(V1V2) = f-1(V1) ∩ f-1(V2) ∈ T (T satisfies the third condition)
V1V2T'.

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

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

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

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

Similarly, T3 is strictly finer than T1.

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

B2B4T4 is finer than T2. On the other hand, if xB for some BB4, then we have two cases:

1. BB1. In this case, we have xB = (a, b). Then x ∈ [x, a) ⊂ B, with [x, a) ∈ B2.
2. BB2.

In either case, we have xB'B for some B'B2. Thus T2 is finer than T4. We conclude that T2 is the same as T4.

B5B1T1 is finer than T5. On the other hand, x ∈ (x - 1, x + 1), but there is no (a, ∞), such that x ∈ (a, ∞) ⊂ (x - 1, x + 1). Therefore T1 is not finer than T5. We conclude that T1 is strictly finer than T5.

Similarly, T1 is strictly finer than T6.

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

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

B8B2T2 is finer than T8. On the other hand, √2 ∈ [√2, 2), but there is no rational a, b, such that √2 ∈ (a, b) ⊂ [√2, 2). Therefore T8 is not finer than T2. We conclude that T2 is strictly finer than T8.

The reason similar to the comparison between T1 and T2 shows that T8 is strictly finer than T7.

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

The single points sets are included in B10. This shows that B10 induces the discrete topology. Therefore B10 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.

T10 > T2 = T4 > T8 > T1 = T7 > T5, T6, T9,
T10 > T3 > T1 = T7 > T5, T6, T9.

Finally, we note that Ti > Tj > Tk implies Ti > Tk.

2. We compare

T1: induced by topological subbasis {pN: p prime} and basis {nN: n has no square factor} (see Exercise 4.1.9)
T2: a subset is open if it contains no odd numbers
T3: open subsets are 2nN
T4: induced by 2-adic metric. The balls are given by B(a, ε) = (a + 2nZ) ∩ N = {a + k2n: kZ} ∩ N, where 2-n < ε ≤ 2-n+1.

3N is T1-open but obvious not T2-open and not T3-open. Since for any a and n, there is k, such that a + k2n = a + k(-1)n ≠ 0 modulo 3, we see that 3N never contain subsets of the form (a + 2nZ) ∩ N. Therefore 3N is not T4-open.

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

T3-open clearly implies T2-open and T4-open (T3-open subsets are T4-balls). However, 4N is T3-open but not T1-open.

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

We conclude that T3 is strictly coarser than T2 and T4. 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 L1-open. Therefore the pointwise convergence topology is not coarser than the L1-topology.

The ball BL1(0, 1) = {f: |∫01f(t)dt| < 1} is L1-open. On the other hand, for any subset B = B(a1, …, an, t1, …, tn, ε) containing 0, we can easily find a function gB with ∫01g(t)dt to be any number we want. Thus BL1(0, 1) is not pointwise convergence open. Therefore the pointwise convergence topology and the L-topology are not comparable.

4.4.6 Let TA = {UB: UT, BA}. 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 TAT'. On the other hand, TA is already a topology:

UiT and BiA ⇒ ∪ UiT, ∪ BiA ⇒ ∪ (UiBi) = (∪ Ui) ∪ (∪ Bi) ∈ TA

U, U'T and B, B'AUU'T and UB', BU', BB'A ⇒ (UB) ∩ (U'B') = (UU') ∪ [ (UB') ∪ (BU') ∪ (BB') ] ∈ TA

Thus we conclude that TA 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' = BT and Lemma 4.8, we get T'T. On the other hand, by B = S'T' and Lemma 4.8 again, we get TT'. Thus we conclude T = T'.