topology.tex

\documentclass{article}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{hyperref}
\usepackage{xypic}

\newtheorem{theorem}{Theorem}%[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}%[section]
\newtheorem{conjecture}{Conjecture}%[section]
\newtheorem{example}{Example}%[section]
\newtheorem{remark}{Remark}

\newcommand{\Reals}[0]{\mathbb{R}}
\newcommand{\Rats}[0]{\mathbb{Q}}

\title{Notes on Topology}

\author{Jeremy G. Siek}

\begin{document}
\maketitle

Questions:
\begin{itemize}
\item What is the relationship between $\epsilon$-$\delta$ continuity
  (i.e. limit-based continuity) on reals and continuity for complete
  partial orders?
\item How does the slogan: ``only finite input is needed to produce
  finite output'' apply to continuous functions on the reals?
\item How does this relate to the topology on $\mathcal{P}(\mathbb{N})$?
\end{itemize}


From Wikipedia:
\begin{quote}
``For example, in order theory, an order-preserving function $f: X \to
  Y$ between particular types of partially ordered sets $X$ and $Y$ is
  continuous if for each directed subset A of X, we have $\bigsqcup
  f(A) = f(\bigsqcup A)$. Here $\bigsqcup$ is the least-upper bound
  with respect to the orderings in $X$ and $Y$, respectively. This
  notion of continuity is the same as topological continuity when the
  partially ordered sets are given the Scott topology.''
\end{quote}

From Davey and Priestley:
\begin{quote}
  ``In analysis, a function is continuous if it preserves limits.
  In a context in which a computation is modelled as the join (= limit)
  of a directed set, it is natural to consider a map as being continuous if it is compatible with
  the formation of directed joins. Formally, we say $f : P \to Q$ is continuous if,
  for every directed set $D$ in $P$, the subset $f(Q)$ of $Q$ is directed and
  \[
  f\left(\sqcup D\right) = \bigsqcup \{ f(x) \mid x \in D \}
  \]
  ... every continous map is order preserving. Where the order represents 'is less defined than'
  or 'is a worse approximation then', an order-preserving map $f$ is one in which the
  better the input $x$, the better the output $f(x)$.
\end{quote}

\section{Topology on $\Reals$}

We consider topological notions in the familiar setting of the real
numbers $\Reals$.

\begin{definition}[Open Interval]
  $\mathcal{I}_r(x) = (x-r,x+r)$
\end{definition}

\begin{definition}[Accumulation Point]
  A point $x \in \Reals$ is an accumulation point of $A \subseteq
  \Reals$ if for every $\delta > 0$, there exists $z \in
  \mathcal{I}_\delta(x) \cap A$ such that $z \neq x$.
\end{definition}


\begin{definition}[Limit of Function]
  Suppose $f : A \to \Reals$ and $A \subseteq \Reals$.
  Suppose $c \in \Reals$ is an accumulation point of $A$.
  Then
  \[
   \lim_{x\to c} f(x) = \ell
  \]
  if for every $\epsilon > 0$ there exists a $\delta > 0$
  such that
  \[
  x \in \mathcal{I}_\delta(c) \implies f(x) \in \mathcal{I}_\epsilon(\ell)
  \]
\end{definition}

\begin{definition}[Continuous]
  A function $f : A \to \Reals$, with $A \subseteq \Reals$,
  is continuous at $c \in A$ if $f$ preserves the limit at $c$:
  \[
    \lim_{x\to c} f(x) = f(c)
  \]
  or equivalently, expanding the definition of limit, for every
  $\epsilon > 0$, there exists $\delta > 0$ such that
  \[
    |x - c| < \delta \land x \in A \implies |f(x) - f(c)| < \epsilon
  \]
  or in terms of open intervals,
  \[
    x \in \mathcal{I}_\delta(c) \land x \in A \implies f(x) \in \mathcal{I}_\epsilon(f(c)).
  \]

  A function $f$ is continuous on a set $B \subseteq A$ if it is
  continuous on every element in B.
\end{definition}

\begin{example}
$f(x) = \sqrt x$ is continuous at all $c > 0$. 
For $0 \leq x$, we calculate
\begin{equation}\label{eq:sqrt-cont-1}
   |f(x) - f(c)| = |\sqrt x - \sqrt c| 
    = \left| \frac{x - c}{\sqrt x + \sqrt c} \right|
    \leq \frac{1}{\sqrt c} |x - c|
\end{equation}
Choose $\delta = \epsilon \sqrt c$. Assume $|x - c| < \epsilon \sqrt c$
and $x \in A$. We need to show that $|\sqrt x - \sqrt c| < \epsilon$.
From the assumption we have $\frac{1}{\sqrt c}|x - c| < \epsilon$,
and then by calculation \eqref{eq:sqrt-cont-1} we conclude.
\end{example}

