\documentclass[%
version=last,%
a5paper,
10pt,%
headings=small,%
%bibliography=totoc,%
twoside,%
reqno,%
cleardoublepage=empty,%
%open=any,%
parskip=half,%
draft=true,%
%DIV=classic,%
DIV=12,%
headinclude=false,%
pagesize]
{scrartcl}

%\usepackage[notref,notcite]{showkeys}

\usepackage{hfoldsty}
\usepackage[neverdecrease]{paralist}
\usepackage{verbatim}  % for the comment environment

\usepackage{amsmath,amssymb,amsthm,upgreek,url}

\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\newcommand{\N}{\mathbb N}
\newcommand{\Q}{\mathbb Q}
\newcommand{\C}{\mathbb C}
\newcommand{\cn}[1][\R]{\mathrm C(#1)}
\newcommand{\supp}[1]{\operatorname{supp}(#1)}
\newcommand{\Supp}[1][Q]{\operatorname{supp}[#1]}
\newcommand{\inv}{^{-1}}
\newcommand{\comp}{^{\mathrm c}}
\newcommand{\interior}{^{\circ}}
\newcommand{\str}[1]{\mathfrak{#1}}
\newcommand{\sig}{\mathscr S}
\newcommand{\Exists}[1]{\exists{#1}\;}
\newcommand{\included}{\subseteq}
%\newcommand{\dand}{\quad\&\quad}  %  Use \And !
\newcommand{\Or}{\DOTSB\;\lor\;}
\newcommand{\liff}{\leftrightarrow}
\newcommand{\lto}{\rightarrow}

\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\dom}[1]{\operatorname{dom}(#1)}

\usepackage{mathrsfs}
\newcommand{\pow}[1][\R]{\mathscr P(#1)}
\newcommand{\powo}[1][\R]{\mathscr P_{\mathrm o}(#1)}

\newcommand{\nmodels}{\nvDash}
\renewcommand{\models}{\vDash}

\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\phi}{\varphi}
\renewcommand{\setminus}{\smallsetminus}
\renewcommand{\epsilon}{\varepsilon}
\usepackage{bm}
\renewcommand{\vec}[1]{\bm{#1}}
\renewcommand{\emptyset}{\varnothing}

%\renewcommand{\theequation}{\fnsymbol{equation}}

\newtheorem{theorem}{Theorem}
%\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{lemma}{Lemma}
\newtheorem*{porism}{Porism}
\begin{document}
\title{Ultraproducts and variants}
\author{David Pierce}
\date{June 22, 2012}
\maketitle

This note is inspired by observations and questions of Vasudevan
Srinivas at Antalya Algebra Days XIV in \c Ce\c sme, 2012.  The
current version of this document should be available at 
\begin{center}
  \url{http://dl.dropbox.com/u/18101757/Ultraproducts/ultraproducts.pdf}
\end{center}
We want to understand the maximal ideals of the ring $\cn$ of
continuous functions from $\R$ to itself.  What are the fields that
are quotients of this ring?  Can they be understood as ultrapowers of
$\R$?  In fact, they can.

  The results of \S\S\ \ref{sect:up} and \ref{sect:fields} are standard.

\tableofcontents


\section{Ultraproducts}\label{sect:up}

We begin with a review of ultraproducts in general, and \L o\'s's Theorem.

Suppose $(\str A_i\colon i\in I)$ is a family of structures with a
common signature $\sig$.  (We shall be interested mainly in the case
when these structures are fields, in the signature
$\{+,-,\cdot,0,1\}$.)  We aim to produce a kind of `average' of the
structures $\str A_i$.  To this end, let $P$ be a proper \emph{ideal}
of the power set $\pow[I]$; this means 
\begin{gather}\label{0}
\emptyset\in P\And I\notin P,\\\label{sub}
	X\included Y\And Y\in P\implies X\in P,\\\label{cup}
X\in P\And Y\in P\implies X\cup Y\in P.
\end{gather}
For example, for some proper subset $A$ of $I$, $P$ might consist of all subsets of $A$; or if $I$ is infinite, $P$ might consist of the finite subsets of $I$.
In general, elements of $P$ can be considered as \textbf{small;} their complements (which compose a \emph{filter} of $\pow[I]$) are \textbf{large.}  Since $P$ is a \emph{proper} ideal, the same set cannot be both small and large.  Since $P$ is not yet assumed to be maximal, some elements might be neither small nor large.

An element of the Cartesian product $\prod_{i\in I}A_i$ is a tuple $(a_i\colon i\in I)$, where $a_i\in A_i$; we may write this tuple simply as $a$.  Two such tuples are \textbf{congruent} \emph{modulo} $P$ if they disagree only on a small set of indices:\footnote{Equivalently, they agree on a large set of indices.  Everything below can be expressed in terms of filters rather than ideals; and indeed it may be easier to think in terms of filters rather than ideals.  I stick with ideals here, because they are already familiar from ring theory.}
\begin{equation}\label{cong}
\{i\in I\colon a_i\neq b_i\}\in P\iff
a\equiv b\pmod P.
\end{equation}
We may write $a/P$ for the congruence-class $\{b\colon a\equiv b\pmod P\}$.
Let $M$ be the set of these congruence-classes.  We turn this into a structure $\str M$ of $\sig$ by requiring, for each $n$ in $\upomega$,
\begin{equation}\label{L}
\str M\models\phi(a^0/P,\dots,a^{n-1}/P)\iff
\{i\colon\str A_i\models\lnot\phi(a^0_i,\dots,a^{n-1}_i)\}\in P
\end{equation}
for all $n$-ary \emph{unnested atomic formulas} $\phi$ of $\sig$, that is, all $\phi$ having one of the forms\footnote{The equation $x=y$ can also be considered as an unnested atomic formula; but if $\phi$ is this, then \eqref L becomes a restatement of \eqref{cong}.}
\begin{compactenum}[1)]
\item
 $Rx^0\cdots x^{n-1}$ for some $n$ predicate $R$ in $\sig$, or
 \item
 $x^0=Fx^1\cdots x^{n-1}$ for some $(n-1)$-ary operation-symbol $F$ in $\sig$,
 \end{compactenum} 
 for some $n$ in $\upomega$ (where $n>0$ in the second case; in this case, if $n=1$, then $F$ is a constant).
This definition of $\str M$ is valid since\footnote{All of the superscripts below are merely indices, not exponents.}
\begin{align*}
&\phantom{{}\included{}}\{i\colon\str A_i\models\lnot\phi(b^0_i,\dots,b^{n-1}_i)\}\\
&\included
\{i\colon\str A_i\models\lnot\phi(a^0_i,\dots,a^{n-1}_i)\}
\cup\{i\colon a^0_i\neq b^0_i\}\cup\dots\cup\{i\colon a^{n-1}_i\neq b^{n-1}_i\},
\end{align*}
so that if $a^k\equiv b^k$ for each $k$, then
\begin{equation*}
\{i\colon\str A_i\models\lnot\phi(a^0_i,\dots,a^{n-1}_i)\}\in P\iff
\{i\colon\str A_i\models\lnot\phi(b^0_i,\dots,b^{n-1}_i)\}\in P
\end{equation*}
by \eqref{sub} and \eqref{cup}.  Another way to express \eqref L in the two cases is that
\begin{equation*}
R^{\str M}=\bigl\{(a^0/P,\dots,a^{n-1}/P)\colon\bigl((a^0_i,\dots,a^{n-1}_i)\colon i\in I\bigr)\in\prod_{i\in I}R^{\str A_i}\bigr\},
\end{equation*}
for $n$-ary predicates $R$, and for $(n-1)$-ary operation-symbols $F$,
\begin{equation}\label{F}
F^{\str M}(a^1/P,\dots,a^{n-1}/P)=(F^{\str A_i}(a^1,\dots,a^{n-1})\colon i\in I)/P.
\end{equation}
The structure $\str M$ is a \textbf{reduced product} of the family $(\str A_i\colon i\in I)$; as such it might be denoted by something like
\begin{equation*}
\prod_{i\in I}\str A_i/P.
\end{equation*}

We can understand each element $a$ of $\prod_{i\in I}A_i$ as a new constant or \emph{parameter,} to be interpreted in each $\str A_i$ as $a_i$, and in $\str M$ as $a/P$.  Then we can write \eqref L as
\begin{equation*}
\str M\models\phi(a^0,\dots,a^{n-1})\iff\{i\colon\str A_i\models\lnot\phi(a^0,\dots,a^{n-1})\}\in P.
\end{equation*}
Then, letting $\vec a$ stand for $(a^0,\dots,a^{n-1})$, we can write \eqref L simply as
\begin{equation*}
\str M\models\phi(\vec a)\iff\{i\colon\str A_i\models\lnot\phi(\vec a)\}\in P,
\end{equation*}
---that is, $\phi(\vec a)$ is true in $\str M$ just in case, for a large set of $i$, it is true in $\str A_i$.  Writing $\phi(\vec a)$ then simply as $\sigma$, we get
\begin{equation}\label{g}
\str M\models\sigma\iff\{i\colon\str A_i\models\lnot\sigma\}\in P.
\end{equation}
Again, this is true by definition when $\sigma$ is an unnested atomic sentence (in the expanded signature); for which other $\sigma$ is it true?

\begin{lemma}\label{land}
The equivalence \eqref g in $\sigma$ is preserved under conjunction, in that if it holds when $\sigma$ is $\tau$ or $\rho$, then it holds when $\sigma$ is $\tau\land\rho$.
\end{lemma}

\begin{proof}
We use \eqref{cup} and its converse (which is true by \eqref{sub}).  If \eqref g holds when $\sigma$ is $\tau$ or $\rho$, then the following are equivalent:
\begin{gather*}
\str M\models\tau\land\rho,\\
\str M\models\tau\And\str M\models\rho,\\
\{i\colon\str A_i\models\lnot\tau\}\in P\And
\{i\colon\str A_i\models\lnot\rho\}\in P,\\
\{i\colon\str A_i\models\lnot\tau\}\cup
\{i\colon\str A_i\models\lnot\rho\}\in P,\\
\{i\colon\str A_i\models\lnot\tau\lor\lnot\rho\}\in P,\\
\{i\colon\str A_i\models\lnot(\tau\land\rho)\}\in P.\qedhere
\end{gather*}
\end{proof}

\begin{lemma}\label{exists}
The equivalence \eqref g in $\sigma$ is preserved under quantification, in the sense that
\begin{compactdesc}
\item[if] \eqref g holds when $\sigma$ is $\psi(a)$, for all parameters $a$, for some singulary formula $\psi$ (possibly with parameters),
\item[then] \eqref g holds when $\sigma$ is $\Exists x\psi(x)$.
\end{compactdesc}
\end{lemma}

\begin{proof}
Under the given hypothesis, the following are equivalent:
\begin{gather*}
\str M\models\Exists x\psi(x),\\
\str M\models\psi(a)\text{ for some $a$},\\
\{i\colon\str A_i\models\lnot\psi(a)\}\in P\text{ for some $a$}.	
\end{gather*}
The last statement easily implies
\begin{equation*}
\{i\colon\str A_i\models\lnot\Exists x\psi(x)\}\in P,
\end{equation*}
since for all $a$,
\begin{equation}\label{a}
\{i\colon\str A_i\models\lnot\Exists x\psi(x)\}\included
\{i\colon\str A_i\models\lnot\psi(a)\}.
\end{equation}
Conversely,
there is some $a$ for which this inclusion is an equation.
\end{proof}

Suppose finally $P$ is a \emph{maximal} ideal of $\pow[I]$, so that the set of complements of elements of $P$ is an \emph{ultrafilter} of $\pow[I]$.  Then the reduced product $\str M$ is called more precisely an \textbf{ultraproduct} of $(\str A_i\colon i\in I)$.  There is a trivial example:  For some $j$ in $I$, let $P$ be the \emph{principal} ideal $(I\setminus\{j\})$ of $\pow[I]$, that is, $P=\{X\included I\colon j\notin I\}$.  Then
\begin{equation*}
\prod_{i\in I}\str A_i/P\cong \str A_j.
\end{equation*}
All ultraproducts are thus if $I$ is finite; but if $I$ is infinite, then $P$ may contain all finite subsets of $I$, so that (since it is proper) it must not be principal.

\begin{lemma}
An ideal $P$ of $\pow[I]$ is maximal if and only if
\begin{equation}\label{c}
X\notin P\iff X\comp\in P.
\end{equation}
\end{lemma}

\begin{proof}
The set $\pow[I]$ can be considered as a ring in which sums are symmetric differences, and products are intersections.  Then ideals as defined above are just ideals in the ring-theoretic sense.  The ring $\pow[I]$ is then a \emph{Boolean} ring, because it satisfies the identity $x^2=x$.  If $P$ is a maximal ideal, then the quotient $\pow[I]/P$ is a field as well as a Boolean ring; therefore it must be a two-element field.   Thus \eqref c holds.  Conversely, any ideal with this property must be maximal.
\end{proof}

Immediately we have:

\begin{lemma}\label{lnot}
If $P$ is a maximal ideal of $\pow[I]$, then \eqref g in $\sigma$ is preserved under negation.
\end{lemma}

Lemmas \ref{land}, \ref{exists}, and \ref{lnot} together yield:

\begin{theorem}[\L o\'s\footnote{The usual reference is \cite{MR0075156} although the theorem is not given clearly there.}]
If $P$ is a maximal ideal of $\pow[I]$, then \eqref g holds for all $\sigma$ (with parameters).
\end{theorem} 

As a special case, if each $\str A_i$ is the same structure $\str A$, so that in particular $\prod_{i\in I}A_i$ is the Cartesian power $A^I$, then the ultraproduct $\str M$ (that is $\str A^I/P$) is an \textbf{ultrapower} of $\str A$.
The diagonal embedding $a\mapsto(a\colon i\in I)$ of $\str A$ in $\str M$ is now an \emph{elementary embedding,} that is, for all sentences $\sigma$ with parameters from $A$ (or more precisely from the image of $A$ in $A^I$),
\begin{equation*}
\str M\models\sigma\iff\str A\models\sigma.
\end{equation*}
Considering the embedding as an inclusion (that is, identifying $\str A$ with its image in $\str M$), we may write then
\begin{equation*}
\str A\preccurlyeq\str M.
\end{equation*}

\section{Fields}\label{sect:fields}

We now consider the case where each structure $\str A_i$ is a field $K_i$.  Write
\begin{equation*}
\prod_{i\in I}K_i=R;
\end{equation*}
this is a ring in the usual way.
There is a map $a\mapsto\supp a$ from $R$ to $\pow[I]$ given by
\begin{equation*}
\supp a=\{i\colon a_i\neq0\};
\end{equation*}
here $\supp a$ is the \textbf{support} of $a$.
If $A\included I$, let $\chi_A$ be the element of $R$ be given by
\begin{equation*}
\chi_A(i)=\begin{cases}
	1,&\text{ if }i\in A,\\
	0,&\text{ if }i\notin A.
\end{cases}
\end{equation*}

\begin{lemma}
The map $Q\mapsto\Supp$ is a one-to-one, inclusion-preserving correspondence between ideals of $R$ and ideals of $\pow[I]$.
\end{lemma}

\begin{proof}
If $A\included\supp b$, then $A=\supp{b\cdot\chi_A}$.  Also
\begin{equation*}
\supp b\cup\supp c=\supp{b+c\cdot\chi_{\supp b\comp}}.
\end{equation*}
Thus if $Q$ is an ideal of $R$, then $\Supp$ is an ideal of $\pow[I]$.  Moreover, if $\supp b=\supp c$, then an ideal of $R$ contains $b$ if and only if it contains $c$; thus the map $Q\mapsto\Supp$ on the set of ideals of $R$ is injective.  Since in general
\begin{gather*}
	\supp{a\cdot b}\included\supp b,\\
	\supp{a+b}\included\supp a\cup\supp b,
\end{gather*}
if $P$ is an ideal of $\pow[I]$, then $\{a\colon\supp a\in P\}$ is an ideal $Q$ of $R$ such that $\Supp =P$.
Thus the map $Q\mapsto\Supp$ is surjective onto the set of ideals of $\pow[I]$.
\end{proof}

\begin{lemma}
If $Q$ is an ideal of $R$, and $P=\Supp$, then
\begin{equation*}
\prod_{i\in I}K_i/P=R/Q
\end{equation*}
(the reduced product is equal to the ring-quotient).
\end{lemma}

\begin{proof}
Because
\begin{equation*}
a-b\in Q\iff a\equiv b\pmod P,
\end{equation*}
that is $a+Q=a/P$, the underlying sets of the reduced product and the quotient are the same.  The ring-structures are the same by \eqref F.
\end{proof}

\section{Continuous functions}

We now consider the special case when $I=\R$ and each $K_i$ is $\R$, so that $\prod_{i\in I}K_i$ is the Cartesian power $\R^{\R}$.  By the last lemma, a quotient of this power by a maximal ideal is an ultrapower of $\R$.  Such an ultrapower is a \emph{non-standard} model of the theory of $\R$ (assuming the maximal ideal is non-principal).  Here $\R$ can be considered as an ordered field.\footnote{In real analysis we may quantify, not just over elements of $\R$, but over sets of these (as in the Completeness Axiom), over finite sequences of arbitrary length (as in the definition of the Riemann integral), and so forth.  We may then want to consider an ultrapower, not just of $\R$, but of a certain \emph{many-sorted} structure, namely a structure of which $\R$ is one sort, but also the power set of any finite Cartesian product of sorts is a sort \cite{MR1373196}.}

The power $\R^{\R}$ has the sub-ring $\cn$ of continuous real-valued functions on $\R$.  The supports of its elements are open subsets of $\R$, and every such set is the support of some element of $\cn$.  

Let $\powo$ be the set of all open subsets of $\R$.  This set is a distributive lattice, but not a Boolean ring or algebra; however, ideals can be defined as before, by \eqref0, \eqref{sub}, and \eqref{cup}.  

\begin{lemma}
The map $Q\mapsto\Supp$ is a surjection from the set of ideals of $\cn$ to the set of ideals of $\powo$.  It takes proper ideals to proper ideals.	 
\end{lemma}

\begin{proof}
Since
\begin{gather*}
\supp f\included\supp g\implies\supp f=\supp{f\cdot g},\\
\supp f\cup\supp g=\supp{f^2+g^2},
\end{gather*}
the support-map still takes ideals of $\cn$ to ideals of $\powo$.  Moreover, it takes proper ideals to proper ideals.
As before, every ideal $P$ of $\powo$ is the image of some ideal of $\cn$, namely $\{f\colon\supp f\in P\}$.
\end{proof}

The same ideal of $\powo$ may be the image of more than one ideal of $\cn$.  For example, the ideals generated respectively by $x\mapsto x$ and $x\mapsto x^2$ have the same image, but are themselves different, since there is no \emph{continuous} function $f$ such that $x^2\cdot f(x)=x$ for all $x$ in $\R$.

Since $\powo$ is not closed under complementation, \emph{maximal} ideals are not characterized as before, by \eqref c; but an ideal $P$ of $\powo$ is maximal if and only if 
\begin{equation}\label{o}
X\notin P\implies\Exists Y(Y\in P\And X\cup Y=\R).
\end{equation}

\begin{lemma}
The map $Q\mapsto\Supp$ is a one-to-one correspondence between maximal ideals of $\cn$ and maximal ideals of $\powo$.
\end{lemma}

\begin{proof}
Suppose $Q$ is a maximal ideal of $\cn$.
If $X\in \powo\setminus\Supp$, then $X=\supp f$ for some $f$ in $\cn\setminus Q$.  Since $Q$ is maximal, for some $g$ in $\cn$ and $h$ in $Q$,
\begin{equation*}
fg+h=1.
\end{equation*}
Therefore $X\cup\supp h=\R$.  Thus $\Supp$ is maximal.
Moreover,
if $f\in Q$ and $\supp f=\supp g$, then $g\in Q$ by maximality of $Q$; thus the support-map is injective on the set of maximal ideals of $\cn$.  Finally, if $P$ is a maximal ideal of $\powo$, then $\{f\in\cn\colon\supp f\in P\}$ must be a maximal ideal.
\end{proof}

Given the maximal ideal $Q$ of $\cn$, we shall establish a version of \L o\'s's Theorem for $\cn/Q$.  This is stated as Theorem~\ref{thm:cn} below; but the proof is everything between here and there.
 
If $\phi$ is an $n$-ary equation in the signature of fields (that is, $\phi$ is a polynomial equation in $n$ variables over $\Z$), then,
writing $\vec f$ for a finite tuple $(f^0,\dots,f^{n-1})$ of elements of $\cn$, and $\vec f+Q$ for $(f^0+Q,\dots,f^{n-1}+Q)$, we have
\begin{equation}\label{Q}
\cn/Q\models\phi(\vec f+Q)\iff\{x\colon\R\models\lnot\phi(\vec f(x))\}\in\Supp.
\end{equation}
Moreover, this equivalence is preserved under conjunctions, just as in Lemma~\ref{land}.  Similarly, it is preserved under disjunctions, by the following rule, derivable from \eqref o:  If $P$ is a maximal ideal of $\powo$, then
\begin{equation}\label{cap}
X\in P\Or Y\in P\iff X\cap Y\in P.
\end{equation}
But \eqref Q is not preserved under negations: if $\phi$ is an inequation, then \eqref Q fails, because the set $\{x\colon\R\models\lnot\phi(\vec f(x))\}$ is then closed, so if it is nonempty, it is simply not in $\Supp$.

Nonetheless, we can use \eqref Q in case $\phi$ is $y\leq z$ to define the relation $\leq$ on $\cn/Q$:

\begin{lemma}
If $Q$ is a maximal ideal of $\cn$, and
$\cn/Q$ is linearly ordered by the relation $\leq$ given by
\begin{equation*}
\cn/Q\models f+Q\leq g+Q\iff\{x\colon\R\models f(x)>g(x)\}\in\Supp;
\end{equation*}
and then $\cn/Q$ is an ordered field.
\end{lemma}

\begin{proof}
The relation $\leq$ is well-defined, by the same argument by which reduced products are well-defined.  The relation is then reflexive, by \eqref{0}; antisymmetric, by \eqref{cup}; transitive, by \eqref{cup} and \eqref{sub}.  It is linear, by \eqref0 and \eqref{cap}: since $\{x\colon\R\models f(x)>g(x)\land f(x)<g(x)\}\in\Supp$, one of $\{x\colon\R\models f(x)>g(x)\}$ and $\{x\colon\R\models f(x)<g(x)\}$ is in $\Supp$.  Moreover,
\begin{align*}
&\phantom{{}\implies{}}f\geq0\And g\geq0\\
&\implies\{x\colon f(x)<0\}\in\Supp\And\{x\colon g(x)<0\}\in\Supp\\
&\implies\{x\colon f(x)<0\}\cup\{x\colon g(x)<0\}\in\Supp\\
&\implies\{x\colon f(x)<0\lor g(x)<0\}\in\Supp\\
&\implies\{x\colon f(x)+g(x)<0\}\in\Supp\\
&\implies f+g\geq0
\end{align*}
since $f(x)+g(x)<0\implies f(x)<0\Or g(x)<0$.  Similarly
\begin{equation*}
f\geq0\And g\geq0\implies fg\geq0.\qedhere
\end{equation*}
\end{proof}

We handle negations by observing that there is a maximal ideal $P$ of $\pow$ such that $\Supp\included P$.  
The intersection $P\cap\powo$ is an ideal of $\powo$ that includes $\Supp$.  Moreover, an ideal of $\pow$ or $\powo$ is proper if and only if it does not contain $\R$; therefore $P\cap\powo$  is a proper ideal of $\powo$, so it is just $\Supp$.  This gives us:

\begin{lemma}
If $Q$ is a maximal ideal of $\cn$, and $P$ is a maximal ideal of $\pow$ such that $\Supp\included P$, then
\begin{equation}\label{L'}
\cn/Q\models\phi(\vec f+Q)\iff\{x\colon\R\models\lnot\phi(\vec f(x))\}\in P
\end{equation}
for all quantifier-free formulas $\phi$ in the signature of ordered fields.  Moreover, this equivalence in $\phi$ is preserved under conjunction and negation (and hence under disjunction).
\end{lemma}

We want to show that \eqref{L'} is preserved under quantification.

If $P$ is an arbitrary maximal ideal of $\pow$, it need not be the case that $P\cap\powo$ is a maximal ideal of $\powo$.  We do have:

\begin{lemma}\label{lem:int}
For a maximal ideal $P$ of $\pow$, the intersection $P\cap\powo$ is a maximal ideal of $\powo$ if and only if $P$ contains an open neighborhood of each of its closed elements.
\end{lemma}

\begin{proof}
This is a reworking of \eqref o.  We have that $P\cap\powo$ is maximal if and only if, for all $O$ in $\powo\setminus P$, there is an open neighborhood of $O\comp$ in $P$.  By maximality of $P$, this condition is that for all closed sets $F$ in $P$, there is an open neighborhood of $F$ in $P$.
\end{proof}

The condition of the lemma need not be met.
For example, an arbitrary maximal ideal $P$ of $\pow$ might contain $\{0\}$, but also $(-\infty,-\epsilon)\cup(\epsilon,\infty)$ for all positive $\epsilon$, so that $P$ (being proper) can contain no open neighborhood of $0$.

We continue to assume that $Q$ is a maximal ideal of $\cn$, and $P$ is a maximal ideal of $\pow$ such that $P\cap\powo=\Supp$.
Then the inclusion of $\cn$ in $\R^{\R}$ induces an embedding of the quotient $\cn/Q$ in the ultrapower $\R^{\R}/P$.  If we have \eqref{L'} for \emph{all} formulas $\phi$, then not only is the embedding of $\R$ in $\cn/Q$ elementary, but the embedding of $\cn/Q$ in $\R^{\R}/P$ is elementary: this is \eqref{eqn:el} below.

Supposing \eqref{L'} to hold when $\phi$ is $\psi$, we want to show that it holds when $\phi$ is $\Exists y\psi$.  The
analogue of \eqref a in the proof of Lemma \ref{exists} is now 
\begin{equation}\label{ineq}
\{x\colon\R\models\lnot\Exists y\psi(\vec
f(x),y)\}\included\{x\colon\R\models\lnot\psi(\vec f(x),g(x))\},
\end{equation}
or equivalently
\begin{equation*}
\{x\colon\R\models\psi(\vec f(x),g(x))\}\included\{x\colon\R\models\Exists y\psi(\vec
f(x),y)\}.
\end{equation*}
As before, we try to choose $g$ so that this inclusion is an equation.   However, this may not be possible, since we now have the further requirement that $g$ be continuous.  For example, $\psi(\vec f(x),y)$ could be
\begin{equation*}
(x\geq0\land y=1)\lor(x<0\land y=0),
\end{equation*}
defining the graph of $\chi_{[0,\infty)}$, a non-continuous function.  Nonetheless,
we shall still have what we want if we can make \eqref{ineq} `nearly' an equation,
that is, find $g$ so that
\begin{equation*}
  \{x\colon\R\models\Exists y\psi(\vec f(x),y)\land\lnot\psi(\vec
  f(x),g(x))\}\in P.
\end{equation*}
Indeed, it is sufficient to show that if 
\begin{equation}\label{psi}
\{x\colon\R\models\lnot\Exists y\psi(\vec f(x),y)\}\in P,
\end{equation}
then there is $g$ in $\cn$ such that
\begin{equation}\label{fg}
\{x\colon\R\models\lnot\psi(\vec f(x),g(x))\}\in P.
\end{equation}
Suppose for example $\psi(\vec f(x),y)$ is $xy=1$, and \eqref{psi} holds in this case.  Then $\{0\}\in P$, so $P$ has an element $(-\epsilon,\epsilon)$ by Lemma \ref{lem:int}.  If we define $g$ by
\begin{equation*}
g(x)=
\begin{cases}
	1/x,&\text{ if }\abs x\geq\epsilon,\\
	x/\epsilon^2,&\text{ if }\abs x<\epsilon,
\end{cases}
\end{equation*}
then $g\in\cn$, and \eqref{fg} holds.

We suppose \eqref{psi} for some $\psi$ and $\vec f$.
By Tarski's theorem on quantifier-elimination in the theory of $\R$ as
an ordered field, 
we may assume that $\psi$ is quantifier-free in the signature of
ordered fields.  Thus we may consider $\psi(\vec f(x),y)$ as a Boolean combination of equations and inequalities of polynomials in $y$ whose coefficients are
themselves polynomial functions of the entries in $\vec f(x)$.  In particular, these
coefficients are continuous functions of $x$.  We may assume $\psi(\vec f(x),y)$ is a Boolean combination of strict inequalities only, since
\begin{equation*}
x=0\iff x\not>0\land x\not<0.
\end{equation*}

\begin{lemma}
A formula
\begin{equation}\label{>}
g_0(x)+g_1(x)\cdot y+\dots+g_n(x)\cdot y^n>0,
\end{equation}
where the $g_i$ are in $\cn$, is equivalent in $\R$ to a Boolean combination of such formulas in which $n=1$ in each case.
\end{lemma}

\begin{proof}[Proof (sketch).]
The equation
$g_0(x)+g_1(x)\cdot y+\dots+g_n(x)\cdot y^n=0$
defines the union of
\begin{equation*}
\{(x,y)\colon g_0(x)=0\land\dots\land g_n(x)=0\}
\end{equation*}
with the graphs of $n$ functions $h_0$, \dots, $h_{n-1}$, where each $h_i$ is a continuous function whose domain is the intersection of a closed subset and an open subset of $\R$.  In particular, the domain of each $h_i$ is defined by a formula $\phi_i(x)$, which is of the form $f_0(x)=0\land f_1(x)>0$ for some $f_0$ and $f_1$ in $\cn$.  Then \eqref> is equivalent to a Boolean combination of various $y<h_i(x)$ and $y>h_j(x)$.  But here the $h_i$ are not necessarily in $\cn$.  If $h_i$ \emph{extends} to an element $f$ of $\cn$, then we can replace $y<h_i(x)$ with $y<f(x)\land\phi_i(x)$, so we are done.  However, possibly $h_i$ approaches no limit at boundary points of its domain.  In that case, there will be some $f_0$ in $\cn$, positive on the domain of $h_i$, such that $f_0\cdot h_i$ does approach a limit at the boundary points, so that it extends to an element $f_1$ of $\cn$.  Then we can replace $y<h_i(x)$ with $f_0(x)\cdot y<f_1(x)\land\phi_i(x)$.
\end{proof}

\begin{comment}



\begin{lemma}
If $f$ is $(x,y)\mapsto g_0(x)+g_1(x)\cdot y+\dots+g_n(x)\cdot y^n$ on
$\R\times\R$, where the $g_i$ are continuous, then there are $n$
continuous functions $h_k$, whose domains are closed (and possibly
empty) subsets of $\R$ [THIS PART IS WRONG: CONSIDER $xy=1$], such that 
\begin{equation*}
\{(x,y)\colon f(x,y)=0\}=\bigcup_{k<n}\{(x,y)\colon h_k(x)=y\}.
\end{equation*}
\end{lemma}

\begin{proof}{}
[To be fleshed out, unless the lemma can be cited from somewhere else.]  Suppose $f(a,b)=0$, and for positive $\epsilon$
sufficiently small, $f(a,b+\epsilon)>0$, but $f(a,b-\epsilon)<0$.
Then for some positive $\delta$, if $a-\delta<x<a+\delta$, then
$f(x,b+\epsilon)>0$, but $f(x,b-\epsilon)<0$, so the function
$y\mapsto f(x,y)$ has a zero in $(b-\epsilon,b+\epsilon)$.  In this
way we obtain the existence of the functions $h_k$ on a neighborhood
of every point $a$ such that $f(a,y)$ has no multiple roots\dots 
\end{proof}

This lemma allows a further simplification: we may assume $\psi(\vec
f(x),y)$ is a Boolean combination of formulas of the form $y=g(x)$,
$y>g(x)$, or $y<g(x)$, where now the domain of each $g$ is some closed
subset of $\R$ (and $g$ is continuous on this domain).  But in this
case $\dom g=\{x\colon h_0(x)=0\}$ for some $h_0$ in $\cn$; also
$g=h_1\restriction\dom f$ for some $h_1$ in $\cn$.


\end{comment}

So now we may assume $\psi(\vec f(x),y)$ is a (finite) disjunction
\begin{equation*}
\bigvee_{\theta}\theta(\vec f(x),y),
\end{equation*}
where each $\theta(\vec f(x),y)$ is a (finite) conjunction of
formulas of the form $g(x)\cdot y=h(x)$ and $g(x)\cdot y<h(x)$, where
each $g$ and each $h$ is in $\cn$.
If \eqref{psi} now holds, this means
\begin{equation*}
\bigcap_{\theta}\{x\colon\R\models\lnot\Exists y\theta(\vec f(x),y)\}\in P,
\end{equation*}
and therefore, by \eqref{cap}, for one of the $\theta$,
\begin{equation}\label{theta}
\{x\colon\R\models\lnot\Exists y\theta(\vec f(x),y)\}\in P.
\end{equation}
Suppose first that one of the conjuncts of $\theta(\vec f(x),y)$ is (equivalent to a formula) of the form $f(x)\cdot y=g(x)$.  If $f$ has no real zeros, then
\begin{equation}\label{h}
\{x\colon\R\models\lnot\Exists y\theta(\vec f(x),y)\}=\{x\colon\R\models\lnot\theta(\vec f(x),h(x))\},
\end{equation}
where $h(x)=g(x)/f(x)$.  However, $f$ may in fact have real zeros.  Still, by \eqref{theta}, we have $\{x\colon\R\models\lnot\Exists yf(x)\cdot y=g(x)\}\in P$, that is,
\begin{equation*}
\{x\colon f(x)=0\land g(x)\neq0\}\in P.
\end{equation*}
Therefore
\begin{equation*}
\{x\colon f(x)=0\land g(x)=0\}\in P\iff\{x\colon f(x)=0\}\in P.
\end{equation*}
Suppose first $\{x\colon f(x)=0\}\in P$.  Then some open neighborhood $U$ of this set is in $P$, by Lemma \ref{lem:int}.  In this case, there is $h$ in $\cn$ that agrees with $g/f$ on the complement of $U$, and then we have, perhaps not \eqref h, but still
\begin{equation}\label{h'}
\{x\colon\R\models\lnot\theta(\vec f(x),h(x))\}\in P.
\end{equation}
The other possibility is $\{x\colon f(x)=0\land g(x)=0\}\notin P$.  In this case, the equation $f(x)\cdot y=g(x)$ imposes no condition on $y$; that is, we can remove the equation from $\psi(\vec f(x),y)$.

It thus remains only to consider the case where $\psi(\vec f(x),y)$ is a conjunction of inequalities of the form $f(x)\cdot y<g(x)$.  Again by \eqref{theta} we have that $\{x\colon\R\models\lnot\Exists yf(x)\cdot y<g(x)\}\in P$, that is,
\begin{equation*}
\{x\colon f(x)=0\land g(x)\leq0\}\in P.
\end{equation*}
Therefore
\begin{equation*}
\{x\colon f(x)=0\land g(x)>0\}\in P\iff\{x\colon f(x)=0\}\in P.
\end{equation*}
If $\{x\colon f(x)=0\land g(x)>0\}\notin P$, then we can remove $f(x)\cdot y<g(x)$ from $\psi(\vec f(x),y)$.
If $\{x\colon f(x)=0\}\in P$, then some open neighborhood $U$ of this set is in $P$, and there is $h$ in $\cn$ that agrees with $g/f$ on the complement of $U$, so that in $\psi(\vec f(x),y)$ we can replace the inequality $f(x)\cdot y<g(x)$ with
\begin{equation*}
(f(x)>0\lto y<g(x))\land(f(x)<0\lto y>g(x)).
\end{equation*}
or rather with
\begin{equation*}
(f(x)>0\land y<g(x))\lor(f(x)<0\land y>g(x))
\end{equation*}
(these two equations are not equivalent; but they are interchangeable, since it does not matter what happens when $f(x)=0$).
So now we are reduced to the case where $\psi(\vec f(x),y)$ is a conjunction of formulas of this form $y<g(x)$ and $y>g(x)$, along with quantifier-free formulas in $x$ alone.
Two inequalities $y>g_0(x)$ and $y>g_1(x)$ can be replaced
with $y>\max(g_0(x),g_1(x))$, and so forth.  Then we may assume that  $\psi(\vec
f(x),y)$ is of one of the three forms
\begin{align*}
  g_0(x)<y&\land y<g_1(x),&g_0(x)&<y,&y<g_1(x),
\end{align*}
in conjunction with a formula $g_2(x)=0\land g_3(x)>0$.
Under the first form, we have \eqref{h'} when $h=(g_0+g_1)/2$; under the others, $h=g_0\mp1$.  In all cases then, \eqref{psi} implies \eqref{fg} for some $g$ in $\cn$.
So we do indeed have \eqref{L'} for all $\phi$:

\begin{theorem}\label{thm:cn}
If $Q$ is a maximal ideal of $\cn$,
and $P$ is a maximal ideal of $\pow$ such that $\Supp\included P$, then
\begin{equation*}
\cn/Q\models\phi(\vec f+Q)\iff\{x\colon\R\models\lnot\phi(\vec f(x))\}\in P
\end{equation*}
for all formulas $\phi$ in the signature of ordered fields.  In particular
\begin{equation}\label{eqn:el}
\R\preccurlyeq\cn/Q\preccurlyeq\R^{\R}/P.
\end{equation}
\end{theorem}



\section{Ideals}\label{sect:ideals}

Here are some further observations about ideals of $\powo$ and $\pow$.



We can require a maximal ideal $P$ of $\pow$ to contain, for each
countable subset of $\R$, an open set that includes it.  Indeed,
suppose $X$ is a countable subset of $\R$.  Then
$X\cap([-n,-n+1]\cup[n-1,n])$ is included in an open set $U_n$ of
measure less than $1/n$.  We put $\bigcup_{n\in\N}U_n$ in $P$.  Then
$m$ such sets cannot cover $[m,m+1]$.  So such sets can all be members
of $P$. 

The condition in Lemma \ref{lem:int} can be strengthened:

\begin{lemma}
For a maximal ideal $P$ of $\pow$, the intersection $P\cap\powo$ is a maximal ideal of $\powo$ if and only if $P$ contains the closure of an open neighborhood of each of its closed elements.
\end{lemma}

\begin{proof}
Suppose $P$ contains a closed set $F$ and a neighborhood $V$ of $F$.  Each point $a$ of $F$ is at a positive distance $d_a$ from $V\comp$; here
\begin{equation*}
d_a=\inf_{x\in V\comp}\abs{a-x}.
\end{equation*}
Now let
\begin{equation*}
U=\bigcup_{a\in F}\Bigl(a-\frac{d_a}2,a+\frac{d_a}2\Bigr).
\end{equation*}
Then $U$ is an open neighborhood of $F$, and $\overline U\included V$, so $\overline U\in P$.
\end{proof}

It is not the case that
the closure of every element of $P$ is in $P$.  Indeed, either $\Q$ or its complement is in $P$, but the closure of either of these is $\R$.

%\bibliographystyle{amsplain}
%\bibliography{../references}

\def\rasp{\leavevmode\raise.45ex\hbox{$\rhook$}} \def\cprime{$'$}
  \def\cprime{$'$} \def\cprime{$'$} \def\cprime{$'$}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{1}

\bibitem{MR0075156}
Jerzy {\L}o{\'s}, \emph{Quelques remarques, th\'eor\`emes et probl\`emes sur
  les classes d\'efinissables d'alg\`ebres}, Mathematical interpretation of
  formal systems, North-Holland Publishing Co., Amsterdam, 1955, pp.~98--113.
  \MR{MR0075156 (17,700d)}

\bibitem{MR1373196}
Abraham Robinson, \emph{Non-standard analysis}, Princeton Landmarks in
  Mathematics, Princeton University Press, Princeton, NJ, 1996, Reprint of the
  second (1974) edition, With a foreword by Wilhelmus A. J. Luxemburg.
  \MR{MR1373196 (96j:03090)}

\end{thebibliography}

\end{document}
