Past exam of the mathematics course of the University of Cambridge 2007 ii Paper 1 16G Solution Created 2026-09-24 Updated 2026-10-14
A complete lattice has every join, hence every directed and finite join. Conversely, if a partially ordered set is directed-complete and has finite joins including the empty join, then for any subset the set of joins of its finite subsets is nonempty and directed. Its least upper bound is . Including the empty join supplies a bottom element and handles .
For a directed set of partial functions from to , their union is a function: any two functions have a common extension, so they agree wherever their domains overlap. This union is exactly their least upper bound in the extension order, proving directed completeness.
Write for the intersection of all sets containing and closed under and directed joins. Then means . Reflexivity is immediate, and transitivity follows because any closed set containing must contain and then every with . The upper set is closed: is inflationary, and a directed join of elements above is above . Thus implies , proving antisymmetry.
If , then , so . Moreover by monotonicity, and by inflationarity. This proves that is directed. Define . Pointwise monotonicity of every implies monotonicity of . Since and is closed under directed joins, ; hence .
The original map belongs to by the definition of closedness, so and by the definition of the join. Inflationarity gives the reverse inequality. Finally, if and , the lower set is closed by monotonicity of and the join property. Thus every is at most , and so is . This proves the least fixed point from a directed family of maps: is the least fixed point above .