\documentstyle[12pt]{report}
\pagestyle{myheadings}
\def\headlineaux{\sc Math 688: Theory of Computability and Complexity \hrulefill}
\markboth{\headlineaux}{\headlineaux}

\newcommand{\assignmentNumber}{4}
\newcommand{\outdate}{13 October, 1992}
\newcommand{\userEnter}[2]{\begin{itemize}\item[$>$]
   {\bf #1 } {\em #2}\end{itemize}}
\newcommand{\naturals}{\mbox{\bf N}}
\newcommand{\compose}{\circ}

\newtheorem{theorem}{Theorem}

\begin{document}
\begin{titlepage}\begin{centerline}{\Huge \framebox{Burt Rosenberg}}
\end{centerline}\end{titlepage}

\section*{Least Fixed Points \hfill{\parbox{3in}
    {\small\sc\begin{flushright} Date: \outdate\end{flushright}}}}

Some non-examples of the least-fixed-point theorem.

\begin{theorem}[Least Fixed Point]
Let $A$ have a partial-order with least element $\bot$ and such that any
ascending chain as a least upper bound. Let $\Theta$ be an endomorphism
of $A$ which is continuous and total. Then,
\[ Y(\Theta) = \bigvee_{n\ge 0}\Theta^n(\bot) \]
exists and is the unique least fixed point of $\Theta$.
\end{theorem}

\begin{enumerate}
\item Take $A$ the set of opens of a topological space except for the empty
set. The $A$ fails the hypothesis of the theorem only it that it lacks a least
element. Let $\Theta$ be the identity, it is continuous and total. Yet is
has no least fixed point.
\item Take $A$ to be the set of all subsets of a set except the empty set and
$\Theta$ the identity. The failure here is that $A$ has no least element.
All singletons are least fixed points.
\item Let $A$ be the reals in the interval $[0,1]$ with usual size
ordering. It is an $\omega$-cpo with $\bot=0$. Let
$\Theta$ be the discontinuous map,
\[ \Theta(x) = \left\{\begin{array}{ll}
            1/4 + x/2 & x\in [0,1/2) \\
            1/2 + x/2 & x\in [1/2,1]
\end{array}\right. \]
Then $\Theta(1)=1$ is the least-fixed-point although the sup of $\Theta^n(\bot)$
is 1/2.
\end{enumerate}
\end{document}