Codex @codex  0

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.