\begin{example}
\[
   \mathrm{sign}(x) = 
   \begin{cases}
     1 & \text{if } x > 0 \\
     0 & \text{if } x = 0 \\
     -1 & \text{if } x < 0 
   \end{cases}
\]
$\mathrm{sign}$ is not continuous at $0$. Consider $\epsilon = \frac{1}{2}$.
We have $|f(x)| = 1$ for any $x \neq 0$, no matter how close $x$ is to
$0$. And obviously, $|f(x)| = 1 \not < \frac{1}{2}$.
\end{example}


\begin{definition}[Neighborhood]
  A set $U \subseteq \Reals$ is a neighborhood of $x \in \Reals$
  if there is a $\delta > 0$ such that $\mathcal{I}_\delta(x) \subseteq U$.
  (Munkres instead defines a neighborhood of $x$ to be
   an open set containing $x$.)
\end{definition}


\begin{definition}[N-Continuous]
  A function $f : A \to \Reals$, with $A \subseteq \Reals$,
  is n-continuous at $c \in A$ if for every neighborhood
  $V$ of $f(c)$ there exists a neighborhood $U$ of $c$
  such that
  \[
    x \in A \cap U \implies f(x) \in V
  \]
\end{definition}

\begin{proposition}
  Continuous and n-continuous are equivalent.
\end{proposition}
\begin{proof}
   Intuitively, the reason that they are the same is that in the
   definition of continuity, we talk of all the $x$'s that are within
   a certain distance of $c$, which means we're talking about an open
   interval around $c$, and a neighborhood of $c$ is guaranteed to
   include such a open interval around $c$. (And similarly for an open
   interval around $f(c)$.)
   \begin{enumerate}
   \item (continuous $\implies$ n-continuous)
     Suppose $f$ is continuous at $c$.
     Let $V$ be a neighborhood of $f(c)$.
     By the definition of neighborhood there exists a $\epsilon > 0$ such that
     \begin{equation} \label{eq:ball-V-1}
     \mathcal{I}_\epsilon(f(c)) \subseteq V
     \end{equation}
     Because $f : A \to \Reals$ is continuous at $c$, 
     there exists $\delta > 0$ such that
     \begin{equation} \label{eq:ed-cont-1}
     |x - c| < \delta \land x \in A \implies |f(x) - f(c)| < \epsilon
     \end{equation}
     Choose $U=\mathcal{I}_\delta(c)$. We need to show
     \[
     x \in A \cap U \implies f(x) \in V
     \]
     We assume $x \in A \cap U$. Then by \eqref{eq:ed-cont-1} we have
     $|f(x) - f(c)| < \epsilon$. So $f(x) \in \mathcal{I}_\epsilon(f(c))$
     and then $f(x) \in V$ by \eqref{eq:ball-V-1}.
     Therefore $f$ is n-continuous.

   \item (n-continuous $\implies$ continuous) Suppose $f$ is
     n-continouous at $c$ and $\epsilon > 0$. Note that
     $\mathcal{I}_\epsilon(f(c))$ is a neighborhood of $f(c)$. Then because $f$
     n-continuous there is a neighborhood $U$ of $c$ such that
     \begin{equation}\label{eq:xU-fx-Be}
       x \in A \cap U \implies f(x) \in \mathcal{I}_\epsilon(f(c))
     \end{equation}
     Because $U$ is a neighborhood of $c$, there is a $\delta > 0$
     such that $\mathcal{I}_\delta(c) \subseteq U$. We need to show that
     \[
     |x - c| < \delta \land x \in A \implies |f(x) - f(c)| < \epsilon
     \]
     Assume $|x - c| < \delta$ and $x \in A$.
     We have $x \in U$, then by \eqref{eq:xU-fx-Be} obtain
     $f(x) \in \mathcal{I}_\epsilon(f(c))$. From this we conclude that
     $|f(x) - f(c)| < \epsilon$. Therefore $f$ is continuous.

   \end{enumerate}
\end{proof}


\begin{definition}[Open Set]
  A set $A$ is open in $\Reals$ if for every $x \in A$ there exists
  $\delta > 0$ such that $\mathcal{I}_\delta(x) \subseteq A$.
\end{definition}

\begin{definition}[O-Continuous]
  A function $f : A \to \Reals$ is o-continuous if for each
  open set $V \subseteq \Reals$, $f^{-1}(V)$ is an open subset of $A$.
\end{definition}

\begin{proposition}
  Continuous and o-continuous are equivalent.
\end{proposition}
\begin{proof}\ 
\begin{enumerate}
\item (continuous $\implies$ o-continuous)
  Let $V \subseteq \Reals$ be an open set.
  We need to show that $f^{-1}(V)$ is an open set.
  Let $c$ be an arbitrary member of $f^{-1}(V)$. We need 
  to show that there exists an open interval around $c$
  that is contained by $f^{-1}(V)$.
