Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 1 / 16F (Logic and Set Theory)

The Knaster-Tarski theorem says that the fixed points of a monotone self-map of a complete lattice form a complete lattice. In particular,For the first formula, let $a$ be the displayed meet. Monotonicity gives $f(a)\le f(x)\le x$ for every prefixed point $x$, hence $f(a)\le a$. Then $f(f(a))\le f(a)$, so $f(a)$ is itself prefixed; minimality of $a$ gives $a\le f(a)$. Thus $f(a)=a$. The dual argument gives the greatest fixed point. Applying the same construction above the join of any family of fixed points, and dually below its meet, supplies joins and meets within the fixed-point set.

A down-set contains every element below any of its members. Arbitrary unions and intersections of down-sets are down-sets. Thus the down-sets of $X$, ordered by inclusion, have joins given by unions and meets by intersections, so they form a complete lattice.

For the requested counterexample, takewith their usual orders. The set $X$ is a down-set in $Y$, while $Y$ is order-isomorphic to the down-set $[0,1/2]$ of $X$. They are not isomorphic because $Y$ has a greatest element and $X$ does not.

Let $f:X\to A\subseteq Y$ be an order isomorphism onto a down-set, and let $g:Y\to U=X\setminus B$ be an order isomorphism onto the complement of a down-set $B$. Define increasing down-setsThe order assumptions ensure inductively that each $D_n$ is a down-set. DefineThe usual Cantor-Schröder-Bernstein theorem orbit argument shows that these two pieces partition both domain and codomain bijectively: points generated from $B$ move forward through $f$, while every remaining point lies in $U$ and moves backward through $g$. Each branch preserves order. If $x\in D$ and $x^{\prime }<x$ then $x^{\prime }\in D$; hence the only mixed case has $x\notin D<x^{\prime }\in D$, and the initial/final-segment hypotheses put $h(x)<h(x^{\prime })$. Thus $h$ is an order isomorphism and