I didn’t use the hint, so my solution looks different. I also don’t get how the intended solution works—you can’t choose the cubes in S small enough to make sure that f is constant on each cube C, so f(C) may not be convex. This seems to kill the straight-line solution, and I didn’t see a way to salvage it.
Here’s what I did in one paragraph. Divide both S and T into cubes. For any horizontal edge e in S, make sure fn hits the centers of all cubes that f touches on points within distance ϵ of e (where ϵ is at least the diameter of a cube in S), while moving around only within those cubes. Extend fn to S without wandering off too far, and voilà.
Proof roadmap:
Embed S and T into unit cubes
Cut the unit cubes into small cubes
Prove a bunch of helpful Lemmas
Define fn on some subset of the unit cube containing S
Argue that this approximates f on S
(1) Since S and T are compact and hence bounded, we can scale them down such that we can consider them subspaces of the unit cubes, i.e., S⊆X:=[0,1]d and T⊆Y:=[0,1]m, where we choose d,m as small as possible. (This is the abbreviated version of working with embedding functions.)
Let n∈N+.
(2) By cutting each interval into n pieces, i.e., [0,1n],[1n,2n],...[n−1n,1], we obtain nd small cubes in X of the form
[j1n,j1+1n]×⋯×[jnn,jn+1n]
where j1,...,jn∈{0,...,n−1}. Enumerate these cubes as Cubes(X):={C1,...,Cnd}. An analogous construction for Y yields Cubes(Y):={D1,...,Dnm}.
Given any set Q⊆Y, we define the operator Expand to ‘expand’ Y to all the cubes that it touches, i.e.,
Expand(Q):={D∈Cubes(Y)|D∩Q≠∅}
(3) We do most work via paths. This requires a bunch of Lemmas.
Lemma 1. For any connected set C⊆S, the set f(C) is connected.
Proof. Let f(C)=U⊔V be a separation into two closed sets. Suppose first there is a point x∈C not entirely contained in U or V. Then, U∩f(x) and V∩f(x) is a separation of f(x), contradicting the fact that f(x) is convex (and hence (path)-connected.) Thus, each f(x) either lies entirely in U or entirely in V.
Since U is closed, so is (S×U)∩Gf and π1((S×U)∩Gf) (where Gf is the graph of f), which is simply f−1(U). (The preimage function is well-defined for U and V due to the result from the previous paragraph, and the projection is closed because S is compact.) Analogously, f−1(V) is closed. Then, C=(C∩f−1(V))⊔(C∩f−1(U)) is a separation of C, implying that (because C is connected), one of them is the empty set. Since U,V⊆f(C), this implies that U=∅ or V=∅.
This is only needed to prove Lemma 2.
Lemma 2. For any connected set C⊆S, the set Z:=Expand(f(C)) is path-connected.
Proof. The set Z consists of cubes in Y. Consider the graph G where all cubes in Z are nodes, and there is an edge between two nodes iff the cubes share at least a point. If this graph were disconnected, then there would be a minimal distance between the sets of cubes corresponding to two disconnected parts of the graph. This yields a separation of Z, which is also a separation of f(C), contradicting the previous lemma. (The distance can, in fact, be lower-bounded, but it suffices to use the fact that two closed disjoint sets in a metric space have non-zero distance.) Thus, G is connected. This allows us to construct a path between the center points of two arbitrary cubes in Z (since there is a corresponding path in G and the straight-line connection between the centers of two cubes that share at least one vertex yields a continuous path). Now, given two points p,p′ and two cubes D,D′ such that p∈D⊆Z and p′∈D′⊆Z, we can construct a path from p to p′ via
p→center(D)→center(D′)→p′.
Lemma 3. Given k∈N+ and any path-connected space Z, all functions from [0,1]k to Z are homotopic.
Proof. Let ϕ:[0,1]k→Z. Define a homotopy Φ:[0,1]×[0,1]k→Z by the rule Φ(t,x1,...,xk)=Φ((1−t)x1,...,(1−t)xk). Then, Φ(0) is ϕ, and Φ(1) is a constant map, proving that ϕ is null-homotopic. Since being homotopic is an equivalence relation (and any two constant maps are trivially homotopic in a path connected space), it follows that all maps [0,1]k→Z are homotopic to each other.
(4) Let ϵ∈R+ be a parameter that depends on n. We will specify how ϵ is chosen in the last part of the proof. It will have the properties that it’s at least as large as the diameter of a cube and that it converges to 0 as n grows.
Let A⊂S be connected. We define two operators on A. The first is the set of points in Y that wish for fn to hit on points near it. We set
Targets(A):={center(D)|∃x∈B(A,ϵ):f(x)∩D≠∅}
where B(A,ϵ)={x∈X|d(x,A)<ϵ}. The second is a sufficiently small subspace of Y that is guaranteed to contain all points that f touches on A. We set Area(A):=Expand(Targets(A)). Note that this set is identical to Expand(f(B(A,ϵ))), which makes it path-connected by Lemma 2.
We now want to define a partial function fn:X→Y. We begin by defining it on vertices, then generalize it to specific edges, then specific faces, and so on, until we define it on all cubes C∈Cubes(X) that intersect S.
A vertex v is defined to be a point v∈X of the form
v=(j1n,j2n,...,jnn)
for some j1,...,jn∈N. The set Area(v) may be empty if v is too far outside S, in which case we leave fn undefined on v. If it is not empty, choose y∈Area(v) arbitrarily and set fn(v):=y.
We now turn to edges. However, we only consider ‘horizontal’ edges, that is, subspaces e⊂X of the form
e={(a,j2n,...,jnn)|a∈(j1n,j1+1n)}
for some j1,...,jn∈N. Let v and w be the two vertices of e. If fn is undefined on either, we leave it undefined on e. If not, we define it in the following. Note that this is the step where we guarantee that fn hits all points in the target set.
We know from Lemma 3 that there is a path p:[0,1]→Area(e) from f(v) to f(w). Since e is homeomorphic to [0,1], it’s easy to transform p into a ‘path’ p′:e→Area(e). But we can do even better and construct a path p∗:e→Area(e) that starts at fn(v), ends at fn(w), and hits all points in Targets(e) on the way. (All trivial since Area(e) is path-connected.) Now we simply set fn(x)=p∗(x)∀x∈e.
We next consider all ‘horizontal-vertical’ faces, that is, all sets q⊂X of the form
q={(a,b,j3n,...,jnn)|a∈(j1n,j1+1n),b∈(j2n,j2+1n)}
for some j1,...,jn∈N. Let e and e′ be the two horizontal edges of q. If fn is undefined on either, we leave it undefined on q. If not, we have two paths p:[0,1]→Area(q) and p′:[0,1]→Area(q) which implement fn on e and e′, respectively. Using Lemma 3, we obtain a homotopy F:[0,1]×[0,1]→Area(q) that continuously deforms p into p′. Since our face q is homeomorphic to [0,1]×[0,1], it’s easy to transform F into a function F∗:q→Area(q). Now we simply set fn(x)=F∗(x)∀x∈q.
Now we do the same for 3-dimensional subspaces r⊂X of the form
where fn has been defined on the two horizontal-vertical faces, and so on. This way, every k-dimensional subspace of this kind contains precisely two k−1-dimensional subspaces of this kind, and if we have defined fn on both, we can apply a construction analogous to the above to define fn on the k-dimensional subspace. Eventually, we define fn on d-dimensional subspaces, which are precisely our cubes. (In the case of d-dimensional subspaces, the definition above doesn’t pose any restriction; it coincides with the definition of a cube C∈Cubes(X)). Importantly, this defines fn on any cube C∈Cubes(X) that intersects S. (This is so because any vertex of this cube is within ϵ of S, which means that it has non-empty area. This implies that we have defined fn on any edge, face, and so on, of C.) Thus, we end up having defined fn on some subspace of X that includes all cubes that intersect S.
The advantage of this construction is that, for any C∈Cubes(X), we know that f(C) is contained in Area(C), which is the same as the union of all cubes in Y that f touches on points near C. If we had used the homomorphic extension of fn instead (i.e., connecting via straight lines), we could merely guarantee that f(C) is contained in the convex hull of certain points in Y, which may be much larger.
(5) Having defined fn on a subset of X that contains S, we take a projection π:Y→T, and define ϕn:S→T by the rule ϕn(x)=π(fn(x)). It remains to show that our construction is such that the Hausdorff distance between f and fn converges to 0 as n→∞, then the distance between f and ϕn converges to 0 as well. (To see this, note that, if fn(x) is within δ of f(x) (which lies in S), then π can move it by at most δ, which means that π(fn(x)) is within 2δ of f(x).)
To do this, we now explain how ϵ is chosen, and then argue that the Hausdorff distance can be upper-bounded by some constant times ϵ.
The issue we have to deal with is that, by default, a point on the boundary of S may not have any edge close to it that is contained in S. (In fact, it may not even have an edge close to it that intersects S.) Thus, we would like ϵ to be so large that any ϵ-ball around a point in S must contain a δ-ball entirely contained in S, where δ is larger than the diameter of a cube. In that case, any x∈S is within ϵ of a cube entirely contained in S and thus also within ϵ of an edge entirely contained in S.
It remains to show that we can choose ϵ such that it (a) has this property and (b) converges to 0 as a function of n. To show this, we consider ϵ∈R+ fixed, and show that n eventually grows large enough for that ϵ to suffice.
For every point x∈S, there exists some δ∈R+ such that B(x,ϵ) contains some δ-ball entirely contained in S. Define a function γ:S→R+ that each point to the supremum of such δ’s. Then, γ is a continuous function from a compact set to R+, which means it takes on a minimum value. It now suffices to choose n large enough that the diameter of a cube is smaller than this minimum. (To verify that γ is continuous, take a sequence (xn)n∈N of points in S, assuming that (γ(xn))n∈N doesn’t converge, and derive a contradiction.)
With this out the way, we return to the proof that f is the Haudorff limit of the fn. This consists of showing two parts:
for any point on Gf (the graph of f), there exists a close point on Gfn (i.e., fn comes sufficiently close to all points on Gf); and
for any point on Gfn, there exists a close point on Gf (i.e., fn has no points too far away from Gf).
Both are now easy:
Let (x,y)∈Gf, and let D∈Cubes(Y) be a cube that contains y. Let e⊂S be an edge with distance at most ϵ to x. By construction, we have center(D)∈Targets(e), which means that there is a point x′∈e such that y′:=fn(x′)=center(D). Since d(x,x′)<ϵ and d(y,y′)<ϵ, the distance between (x,y) and (x′,y′) converges to 0 as n→∞.
Let (x′,y′)∈Gfn, and let D∈Cubes(Y) be a cube containing y′. Since y′∈D, it follows that D⊂Area(x′), which means there exists a point x∈S such that f(x)∩D≠∅, which is to say, such that there is a y∈D for which (x,y)∈Gf. Now d(x,x′)<ϵ and d(y,y′)<ϵ, and thus the distance between (x′,y′) and (x,y) again converges to 0 as n→∞.
Ex12
I didn’t use the hint, so my solution looks different. I also don’t get how the intended solution works—you can’t choose the cubes in S small enough to make sure that f is constant on each cube C, so f(C) may not be convex. This seems to kill the straight-line solution, and I didn’t see a way to salvage it.
Here’s what I did in one paragraph. Divide both S and T into cubes. For any horizontal edge e in S, make sure fn hits the centers of all cubes that f touches on points within distance ϵ of e (where ϵ is at least the diameter of a cube in S), while moving around only within those cubes. Extend fn to S without wandering off too far, and voilà.
Proof roadmap:
Embed S and T into unit cubes
Cut the unit cubes into small cubes
Prove a bunch of helpful Lemmas
Define fn on some subset of the unit cube containing S
Argue that this approximates f on S
(1) Since S and T are compact and hence bounded, we can scale them down such that we can consider them subspaces of the unit cubes, i.e., S⊆X:=[0,1]d and T⊆Y:=[0,1]m, where we choose d,m as small as possible. (This is the abbreviated version of working with embedding functions.)
Let n∈N+.
(2) By cutting each interval into n pieces, i.e., [0,1n],[1n,2n],...[n−1n,1], we obtain nd small cubes in X of the form
[j1n,j1+1n]×⋯×[jnn,jn+1n]
where j1,...,jn∈{0,...,n−1}. Enumerate these cubes as Cubes(X):={C1,...,Cnd}. An analogous construction for Y yields Cubes(Y):={D1,...,Dnm}.
Given any set Q⊆Y, we define the operator Expand to ‘expand’ Y to all the cubes that it touches, i.e.,
Expand(Q):={D∈Cubes(Y)|D∩Q≠∅}
(3) We do most work via paths. This requires a bunch of Lemmas.
Lemma 1. For any connected set C⊆S, the set f(C) is connected.
Proof. Let f(C)=U⊔V be a separation into two closed sets. Suppose first there is a point x∈C not entirely contained in U or V. Then, U∩f(x) and V∩f(x) is a separation of f(x), contradicting the fact that f(x) is convex (and hence (path)-connected.) Thus, each f(x) either lies entirely in U or entirely in V.
Since U is closed, so is (S×U)∩Gf and π1((S×U)∩Gf) (where Gf is the graph of f), which is simply f−1(U). (The preimage function is well-defined for U and V due to the result from the previous paragraph, and the projection is closed because S is compact.) Analogously, f−1(V) is closed. Then, C=(C∩f−1(V))⊔(C∩f−1(U)) is a separation of C, implying that (because C is connected), one of them is the empty set. Since U,V⊆f(C), this implies that U=∅ or V=∅.
This is only needed to prove Lemma 2.
Lemma 2. For any connected set C⊆S, the set Z:=Expand(f(C)) is path-connected.
Proof. The set Z consists of cubes in Y. Consider the graph G where all cubes in Z are nodes, and there is an edge between two nodes iff the cubes share at least a point. If this graph were disconnected, then there would be a minimal distance between the sets of cubes corresponding to two disconnected parts of the graph. This yields a separation of Z, which is also a separation of f(C), contradicting the previous lemma. (The distance can, in fact, be lower-bounded, but it suffices to use the fact that two closed disjoint sets in a metric space have non-zero distance.) Thus, G is connected. This allows us to construct a path between the center points of two arbitrary cubes in Z (since there is a corresponding path in G and the straight-line connection between the centers of two cubes that share at least one vertex yields a continuous path). Now, given two points p,p′ and two cubes D,D′ such that p∈D⊆Z and p′∈D′⊆Z, we can construct a path from p to p′ via
p→center(D)→center(D′)→p′.
Lemma 3. Given k∈N+ and any path-connected space Z, all functions from [0,1]k to Z are homotopic.
Proof. Let ϕ:[0,1]k→Z. Define a homotopy Φ:[0,1]×[0,1]k→Z by the rule Φ(t,x1,...,xk)=Φ((1−t)x1,...,(1−t)xk). Then, Φ(0) is ϕ, and Φ(1) is a constant map, proving that ϕ is null-homotopic. Since being homotopic is an equivalence relation (and any two constant maps are trivially homotopic in a path connected space), it follows that all maps [0,1]k→Z are homotopic to each other.
(4) Let ϵ∈R+ be a parameter that depends on n. We will specify how ϵ is chosen in the last part of the proof. It will have the properties that it’s at least as large as the diameter of a cube and that it converges to 0 as n grows.
Let A⊂S be connected. We define two operators on A. The first is the set of points in Y that wish for fn to hit on points near it. We set
Targets(A):={center(D)|∃x∈B(A,ϵ):f(x)∩D≠∅}
where B(A,ϵ)={x∈X|d(x,A)<ϵ}. The second is a sufficiently small subspace of Y that is guaranteed to contain all points that f touches on A. We set Area(A):=Expand(Targets(A)). Note that this set is identical to Expand(f(B(A,ϵ))), which makes it path-connected by Lemma 2.
We now want to define a partial function fn:X→Y. We begin by defining it on vertices, then generalize it to specific edges, then specific faces, and so on, until we define it on all cubes C∈Cubes(X) that intersect S.
A vertex v is defined to be a point v∈X of the form
v=(j1n,j2n,...,jnn)
for some j1,...,jn∈N. The set Area(v) may be empty if v is too far outside S, in which case we leave fn undefined on v. If it is not empty, choose y∈Area(v) arbitrarily and set fn(v):=y.
We now turn to edges. However, we only consider ‘horizontal’ edges, that is, subspaces e⊂X of the form
e={(a,j2n,...,jnn)|a∈(j1n,j1+1n)}
for some j1,...,jn∈N. Let v and w be the two vertices of e. If fn is undefined on either, we leave it undefined on e. If not, we define it in the following. Note that this is the step where we guarantee that fn hits all points in the target set.
We know from Lemma 3 that there is a path p:[0,1]→Area(e) from f(v) to f(w). Since e is homeomorphic to [0,1], it’s easy to transform p into a ‘path’ p′:e→Area(e). But we can do even better and construct a path p∗:e→Area(e) that starts at fn(v), ends at fn(w), and hits all points in Targets(e) on the way. (All trivial since Area(e) is path-connected.) Now we simply set fn(x)=p∗(x)∀x∈e.
We next consider all ‘horizontal-vertical’ faces, that is, all sets q⊂X of the form
q={(a,b,j3n,...,jnn)|a∈(j1n,j1+1n),b∈(j2n,j2+1n)}
for some j1,...,jn∈N. Let e and e′ be the two horizontal edges of q. If fn is undefined on either, we leave it undefined on q. If not, we have two paths p:[0,1]→Area(q) and p′:[0,1]→Area(q) which implement fn on e and e′, respectively. Using Lemma 3, we obtain a homotopy F:[0,1]×[0,1]→Area(q) that continuously deforms p into p′. Since our face q is homeomorphic to [0,1]×[0,1], it’s easy to transform F into a function F∗:q→Area(q). Now we simply set fn(x)=F∗(x)∀x∈q.
Now we do the same for 3-dimensional subspaces r⊂X of the form
r={(a,b,c,j4n,...,jnn)|a∈(j1n,j1+1n),b∈(j2n,j2+1n),c∈(j3n,j3+1n)}
where fn has been defined on the two horizontal-vertical faces, and so on. This way, every k-dimensional subspace of this kind contains precisely two k−1-dimensional subspaces of this kind, and if we have defined fn on both, we can apply a construction analogous to the above to define fn on the k-dimensional subspace. Eventually, we define fn on d-dimensional subspaces, which are precisely our cubes. (In the case of d-dimensional subspaces, the definition above doesn’t pose any restriction; it coincides with the definition of a cube C∈Cubes(X)). Importantly, this defines fn on any cube C∈Cubes(X) that intersects S. (This is so because any vertex of this cube is within ϵ of S, which means that it has non-empty area. This implies that we have defined fn on any edge, face, and so on, of C.) Thus, we end up having defined fn on some subspace of X that includes all cubes that intersect S.
The advantage of this construction is that, for any C∈Cubes(X), we know that f(C) is contained in Area(C), which is the same as the union of all cubes in Y that f touches on points near C. If we had used the homomorphic extension of fn instead (i.e., connecting via straight lines), we could merely guarantee that f(C) is contained in the convex hull of certain points in Y, which may be much larger.
(5) Having defined fn on a subset of X that contains S, we take a projection π:Y→T, and define ϕn:S→T by the rule ϕn(x)=π(fn(x)). It remains to show that our construction is such that the Hausdorff distance between f and fn converges to 0 as n→∞, then the distance between f and ϕn converges to 0 as well. (To see this, note that, if fn(x) is within δ of f(x) (which lies in S), then π can move it by at most δ, which means that π(fn(x)) is within 2δ of f(x).)
To do this, we now explain how ϵ is chosen, and then argue that the Hausdorff distance can be upper-bounded by some constant times ϵ.
The issue we have to deal with is that, by default, a point on the boundary of S may not have any edge close to it that is contained in S. (In fact, it may not even have an edge close to it that intersects S.) Thus, we would like ϵ to be so large that any ϵ-ball around a point in S must contain a δ-ball entirely contained in S, where δ is larger than the diameter of a cube. In that case, any x∈S is within ϵ of a cube entirely contained in S and thus also within ϵ of an edge entirely contained in S.
It remains to show that we can choose ϵ such that it (a) has this property and (b) converges to 0 as a function of n. To show this, we consider ϵ∈R+ fixed, and show that n eventually grows large enough for that ϵ to suffice.
For every point x∈S, there exists some δ∈R+ such that B(x,ϵ) contains some δ-ball entirely contained in S. Define a function γ:S→R+ that each point to the supremum of such δ’s. Then, γ is a continuous function from a compact set to R+, which means it takes on a minimum value. It now suffices to choose n large enough that the diameter of a cube is smaller than this minimum. (To verify that γ is continuous, take a sequence (xn)n∈N of points in S, assuming that (γ(xn))n∈N doesn’t converge, and derive a contradiction.)
With this out the way, we return to the proof that f is the Haudorff limit of the fn. This consists of showing two parts:
for any point on Gf (the graph of f), there exists a close point on Gfn (i.e., fn comes sufficiently close to all points on Gf); and
for any point on Gfn, there exists a close point on Gf (i.e., fn has no points too far away from Gf).
Both are now easy:
Let (x,y)∈Gf, and let D∈Cubes(Y) be a cube that contains y. Let e⊂S be an edge with distance at most ϵ to x. By construction, we have center(D)∈Targets(e), which means that there is a point x′∈e such that y′:=fn(x′)=center(D). Since d(x,x′)<ϵ and d(y,y′)<ϵ, the distance between (x,y) and (x′,y′) converges to 0 as n→∞.
Let (x′,y′)∈Gfn, and let D∈Cubes(Y) be a cube containing y′. Since y′∈D, it follows that D⊂Area(x′), which means there exists a point x∈S such that f(x)∩D≠∅, which is to say, such that there is a y∈D for which (x,y)∈Gf. Now d(x,x′)<ϵ and d(y,y′)<ϵ, and thus the distance between (x′,y′) and (x,y) again converges to 0 as n→∞.
Ex13
Follows from Ex11 and Ex12 :-)