%
  We have $f(c) \in V$. Then because $V$ is open, there exists
  $\epsilon > 0$ such that
  \begin{equation}\label{eq:i-fc-v}
  \mathcal{I}_\epsilon(f(c)) \subseteq V
  \end{equation}
  Then by the
  continuity of $f$, there is a $\delta > 0$ such that 
  \begin{equation}\label{eq:fx-iefc}
    x \in \mathcal{I}_\delta(c) \implies  f(x) \in \mathcal{I}_\epsilon(f(c))
  \end{equation}
  Now that we have an appropriate $\delta$, we need to show
  \[
  \mathcal{I}_\delta(c) \subseteq f^{-1}(V) = \{ x \mid f(x) \in V \}
  \]
  Let $x$ be an arbitrary point in $\mathcal{I}_\delta(c)$.  So by
  \eqref{eq:fx-iefc} we have $f(x) \in \mathcal{I}_\epsilon(f(c))$.  Then by
  \eqref{eq:i-fc-v} we have $f(x) \in V$, therefore $x \in f^{-1}(V)$.


\item (o-continuous $\implies$ continuous) Let $\epsilon > 0$. Observe
  that $V=\mathcal{I}_\epsilon(f(c))$ is an open set.  Then because $f$ is
  o-continuous, $f^{-1}(V)$ is an open set.  We know $c \in
  f^{-1}(V)$, so there exists a $\delta > 0$ such that
  \begin{equation}\label{eq:id-fv}
    \mathcal{I}_\delta(c) \subseteq f^{-1}(V)
  \end{equation}
  We need to show that
  \[
  x \in \mathcal{I}_\delta(c)  \implies f(x) \in V
  \]
  We assume $x \in \mathcal{I}_\delta(c)$, so also $x \in f^{-1}(V)$
  by \eqref{eq:id-fv} and therefore $f(x) \in V$.

\end{enumerate}
\end{proof}





\begin{definition}[S-Continuous]
  Suppose $f : A \to \Reals$ and $A \subseteq \Reals$.
  Let $(x_n)_{n \in \mathbb{N}}$ be a sequence in $A$.
  If $(x_n)$ converges to $c$, then $(f(x_n))$ converges to $f(c)$.
  \[
    \lim_{n\to\infty} x_n = c \implies
    \lim_{n\to\infty} f(x_n) = f(c)
  \]
\end{definition}


\paragraph{Rational (Finite) Approximations of Reals}

Next we talk about using rational intervals to approximate real
numbers. For $p,q \in \Rats$ with $p \leq q$, the pair $\langle p,q \rangle$
represents the closed interval from $p$ to $q$. Alternatively, one can
consider an interval centered at $r$ with error bound $e$, but then we
just have $p = r-e$ and $q = r+e$.  We form a partial order
$\mathcal{R}$ containing both the real numbers and the rational
intervals.
\[
   \mathcal{R} = \Reals \cup \{ \langle p,q \rangle \mid p,q \in \Rats \}
\]
Each rational interval can be viewed as a finite approximation for any
real number $x$ within the interval.
\[
  \langle p,q \rangle  \sqsubseteq x \qquad \text{iff } p \leq x \leq q
\]
An interval $\langle p_1,q_1 \rangle$ is a worse approximation than interval
$\langle p_2,q_2 \rangle$ if the first interval contains the second, i.e.
\[
  \langle p_1,q_1 \rangle \sqsubseteq \langle p_2,q_2 \rangle
  \qquad
  \text{iff }
  p_1 \leq p_2
  \text{ and }
  q_2 \leq q_1
\]
\[
\xymatrix@=15pt{
  \underset{p_1}{\bullet} \ar@{-}[rrr] & & & 
  \underset{p_2}{\bullet} \ar@{-}[rr] & & 
  \underset{q_2}{\bullet} \ar@{-}[r] & 
  \underset{q_1}{\bullet}
}
\]
The interval $\langle q,q \rangle$ is just as good an approximation of the rational
number $q$ as $q$, so we have
\[
  q \sqsubseteq \langle q,q \rangle
\]
And of course, every real $x \in \Reals$ is an equally good
approximation to itself.
\[
  x \sqsubseteq x  
\]
We write $a \sqsubset b$ if $a \sqsubseteq b$ and $a \neq b$.


