I have fond memories of the contraction mapping theorem, because it was the first fixed point theorem I ever learned.
1:
Let c = d(x, f(x)). Then d(f(x), f^2(x)) ⇐ q d(x, f(x)) = qc, and in general d(f^n(x), f^{n+1}(x)) ⇐ q^n c.
Now, d(f^n(x), f^{m}(x)) ⇐ c * \sum_{n ⇐ i ⇐ m} q^i which is a geometric series. The sum of this is then c q^n (1 - q^{m-n})/(1 - q) ⇐ the full series (which converges since q < 1) = c q^n/(1 - q)
This can be made arbitrarily small, so the sequence is Cauchy, so since we are in a complete metric space it converges.
The distance to the limit point is at most that value c q^n/(1 - q), because all terms after the nth iterate are within that of the nth iterate. This gives us the exponential convergence.
2:
First, there’s at most one fixed point for a contraction mapping. For if we had two, then we could take d(x,y) = d(f(x), f(y)) ⇐ q d(x,y) < d(x,y) for the two fixed points x,y. But then, we get a contradiction—unless x = y, in which case q d(x,y) = d(x,y) = 0.
For existence: the limit of the iterates of any x is our fixed point. This is because f(lim f^n(x)) = lim f(f^n(x)) = lim f^{n+1}(x) = lim f^n(x), where the first equality is from continuity of f
3:
Take the space of infinite binary sequences, where the distance we assign is 1/N where N is the earliest index for which two sequences differ (or 0 if they are the same always). This is a complete metric space, actually (as you can easily check). But the right shift operator is continuous (since if you differ no earlier than the Nth spot, then the image of you differs by no earlier than the (N+1)th spot), and has no fixed point, despite the fact that it also is a weak contraction (by virtue of pushing any differences to the right). This is because N/(N+1) isn’t bounded by a constant.
4: TODO
Take two points x, y. We’d like to show that there’s an epsilon such that ||(x—eps grad(f)(x)) - (y—eps grad(f)(y))|| is bounded by ||x—y|| times some constant less than 1.
We have ||x—y + eps (grad(f)(y) - grad(f)(x))|| =
5: TODO
6:
WLOG suppose x ⇐ f(x). Then f(x) ⇐ f^2(x), and we can repeat upwards. For n > |P|, by the pigeonhole principle the nth iterate is equal to some earlier iterate, so there’s n and m such that m < n f^n(x) = f^m(x). Thus all the iterates between these two are also equal. But then f(f^m(x)) = f^m(x) , so f^m(x) is a fixed point, but this is the same as f^n(x).
7:
f^n(x) is the same as max {f(f^m(x)) : m < n}. So let’s define f^alpha(x) as sup {f(f^beta(x)) : beta < alpha}
WLOG suppose again that x ⇐ f(x). Now if alpha is a limit ordinal than f(f^beta(x)) for any beta < alpha will just be equal to f^gamma(x) with gamma = beta + 1 < alpha. Thus this is really the sup of all previous iterates, and thus larger than it. For successor ordinals, we need to iterate the previous iterate once more—but we can use monotonicity here to get that we are larger than the previous iterate.
Thus we see that f^beta(x) ⇐ f^alpha(x) for all beta < alpha.
Suppose we have some alpha such that |alpha| > |L|. Then if this sequence is made of all unique elements, we would be able to monotonically inject alpha into L by sending each smaller ordinal to the associated iterate. This totally ordered chain of iterates has an ordinal type, which we just mapped alpha to an initial element of, and so we have |alpha| ⇐ |L| as ordinals, a contradiction (if instead we were to take them as cardinals, we’d still have a contradiction, because we can ordinal inject the least ordinal with the same cardinality with alpha, which then gives us an ordinal injection to L). Thus we have some repeat where f^beta(x) = f^alpha(x) for beta < alpha. But then all the iterates between these two are also equal.
So f(f^(beta)(x)) = f^beta(x), so f^beta(x) is a fixed point of f, f^beta(x) = f^alpha(x) so f^alpha(x) is a fixed point of f.
8:
The question is asking whether the set of fixed points has a sup and an inf.
Suppose we have some subset S of fixed points. I hope that the sup of these fixed points in the original lattice is actually a fixed point.
For any element x, the supremum s is larger than x, and so f(x) = x ⇐ f(s). Thus f(s) is an upper bound for the subset, and thus s ⇐ f(s). But then for some alpha, f^alpha(s) is a fixed point of f that’s an upper bound. So now I hope f^alpha(s) is our supremum in the fixed point lattice.
Suppose there was an upper bound that was a fixed point, u. Since s is a supremum in the encompassing lattice L, we have s ⇐ u. Thus f(s) ⇐ f(u) = u. In general, f^n(s) ⇐ f^n(u) = u. We can also take a sup of them to get f^beta(s) ⇐ u for limit ordinals beta. Therefore f^alpha(s) ⇐ u. But then f^alpha(s) is smaller than all upper bounds that are fixed points, and so f^alpha(s) is a supremum in the fix point lattice
Likewise for infimums.
Incidentally: The least element l satisfies l ⇐ f(l), so there’s an alpha such that the alpha iterate is a fixed point. If x is a fixed point, then since l ⇐ x for all x, we have f^alpha(l) ⇐ f^alpha(x) = x. But then f^alpha(l) is the least fixed point.
9: TODO
P(A) is clearly a lattice. To take sups and infs, we can just take arbitrary unions and intersections. (I think technically you need the axiom of choice, but whatever). Given a function f: A → B, we have that S ⇐ S’ ⇐ A implies f^img(S) ⇐ f^img(S’) (we don’t need injectivity for this), so the induced f is monotone.
Since f,g are injective, we know that the induced functions on the powerset lattices are also injective—that is, that f^img(S) != f^img(S’) if S != S’. Also, for injective functions, f(X—Y) = f(X) - f(Y)
...
10:
Using problem 9, there is a set A’ and B’ such that f(A’) = B’ and A—A’ = g(B—B’)
Now, we’d like to biject A’ with B’ and A—A’ with B—B’. To do this, we can take the restriction of f on A’ (restricting the codomain to B’ as well), and likewise take the restriction of g. The restrictions are bijections, because they are surjections and we already knew they were injections.
Then we can take the union of the relation associated to the restriction of f and the inverse of the relation associated with the restriction of g. This is then a function A → B, and it’s a bijection.
I have fond memories of the contraction mapping theorem, because it was the first fixed point theorem I ever learned.
1:
Let c = d(x, f(x)). Then d(f(x), f^2(x)) ⇐ q d(x, f(x)) = qc, and in general d(f^n(x), f^{n+1}(x)) ⇐ q^n c.
Now, d(f^n(x), f^{m}(x)) ⇐ c * \sum_{n ⇐ i ⇐ m} q^i which is a geometric series. The sum of this is then c q^n (1 - q^{m-n})/(1 - q) ⇐ the full series (which converges since q < 1) = c q^n/(1 - q)
This can be made arbitrarily small, so the sequence is Cauchy, so since we are in a complete metric space it converges.
The distance to the limit point is at most that value c q^n/(1 - q), because all terms after the nth iterate are within that of the nth iterate. This gives us the exponential convergence.
2:
First, there’s at most one fixed point for a contraction mapping. For if we had two, then we could take d(x,y) = d(f(x), f(y)) ⇐ q d(x,y) < d(x,y) for the two fixed points x,y. But then, we get a contradiction—unless x = y, in which case q d(x,y) = d(x,y) = 0.
For existence: the limit of the iterates of any x is our fixed point. This is because f(lim f^n(x)) = lim f(f^n(x)) = lim f^{n+1}(x) = lim f^n(x), where the first equality is from continuity of f
3:
Take the space of infinite binary sequences, where the distance we assign is 1/N where N is the earliest index for which two sequences differ (or 0 if they are the same always). This is a complete metric space, actually (as you can easily check). But the right shift operator is continuous (since if you differ no earlier than the Nth spot, then the image of you differs by no earlier than the (N+1)th spot), and has no fixed point, despite the fact that it also is a weak contraction (by virtue of pushing any differences to the right). This is because N/(N+1) isn’t bounded by a constant.
4: TODO
Take two points x, y. We’d like to show that there’s an epsilon such that ||(x—eps grad(f)(x)) - (y—eps grad(f)(y))|| is bounded by ||x—y|| times some constant less than 1.
We have ||x—y + eps (grad(f)(y) - grad(f)(x))|| =
5: TODO
6:
WLOG suppose x ⇐ f(x). Then f(x) ⇐ f^2(x), and we can repeat upwards. For n > |P|, by the pigeonhole principle the nth iterate is equal to some earlier iterate, so there’s n and m such that m < n f^n(x) = f^m(x). Thus all the iterates between these two are also equal. But then f(f^m(x)) = f^m(x) , so f^m(x) is a fixed point, but this is the same as f^n(x).
7:
f^n(x) is the same as max {f(f^m(x)) : m < n}. So let’s define f^alpha(x) as sup {f(f^beta(x)) : beta < alpha}
WLOG suppose again that x ⇐ f(x). Now if alpha is a limit ordinal than f(f^beta(x)) for any beta < alpha will just be equal to f^gamma(x) with gamma = beta + 1 < alpha. Thus this is really the sup of all previous iterates, and thus larger than it. For successor ordinals, we need to iterate the previous iterate once more—but we can use monotonicity here to get that we are larger than the previous iterate.
Thus we see that f^beta(x) ⇐ f^alpha(x) for all beta < alpha.
Suppose we have some alpha such that |alpha| > |L|. Then if this sequence is made of all unique elements, we would be able to monotonically inject alpha into L by sending each smaller ordinal to the associated iterate. This totally ordered chain of iterates has an ordinal type, which we just mapped alpha to an initial element of, and so we have |alpha| ⇐ |L| as ordinals, a contradiction (if instead we were to take them as cardinals, we’d still have a contradiction, because we can ordinal inject the least ordinal with the same cardinality with alpha, which then gives us an ordinal injection to L). Thus we have some repeat where f^beta(x) = f^alpha(x) for beta < alpha. But then all the iterates between these two are also equal.
So f(f^(beta)(x)) = f^beta(x), so f^beta(x) is a fixed point of f, f^beta(x) = f^alpha(x) so f^alpha(x) is a fixed point of f.
8:
The question is asking whether the set of fixed points has a sup and an inf.
Suppose we have some subset S of fixed points. I hope that the sup of these fixed points in the original lattice is actually a fixed point.
For any element x, the supremum s is larger than x, and so f(x) = x ⇐ f(s). Thus f(s) is an upper bound for the subset, and thus s ⇐ f(s). But then for some alpha, f^alpha(s) is a fixed point of f that’s an upper bound. So now I hope f^alpha(s) is our supremum in the fixed point lattice.
Suppose there was an upper bound that was a fixed point, u. Since s is a supremum in the encompassing lattice L, we have s ⇐ u. Thus f(s) ⇐ f(u) = u. In general, f^n(s) ⇐ f^n(u) = u. We can also take a sup of them to get f^beta(s) ⇐ u for limit ordinals beta. Therefore f^alpha(s) ⇐ u. But then f^alpha(s) is smaller than all upper bounds that are fixed points, and so f^alpha(s) is a supremum in the fix point lattice
Likewise for infimums.
Incidentally: The least element l satisfies l ⇐ f(l), so there’s an alpha such that the alpha iterate is a fixed point. If x is a fixed point, then since l ⇐ x for all x, we have f^alpha(l) ⇐ f^alpha(x) = x. But then f^alpha(l) is the least fixed point.
9: TODO
P(A) is clearly a lattice. To take sups and infs, we can just take arbitrary unions and intersections. (I think technically you need the axiom of choice, but whatever). Given a function f: A → B, we have that S ⇐ S’ ⇐ A implies f^img(S) ⇐ f^img(S’) (we don’t need injectivity for this), so the induced f is monotone.
Since f,g are injective, we know that the induced functions on the powerset lattices are also injective—that is, that f^img(S) != f^img(S’) if S != S’. Also, for injective functions, f(X—Y) = f(X) - f(Y)
...
10:
Using problem 9, there is a set A’ and B’ such that f(A’) = B’ and A—A’ = g(B—B’)
Now, we’d like to biject A’ with B’ and A—A’ with B—B’. To do this, we can take the restriction of f on A’ (restricting the codomain to B’ as well), and likewise take the restriction of g. The restrictions are bijections, because they are surjections and we already knew they were injections.
Then we can take the union of the relation associated to the restriction of f and the inverse of the relation associated with the restriction of g. This is then a function A → B, and it’s a bijection.