Ex 6:

If at any point $f^n\left(b\right)=f^{n-1}\left(x\right)$, then we're done. So assume that we get a strict increase each time up to $n=|P|$. Since there are only $|P|$ elements in the entire poset, and $f$ is monotone, $f^{n+1}\left(x\right)$ has to equal $f^n\left(x\right)$.

Ex 7:

For a limit ordinal $\alpha$, define $f^{\alpha }\left(x\right)$ as the least upper bound of $f^n\left(x\right)$ for all $n<\alpha$. If $\alpha >|L|$, then the set $f^n\left(x\right)$ for $n<\alpha$ is a set of size $\alpha$ that maps into a set of size $L$ by taking the value of the element. Since there are no injections between these sets, there must be two ordinals $n<m$ such that$f^n\left(x\right)=f^m\left(x\right)$. Since $f$ is monotone, that implies that for every ordinal $l>n$, $f^l\left(x\right)=f^n\left(x\right)$and thus is a fixed point. Since $n<\alpha$ this proves the exercise.

Ex 8:

Starting from $x$, we can create a fixed point via iteration by taking $\alpha >|L|$, and iterating $\alpha$ times as demonstrated in Ex 7. Call this fixed point $f_x$. Suppose there was a fixed point $k$ such that $x\le k$ and $k\le f_x$. Then at some point $f^n\left(x\right)\le f^n\left(k\right)=k$, but $f^{n+1}\left(x\right)\ge f^{n+1}\left(k\right)=k$, which breaks the monotonicity of $f$ unless $k=f_x$. So $f_x$ generated this way is always the smallest fixed point greater than $x$.

Say we have fixed points $x_i$. Then let $x$ be the least upper bound of $x_i$, and generate a fixed point from $f_x$. So $f_x$ will be greater than each element of $x_i$ since $f$ is monotone, and is the smallest such fixed point as shown in the above paragraph. So the poset of fixed points is semi-complete with upper bounds.

Now take our fixed points $x_i$ again. Now let $x$ be the greatest lower bound of $x_i$, and generate a fixed point $f_x$. Since $x\le x_i$ and $f$ is monotonic, $f^{\alpha }\left(x\right)\le f^{\alpha }\left(x_i\right)=x_i$, and so $f_x$ is a lower bound of $x_i$. It has to be the greatest such bound because $x$ itself is already the greatest such bound in our poset, and $f$ is monotonic.

Thus the lattice of fixed points has all least upper bounds and all greatest lower bounds, and is thus complete!

Q1

We wish to show that the terms of $x_n$ form a Cauchy sequence, which suffices to demonstrate they converge in a complete space. Take $m,n\in N^{+}$, and WLOG $m<n$. Then we know from the definition of contraction that $d(x_m,x_n)\le q^m\cdot d(x_0,x_{n-m})$. This converges to 0 as m increases, so the sequence is Cauchy.

It's easy to see that this makes the rate of convergence between terms of the Cauchy sequence exponentially quick. Intuitively that seems like it ought to make the sequence converge to its limit with the same speed, but I don't think that can be made rigorous without more steps.

Q2

Take a sequence $\{x_n=f^n(x_0\left)\right\}$. This converges to some $L$. Suppose $L$ was not a fixed point. Then choose an $ϵ=(L-f(L\left)\right)/10$ . A sequence $\left\{x_n\right\}$ which converges to a limit has, for every $ϵ$, some $N$ such that $\forall n>=N:|x_n-L|<ϵ$. Then we know that $d(x_N,L)<ϵ$ but $d\left(f\right(x_N),f(L\left)\right)>ϵ$ , contradicting the contraction condition. So there is at least one fixed point, $L$.

Suppose there are two fixed points, $f\left(x\right)=x$, $f\left(y\right)=y$ for distinct $x$ and $y$. If so, $d\left(f\right(x),f(y\left)\right)=d(x,y)$, which again contradicts the contraction condition. So there is at most one fixed point.