The join $\sqcup$ is induced by the $\sqsubseteq$ ordering, so $a
\sqcup b$ is the least upper bound of $\{a,b\}$.  Similarly, the meet
$a \sqcap b$ is greatest lower bound of $\{a,b\}$.  For example, the
join $\sqcup$ of two intervals collects their common information, that
is, it is the intersection of the two intervals.
\[
  \langle p_1,q_1 \rangle \sqcup \langle p_2,q_2 \rangle = \langle \max(p_1, p_2), \min(q_1, q_2) \rangle
\]
Given a subset $S \subseteq \mathcal{R}$, the least upper bound of $S$
is written $\bigsqcup S$.  Some sets of rational intervals do not have
a least upper bound because they have no intersection, such as $\{
\langle 0,\frac{1}{3} \rangle, \langle \frac{2}{3},1 \rangle \}$.  A
real number can be identified by the least upper bound of an infinite
set of rational intervals.  If we have an infinite sequence of
intervals that are progressively better approximations
\[
a_1 \sqsubset a_2 \sqsubset a_3  \sqsubset \cdots
\]
then the Nested Intervals Theorem says the sequence will have a real
number as its least upper bound
\[
  \bigsqcup \{ a_1,a_2,a_3,\ldots \} \in \Reals
\]


Need to review what is a real number.
\begin{itemize}
\item Dedekind: a real number is a pair $\langle L, R \rangle$
  where $L$ and $R$ are sets of rational numbers that partition
  $\Rats$ and that for every $p \in L, q \in R$ we have $p < q$.
\end{itemize}

%% The meet $\sqcap$ of two intervals is the interval that contains both
%% of them. (Or should we add collections of intervals to $\mathcal{R}$
%% as in Vickers?)
%% \[
%%   \langle p_1,q_1 \rangle \sqcap \langle p_2,q_2 \rangle = \langle \min(p_1, p_2), \max(q_1, q_2) \rangle
%% \]
%% Given a subset $S \subseteq \mathcal{R}$, the greatest lower bound of
%% $S$ is written $\bigsqcap S$.


Now let us consider functions on real numbers, and how we might
approximate them on rationals. Suppose $f \in A \to \Reals$ and $x \in
A \subseteq \Reals$. We wish we could have the exact result $f(x)$ but
will be satisfied if we are given a rational interval $\langle p', q'
\rangle$ that contains $f(x)$ and that is small enough, i.e., $|p' -
q'| < \epsilon$ for some choice of $\epsilon$.  If $f$ is continuous,
then we know there is a $\delta$ such that
\[
  \forall y.\; |y-x| < \delta \implies |f(y) - f(x)| < \epsilon
\]
If we can find a rational number $p$ that is close enough to $x$, that
is, $|p-x| < \delta$, then we'll know that $f(p)$ is close enough to
$f(x)$, that is $|f(p) - f(x)| < \epsilon$. 

Is there a sequence of rational intervals for every real number?  If
so, then we can march through the sequence $\langle p_1,q_1 \rangle,
\langle p_2,q_2 \rangle, \ldots$ until we get to an interval $\langle
p_i,q_i \rangle$ that is small enough ($|p_i - q_i| < \delta$) and
choose the middle $m=\frac{q_i - p_i}{2}$. So we have $|m - x| <
\delta$ and therefore $|f(m) - f(x)| < \epsilon$, as desired.





%% Now let us consider the relationship between rational intervals and
%% continuous functions on the reals. Suppose $f : A \to \Reals$ with $A
%% \subseteq \Reals$. 



Hmm, how to relate the above to the following.

We lift $f$ to a function $f^\dagger : A' \to \mathcal{R}$ with $A'
\subseteq \mathcal{R}$ as follows.
\begin{align*}
  f^\dagger(a) = 
  \begin{cases}
    f(x) & \text{if } a=x \in \Reals \\
    \langle p',q' \rangle & \text{if } a = \langle p,q \rangle \text{ and }
         \forall x, p \leq x \leq q \implies p' \leq f(x) \leq q'
  \end{cases}
\end{align*}

\begin{theorem}
  If $f : A \to \Reals$ is continuous and $S \subseteq \mathcal{R}$
  with some conditions on $S$, 
  then 
  \[
  \bigsqcup \{ f^\dagger(a) \mid a \in S \} = f^\dagger\left(\bigsqcup S\right)
  \]
\end{theorem}
\begin{proof}
UNDER CONSTRUCTION
\end{proof}



\section{Topology on $\mathcal{P}(\mathbb{N})$}



\section{Scott Topology}

\begin{definition}
A set $S \subseteq P$ of a poset $P$ is Scott-open if it is upward
closed and if all directed sets $D$ with lub in $S$ have non-empty
intersection with $S$.

A partial order $P$ and all of its Scott-open subsets forms a
topological space, the Scott-topology.
\end{definition}

\section{Miscelaneous}

In a $T_0$ space on $X$ (aka. Kolmogorov space), for every pair of
points in $X$, at least one of the points is in a neighborhood that
does not contain the other point. (Wikipedia)


\end{document}