%Version of December 5, 2000

\documentclass[12pt]{article}
\usepackage{amssymb}
\date{December 5, 2000}
\title{Polish spaces, computable approximations, \\
and bitopological spaces}
\author{Krzysztof Ciesielski%
\thanks{Work partially supported by the NATO Collaborative Research Grant
CRG~950347.}\\
{\footnotesize Department of Mathematics,}
{\footnotesize West Virginia University,}\\
{\footnotesize Morgantown, WV 26506-6310, USA; }
{\footnotesize e-mail: K\_Cies@math.wvu.edu}\\
{\footnotesize web page: {\tt http://www.math.wvu.edu/homepages/kcies}}\\
Bob Flagg\\
{\footnotesize Department of Mathematics,}
{\footnotesize University of Southern Maine,}\\
{\footnotesize Portland, ME 04103, USA; }
{\footnotesize e-mail: Bob@calcworks.com}\\
Ralph Kopperman,%
\thanks{Work partially supported by CUNY-PSC Research Grant 669421.\endgraf
\hskip-10pt
AMS classification numbers: 06B35, 06F30, 54C25, 54D30, 54D80, 54E50,
54E55, 54H12.
\endgraf
\hskip-10pt
Key words and phrases: directed complete poset (dcpo),
bounded dcpo, $\omega$-continuous dcpo, maximal-point space, Scott
topology, Polish space, pairwise regular bitopological space.}\\
{\footnotesize Department of Mathematics,}
{\footnotesize City College, CUNY,}\\
{\footnotesize New York, NY 10031, USA; }
{\footnotesize e-mail: rdkcc@cunyvm.cuny.edu}
}
%Macro to include theorem labels in the margins.

\newcommand{\marginlabels}[1]{\def\margintags{#1}}
\marginlabels{n} \def\nolabels{n}
\newcommand{\Label}[1]
        {\if\margintags\nolabels
                \label{#1}
         \else
                \label{#1}\marginpar{{\tiny #1}}
        \fi}
\newcommand{\ch}[1]{\marginpar{{\tiny #1}}}
\newcommand{\chKC}[1]{\marginpar{{\tiny KC: #1}}}
\newcommand{\chrk}[1]{\marginpar{{\tiny RK: #1}}}
\newcommand{\chre}[1]{\marginpar{{\tiny Referee. #1}}}
\newcommand{\chop}[1]{\marginpar{{\tiny Optional. #1}}}
\newcommand{\suc}{{\rm succ}}
\newcommand{\ccc}{{\rm con}}
\newcommand{\supp}{{\rm supp}}
\newcommand{\nor}{{\rm norm}}
\newcommand{\norsup}{{\rm\underline{norm}}}
\newcommand{\sq}{\subseteq}
\newcommand{\real}{{\mathbb R}}
\newcommand{\R}{{\real}}
\newcommand{\rational}{{\mathbb Q}}
\newcommand{\Q}{{\rational}}
\newcommand{\integer}{{\mathbb Z}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\NN}{{\cal N}}
\newcommand{\nnn}{{\rm N}}
\newcommand{\Sg}{{\Sigma}}
\newcommand{\s}{{\sigma}}
\newcommand{\h}{{\aleph}}
\newcommand{\la}{{\langle}}
\newcommand{\ra}{{\rangle}}
\newcommand{\restr}{{\hbox{$\,|\grave{}\,$}}}
\newcommand{\srestr}{{\hbox{${\scriptstyle\,|\grave{}\,}$}}}
\newcommand{\A}{{\cal A}}
\newcommand{\M}{{\cal M}}
\newcommand{\F}{{\cal F}}
\newcommand{\G}{{\cal G}}
\newcommand{\C}{{\cal C}}
\newcommand{\B}{{\cal B}}
\newcommand{\T}{{\cal T}}
\newcommand{\D}{{\cal D}}
\newcommand{\E}{{\cal E}}
\newcommand{\K}{{\bf S}}
\newcommand{\RR}{{\cal R}}
\newcommand{\U}{{\cal U}}
\renewcommand{\-}{{\setminus}}
\newcommand{\e}{{\varepsilon}}
\newcommand{\g}{{\gamma}}
\renewcommand{\d}{{\delta}}
\renewcommand{\H}{{\cal H}}
\renewcommand{\P}{{\cal P}}
\newcommand{\const}{{\rm Const}}
\newcommand{\bor}{\mbox{${\cal B}or$}}
\def\cl{{\rm cl}}
\def\<{\ll}
\def\int{{\rm int}}
\def\diam{{\rm diam}}
\def\dist{{\rm dist}}
\def\inter{{\rm int}}
\def\bd{{\rm bd}}
\def\ord{<\hskip -4pt<}
\def\bbD{{\mathbb D}}
\def\bbU{{\mathbb U}}
\newcommand{\continuum}{{\cont}}
\def\dom{{\rm dom}}
\def\proof{\noindent {\sc Proof. }}
\def\qed{\hfill\vrule height6pt width6pt depth1pt\medskip}
\def\endproof{{\qed}}
\def\AA{{\cal A}}
\newcommand{\tr}{{\rm tr}}
\newcommand{\sru}{{\rm sru}}
\def\implies{\longrightarrow}
\newcommand{\Equi}{\mbox{$\Longleftrightarrow$}}

%% Theorems, etc.
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{Fact}[theorem]{Fact}
\newcommand{\thm}[2]{\begin{theorem}\label{#1}{\sl #2}\end{theorem}}
\newcommand{\cor}[2]{\begin{corollary}\label{#1}{\sl #2}\end{corollary}}
\newcommand{\prop}[2]{\begin{proposition}\label{#1}{\sl
#2}\end{proposition}}
\newcommand{\lem}[2]{\begin{lemma}\label{#1}{\sl #2}\end{lemma}}
\newcommand{\pr}[2]{\begin{problem}\label{#1}{\rm #2}\end{problem}}
\newcommand{\ex}[2]{\begin{example}\label{#1}{\sl #2}\end{example}}
\newcommand{\df}[2]{\begin{definition}\label{#1}{\rm #2}\end{definition}}
\newcommand{\rem}[2]{\begin{remark}\label{#1}{\rm #2}\end{remark}}
\newcommand{\fact}[2]{\begin{Fact}\label{#1}{\sl #2}\end{Fact}}
\begin{document}
\maketitle

\begin{abstract}
Answering a  question of J.~Lawson (formulated also earlier, in 1984, by
Kamimura and Tang~\cite{KT}) we show that every Polish space admits a
bounded complete computational model, as defined below. This results
from our construction, in each Polish space $\la X,\tau\ra $, of a
countable family $\C$ of non-empty closed subsets of $X$ such that:
\begin{itemize}
\item[(cp)] each subset of $\C$ with the finite intersection property has
non-empty intersection;

\item[(br)] if $x\in T$ and $T\in\tau$ then there exists $C\in\cal C$ such
that $x\in\int(C)$ and $C\subset T$, and

\item[(r*)] for every $C\in\C$ and $x\in X\setminus C$ there is a $D\in\C$
such that $C\subset\int(D)$ and $x\notin D$.
\end{itemize}
These conditions assure us that there is another compact topology $\tau\sp
*\subset\tau$ on $X$ such that the bitopological space $\la X,\tau,\tau\sp
*\ra$, is pairwise regular. The existence of such a topology is also shown
equivalent to admitting a bounded complete computational model.
\end{abstract}

%\vfill\eject

\section{Background: what is a bounded complete computational model?}

In this section we will introduce the notions coming from theoretical
computer science and necessary for understanding the main problem. These
notions are standard in domain theory, but are unknown to many
topologists. Thus, we take extra time and space to explain the motivation
behind these notions.

In the past few decades theoretical computer science has considered the
basic problem: What is the best way to approximate mathematical objects?
One of the most fundamental of such questions is about the representation
of a real number. A common theoretical approach to this problem is to
identify each real number $r$ with a collection of intervals whose
intersection is $\{r\}$. In such a representation a smaller interval gives
more information about a number than a bigger interval. So an interval $I$
carries more information than an interval $J$, which we represent by
writing $J\leq I$, provided that $J\supset I$.

An approximation of a number (some knowledge accumulated about it) is
stored in the partially ordered set $\la P_\real,\leq\ra$ whose elements
are $\real$, and all its closed bounded intervals including singletons,
and whose partial order, $\leq$, is reverse set inclusion, $\supset$. The
numbers themselves are represented by singletons, denoted here by ${\rm
Max}(P_\real)$, since they are the maximal elements of $P_\real$. Each
element of~$P_\real$ is below a maximal element.

More generally, certain partially ordered sets $\la P,\leq\ra$ each of
whose elements is below a maximal element, can be considered as models for
approximating their maximal elements. This idea has been explored by many
authors (see e.g. Scott~\cite{SC}, Edalat~\cite{Ed}, Edalat and  Heckmann
\cite{EH}, or Lawson~\cite{LA}) and led to a field known as domain
theory. An authoritative reference in this area is \cite{AJ}, which has
set much of the standard notation in the subject.

To make approximation in a model computationally feasible a poset $P$ must
have several nice properties. The most fundamental is that after we go
through all the work of approximation, we have actually approximated an
object. We see that this is embodied by the following:

\df{def1}{A poset $\la P,\leq\ra$ is {\it directed complete}\/
(abbreviated as {\em dcpo}) provided each directed subset $D$ of $P$ has
a supremum $\bigvee D$. It is {\it bounded complete}\/ (abbreviated as
{\em bcpo}) if it is a dcpo and each subset which is bounded above has a
supremum.}

The importance of the notion of dcpo is that when increasingly fine
approximations are obtained, they indeed approximate some object; for
example, this would be false if we used $P_\rational$ to try to compute
rational numbers.

For a dcpo $\la P,\leq\ra$, each $x\in P$ is below the join (i.e.,
supremum) of a maximal chain of elements $\geq x$, which is certainly an
element of ${\rm Max}(P)$.

The definition of dcpo also requires the existence of a bottom element,
$\bigvee\emptyset$, which in the case of $P_\real$ is equal to
$\real$. Certainly $P_\real$ is bounded complete with $\bigvee D=\bigcap
D$ for any directed or bounded subset of $P_\real$.

As we shall see, bounded completeness has important consequences, although
its theoretical value is less clear. Note that a dcpo in which pairs that
are bounded above have suprema, is bounded complete (since for any bounded
set, the set of suprema of its finite subsets then is directed, thus must
have a supremum and that is the supremum of the original set).

The next issue is that of ``observability;'' the idea that we should be
able to see whether $r$ is in one of its supposed approximations. For
example, if $r$ is an endpoint of the interval $I$, no magnification of
the real line would make it possible to see whether $r$ is actually in $I$
or not. Similarly, for another interval $J\in P_\real$, if either the left
endpoints of $I$ and $J$ are identical, or their right endpoints are, it
will not be possible under any magnification of the real line to see
whether one of the intervals contains the other. This problem has an
obvious answer involving topology: given two intervals $I,J$ in the poset
$\la P_\real,\supset\ra$, $J$ is observably below $I$ if $I$ is a subset
of the interior ${\rm int}(J)$ of $J$. But this can be expressed just in
terms of posets:

\df{def2}{For a dcpo and $x,y\in P$  we say that {\it $x$ is
way-below~$y$\/} (written $x\<y$) if whenever $y\leq\bigvee D$ and
$D$ is directed, then there is some $z\in D$ such that $x\leq z$.}

The compactness of the elements of $P_\real$ immediately implies that $K
\in P_\real$ is way-below $M\in P_\real$ if and only if $M\subset{\rm int}
(K)$. The reader should check that if $P$ is the collection of all compact
subsets of a locally compact topological space $X$, then $\la P\cup\{X\},
\supset\ra$ is a dcpo, and $M\subset{\rm int}(K)$ if and only if $K\<M$.

In any dcpo, the bottom element, $\bigvee\emptyset$, is way-below itself.
This is the only element of $P_\real$ that is way-below itself, and in
what follows we will be mainly concerned with posets for which $x\<x$ only
for the bottom element. However, there is much interest, both in domain
theory and in algebra, in continuous posets in which each element $x$ is
the supremum of the set $\{y\leq x\colon y\<y\}$, and this set is
directed. These are called {\em algebraic posets,} and include the
algebraic lattices (such as the collection of all ideals of a ring,
ordered by $\subset$, and many other examples). See \cite{Gand} or
\cite{AJ} for further discussion, and \cite{fk} for discussion of a
topological example of interest in domain theory (ultrametric separable
spaces).

The interpretation of the definition of continuous dcpo which follows, is
that sufficient information needed to compute any object is available in
the objects way-below it.

\df{def3}{For $A\subset P$ we define $\Uparrow A=\{x\in P\colon a\<x\
\mbox{ for some }\ a\in A\}$ and $\Downarrow A=\{x\in P\colon x\< a\
\mbox{ for some }\ a\in A\}$. For $a\in P$ the symbols $\Uparrow a$ and
$\Downarrow a$ stand for $\Uparrow\{a\}$ and $\Downarrow\{a\}$,
respectively.

A {\em continuous dcpo}\/ is a dcpo $P$ such that for every $x\in P$,
$\Downarrow x$ is directed and $x=\bigvee(\Downarrow x)$.}

Clearly for $[p,q]\in P_\real$ we have $\bigvee(\Downarrow [p,q])=\bigcap
\{[r,s]\colon r<p\leq q<s\}=[p,q]$, so $P_\real$ is a continuous dcpo.

Let us note that $\<$ satisfies a transitivity condition and it is
stronger than $\leq$:
\begin{description}
\item{(str)} if $x\< y$ then $x\leq y$;
\item{(trans)} if $w\leq x\< y\leq z$ then $w\< z$.
\end{description}
(To see the (str) condition take $D=\{y\}$ in the definition of $\<$.)

The properties (str) and (trans) immediately imply that $\Downarrow
(\Downarrow x)\subset\Downarrow x$. The reverse inclusion is not
automatic, however it holds for continuous dcpo's.

\fact{fact1}{If $P$ is a continuous dcpo then $\Downarrow(\Downarrow
x)=\Downarrow x$ for every $x\in P$.}

\proof We need only show that $\Downarrow x\subset\Downarrow(\Downarrow
x)$. So, first note that
\begin{center}
$\Downarrow(\Downarrow x)$ is directed.
\end{center}
Indeed, if $y\<y'\<x$ and $z\<z'\<x$ then, since $\Downarrow x$ is
directed, we can find a $w\in\Downarrow x$ such that $y',z'\leq w$. Thus,
by (trans), $y,z\< w$. Since $\Downarrow w$ is directed, we can find a
$v\< w$ for which $y,z\leq v$. But $v\in\Downarrow(\Downarrow x)$. So
$\Downarrow(\Downarrow x)$ is directed.

Next note that if $y\in\Downarrow x$ then $\Downarrow y\subset\Downarrow
(\Downarrow x)$, so $y=\bigvee\Downarrow y\leq\bigvee\Downarrow(\Downarrow
x)$. Thus $x=\bigvee\Downarrow x\leq\bigvee\Downarrow(\Downarrow x)$, so
by definition of $\<$, if $y\in\Downarrow x$ (i.e., $y\<x$), then $y\leq w$
for some $w\in\Downarrow(\Downarrow x)$, and so $y\in\Downarrow(\Downarrow
x)$.\qed

We restate the conclusion of Fact~\ref{fact1} in a form in which we will
use it:
\begin{description}
\item{(interpolation)} if $x\<y$ then there exists a $z\in P$ such that
$x\<z\<y$.
\end{description}

In the case of $P_\real$ the interpolation property is obvious. Later we
will consider similarly-defined posets for more general topological
spaces, and the interpolation property for these will follow from the
normality of the topology.

Finally, computation requires the existence in $P$ of a nice countable
subset $B$ (called a basis) whose elements may be used to recursively
approximate maximal elements of $P$. The full information on a maximal
element $x$ of $P$ can be represented as the filter $\F_x$ of all elements
in $B$ which are above $x$. However, we should imagine that at any
particular moment of approximating $x$ we have access only to the elements
of $\F_x$ but not to the entire $\F_x$. (The situation is quite similar to
that in forcing -- a generic number is represented by a generic filter
$\F$, but in the ground model we have access only to elements of $\F$, but
not the entire $\F$.)

\df{def4}{Following \cite[page~168]{Gand} we say that a subset $D$ of a
dcpo $P$ is a {\em basis}\/ for $P$ provided for every $x\<y$ from
$P$ there exists a $d$ in $D$ such that $x\leq d\<y$. A poset $P$ is {\em
$\omega$-continuous}\/ provided it is a continuous dcpo and has a
countable basis.}
Notice that if $D$ is a basis for a dcpo $P$ then
\begin{center}
$x=\bigvee(D\cap\Downarrow x)$ for every $x\in P$.
\end{center}
It is also easy to see that if $P$ has the interpolation property then $D$
is a basis for $P$ if and only if $D$ is $\<$-dense in $P$ in the sense
that
\begin{center}
if $x\<y$ then there exists a $d\in D$ such that $x\<d\<y$.
\end{center}
Clearly the family of all intervals with rational endpoints form a
countable $\<$-dense subset of $P_\real$.

Note, that the property $x=\bigvee(D\cap\Downarrow x)$ means that $x$ is
uniquely determined by $F(x)=D\cap\Downarrow x$ which is a filter in $D$.
This means that the ``learning process'' about the object $x\in{\rm Max}
(P)$ can be done by coding the incoming information using the elements
from the countable set $D$. In fact, we do not need to know the entire
structure of $P$ to recover the elements of ${\rm Max}(P)$; we just need
to know the full order structure of the set $D$. Moreover, notice that our
knowledge about $x$ is ``continuously approaching'' full information,
since $x$ is a limit of $D\cap\Downarrow x$. Thus, the bounded $\omega
$-continuous dcpo's (or, more precisely, their $\<$-dense subsets)
are a tool to recover the information on the structure of ${\rm Max}(P)$.
That is, the knowledge gathered in an $\omega$-continuous poset allows us
to reconstruct the set ${\rm Max}(P)$.

Confronted with the situation described above to compute real numbers, it
is natural to ask when we can find a similar model for a topological
space~$X$: an $\omega$-continuous poset $\la P,\leq\ra$ which approximates
the elements of $X$. Can the structure on $P$ also encode the topological
structure on $X$?

The topological spaces for which such a bounded $\omega$-continuous dcpo
can be found were studied by Lawson in \cite{LA}, where he calls such
spaces maximal point spaces. To define the notion of a maximal point space
precisely we need to recall that each poset $P$ can be equipped with the
information-motivated {\em Scott topology $\sigma$}; certainly, it is
natural to think of a set, $C$, as ``knowledge-closed" (= Scott-closed)
if, whenever $x\leq y\in C$, then $x\in C$, and whenever $D\subset C$ is
directed, then its supremum $\bigvee D\in C$. Of course, then a set $T$ is
Scott-open if, as the complement of a Scott-closed set, whenever $y\geq
x\in T$, then $y\in T$, and whenever $D$ is directed and $\bigvee D\in T$,
then $D$ meets $T$. For a poset with the interpolation property, it is
easy to check that the collection of sets $\Uparrow x$ with $x\in P$, is a
base for the topology $\sigma$.

\df{def5}{A topological space $\la X,\tau\ra$ is a {\em maximal point
space}\/ provided there exists an $\omega$-continuous dcpo $P$ and a
bijection $i\colon X\to{\rm Max}(P)$ such that \begin{itemize}
\item[(i)] $i$ is a homeomorphism between $\la X,\tau\ra$ and ${\rm
Max}(P)$ considered with a subspace topology of $\la P,\sigma\ra$;
\item[(ii)] for every $x\in P$ the set $i\sp{-1}(\{y\in{\rm Max}(P) \colon
x\leq y\})$ is $\tau$-closed.
\end{itemize}
Such a poset $P$ is a {\em computational model}\/ for $X$,
and if the poset $P$ is bounded complete, then $P$ is a {\em bounded
complete computational model}\/ for $X$.}

It is easy to see that for each locally compact space $X$ the poset $P$
formed with $X$ and all compact subsets of $X$, and ordered by the reverse
inclusion, is a bcpo. If further, $X$ is a separable locally compact
metrizable space, then $P$ is a bounded complete computational model for
$X$.

Lawson~\cite{LA} shows that a topological space is a maximal point space
if and only if it is a Polish space. Also, using ``formal balls,'' Edalat
and Heckmann \cite{EH} provide a simple explicit construction of a maximal
point space $P_X$ for every Polish space $X$. Lawson's characterization
and the Edalat-Heckmann construction are remarkable achievements, but they
lack some desirable properties. In particular, posets $P_X$ constructed by
them are not bounded complete. Thus, at the North Bay Summer Conference,
Jimmie Lawson asked whether every Polish space is the maximal point space
of a {\em bounded complete}\/ $\omega$-continuous poset. (The same
question was also posed earlier, in 1984, by Kamimura and Tang~\cite{KT}.)
The goal of this paper is to give an affirmative answer for this question.
It should be pointed out that the property of bounded completeness of the
representation $P_X$ of $X$ gives advantages that are not present if $P_X$
is just directed complete. For example, given a Scott continuous function
from a maximal point space $P_X$ into another, $P_Y$, its restriction to
${\rm Max}(X)$ (identified with $X$) is a continuous function from $X$
into $Y$. It is desirable (cf, Escard\'o~\cite{ES}) that every continuous
map $X\to Y$ also extends to a Scott continuous function from $P_X$ into
$P_Y$. This is the case if $P_X$ and $P_Y$ are bounded complete
computational models for $X$ and $Y$, respectively.\footnote{To see this
it is enough to notice that ${\rm Max}(P_X)$ is dense in the Scott
topology and every continuous function defined on a dense subset of a
bounded complete $\omega$-continuous poset $P$ (considered with the Scott
topology $\sigma$) can be extended continuously to $P$ \cite[Exercise
II, 3.19]{Gand}.}

%\vfill\eject
\section{Topological reduction of the problem}

The motivation for the definitions stated above came from a situation,
which we now describe in the language of general Hausdorff topological
spaces $\la X,\tau\ra$. We considered a family $P_X$ of non-empty closed
subsets of $X$ whose interiors formed a base for $X$. We ordered $P_X$ by
reverse inclusion, introduced in $P_X$ a way-below relation $\<$, and
noted that in our particular case $K\<M$ was equivalent to $M\subset{\rm
int}(K)$. Then we found a $\<$-dense subfamily $D$ of $P_X$ and identified
each $x\in X$ with the filter $F(x)=D\cap\Downarrow x$. In the case we
considered, the interiors of sets from $D$ also formed a base for sets
from $D$, so for each $K\in D$ we could also define the following filter
in $\la D,\supset\ra$
\[
j(M)=D\cap\Downarrow M=\{K\in D\colon K\< M\}
\]
and note that $j(M)$ still uniquely determines $M$, since $M=\bigcap
j(M)$. Now, let $P_X\sp*(D)$ (we will write only $P_X\sp*$ where $D$ is
clear from the context) be the family of all filters $\F$ in $\la D,
\supset\ra$ with the property that
\begin{equation}\label{con:filters}
\mbox{for every $F\in\F$ there exists a $K\in\F$ such that $K\subset\int
(F)$.}\footnote{For $D=\P(X)$ filters satisfying (\ref{con:filters}) are
sometimes called {\em round filters}\/ (in a topological space
$X$).}
\end{equation}
$P_X\sp *$ is ordered by the inclusion $\subset$.

It is not difficult to see that if $X$ is locally compact and $P_X$ is the
family of all compact sets, then $P_X\sp *$ is a bounded complete
computational model for $X$ with $j$ (restricted to singletons) being a
homeomorphism witnessing it. The main reason for this is that in this
particular situation the mapping $k\colon P_X\sp*\to P_X$, given by $k(F)=
\bigcap F$, is an order isomorphism between $P_X\sp*$ and $P_X$. If $X$ is
a Polish space which is not locally compact the mapping $k$ will need not
even be one-to-one. The next theorem gives (implicitly) the properties of
the families $P_X$ and $D$ (denoted there by $\Gamma$) which imply that
$P_X\sp*$ is a bounded complete computational model for $X$.

Of course, each family $D$ generates a smallest topology $\tau\sp*$ on $X$
such that all sets in $D$ are closed. Since sets in $D$ are closed in
$\tau$, we have $\tau\sp*\subset\tau$. Note that even in the case of
$P_\real,\ \tau\sp*$ was strictly smaller than $\tau$. So our notion of
bounded complete computational model carries the bitopological structure
$\la X,\tau,\tau\sp*\ra$. In our next theorem we will show that such a
structure is not just a convenience --- a bitopological structure is
always associated with a computational model.

In what follows we will need the following definition (see~\cite{AD}):

\df{def8}{Given a property $Q$, a bitopological space $\la X,\tau,\tau\sp
*\ra$ is {\it pairwise $Q$\/} if both it and its {\it bitopological dual},
$\la X,\tau\sp*,\tau\ra$ are $Q$.

Let $\la X,\tau,\tau\sp *\ra$ be a bitopological space. We say it is {\it
regular}\/ provided that for each $x\in U\in\tau$ there is a $V\in\tau$
such that $x\in V$ and $\cl_{\tau\sp*}(V)\subset U$.

It is {\em normal}\/ provided for every pair of disjoint sets:
$\tau$-closed $E$ and $\tau\sp*$-closed $F\sp *$, there exist disjoint
sets $U\sp *\in\tau\sp *$ and $V\in\tau$ such that $E\subset U\sp *$ and
$F\sp *\subset V$.}

In fact, if $\la X,\tau,\tau\sp *\ra$ is normal, then notice that it is
pairwise normal. Below, we use the terminology ``pairwise normal" for this
situation, and ``normal" only for topological spaces.

In what follows we will need the following fact.

\fact{fact:Norm}{If a bitopological space $\la X,\tau,\tau\sp *\ra$ is
pairwise regular and $X$ considered with the join topology $\tau\vee\tau
\sp*$ is Lindel\"of then $\la X,\tau,\tau\sp *\ra$ is pairwise normal.}

\proof This can be shown by a small adjustment of the usual proof that a
regular Lindel\"of space is normal:

Take disjoint sets $E$ and $F\sp *$ such that $E$ is $\tau$-closed and
$F\sp *$ is $\tau\sp *$-closed. By pairwise regularity, and since
$E$ and $F\sp*$ are $\tau\vee\tau\sp*$-closed, we can find a family
$\C_{F\sp *}=\{C_i\colon i<\omega\}$ of $\tau\sp *$-closed sets such that
\[ E\subset \bigcup_{i<\omega}(X\setminus C_i)\ \ \&\ \ F\sp *\subset
\bigcap_{i<\omega}\int_\tau(C_i) \]
and a family $\B_E=\{B_i\colon i<\omega\}$ of $\tau$-closed sets such that
\[ F\sp *\subset \bigcup_{i<\omega}(X\setminus B_i)\ \ \&\ \
E\subset \bigcap_{i<\omega}\int_{\tau\sp *}(B_i). \]
Now, define the sets $U\sp *\in\tau\sp *$ and $V\in\tau$ as in the
standard proof that every Lindel\"of space is normal:
\[ U\sp *=\bigcup_{n<\omega}\left(\int_{\tau\sp *}(B_n)\setminus\bigcap_
{i\leq n}C_i\right)\in\tau\sp *\ \ \ \&\ \ \ V=\bigcup_{n<\omega}\left(
\int_{\tau}(C_n)\setminus\bigcap_{i\leq n}B_i\right)\in\tau.\]
But then $U\sp*\supset E$ and $V\supset F\sp*$ are disjoint.
So, $\la X,\tau,\tau\sp *\ra$ is pairwise normal. \qed

\thm{thChar}{The following are equivalent for a topological space $\la
X,\tau\ra$.
\begin{itemize}
\item[(1)] $X$ has a bounded complete computational model.

\item[(2)] There is a countable family $\C$ of nonempty
$\tau$-closed subsets of $X$ such that:
\begin{itemize}
\item[(cp)] each subset of $\cal C$ with the finite intersection property
                has nonempty intersection,
\item[(br)] if $x\in T$ and $T\in\tau$ then there exists $C\in\cal C$ such
                 that $x\in\int(C)$ and $C\subset T$, and
\item[(r*)] if $x\in X\setminus C$ for some $C\in\C$ then there exists a
                  $D\in\C$ such that $x\not\in D$ and $C\subset\int(D)$.
\end{itemize}

\item[(3)] $\la X,\tau\ra$ is second countable and $T_1$, and there
is a compact topology $\tau\sp*\subset\tau$ on $X$ such that $\la
X,\tau,\tau\sp *\ra$ is pairwise regular.
\end{itemize}}

\proof (3)$\Rightarrow$(2): By the regularity of $\la X,\tau\sp*,\tau\ra$,
for every $\tau\sp*$-closed set $F$ and $x\in X\-F$ there exists a $\tau
\sp*$-open set $T_x$ such that $x\in T_x$ and $\cl_\tau T_x
\subset X\-F$. Since $\tau=\tau\vee\tau\sp*$ is second countable, so is
its restriction to the subspace $X\-F$; thus this restriction is
Lindel\"of. In particular, there exists a countable subfamily of $\{T_x
\colon x\in X\setminus F\}$ which covers $X\setminus F$. Let $\C_F$ be the
set of complements of elements of this countable family. Then $\C_F$ is
countable and
\begin{equation}\label{eq32}F\subset\int(C) \ \mbox{ for every } C\in\C_F
\ \ \&\ \ F=\bigcap\C_F.\end{equation}

Let $\B$ be a countable base for $\la X,\tau\ra$ and $\C_0=\{\cl_{\tau\sp
*}(B)\colon B\in\B\}$. Define a sequence $\la \C_n\colon n<\omega\ra$ by
putting \[ \C_{n+1}=\C_n\cup\bigcup_{F\in\C_n}\C_F\] for every $n<\omega$.
Then each $\C_n$ is a countable family of $\tau\sp *$-closed sets.
Thus $\C=\bigcup_{n<\omega}\C_n$ is also a countable family of $\tau\sp
*$-closed sets and it is easy to see that $\C$ is as required.

\medskip To show $(2)\Rightarrow(1)$ first note that, by (br),
$\tau$-interiors of the sets from $\C$ form a base for $\tau$. Thus $\la
X,\tau\ra$ is second countable. Next, let $\tau\sp *$ be the topology
generated by the complements of sets from $\C$. Then condition (cp)
implies that $\la X,\tau\sp *\ra$ is compact.

Note also that (br) implies also that $\la X,\tau,\tau\sp*\ra$ is regular,
while the regularity of $\la X,\tau\sp*,\tau\ra$ follows from (r*). Thus
$\la X,\tau,\tau\sp*\ra$ is pairwise regular. Moreover, $\tau\vee\tau\sp*
=\tau$ is Lindel\"of (as second countable) so, by Fact~\ref{fact:Norm},
$\la X,\tau,\tau\sp*\ra$ is pairwise normal. Thus, for every pair $\la
A,B\ra$ of subsets of $X$ where $A$ is $\tau\sp*$-closed and $A\subset\int
_\tau(B)$ there exists a $\tau\sp*$-closed set $c(A,B)$ such that
$A\subset\int(c(A,B))$ and $c(A,B)\subset\int(B)$.

Let $\Gamma$ be the closure of $\C$ under the binary operations of
union $\cup$, intersection $\cap$, and $c$ defined above. More directly,
we put $\Gamma_0=\C\cup\{X\}$, for each $k\in\omega$ let
\[
\Gamma_{k+1}=\bigcup\{\{c(A,B),B\cup C,B\cap C\} \colon A,B,C\in\Gamma_k\
\&\ B\cap C\not=\emptyset \ \&\ A \subset\int(B)\}
\]
and define $\Gamma$ as $\bigcup_{k\in\omega}\Gamma_k$. Then $\Gamma$ is a
countable family of $\tau\sp*$-closed sets which satisfies conditions
(br), (r*), and (cp), while it is closed under finite intersections,
finite unions, and the operation $c$.

Let $P_X\sp *=P_X\sp *(\Gamma)$ be defined as in (\ref{con:filters}) near
the beginning of this section. We will show that $P_X\sp *$ is a
bounded complete computational model for $X$.\footnote{This construction
is closely related to that of rounded ideal completion, which is discussed
in some detail in \cite{AJ}.} \smallskip

First note that for every $A\in\Gamma$ the filter $j(A)=\{B\in\Gamma\colon
A\subset\int_\tau(B)\}$ belongs to $P_X\sp *$, since $\Gamma$ is closed
under the operation $c$.

It should also be clear that if $\K\subset P_X\sp*$ is directed then
$\bigcup\K$ is a filter, in which case $\bigcup\K=\bigvee\K\in
P_X \sp *$. In particular, $P_X\sp *$ is a dcpo. It is also bounded
complete: if $\K\subset P_X\sp*$ is bounded by an $\F\in P_X\sp*$, then
$u(\K)=\left \{\bigcup F\colon F \mbox{ a finite subset of
}\bigcup\K\right\}$ is a directed subset of $\F$, so $\bigvee\K=\bigcup
u(\K)\in P_X\sp*$.

Next note that for every $\E,\F\in P_X\sp *$
\begin{equation}\label{eq:way}
\E\<\F\  \ \Equi\ \ (\exists F\in\F)\ \E\subset j(F).
\end{equation}
To see this first assume that there exists an $F\in\F$ such that
$\E\subset j(F)$ and let $\K\subset P_X\sp *$ be a directed set with
$\F\subset\bigvee\K=\bigcup\K$. Then there exists an $\F_0\in\K$ with
$F\in\F_0$. So, $\E\subset j(F)\subset\F_0$.

To see the other implication assume that $\E\<\F$ and consider the family
$\K=\{j(F)\colon F\in\F\}$. Clearly $\K$ is directed and, by
(\ref{con:filters}), $\F=\bigcup\K=\bigvee\K$.

With (\ref{eq:way}) in hand it is clear that $P_X\sp *$ is a continuous
dcpo: if $\F\in P_X\sp *$ then $\Downarrow\F=\{\E\in P_X\sp *\colon
(\exists F\in\F)\ \E\subset j(F)\}$ and so, by (\ref{con:filters}),
$\F=\bigcup\Downarrow\F$.

The above shows also immediately that the family $\D=\{j(A)\colon A\in
\Gamma\}$ forms a basis for $P_X\sp *$. Thus, $P_X\sp *$ is a bounded
complete $\omega$-continuous dcpo. To finish the proof it is enough to
show that $P_X\sp *$ is a complete computational model for $X$.
\medskip

We do this by showing that a homeomorphism
$i\colon X\to{\rm Max}(P_X\sp *)$ can be defined by $i(x)=j(\{x\})$.

To see the maximality of each $i(x)$, let $i(x)\subset{\cal F}\in P_X\sp*$
and, by way of contradiction, assume that there is an $A\in{\cal F}
\setminus i(x)$. Then there is a $D\in{\cal F}\cap\Gamma$ such that
$D\subset{\rm int}(A)$; if $D\in i(x)$ then $A\in i(x)$, contradicting our
assumption. Thus $x\not\in D$, and so by (br), there is a $C\in\Gamma$ so
that $x\in\int(C)\subset C\subset X\setminus D$, so $X\setminus D\in i(x)
\subset\cal F$, a contradiction to $D\in\cal F$. Thus $i(x)$ is maximal.

Since $\la X,\tau\ra$ is $T_1$, $\{x\}=\bigcap i(x)$, so $i$ is
one-to-one. To see that so $i$ is onto ${\rm Max}(P_X\sp*)$ take an $\F
\in{\rm Max}(P_X\sp*)$. The compactness of $\tau\sp*$\ guarantees
that $\bigcap\cal F\neq\emptyset$. If $x\in\bigcap\cal F$ and ${\cal
F}\neq i(x)$, then $\cal F$ is a proper subset of $i(x)$, contradicting
the maximality of $\F$. Thus ${\cal F}=i(x)$, so $i$ is onto.

To see that $i$ is a homeomorphism we need to show that the sets
\[
U(\F)=\{x\in X\colon j(\{x\})\in\Uparrow\F\}
=\{x\in X\colon \F\< j(\{x\})\}
\]
with $\F\in P_X\sp *$ form a base for $\tau$. But, by (\ref{eq:way}),
\[ U(\F)=\{x\in X\colon \exists D_x\in j(\{x\}),\ \F\subset j(D_x)\}.
\]
Thus the $U(\F)$ are open: for note that if $x\in U(\F)$ then $x\in
\int_\tau(D_x)\subset U(\F)$. On the other hand, by (br), for every $W\in
\tau$ and $x\in W$ there exists a $D\in\Gamma$ with $x\in\int_\tau(D)
\subset W$ and it is easy to see that $x\in U(j(D))\subset\int_\tau(D)
\subset W$. Thus, $i$ is a homeomorphism.

Finally we need to show that for every $\F\in P_X\sp *$ the set
\[ K(\F)=i\sp {-1}(\{\E\in {\rm Max}(P_X\sp *)\colon \F\subset \E\})
=\{x\in X\colon \F\subset j(\{x\})\} \]
is $\tau$-closed. For this it is enough to prove that
\[ K(\F)=\bigcap\F. \]
But if $x\in K(\F)$ and $F\in\F$ then $F\in j(\{x\})$ implying that
$x\in \int_\tau(F)\subset F$. So, $K(\F)\subset\bigcap\F$.

Conversely, assume that $x\in\bigcap\F$ and let $F\in\F$. Then, by
(\ref{con:filters}), there exists an $E\in\F$ with $E\subset\int_\tau(F)$.
Since $x\in\bigcap\F\subset E$ we conclude that $F\in j(\{x\})$.
\medskip

(1)$\Rightarrow$(3): Assume $\la P,\leq\ra$ is a bounded complete
computational model for $\la X,\tau\ra$ as in Definition~\ref{def5}. We
will identify $\la{\rm Max}(P),\sigma\ra$, with $\la X,\tau\ra$, since
they are homeomorphic. Let $D$ be a countable $\<$-dense subset of $P$.
Then, for every $p\in P$, by interpolation:
\[ (\Uparrow p)\cap{\rm Max}(P)=
\bigcup\{(\Uparrow q)\cap{\rm Max}(P)\colon p\< q\ \&\ q\in D\}. \]
The sets $(\Uparrow q)\cap{\rm Max}(P)$, $q\in D$, form a countable base
for $\la{\rm Max}(P),\sigma\ra$. So, $\la X,\tau\ra$ is second countable.

To see that $\la X,\tau\ra$ is $T_1$ take an $x\in{\rm Max}(P)$ and recall
that by the continuity of $P$ we have $x=\bigvee(\Downarrow x)$, so that
\[ \{x\}=\bigcap_{z{<\hskip-6pt\prec}x}
\{y\in{\rm Max}(P)\colon z\leq y\}. \]
Since the sets $\{y\in{\rm Max}(P)\colon z\leq y\}$ are $\tau$-closed,
$\la X,\tau\ra$ is $T_1$.

Now, let $\C$ be the family of all sets $C_d=\{y\in{\rm Max}(P)\colon
d\leq y\}$ with $d\in D$ and let $\tau\sp *$ be the smallest topology for
which all sets from $\C$ are closed. Thus, $\la X,\tau\sp *\ra$ is second
countable, since it is generated by the countable subbase $\B=\{X\setminus
C\colon C\in\C\}$. Since $\B\subset\tau$, we also have $\tau\sp*\subset
\tau$.

Next we will show that $\la X,\tau\sp *\ra$ is compact. For this first
note that \begin{center}
the family $\C$ satisfies the condition (cp).
\end{center}
Indeed, if $D_0\subset D$ is such that $\C_0=\{C_d\colon d\in D_0\}$ has
the finite intersection property then the set $D_0$ is directed: for
if $D_1$ is a finite subset of $D_0$ and $x\in\bigcap_{d\in D_1}C_d$
then $\{x\}$ is an upper bound of $D_1$. Since $P$ is a dcpo, the
supremum $\bigvee D_0$ is well defined. Now, let $\{x\}\in{\rm Max}(P)$ be
such that $\bigvee D_0\leq\{x\}$. Then $x\in\bigcap\C_0$. Now, the
Alexander subbasis theorem implies that $\la X,\tau\sp *\ra$ is compact.

To see that $\la X,\tau,\tau\sp *\ra$ is regular, take $x\in U\in\tau$.
Clearly, we can assume that $U\sp*$ is a basic open set, say $U=(\Uparrow
p)\cap{\rm Max}(P)$. Therefore  $p\<x$ and we can find a $d\in D$
with $p\<d\<x$. Then $V=(\Uparrow d)\cap{\rm Max}(P)$ is as desired, since
$x\in V$ and $\cl_{\tau\sp *}(V) \subset C_d\subset U$.

For the regularity of $\la X,\tau\sp*,\tau\ra$, take $x\in U\sp*\in\tau\sp
*$. We need to find a $V\sp *\in \tau\sp *$ for which $x\in V\sp *$ and
$\cl_{\tau}(V\sp *)\subset U\sp *$. Clearly it will do to prove this for
every $U\sp *$ from the subbase $\B$. So, assume that $U\sp *=X\setminus
C_d$ for some $d\in D$. Thus $x\notin C_d$. Since $d=\bigvee(\Downarrow
d)$ we have  that
\[
C_d=\bigcap_{z{<\hskip-6pt\prec}d}
\{y\in{\rm Max}(P)\colon z\leq y\}.
\]
Thus, there is $z\<d$ such that $x\notin\{y\in{\rm Max}(P)\colon z\leq y\}$.
Take $d_0,d_1\in D$ such that $z\<d_0\<d_1\<d$. Then we have $C_d\subset
(\Uparrow d_1)\cap{\rm Max}(P)\in\tau$ and $x\in X\setminus C_{d_0}\in\tau
\sp *$. So, $V\sp *=X\setminus C_{d_0}$ is as desired. \qed

%\section{The main proof}
\section{Construction of the other topology}

By Theorem \ref{thChar}, in order to learn whether each Polish space has a
bounded complete computational model we must determine whether or not it
has a countable family $\C$ of $\tau$-closed subsets satisfying (cp), (br)
and (r*). Indeed, it does:

\thm{thMain}{Every Polish space $\la X,\tau\ra$ has a bounded complete
computational model.}

\proof It is enough to show that for every Polish space $X$ there exists a
countable collection $\C$ of closed sets satisfying conditions (cp), (br),
and (r*) from Theorem~\ref{thChar}(2).

The set theoretic and topological terminology and notation used are
standard and follow~\cite{CiBook} and~\cite{En}, respectively. For a
subset $K$ of a metric space $\la M,d\ra$ and a number $r>0$, the symbol
$B_r(K)$ will denote the open ball centered in $K$ with radius $r$, that
is, $B_r(K)=\{x\in M\colon d(x,K)<r\}$. For $x\in M$ we will write
$B_r(x)$ for $B_r(\{x\})$.

Since $X$ is Polish, there exists a compact metrizable space $\la M,\tau_
d\ra$ with metric $d$ such that $X$ is a dense $G_\delta$-subspace of $M$.
Thus there are dense open subsets $W_0\supset W_1\supset W_2\supset
\cdots$ of $M$ such that $X=\bigcap_{n<\omega}W_n$. For every $i<\omega$
let $\B_i$ be a finite cover of $M$ by open balls of diameter $\leq 2\sp
{-i}$ and let $\{B_n\colon n<\omega\}$ be an enumeration of $\B=\bigcup_
{i<\omega}\B_i$. Note that $\B$ is a base for $M$ and that the sequence
$\la\diam(B_n) \colon n<\omega\ra$ of diameters of $B_n$'s converges to
$0$. In addition for every $n,i<\omega$ define the sets \[K_n\sp i=\{x\in
M\colon B_{2\sp{-i}}(x)\subset B_n\cap W_n\}=\{x\in M\colon d(x,M
\setminus(B_n\cap W_n))\geq 2\sp{-i}\}.\]
Then
\begin{equation}\label{eq0}
\mbox{each }\ K_n\sp i\mbox{ is closed, }\ \
K_n\sp i\subset\int(K_n\sp {i+1}),\ \ \mbox{ and }\ \ \bigcup_{i<\omega}
K_n\sp i=B_n\cap W_n.
\end{equation}

To begin constructing our family $\C$ we need the following notions. Let

\[
S=\left\{s\in\bigcup_{n=1}\sp \infty\Z\sp n\colon s(0)\geq0>s(i) \ \mbox{
for
every }i>0\right\}.
\]
Thus, $S$ is the set of finite nonempty sequences of integers, whose first
entry is nonnegative and others are negative. Then $S$ is
totally ordered by the lexicographic order $\preceq$. For future use note
that for any $s,t\in S$ if $s\subset t$ (i.e., $t$ is an extension of $s$)
then $s \preceq t$; also let $\prec$ denote the strict order defined by:
$s\prec t$ when $s\preceq t$ and $s\neq t$. We sometimes denote such
sequences as $\la i_0,\ldots,i_{n-1}\ra$ (simply $\la i\ra$ if in
$\omega\sp 1$); if $s= \la i_0,\ldots,i_{n-1}\ra\in S$ and $0>i\in\Z$ then
$s\hat{\ }i$ denotes $\la i_0,\ldots,i_{n-1},i\ra$.

Of course, if for $0<n<\omega$ we set

\[ S_n=\bigcup_{k=0}\sp {n-1}\left(\{0,\ldots,n-1\}\times\{-(n-1),
\ldots,-1\}\sp k\right)=S\cap(-n,n)\sp {\leq n},\]
then $S=\bigcup_{n=1}\sp \infty S_n$. Below, we inductively define finite
collections $\F_n$, indexed by $\{0,\ldots,n-1\}\times S_n$:
$\F_n=\{C_k\sp s\colon s\in S_n,k< n\}$, and consisting of closed sets.
The sequence $\la\F_n\colon n<\omega\ra$ is to satisfy six properties.
Here are the first three, which are used to show (br) and (r*).
\begin{description}
\item{(i)} $K_n\sp i\subset C_n\sp {\la i\ra}\subset\int(K_n\sp
{i+1})$ for $s=\la i\ra\in S$.
\item{(ii)} If $s\in S$ and $0>i\in\Z$, then $C_n\sp {s\hat{\ }i}\subset
B_{2\sp {i}}(C_n\sp s)$.
\item{(iii)} For $s,t\in S$ if $s\prec t$ then $C_n\sp
s\subset\int(C_n\sp t)$.
\end{description}
With all the $\F_n$'s (so $\bigcup_{n<\omega}\F_n=\{C_n\sp s\colon s\in S\
\&\ n<\omega\}$) constructed, we define $\C_n=\{C_n\sp s\colon s\in S\}$,
$\hat\C=\bigcup_{n<\omega}\C_n$, and $\C=\{C\cap X\colon C\in\hat\C\}$.
Then we have the following:

\lem{lem4}{If $\C$ is defined as above and the conditions (i)--(iii) hold
then $\C$ satisfies (br) and (r*).}
\proof For (br) first notice that, by (i) and (iii), $K_n\sp i\subset
C_n\sp {\la i\ra}$ and $C_n\sp s\subset C_n\sp {\la s(0)+1\ra}\subset
\int\left(K_n\sp {s(0)+1}\right)$ for every $s\in S$ and $n,i<\omega$. So,
by (\ref{eq0}),
\begin{equation}\label{conL1}\bigcup\{\int(C)\colon C\in\C_n\}=\bigcup\C_n
=B_n\cap W_n\end{equation}
for each $n<\omega$. If $x\in T$ and $T$ is an open subset of $X$, then
let $U$ be an open subset of $M$ for which $T=U\cap X$. Since the $B_i$'s
form a base for $M$, there exists an $n<\omega$ such that $x\in B_n\subset
U$. So $x\in B_n\cap W_n\subset U\cap W_n$. Thus, by (\ref{conL1}), there
is a $C\in\C_n\subset\hat\C$ for which $x\in\int(C)\subset C\subset
B_n\cap W_n\subset U\cap W_n$. In particular, $x\in\int_X (C\cap X)$ and
$C\cap X\subset U\cap X=T$, i.e., $C\cap X\in\C$ satisfies (br).

To see (r*), if $x\in X\setminus C$ for some $C=C_n\sp s\in \hat\C$, there
is some negative integer $i$ such that $B_{2\sp {i}}(x)\subset X\-C$, so
$x\not\in B_{2\sp {i}}(C)$. By (ii) and (iii), $D=C_n\sp {s\hat{\ }i}$
satisfies (r*).\qed

To state properties (iv)--(vi), which are used to show (cp), we need a
definition. Recall that a closed set $C$ is regular closed if $C=\cl(\int
(C))$. We will say that the family $\F$ of subsets of $M$ is {\em
meet-regular\/} provided $\bigcap\G$ is regular closed for every finite
subfamily $\G$ of $\F$. Moreover for each $n<\omega$ we will choose
$\e_n>0$ and make sure that in addition to (i)-(iii), the following
conditions are satisfied.
\begin{description}
\item{(iv)}  $\F_n$ is meet-regular.
\item{(v)} For every $\G\subset\F_n$ if $\bigcap\G=\emptyset$ then
$\bigcap_{C\in\G}B_{\e_n}(C)=\emptyset$.
\item{(vi)} If $k<n$, $t\in S_{n+1}$, and $s$ is the largest element of
$S_n$ with $s\prec t$ then $B_{\e_{n+1}}(C\sp t_k)\subset B_{\e_n}(C\sp
s_k)$.
\end{description}

Before we describe the details of the construction we show (cp):

\lem{lem5}{If $\C$ is defined as above and the conditions (i)--(vi) hold,
then $\C$ satisfies (cp).}
\proof Let $\hat\D\subset\hat\C$ be such that $\D=\{C\cap X\colon C\in\hat
\D\}$ has the finite intersection property. We have to
show that $\bigcap\D\neq\emptyset$. Consider the set $\Gamma=\{n<\omega
\colon\D\cap\C_n\neq\emptyset\}$. We will consider two cases:
\medskip

\noindent {\bf Case 1:} $\Gamma$ is infinite. Clearly $\bigcap\hat\D\neq
\emptyset$, since $M$ is compact. Since (\ref{conL1}) holds, $\bigcap\hat
\D\subset B_n$ for every $n\in\Gamma$ and the diameters of $B_n$'s tend
to $0$, so we conclude that $\bigcap\hat\D$ is a singleton,
say $\bigcap\hat\D=\{x\}$. If $x\in X$ then $\bigcap\D=\{x\}\neq\emptyset
$. So, by way of contradiction assume that $x\in M\setminus X$. Choose an
$n\in\Gamma$ such that $x\in M\setminus W_n$ and let $C\in\D\cap\C_n$.
Then $\bigcap\hat\D \subset C\subset W_n$ and so, $\bigcap\hat\D=\bigcap
\hat\D\cap W_n=\{x\} \cap W_n=\emptyset$, a contradiction.
\medskip

\noindent {\bf Case 2:} $\Gamma$ is finite. Let $n<\omega$ be such that
for every $k\in\Gamma$, $k<n$ and there exists a $t\in S_n$ so that $C_k
\sp t\in\hat\D$. For $k\in\Gamma$ let $s_k\in S_n$ be a $\prec$-maximal
element of $S_n$ such that $s_k\preceq t$ for each $t\in S$ with $C_k\sp
t\in\hat\D$ (there is such an element since $0<n$, so $S_n$ is a nonempty,
finite set ordered by $\preceq$ and $\la0\ra\in S_n$ is the $\prec$-least
element of $S$). Thus, if $\tilde s_k$ is the immediate
$\prec$-successor of $s_k$ in $S_n$ then there exists a $t_k\in S$ such
that $s_k\preceq t_k\prec\tilde s_k$ and $C_k\sp{t_k}\in\hat\D$. Moreover,
if $t_k\in S_m$ then applying (vi) at most $m-n$ many times we note that
$C_k\sp{t_k}\subset B_{\e_n}(C\sp{s_k}_k)$. By (iii), if $C_k\sp
t\in\hat\D$, then $k\in\Gamma$, $C_k\sp{s_k}\subset C_k\sp t$, so:
\[
\bigcap_{k\in\Gamma}C_k\sp{s_k}\subset\bigcap\hat\D\subset\bigcap_{k\in
\Gamma}C_k\sp{t_k}\subset\bigcap_{k\in\Gamma}B_{\e_n}(C_k\sp{s_k}).
\]
In particular $\bigcap_{k\in\Gamma}B_{\e_n}(C_k\sp {s_k})$ is non-empty
since, $\bigcap\hat\D\neq\emptyset$. Hence, applying (v) to $\G=\{C_k\sp
{s_k}\colon k\in\Gamma\}\subset\C_n$ we conclude that $\bigcap_{k\in
\Gamma}C_k\sp {s_k}\neq\emptyset$. So, by (iv), $\int\left(\bigcap_{k\in
\Gamma}C_k\sp {s_k}\right)\neq\emptyset$ and, by the density of $X$ in $M$
we conclude that $\emptyset\neq\int\left(\bigcap_{k\in\Gamma}C_k\sp
{s_k}\right)\cap X\subset\bigcap\hat\D\cap X=\bigcap\D$.\qed

For the inductive construction we will need two facts. The first is a
special case of~\cite[lemma~4.3]{Gr} (this lemma is actually stated for
finite families of open sets, arbitrary unions of which are regular open;
we use it on the set of complements of our closed sets):

\lem{lem1}{Let $\F$ be a meet-regular finite family of closed subsets of a
metric space. For every open set $U$ and closed set $D\subset U$ there
is a closed regular set $C$ such that $D\subset\int(C)\subset
C\subset U$ and $\F\cup\{C\}$ is meet-regular.}

We now show the second:

\lem{lem2}{For every finite family $\F$ of closed subsets of a compact
metric space there exists an $\e>0$ such that for every $\G\subset\F$ if
$\bigcap\G=\emptyset$ then $\bigcap_{C\in\G}B_{\e}(C)=\emptyset$.}

\noindent{\sc Proof.} Given a compact metric space
$\la M,d\ra$, and a finite family $\H$ of subsets of $M$ let $d_\H\colon
M\to\real$ be defined by $d_\H(x)=\sum_{H\in\H}d(x,H)$. Certainly,
\begin{equation}\label{D}
\mbox{if $d_\H(x)>0$ then $x\notin\bigcap\H$.}\end{equation}
Moreover, if $\H$ is a family of closed sets then
\begin{equation}\label{B}
\mbox{$\bigcap\H=\emptyset$ if and only if $0\notin d_\H[M]$.}
\end{equation}

Let $\F$ be as in the lemma and fix $\G\subset\F$ such that $\bigcap\G=
\emptyset$. Then, by (\ref{B}) and the compactness of $M$,
there is an $\e_\G>0$ such
that $[0,\e_\G)\cap d_\G[M]=\emptyset$. It is also easy to see that if $n$
is the cardinality of $\F$ then for every $x\in M$ and $\e>0$
\[ d_{\{B_\e(G)\colon G\in\G\}}(x)\geq d_\G(x)-n\e.\]
In particular, if $\delta_\G\in(0,\e_\G/(n+1))$ then
\[ d_{\{B_{\delta_\G}(G)\colon G\in\G\}}(x)\geq d_\G(x)-n\delta_\G\geq
\delta_\G.\]

So, by (\ref{D}), $\bigcap_{G\in\G}B_{\delta_\G}(G)=\emptyset$. Let
$\e=\min\{\delta_\G\colon\G\subset\F\ \&\ \bigcap\G=\emptyset\}>0$. Then
$\bigcap_{G\in\G}B_{\e}(G)=\emptyset$ for each $\G\subset\F$ such that
$\bigcap\G=\emptyset$, showing the lemma.\qed

We start our inductive construction with ${\F}_0=\emptyset$. Assume now
that we have $\F_n=\{C_k\sp s\colon s\in S_n,k< n\}$ and $\e_0,\ldots,
\e_n$ satisfying (i)--(vi). We will first construct $\F_{n+1}=\{C_k\sp
s\colon s\in S_{n+1},k<n+1\}$ satisfying (i)--(iv), and then find an
$\e_{n+1}>0$ which will guarantee (v) and (vi).

We find it useful to let $\{\la m_0,v_0\ra,\dots,\la m_{p-1},v_{p-1}\ra
\}$ be the enumeration of the set $\{0,\ldots,n\}\times S_{n+1}\setminus
\{0,\ldots,n-1\}\times S_n$ such that if $0\leq i<j<p$ then:
\begin{equation}\label{AAAA}
\mbox{either $m_j<m_i$ or $m_j=m_i$ and $v_j\prec v_i$.}
\end{equation}
Then for each $i=0,\dots,p$, let $R_i=(\{0,\ldots,n-1\}\times S_n)\cup\{v_
j\colon j<i\}$. Thus $R_0=\{0,\ldots,n-1\}\times S_n$ and $R_p=\{0,\ldots,
n\}\times S_{n+1}$. We will next show inductively that for each $i\leq p$
there is a family \mbox{$\E=\E(R_i)=\{C_k\sp s\colon\la k,s\ra\in R_i\}$}
containing $\F_n$ and satisfying (i)--(iv).

First we notice that for each such $R_i$, the following fact holds:
whenever $\la m,v\ra,\la m,s\hat{\ }j\ra\in\{0,\ldots,n\}\times S_{n+1}$,
and $s\neq\emptyset$,

\begin{equation}\label{iidiiu}
\mbox{if $v\prec s\hat{\ }j$, $\la m,v\ra\in R_i$, and $\la m,s\hat{\
}j\ra\notin R_i$ then $v\preceq s$.} \end{equation}

To see (\ref{iidiiu}) we use the traditional identification
$n=\{0,\ldots,n-1\}$, and notice that
$v\prec s\hat{\ }j$ if and only if there exists a $k<\dom(s\hat{\ }j)$
such that
\begin{equation}\label{ZZZ}
v\restriction k=s\hat{\ }j\restriction k
\ \mbox{ and \ \ \ either }\ \dom(v)=k
\ \mbox{ or }\ v(k)<s\hat{\ }j(k).
\end{equation}
If either $k<\dom(s)$ or $k=\dom(s)=\dom(v)$ then $v\preceq s$.
The remaining case is when $k=\dom(s)<\dom(v)$ in which case
\begin{equation}\label{prec}
v\restriction k=s\ \mbox{ and }\ v(k)<j.
\end{equation}
Now, by way of contradiction, suppose that
$v\prec s\hat{\ }j$, $\la m,v\ra\in R_i$,
and $\la m,s\hat{\ }j\ra\notin R_i$, while $v\not\preceq s$.
First note that $\la m,v\ra\in R_0$ is impossible,
since then, by (\ref{prec}) we would have
$\la m,s\ra\in R_0$, and so $v(k)<s\hat{\ }j(k)=j=-n$.
Thus, $\la m,v\ra,\la m,s\hat{\ }j\ra\notin R_0$ and, by (\ref{AAAA}),
$s\hat{\ }j\prec v$, another contradiction.
This shows (\ref{iidiiu}).

We now show that the assignment $\E$ on $R_{i-1}$ can be extended to one
on $R_i$, that is, setting $t=v_{i-1}$, that there exists a $C_m\sp t$
such that $\E\cup\{C_m\sp t\}$ is meet-regular and satisfies (i)--(iii).

To do this, we first choose finite families $\bbD_m\sp t$ and $\bbU_m\sp
t$ of closed sets and of open sets, respectively, such that $D=\bigcup
\bbD_m\sp t\subset U=\bigcap\bbU _m\sp t$ and then apply Lemma~\ref{lem1}
to $\E$, $D$, and $U$ letting $C_m\sp t=C$. This will guarantee
meet-regularity. To ensure (i)--(iii) we will choose $\bbD_m\sp t$ and
$\bbU_m\sp t$ as follows. (We write (i-iii$\cdot$u) for the upper
estimates and (i-iii$\cdot$d) for the lower estimates; (iid) is
taken care of by (iiid).)
\begin{description}
\item{(id)} If $t=\la j\ra\in S\sp 1$ then $K_m\sp j\in\bbD_m\sp t$.
\item{(iu)} If $t=\la j\ra\in S\sp1$ then
$\int(K_m\sp{j+1})\in\bbU_m\sp t$.
\item{(iiu)} If $C\sp s_m\in{\E}$ and $t=s\hat{\ }j$ then
$B_{2\sp j}(C_m\sp s)\in\bbU_m\sp t$.
\item{(iiid)} If $C\sp v_m\in{\E}$ and $v\prec t$ then
$C_m\sp v\in\bbD_m\sp t$.
\item{(iiiu)} If $C\sp u_m\in{\E}$ and $t\prec u$ then
$\int(C_m\sp u)\in\bbU_m\sp t$.
\end{description}

We now show that $D\subset U$, so this construction is possible, and the
family ${\E}\cup\{C\sp t_m\}$ is meet-regular. We prove that $D\subset
U$ by showing that each element of $\bbD_m\sp t$ is a subset of each
element of $\bbU_m\sp t$. There are six cases, three involving (id) and
three involving (iiid):
\begin{description}
\item{(id)-(iu):} This holds since we already know that $K_m\sp j\subset
\int (K_m\sp {j+1})$.
\item{(id)-(iiu):} This holds trivially, since it never can occur that
$\la j\ra=s\hat{\ }k$.
\item{(id)-(iiiu):} If $\la j\ra=t\prec u$, then $j<u(0)$ or $j=u(0)$ and
$u\not=\la j\ra$; we then have inductively in the first case that $K_m\sp
j \subset\int\left(K_m\sp {u(0)}\right)\subset\int(C_m\sp u)$ and in the
second that $K_m\sp j\subset\int\left(C_m\sp{\la
u(0)\ra}\right)\subset\int(C_m\sp u)$.
\item{(iiid)-(iu):} If $v\prec t=\la j\ra$ then $v(0)<j$ so by (i),
$C_m\sp v\subset K_m\sp{v(0)+1}\subset\int(K_m\sp{j+1})$.

\item{(iiid)-(iiu):} If $v\prec t=s\hat{\ }j$ then, by (\ref{iidiiu}),
$v\preceq s$, so by inductive assumption, $C_m\sp v\subset C_m\sp s\subset
B_{2\sp j}(C_m\sp s)$.
\item{(iiid)-(iiiu):} If $v\prec t$ and $t\prec u$, then $v\prec u$ so
inductively $C_m\sp v\subset\int(C_m\sp u)$.
\end{description}

Next, notice that by inductive hypothesis on ${\E}$, (id) and (iu), ${\E}
\cup\{C\sp t_m\}$ satisfies (i). Similarly, using (iiu), ${\E}\cup\{C\sp
t_m\}$ satisfies (ii); using (iiid) and (iiiu), we conclude ${\E}\cup\{C
\sp t_m\}$ satisfies (iii). This contradicts the maximality of $\E$,
showing that $\F_n$ can be extended to $\F_{n+1}$ satisfying (i)--(iv).

We now choose $\e_{n+1}$ so as to ensure (v) and (vi). First apply
Lemma~\ref{lem2} to the family ${\F}_{n+1}$ to obtain an $\e>0$ so that
for every $\G\subset{\F}_{n+1}$ if $\bigcap\G=\emptyset$ then $\bigcap_
{C\in\G}B_{\e}(C)=\emptyset$. For such an $\e$ any $\e_{n+1}\leq\e$
guarantees (v). Now there are only finitely many triples $\la k,s,t\ra$
relevant for (vi) and for each of them we have $C\sp t_k\subset B_{\e_n}
(C\sp s_k)$, so there is an $\e_{k,s,t}>0$ for which $B_{\e_{k,s,t}}(C\sp
t_k)\subset B_{\e_n}(C\sp s_k)$. Then choose an $\e_{n+1}>0$ less than
$\e$ and all relevant $\e_{k,s,t}$. Now (i)--(vi) hold for ${\F}_{n+1}$
and $\e_0,\ldots,\e_{n+1}$ satisfy (i)--(vi), completing the proof.\qed

\section{Final remarks}

Note that by Lawson's~(\cite{LA}) result that for a topological space~$X$
\begin{quote}
$X$ has a computational model if and only if $X$ is Polish,
\end{quote}
each space with a bounded complete computational model is Polish. Thus by
Theorem~\ref{thChar} we have that
\begin{quote}
$X$ has a bounded complete computational model if and only if $X$ is
Polish,
\end{quote}

and we immediately obtain the following corollary:

\cor{corFinal}{A topological space $\la X,\tau\ra$ is Polish if and only
if $\la X,\tau\ra$ is second countable and $T_1$, and there is a
compact topology $\tau\sp *\subset \tau$ on $X$ such that $\la X,\tau,
\tau\sp*\ra$ is pairwise regular.}

There is a second, somewhat older road to this converse. In \cite{AGM},
(1970), it was shown (in somewhat different terminology) that any
metrizable space $\la X,\tau\ra$ is topologically complete if and only if
there is a second, compact $T_1$ topology on $X$, $\tau\sp*\subset\tau$,
such that $\la X,\tau,\tau\sp*\ra$ is regular. But by \ref{thChar} each
space with a bounded complete computational model is second countable and
has such a topology (with the additional property that $\la X,\tau\sp*,
\tau\ra$, is regular). Thus the space is Polish.

This leads to a question: if a metrizable space $\la X,\tau\ra$ is
complete must there be a second, compact $T_1$ topology $\tau\sp*$ on $X$
such that $\la X,\tau,\tau\sp*\ra$ is {\it pairwise} regular (as we have
shown in the separable case)?


\begin{thebibliography}{22}

\bibitem{AGM} J.~M.~Aarts, J.~de~Groot, and R.~H.~McDowell, {\it
Cotopology for metrizable spaces}, Duke Math. J. {\bf 37} (1970),
291--295.

\bibitem{AJ} S.~Abramsky and A.~Jung, {\it Domain Theory}, in: S.~Abramsky
etal. eds., Handbook of Logic in Computer Science, Vol. 3, Clarendon
Press, 1994.

\bibitem{CiBook} K.~Ciesielski, {\it Set Theory for the Working
Mathematician}, London Math. Soc. Stud. Texts {\bf 39}, Cambridge Univ.
Press 1997.

\bibitem{CFK} K.~Ciesielski, R.~C.~Flagg, and R.~D.~Kopperman, {\it
Characterizing topologies with bounded complete computational models},
Electron. Notes Theor. Comput. Sci. {\sl 20} (1999)\\ URL: {\tt
http://www.elsevier.nl/locate/entcs/volume20.html}\\ 11 pages. (Also
available at \\ {\tt
http://www.math.wvu.edu/homepages/kcies/STA/STA.html}.)

\bibitem{Do} C.~H.~Dowker, {\it Mappings of Proximity Structures},
General Topology and its Relations to Modern Analysis and Algebra (Proc.
Sympos., Prague, 1961), 139-141, Acad. Press, NY; Publ. House Czech.
Acad. Sci., Prague, 1962.

\bibitem{Ed} A.~Edalat, {\it Domains for computation in mathematics,
physics and exact real arithmetic}, Bull. Symbolic Logic {\bf 3(4)}
(1997), 401--452.

\bibitem{EH} A.~Edalat, R.~Heckmann, {\it A computational model for metric
spaces}, Theoret. Comput. Sci. {\bf 193} (1998), 53--73.

\bibitem{En} R. Engelking, {\it General Topology, Revised and Completed
Edition}, Sigma Ser. Pure Math. {\bf 6}, Heldermann, Berlin, 1989.

\bibitem{ES} M.~H. Escard\'o, {\it Properly injective spaces and function
spaces}, Topology Appl. {\bf 89} (1998), 75--120.

\bibitem{FK} R.~C.~Flagg, R.~D.~Kopperman, {\it Tychonoff poset structures
and auxiliary relations},  Papers on General Topology and Applications
(Andima et. al., eds.), Ann. New York Acad. Sci. {\bf 767} (1995), 45--61.

\bibitem{fk} R.~C.~Flagg, R.~D.~Kopperman, {\it Computational models for
ultrametric spaces}, Electron. Notes Theor. Comput. Sci. {\bf 6} (1999),
(Proceedings of Math. Found. of Prog. Semantics XIII), (preliminary,
83-92).

\bibitem{FL} Peter~Fletcher, William~F.~Lindgren, {\it Quasi-uniform
Spaces}, Marcel Dekker, NY, 1982.

\bibitem{Gand} G.~Gierz, K.~H.~Hofmann, K.~Keimel, J.~D.~Lawson,
M.~Mislove, and D.~S.~Scott, {\it A Compendium of Continuous Lattices},
Springer-Verlag, 1980.

\bibitem{dG} J.~de Groot, {\it An isomorphism principle in general
topology}, Bull.  Amer. Math. Soc. {\bf 73} (1967), 465--467.

\bibitem{Gr} Gary~Gruenhage, {\it On the $M_3\Rightarrow M_1$ question},
Topology Proc. {\bf 5} (1980), 77--104.

\bibitem{KT} T.~Kamimura, A.~Tang, {\em Total Objects of Domains},
Theoret. Comput. Sci. {\bf 34} (1984), 275--288.

\bibitem{AD} Ralph~Kopperman, {\it Asymmetry and
Duality in Topology}, Topology Appl. {\bf 66} (1995), 1--39.

\bibitem{LA} J.~D.~Lawson, {\it Spaces of maximal points}, Math.
Structures Comput. Sci. {\bf 7(1)} (1997), 543--555.

\bibitem{SC} D.~S.~Scott, {\it Outline of the mathematical theory of
computation},  Proceedings of the 4th Princeton Conference on
Information  Science, 1970, 169--176.

\bibitem{Sm} M.~B.~Smyth, {\it Topology and tolerance}, Proceedings of the
13th Conference on Mathematical Foundations of Programming Semantics
(S.~Brooks and M.~Mislove, eds.), Electron. Notes Theor. Comput. Sci. {\bf
6}, 1997. URL: {\tt http://www.elsevier.nl/locate/entcs}.

\end{thebibliography}
\end{document}