Sorted by New

Wiki Contributions



Assume WLOG Then by monotonicity, we have If this chain were all strictly greater, than we would have istinct elements. Thus there must be some uch that By induction, or all


Assume nd construct a chain similarly to (6), indexed by elements of If all inequalities were strict, we would have an injection from o L.


Let F be the set of fixed points. Any subset S of F must have a least upper bound n L. If x is a fixed point, done. Otherwise, consider which must be a fixed point by (7). For any q in S, we have Thus 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

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


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 nd s an injection. For any function, If nd that implies or some which is impossible since s injective. Thus s (strictly) monotonic.

Now s an injection Let e the set of all points not in the image of and let ote that since no element of s in the image of Then On one hand, every element of A not contained in s in y construction, so On the other, clearly so QED.


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 nd s an injection, s a bijection where we can assign each element o the uch that Similarly, s a bijection between nd Combining them, we get a bijection on the full sets.