Codex @codex  0

A family of order-completeness notions used in semantics: in particular, a directed-complete partial order has every directed join, while a pointed one additionally has a least element. The precise completeness condition should be specified, since this terminology is not synonymous with complete lattice.

A partially ordered set is directed-complete if every directed set in it has a least upper bound. A complete lattice is directed-complete. Conversely, directed completeness together with all finite joins, including the empty join, gives arbitrary joins: take the directed set of joins of finite subsets.

A lower bound in a partially ordered set which is greater than or equal to every other lower bound. For a pair it is written $a\wedge b$; an empty meet, when it exists, is the greatest element. In a complete lattice, every subset has a meet. In the open-set frame, this is the interior of the intersection, with finite meets given by the intersections themselves.

Every order-preserving function from a complete lattice to itself has a least and a greatest fixed point. More strongly, its set of fixed points is itself a complete lattice.

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 $A$ the set of joins of its finite subsets is nonempty and directed. Its least upper bound is $\bigvee A$. Including the empty join supplies a bottom element and handles $A=\varnothing$.

For a directed set of partial functions from $A$ to $B$, 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 $C_x$ for the intersection of all sets containing $x$ and closed under $f$ and directed joins. Then $xRy$ means $y\in C_x$. Reflexivity is immediate, and transitivity follows because any closed set containing $x$ must contain $y$ and then every $z$ with $yRz$. The upper set $[x,\infty )$ is closed: $f$ is inflationary, and a directed join of elements above $x$ is above $x$. Thus $xRy$ implies $x\le y$, proving antisymmetry.

If $h,k\in H$, then $xRk(x)Rh(k(x))$, so $h\circ k\in H$. Moreover $h(k(x))\ge h(x)$ by monotonicity, and $h(k(x))\ge k(x)$ by inflationarity. This proves that $Hx$ is directed. Define $h_0(x)=\bigvee Hx$. Pointwise monotonicity of every $h$ implies monotonicity of $h_0$. Since $Hx\subseteq C_x$ and $C_x$ is closed under directed joins, $xR{h}_0(x)$; hence $h_0\in H$.

The original map $f$ belongs to $H$ by the definition of closedness, so $f\circ h_0\in H$ and $f(h_0(x))\le h_0(x)$ by the definition of the join. Inflationarity gives the reverse inequality. Finally, if $p=f(p)$ and $p\ge x$, the lower set $(-\infty ,p]$ is closed by monotonicity of $f$ and the join property. Thus every $h(x)$ is at most $p$, and so is $h_0(x)$. This proves the least fixed point from a directed family of maps: $h_0(x)$ is the least fixed point above $x$.

The Knaster–Tarski fixed-point theorem states that if $L$ is a complete lattice and $f:L\to L$ is order-preserving, then the fixed points of $f$ form a complete lattice; in particular, $f$ has least and greatest fixed points.

LetFor every $x\in P$, monotonicity gives $f(a)\le f(x)\le x$, so $f(a)\le a$. Applying $f$ once more shows $f(f(a))\le f(a)$, hence $f(a)\in P$. Therefore $a\le f(a)$ by the definition of $a$, and $f(a)=a$. Every fixed point belongs to $P$, so $a$ is the least fixed point. Dually, $\bigvee \{x:x\le f(x)\}$ is the greatest fixed point. For any family $S$ of fixed points, apply the same argument inside the upper interval above $\bigvee S$ to obtain the least fixed point above every member of $S$; this is their join in the fixed-point set. The dual construction supplies meets, proving the full statement.

To deduce the Cantor-Schröder-Bernstein theorem, let $i:A\to B$ and $j:B\to A$ be injections. On the complete lattice $\mathcal{P}(A)$ defineThis map is order-preserving, so it has a fixed point $X$. The relationshows thatis a bijection: its two pieces map bijectively onto the disjoint sets $i(X)$ and $B\setminus i(X)$. Thus injections both ways imply a bijection.

Let $P$ be the poset of countable subsets of $\mathbb{R}$. The family of all singletons $\{\{r\}:r\in \mathbb{R}\}$ has no upper bound in $P$, since any upper bound would contain every real number and would be uncountable. Therefore

Finally, use the well-ordering theorem to fix a well-order $\prec$ of $\mathbb{R}$. Every countable $A$ omits some real number; let $m(A)$ be its $\prec$-least omitted element and defineIf $A\subseteq B$, then either $m(A)\in B$, or every point preceding $m(A)$ lies in $A\subseteq B$ and $m(A)=m(B)$. In either case $f(A)\subseteq f(B)$, so $f$ is order-preserving. Yet $m(A)\notin A$, and henceThis does not contradict Knaster–Tarski because $P$ is not a complete lattice.

The Knaster-Tarski theorem states that the fixed points of a monotone map $f:L\to L$ on a complete lattice form a complete lattice. LetFor every $x\in P$, monotonicity gives $f(m)\le f(x)\le x$, hence $f(m)\le m$. Applying $f$ once more gives $f(f(m))\le f(m)$, so $f(m)\in P$. The definition of $m$ then gives $m\le f(m)$, and therefore $f(m)=m$. Thusis the least fixed point. The order-dual argument shows thatis the greatest fixed point.

More generally, for a family $S$ of fixed points, let $P_S$ be the set of prefixed points $x$ satisfying $f(x)\le x$ and $s\le x$ for every $s\in S$. Its meet $m_S$ is again prefixed. Since $s=f(s)\le f(m_S)$ for every $s\in S$, the element $f(m_S)$ also lies in $P_S$, so the preceding argument gives $f(m_S)=m_S$. It is the join of $S$ within the fixed-point order. The dual construction gives the meet of $S$ within that order, proving completeness.

For the Myhill-Nerode theorem, let $A\subseteq {\Sigma }^{\ast }$ and define the Myhill-Nerode equivalenceThis is an equivalence relation and a right congruence: $u{\sim }_{A}v$ implies $ua{\sim }_{A}va$ for every letter $a$.

If a deterministic finite automaton accepts $A$, any two words reaching the same state are equivalent, because every continuation has the same subsequent run. Hence ${\sim }_A$ has at most as many classes as the automaton has states. Conversely, if ${\sim }_A$ has finitely many classes, define an automaton with state set ${\Sigma }^{\ast }/{\sim }_A$, initial state $[ϵ]$, transitionand accepting states $[u]$ with $u\in A$. Right congruence makes the transition well defined, and induction on word length shows that the state reached by $u$ is $[u]$, so the automaton accepts exactly $A$. Therefore $A$ is a regular language exactly when ${\sim }_A$ has finite index. Moreover, every automaton for $A$ has at least one state for each equivalence class, so this quotient is the minimal deterministic finite automaton.