(The second half made me realize how much more comfortable I am with abstract exercises than with regular Analysis à la Ex4.)
Ex6
If f(x)≤x, then all fn(x) are comparable to each other: we have
f(x)≤x⟹f(f(x))≤f(x)⟹f3(x)≤f2(x)
and so on. Furthermore, if n∈N is such that fn(x)≠fn−1(x), then fk(x)≠fk−1(x) for all k∈[n] as well (verify by looking at the contrapositive). Consequently (set n:=|P|), if fn(x) were not a fixed point of f, then fn+1(x)<fn(x), and hence {x,f(x),f2(x),...,fn+1(x)}⊆P, which means P would have |P|+2 elements.
If x≤f(x), we get x≤f(x)≤f2(x) and so on, leading to the same argument.
Ex7
Wlog, assume x≤f(x). Set f0(x):=x. Given any non-limit ordinal β, we find a predecessor α and set fβ(x):=f(fα(x)). Given any limit ordinal ω, we set fω(x):=sup{fα(x)|α∈ω}.
Suppose this doesn’t define fα(x) for all ordinals α. Then, there is some smallest ordinal α∗ such that fα∗(x) is not defined. This immediately yields a contradiction (regardless of whether α∗ is a limit ordinal or not).
We want this construction to have the properties that f(x)=x⟹fβ(x)=x and that x≤y⟹fβ(x)≤fβ(y). Thus, let x,y∈L and β be an ordinal. If β has a predecessor, the check for both properties are easy. If not, then fβ(x)=sup{fα(x)|α∈β} and fβ(y)=sup{fα(y)|α∈β}. Then, for the first property, note that the upper-bound of a one-element set is just the element itself. For the second, note that each element in the first set is smaller than some element in the second set, so fβ(y) is an upper-bound for the first set, which implies that fβ(x)≤fβ(y) since fβ(x) is the lowest upper-bound.
Now, given an ordinal α, our construction defines a function ϕ:α→L. If f(fα(x))≠fα(x), then the chain doesn’t become stationary at any earlier point either (to verify, take a smallest α such that [f(fα(x))≠fα(x) but the chain is stationary for smaller ordinals] and derive a contradiction), and hence ϕ is injective, proving that α≤|L|. (This is the generalized version of the argument from Ex6.)
Ex8
Let f:L→L be monotonic and let L′ be the set of fixed points of f. Then L′ inherits the partial order from L; what needs doing is verify the least upper-bound property. So let X⊆L′. Then, X has a least upper-bound u in L.
Let ω be some ordinal with ω>|L|. From the previous exercise, we know that f(fω(u))=fω(u). Choose the smallest α such that f(fα(u))=fα(u). Then, fα(u)∈L′ and x≤u≤fα(u), hence fα(u) is an upper-bound of X.
It remains to show that it is the least upper-bound. Thus, let u′∈L′ be another upper-bound of x. Then, u≤u′ in L, hence fα(u)≤fα(u′)=u′ (apply Ex7).
Ex9
A least upper-bound is obtained via ⋃ on all sets, and the greatest lower-bound via ⋂. (Easy checks.) Given any function f:A→B, we trivially have X⊆Y⟹f(X)⊆f(Y); injectivity is not needed.
We define
A(0):=A
A(n+1):=A(n)−g(B−f(A(n)))∀n∈N
A′:=⋂∞j=0A(j) (i.e., greatest lower bound of the A’s)
We need to verify that g(B−f(A′))=A−A′, then A′ and f(A′) are the desired sets.
“⊆”: Let y∈B−f(A′). Then, there exists some smallest j∈N such that y∈B−f(A(j)). (The case j=0 is possible and included.) We have A(j+1)=A(j)−g(B−f(A(j)), hence g(y)∉A(j). Then, g(y)∉A′, hence g(y)∈A−A′.
“⊇”: Let x∈A−A′. Then, there exists some smallest k∈N such that x∉A(k). In this case, we must have k>0, so we know that x∈A(k−1). It follows that x was lost at this step, i.e.,
x∈A(k−1)−A(k)=g(B−f(A(j)))⊆g(B−f(A′))
Ex10
Let A′ be the set constructed in Ex9. Then, we can define a bijection ϕ:A→B via
(The second half made me realize how much more comfortable I am with abstract exercises than with regular Analysis à la Ex4.)
Ex6
If f(x)≤x, then all fn(x) are comparable to each other: we have
f(x)≤x⟹f(f(x))≤f(x)⟹f3(x)≤f2(x)
and so on. Furthermore, if n∈N is such that fn(x)≠fn−1(x), then fk(x)≠fk−1(x) for all k∈[n] as well (verify by looking at the contrapositive). Consequently (set n:=|P|), if fn(x) were not a fixed point of f, then fn+1(x)<fn(x), and hence {x,f(x),f2(x),...,fn+1(x)}⊆P, which means P would have |P|+2 elements.
If x≤f(x), we get x≤f(x)≤f2(x) and so on, leading to the same argument.
Ex7
Wlog, assume x≤f(x). Set f0(x):=x. Given any non-limit ordinal β, we find a predecessor α and set fβ(x):=f(fα(x)). Given any limit ordinal ω, we set fω(x):=sup{fα(x)|α∈ω}.
Suppose this doesn’t define fα(x) for all ordinals α. Then, there is some smallest ordinal α∗ such that fα∗(x) is not defined. This immediately yields a contradiction (regardless of whether α∗ is a limit ordinal or not).
We want this construction to have the properties that f(x)=x⟹fβ(x)=x and that x≤y⟹fβ(x)≤fβ(y). Thus, let x,y∈L and β be an ordinal. If β has a predecessor, the check for both properties are easy. If not, then fβ(x)=sup{fα(x)|α∈β} and fβ(y)=sup{fα(y)|α∈β}. Then, for the first property, note that the upper-bound of a one-element set is just the element itself. For the second, note that each element in the first set is smaller than some element in the second set, so fβ(y) is an upper-bound for the first set, which implies that fβ(x)≤fβ(y) since fβ(x) is the lowest upper-bound.
Now, given an ordinal α, our construction defines a function ϕ:α→L. If f(fα(x))≠fα(x), then the chain doesn’t become stationary at any earlier point either (to verify, take a smallest α such that [f(fα(x))≠fα(x) but the chain is stationary for smaller ordinals] and derive a contradiction), and hence ϕ is injective, proving that α≤|L|. (This is the generalized version of the argument from Ex6.)
Ex8
Let f:L→L be monotonic and let L′ be the set of fixed points of f. Then L′ inherits the partial order from L; what needs doing is verify the least upper-bound property. So let X⊆L′. Then, X has a least upper-bound u in L.
Let ω be some ordinal with ω>|L|. From the previous exercise, we know that f(fω(u))=fω(u). Choose the smallest α such that f(fα(u))=fα(u). Then, fα(u)∈L′ and x≤u≤fα(u), hence fα(u) is an upper-bound of X.
It remains to show that it is the least upper-bound. Thus, let u′∈L′ be another upper-bound of x. Then, u≤u′ in L, hence fα(u)≤fα(u′)=u′ (apply Ex7).
Ex9
A least upper-bound is obtained via ⋃ on all sets, and the greatest lower-bound via ⋂. (Easy checks.) Given any function f:A→B, we trivially have X⊆Y⟹f(X)⊆f(Y); injectivity is not needed.
We define
A(0):=A
A(n+1):=A(n)−g(B−f(A(n)))∀n∈N
A′:=⋂∞j=0A(j) (i.e., greatest lower bound of the A’s)
We need to verify that g(B−f(A′))=A−A′, then A′ and f(A′) are the desired sets.
“⊆”: Let y∈B−f(A′). Then, there exists some smallest j∈N such that y∈B−f(A(j)). (The case j=0 is possible and included.) We have A(j+1)=A(j)−g(B−f(A(j)), hence g(y)∉A(j). Then, g(y)∉A′, hence g(y)∈A−A′.
“⊇”: Let x∈A−A′. Then, there exists some smallest k∈N such that x∉A(k). In this case, we must have k>0, so we know that x∈A(k−1). It follows that x was lost at this step, i.e.,
x∈A(k−1)−A(k)=g(B−f(A(j)))⊆g(B−f(A′))
Ex10
Let A′ be the set constructed in Ex9. Then, we can define a bijection ϕ:A→B via
ϕ:x↦{f(x)x∈A′g−1(x)x∉A′