Assume WLOG f(x)>=xThen by monotonicity, we have x<=f(x)<=f2(x)<=...<=f|P|(x)If this chain were all strictly greater, than we would have |P|+1istinct elements. Thus there must be some kuch that fk(x)=fk+1(x)By induction, fn+1(x)=fn(x)=fk(x)or all n>k
#7:
Assume f(x)>=xnd construct a chain similarly to (6), indexed by elements of αIf all inequalities were strict, we would have an injection from αo L.
#8:
Let F be the set of fixed points. Any subset S of F must have a least upper bound xn L. If x is a fixed point, done. Otherwise, consider fα(x) which must be a fixed point by (7). For any q in S, we have f(q)≤x⇒fα(q)≤fα(x)⇒q≤fα(x) Thus fα(x)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⇒fα(x)<=fα(b)=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 A0⊆A1nd fs an injection. For any function, f(A0)⊆f(A1) If a∉A0nd f(a)∈f(A0)that implies f(a)=f(a′)or some a′∈A0which is impossible since fs injective. Thus fs (strictly) monotonic.
Now h:=g∘fs an injection A→ALet Xe the set of all points not in the image of gand let A′=X∪h(X)∪h2(X)∪...ote that h(A′)=h(X)∪h2(X)∪h3(X)∪...=A′−Xsince no element of Xs in the image of hThen g(B−f(A′))=g(B)−h(A′)=g(B)−(A′−X)=g(B)−A′+g(B)∩X=g(B)−A′On one hand, every element of A not contained in g(B)s in A′y construction, so A−A′⊆g(B) On the other, clearly g(B)⊆Aso g(B)−A′⊆A−A′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′=f(A′)nd fs an injection, fs a bijection where we can assign each element b′∈B′o the a′∈A′uch that f(a′)=b′Similarly, gs a bijection between B−B′nd A−A′Combining them, we get a bijection on the full sets.
#6:
Assume WLOG f(x)>=xThen by monotonicity, we have x<=f(x)<=f2(x)<=...<=f|P|(x)If this chain were all strictly greater, than we would have |P|+1istinct elements. Thus there must be some kuch that fk(x)=fk+1(x)By induction, fn+1(x)=fn(x)=fk(x)or all n>k
#7:
Assume f(x)>=xnd construct a chain similarly to (6), indexed by elements of αIf all inequalities were strict, we would have an injection from αo L.
#8:
Let F be the set of fixed points. Any subset S of F must have a least upper bound xn L. If x is a fixed point, done. Otherwise, consider fα(x) which must be a fixed point by (7). For any q in S, we have f(q)≤x⇒fα(q)≤fα(x)⇒q≤fα(x) Thus fα(x)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⇒fα(x)<=fα(b)=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 A0⊆A1nd fs an injection. For any function, f(A0)⊆f(A1) If a∉A0nd f(a)∈f(A0)that implies f(a)=f(a′)or some a′∈A0which is impossible since fs injective. Thus fs (strictly) monotonic.
Now h:=g∘fs an injection A→ALet Xe the set of all points not in the image of gand let A′=X∪h(X)∪h2(X)∪...ote that h(A′)=h(X)∪h2(X)∪h3(X)∪...=A′−Xsince no element of Xs in the image of hThen g(B−f(A′))=g(B)−h(A′)=g(B)−(A′−X)=g(B)−A′+g(B)∩X=g(B)−A′On one hand, every element of A not contained in g(B)s in A′y construction, so A−A′⊆g(B) On the other, clearly g(B)⊆Aso g(B)−A′⊆A−A′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′=f(A′)nd fs an injection, fs a bijection where we can assign each element b′∈B′o the a′∈A′uch that f(a′)=b′Similarly, gs a bijection between B−B′nd A−A′Combining them, we get a bijection on the full sets.