Q3

Take as the space $\{n\in R^{+}:n\ge 1\}$, with the usual metric. Define $f\left(x\right)=\frac{x^2+1}{x}$. This is a weak contraction (toward infinity) and has no fixed points within this space.

#6:

Assume WLOG $f\left(x\right)>=x$Then by monotonicity, we have $x<=f\left(x\right)<=f^2\left(x\right)<=...<=f^{|P|}\left(x\right)$If this chain were all strictly greater, than we would have $|P|+1$istinct elements. Thus there must be some $k$uch that $f^k\left(x\right)=f^{k+1}\left(x\right)$By induction, $f^{n+1}\left(x\right)=f^n\left(x\right)=f^k\left(x\right)$or all $n>k$

#7:

Assume $f\left(x\right)>=x$nd construct a chain similarly to (6), indexed by elements of $\alpha$If all inequalities were strict, we would have an injection from $\alpha$o L.

#8:

Let F be the set of fixed points. Any subset S of F must have a least upper bound $x$n L. If x is a fixed point, done. Otherwise, consider $f^{\alpha }\left(x\right)$ which must be a fixed point by (7). For any q in S, we have $f\left(q\right)\le x\Rightarrow f^{\alpha }\left(q\right)\le f^{\alpha }\left(x\right)\Rightarrow q\le f^{\alpha }\left(x\right)$ Thus $f^{\alpha }\left(x\right)$s an upper bound of S in F. To see that it is the least upper bound, assume we have some other upper bound b of S in F. Then $x<=b\Rightarrow f^{\alpha }\left(x\right)<=f^{\alpha }\left(b\right)=b$

To get the lower bound, note that we can flip the inequalities in L and still have a complete lattice.

#9:

P(A) clearly forms a lattice where the upper bound of any set of subsets is their union, and the lower bound is the intersection.

To see that injections are monotonic, assume $A_0\subseteq A_1$nd $f$s an injection. For any function, $f\left(A_0\right)\subseteq f\left(A_1\right)$ If $a\notin A_0$nd $f\left(a\right)\in f\left(A_0\right)$that implies $f\left(a\right)=f\left(a^{\prime }\right)$or some $a^{\prime }\in A_0$which is impossible since $f$s injective. Thus $f$s (strictly) monotonic.

Now $h:=g\circ f$s an injection $A\to A$Let $X$e the set of all points not in the image of $g$and let $A^{\prime }=X\cup h\left(X\right)\cup h^2\left(X\right)\cup ...$ote that $h\left(A^{\prime }\right)=h\left(X\right)\cup h^2\left(X\right)\cup h^3\left(X\right)\cup ...=A^{\prime }-X$since no element of $X$s in the image of $h$Then $g(B-f(A^{\prime }\left)\right)=g\left(B\right)-h\left(A^{\prime }\right)=g\left(B\right)-(A^{\prime }-X)=g\left(B\right)-A^{\prime }+g\left(B\right)\cap X=g\left(B\right)-A^{\prime }$On one hand, every element of A not contained in $g\left(B\right)$s in $A^{\prime }$y construction, so $A-A^{\prime }\subseteq g\left(B\right)$ On the other, clearly $g\left(B\right)\subseteq A$so $g\left(B\right)-A^{\prime }\subseteq A-A^{\prime }$QED.

#10:

We form two bijections using the sets from (9), one between A' and B', the other between A - A' and B - B'.

Any injection is a bijection between its domain and image. Since $B^{\prime }=f\left(A^{\prime }\right)$nd $f$s an injection, $f$s a bijection where we can assign each element $b^{\prime }\in B^{\prime }$o the $a^{\prime }\in A^{\prime }$uch that $f\left(a^{\prime }\right)=b^{\prime }$Similarly, $g$s a bijection between $B-B^{\prime }$nd $A-A^{\prime }$Combining them, we get a bijection on the full sets.