% To: APIXLEY@THUBAN.AC.HMC.EDU
% Subject: most-algebras.tex
% Date: Thu, 3 Jul 1997 18:26:29 +0200 (MET DST)
% In-Reply-To: <01IKKEM4QI2ADVFQU0@THUBAN.AC.HMC.EDU> from "APIXLEY@THUBAN.AC.HMC.EDU" at Jun 27, 97 12:02:47 pm
% Mime-Version: 1.0
% X-sliced-and-diced-by: 'savemail' 0.1, Aug 30, 1997


% This is a latex2e file

\documentclass{amsart}
\usepackage{amsfonts,amssymb}
\advance\textheight8pt %\showthe\textheight

\title{Most  Algebras Have the Interpolation Property}
\author{Martin Goldstern}                                     

%\begin{abstract}
%{We show that for ``almost all'' algebras on a given set 
%$A$, every function on $A$ can be interpolated by a polynomial on any set 
%of cardinality  $\kappa$ (for reasonable $\kappa$).  }
%\end{abstract}

\date{July 3, 97}

\address{Technische Universit\"at\\
Wiedner Hauptstra{\ss}e 8-10/118\\
A-1040 Wien, Austria}
\email{Martin.Goldstern@tuwien.ac.at}
\subjclass{08A40, 54H99}
\keywords{polynomial function, infinite interpolation, meager set}

%\advance\textwidth1.2cm \advance\hoffset-.4cm
%\advance\textheight4.4cm \advance\voffset-2cm

\newcommand{\on}{{\restriction}}

\newtheorem{thm}{thm}[section]
\def\NEWTHEOREM#1 {\newtheorem{#1}[thm]{#1}}

                        \theoremstyle{plain}

\advance\textheight0.6cm

\NEWTHEOREM{Theorem}
\NEWTHEOREM{Lemma}
\NEWTHEOREM{Corollary}
\NEWTHEOREM{Observation}
\NEWTHEOREM{Fact}

\NEWTHEOREM{Reformulation}
                          % \theoremstyle{remark}
\NEWTHEOREM{Remark}
                        \theoremstyle{definition}
\NEWTHEOREM{Definition and Remark}
\NEWTHEOREM{Definition}
\NEWTHEOREM{Notation}
\NEWTHEOREM{Setup}
\NEWTHEOREM{Acknowledgement}
\NEWTHEOREM{Terminology}

\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\cut}{\cap}

%\newcommand{\mylabel}[1]{\marginpar{$\langle$#1$\rangle$}\label{#1}}

%\newcommand{\myref}[1]{\marginpar{#1}\ref{#1}}

%\let\myref\ref
%\let\mylabel\label

%\def\text{\hbox}
%\input mg
\renewcommand{\P}{{\mathfrak P}}
\newcommand{\A}{{\mathfrak A}}
\newcommand{\p}[1]{\tilde{#1}}
\newcommand{\OO}{{\mathcal O}}
\newcommand{\EE}{{\mathcal E}}
\newcommand{\CC}{{\mathcal C}}
\newcommand{\MM}{{\mathcal M}}
\newcommand{\BB}{{\mathcal B}}
\newcommand{\UU}{{\mathcal U}}
\newcommand{\JJ}{{\mathcal J}}
\newcommand{\NN}{{\mathcal N}}
%\def\proof{\medskip\noindent{\em Proof: }}

\newcommand{\limpl}{\Rightarrow}
%\newcommand{\QED}{\null~\hfill \ \ \ {QED}\break\bigskip}
%\newcommand{\qed}{\null~\hfill \ \ \ {qed}\break\bigskip}
\newcommand{\fn}{\operatorname{Fun}}
\newcommand{\fun}{\operatorname{Fun}}
\newcommand{\AAA}[1]{\Alg_\tau(#1)}
\newcommand{\VV}{{\mathbb V}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Alg}{\operatorname{Alg}}

\renewcommand{\O}{{\mathfrak{O}}}
\renewcommand{\o}[1]{{\O_{< #1}}}
%\newcommand{\iso}{\simequiv}
\newcommand{\iso}{\simeq}
\newcommand{\itm}{}
\newcommand{\pre}{}
\def\itm#1 {\item[({#1})]}
\def\pre#1^#2{F^1(#2, #1)}    % {}^{#2}{#1}}

\begin{document}

\begin{abstract}
{We show that for ``almost all'' algebras on a given set 
$A$, every function on $A$ can be interpolated by a polynomial on any set 
of cardinality  $\kappa$ (for reasonable $\kappa$).  }
\end{abstract}

\maketitle

\section{Introduction}

Let  $\A = (A,f_1, \ldots, f_n) $  be  
a universal algebra. 
Let   $F(A)$  be the set  of all functions from some $A^{t}$ to $A$
($t \in \{0,1,2,3\ldots\}$), 
$P(\A)$  the  set of polynomial functions. 

If $A$ is a finite set, then it is possible to have $F(A) = P(\A)$. In
fact, ``most'' algebras will have this property, see \cite{mur}. For
infinite $A$ this is impossible by cardinality considerations: 
$|F(A)|=2^{|A|}>|A|=|P(\A)|$. 

 We can still ask if we can ``interpolate'' all functions by
 polynomial functions on sufficiently large sets: 
Let $L_{k}P(\A)$ be  the set of ``$k$-local'' polynomial functions, 
  [that is, functions which can be interpolated by a polynomial on any
  set  containing less than  $1+k$ (i.e.,  $\le k$) 
   many points],
then  we have 
$$ F(A) = L_1 P(\A) \supseteq L_2 P(\A) \supseteq \cdots \supseteq
L_{\aleph_0} P(\A)$$
where $L_{\aleph_0} P(\A)$ is the set of all ``local'' polynomial
functions, i.e., functions that can be interpolated by a polynomial on
any finite set of points. 

This sequence can also be continued into the transfinite 
by  considering $L_{\kappa}P(A)$
for infinite cardinals $\kappa$. We define $L_\kappa P(\A)$ to be 
 the set of all functions 
from some $A^t$ into $A$  which can be interpolated by a polynomial 
on any set of $< \kappa $ many points. (So $L_{\kappa ^+}P(\A)$ is the
set of functions that can be interpolated by a polynomial on any set
of $\le \kappa $ many points.  See also
\ref{cfsection}.\ref{successorcardinal}) 

  Trivially, $\kappa < \kappa'$
implies $L_{\kappa } P(\A) \supseteq L_{\kappa ' } P(\A)$, and we have
$L_{\kappa}P (\A) = P(\A)$ whenever $\kappa > |A|$, but what else can
be said about these various degrees of interpolability?  
For which $\kappa $ can we have $F(A)= L_\kappa P(\A)$?
In
particular, are there algebras $\A$ on which all functions are
interpolable on all sets of cardinality smaller than $A$ itself, 
i.e., $F(A) = L_{|A|}P(\A)$? 

J\'anos Koll\'ar in \cite{kollar79} has shown that the answer is ``yes''
iff $|A| = |A|^{<|A|}$.  It is easy to see (e.g., from 
 \ref{arithmeticsection}.\ref{konig},  
 \ref{arithmeticsection}.\ref{hausdorff} and \ref{unions}.\ref{inc-e}),
 that $|A|=|A|^{<|A|}$ holds iff 
\begin{itemize}
\item[--]
       either $|A| = \aleph_0$,
\item[--] 
       or  $|A| = \kappa^+ = 2^ \kappa $
       for some infinite cardinal $\kappa$, 
\item[--] 
  or $|A|$ is a strongly inaccessible cardinal.   
\end{itemize}

We give a criterion to decide, for regular $\kappa$,
 when there are algebras $\A$ satisfying 
the $\kappa$-interpolation property (i.e., 
 $F(A) = L_{\kappa} P (\A)$), and  we show that a kind of ``0-1-law''
holds:  If one algebra on the underlying set $A$ has the
$\kappa$-interpolation property, then ``almost all'' algebras have
this property. 

For a fixed set $A$, a trivial counting argument (see \ref{cardarith})
gives an  
upper bound $\kappa^*(A)$
for the set  
$$K(A):=\{\kappa : \mbox{ there is an algebra $\A$ on the set $A$ with 
the $\kappa$-IP}\}.$$
In \ref{general} we show that this bound is sharp: For any 
$\kappa\le\kappa^*(A)$
there are algebras with the $\kappa$-IP.  Moreover, 
for a fixed similarity type $\tau$ and a fixed set $A$
we can define a topology on $\AAA A$, the set of algebras of type 
$\tau$ with underlying set $A$, which naturally induces an
ideal on $\AAA A$, and we will show that   
except for a set in this ideal, 
all algebras in $\AAA A$ have the $\kappa $-IP but not the
$\kappa ^+$-IP. In particular, 
for any 
$\kappa \le \kappa^*(A)$ there are many  $\A \in \AAA A $ with 
$F(A)=L_\kappa P(\A) \not= L_{\kappa ^+} P(\A)$. 

A variation of this argument (in \ref{no-baker-pixley}) gives many 
algebras on $A$ that have a majority function, and have the $\kappa$-IP
but not the $\kappa^+$-IP.   This stands in contrast to the case of 
finite $k$, where in the presence of a majority function
the $k$-IP implies the $k+1$-IP (and hence even the $\aleph_0$-IP). 

For the special case of a countable set $A$ 
we show in \ref{countable}
that the set of algebras on $A$ with the IP
is residual (=co-meager) in the Tychonoff topology.
   If $A$ is
uncountable then the set of algebras with the IP is dense but not
co-meager in the Tychonoff topology.   

Finally we investigate the case of unary algebras in section
\ref{one}. 

In an appendix we review basic notions from set theory.

  \medskip
{\noindent\bf Acknowledgements.}\ \    Part of this research was carried out
while I was supported by a Schr\"odinger fellowship from the  Austrian
Science foundation (FWF). 

I am grateful to the referee for pointing out many inaccuracies in
previous versions of this paper. 
\medskip

\begin{Setup}
\label{setup}
  We  fix a finite similarity type
$\tau=({t}_1, \ldots, {t}_n) $, where the ${t}_\ell$ are finitely 
many  natural numbers.
$\ell$ will always range over $1, \ldots, n$. 
  We
will assume that one of the ${t}_\ell$, say ${t}_1$, is at least 2. (See
section \ref{one}
for the case of unary algebras.)

To simplify the notation (but really without loss of generality) we
 assume  $ {t}_1=2 $. 

\begin{Notation}
\label{fnotation}
  Let $A$  be a nonempty (usually: infinite) set, ${t}$ a natural
  number (usually $>0$). 
   A ${t} $-ary
operation on $A $
is a function from $A^{t} $
into~$A $. We write $\dom(f)$ and $\ran(f)$ for the domain and range
of $f$. 

 We let 
\begin{eqnarray*}
F^{t}(A,B) &=& \{f: \dom(f) = A^{t}, \ \ran(f) \subseteq B \} \\
F(A,B) &= &\bigcup_{{t}=0}^\infty F^{t}(A,B) \\
\end{eqnarray*}
and we let $F^{t}(A) = F^t(A,A)$, $F(A)=F(A,A)$.

We will often have occasion to also consider partial operations, in
particular partial operations with small domain: 
\begin{eqnarray*}
\p F^{t}(A,B) &=& \{f: \dom(f) \subseteq  A^{t}, \ \ran(f) \subseteq B \} \\
\p F^{t} _{\kappa }(A,B) &=& \{f\in \p F^{t}(A,B): 
                |\dom(f)| < \kappa  \}    \\
\p F(A,B) &=& \bigcup_{{t} =1}^\infty \p F^{t}(A,B) \\
\text{ $\p F(A)=\p F(A,A)$, etc.}
\end{eqnarray*}

A function is a set of ordered pairs.  So if $f$ and $g$ are
functions, then $f \subseteq   g$ means that $f$ is a restriction of
$g$. 

If $f$ is a function, $A$ a set, then $f \on A$ is the restriction of
$f$ to $A \cap \dom (f)$, i.e., 
$$ f \on A := f \cap (A\times \ran(f))$$
 \end{Notation}

For any set  $ A $
we let $$ \AAA A := \{(A, f_1, \ldots, f_n): 
        \forall \ell\, f_\ell \in F^{{t}_\ell}(A)\}
$$

Since $A $
is usually held constant, we identify $(A, f_1, \ldots, f_n) $
with $ (f_1, \ldots, f_n) $.
\end{Setup}

\begin{Definition}
\label{poly}

If $\A = 
(A, f_1, \ldots, f_n)$ is in $\AAA A$, then we define the set 
of polynomial functions, $P(\A)$ or $ P(A, f_1, \ldots, f_n)$, 
as the smallest set of functions that contains
all the constant functions and projections, and is closed under the
(pointwise) operations ~$f_\ell$.  So $P(\A) \subseteq 
F(A)$.  

$\p P(\A) \subseteq \p F(A)$ is the set of all partial functions which
are restrictions of polynomial functions, $\p P^{t}(\A) 
= \p P(\A)\cut  \p F^{t}(A)$,  etc.
\end{Definition}

\begin{Definition}
Let $\kappa$ be an infinite cardinal. 
$\A = (A, f_1, \ldots, f_n)$ has the $\kappa$-IP if:  For all ${t}\in \omega$, 
all $f\in F^{t}(A)$, all $B \subseteq A^{t}$:
\begin{quote}
        If $|B| < \kappa$, then there is $g\in P^{t}(\A)$, 
        $g\on B = f\on B$.
\end{quote}
\end{Definition}

The next fact is just a reformulation of this definition. 
\begin{Fact}
\label{ipfact} 
  $\A = (A, f_1, \ldots, f_n) $
has the $\kappa$-IP % (i.e., 
                    % $F(A)=L_\kappa P(\A)$)
 iff $\p F_{ \kappa }(A) \subseteq \p P(\A)$. 
\end{Fact}

If the underlying set $A$ has size $\lambda  $, then there are of
course only $\lambda $ many polynomials on $A$, whereas
$|F(A)|={\lambda} ^ {\lambda} = 2^\lambda > \lambda $.
  It is still possible for $\A$ to have the $\kappa$-IP (for
  sufficiently small $ \kappa $), 
since the same polynomial can serve for many partial functions.  The
following observation, a straightforward  generalization of 
\cite[4.1]{kollar79}, 
gives an upper bound on $\kappa$:

\begin{Lemma}
\label{cardarith}
 Assume that $\A=(A, f_1, \ldots, f_n) $ has the
$\kappa$-IP, $|A|  \ge {\aleph_0} $.
Then $|A|^{{<} \kappa } = |A|$.
 (See \ref{arithmeticsection})
\end{Lemma}

\begin{proof}
  Clearly $\A$ does not have
the $|A|^+$-IP, so $ \kappa \le |A|  $. 

Let $\mu <\kappa $ be arbitrary, and fix a set $B \subseteq A $ of
size~$\mu$. We have $|F^1(B, A)| = |A| ^\mu$. Each $f\in F^1(B, A)$
is the restriction of some polynomial function 
$\bar f \in P^1(\A) $, and clearly $f \not= f' $ implies 
$\bar f \not= \bar f' $, so $ |A| = |P^1(\A)| \ge |A| ^\mu$. 
\end{proof}

\begin{Reformulation}\label{cardarith2}
Let $\kappa^*(A):= \min\{\kappa: |A|^{\kappa} > |A| \}$.   
Then $\A$ can have the $\kappa$-IP only if  $\kappa \le \kappa^*(A)$. 
\end{Reformulation}

In section~\ref{bigger} we will show that
this estimate is best possible.  That is:  If $\kappa \le
\kappa^*(A)$, then ``most'' 
algebras on $A$ will have the $\kappa$-IP.
(Our notion of ``most'' will depend on $\kappa$, see \ref{meagerdef}.)

\section{$\kappa$-topologies}

\label{bigger}

We will consider universal algebras of a fixed type
$\tau = ({t}_1, \ldots, {t}_n)$, over a fixed (infinite) set $A$, 
i.e., structures of the form 
$\A = (A, f_1, \ldots, f_n)$, where 
$f_\ell\in F^{{t}_\ell}(A)$.   We assume ${t}_1=2$.

\begin{Fact}
\label{01}
  If $A$ is  an infinite set of cardinality $\lambda$, 
$\kappa$ a cardinal $ \le \lambda$, then there is a continuous
increasing chain $(A_\gamma:\gamma < \kappa )$ such that
$\bigcup_{\gamma< \kappa } A_\gamma = A $ and 
$\forall \gamma<\kappa:      |A_{\gamma+1} \setminus A_\gamma | =
\lambda$, $|A_{\gamma}| = {\lambda} $.  (See section \ref{unions})
\end{Fact}
\begin{proof} Since $ \kappa \cdot \lambda  = \lambda  $, 
there is a bijection $f: \{ (\alpha, {\beta}) : \alpha <
  {\lambda}, {\beta} < \kappa  \} \to A$. Let $A_\alpha:= 
\{ f({\gamma}, {\beta}) : {\gamma} < {\lambda} , {\beta} < \alpha\}$. 
\end{proof}

\begin{Definition}
\label{defineu}
 Assume that $A$, $(A_\gamma:\gamma < \kappa)$ 
satisfy 
\begin{itemize}
\item[--]
 $A = \bigcup_ { {\gamma} < \kappa } A_ {\gamma} $, $|A|= \lambda $
\item[--]
  $ (A_\gamma:\gamma < \kappa)$ is  continuous and increasing
\item[--]
 $\forall \gamma<\kappa:      |A_{\gamma+1} \setminus A_\gamma | =
\lambda$, $|A_{\gamma}| = {\lambda} $.  
\end{itemize}
Then: 
\begin{enumerate}
\item
For any $\gamma < \kappa $ we let 
$$ \fn(\gamma) := \{(\eta_1, \ldots, \eta_n): 
        \text{each $\eta_\ell $ is in $F^{{t}_\ell}(A_\gamma, A)$}
\}$$
\item For $\eta = (\eta_1, \ldots, \eta_n)\in \fn(\gamma)$  we
define 
$$ \BB_{\eta}:= \{(f_1, \ldots, f_n) \in \AAA A : 
        \text{for each $\ell$, $\eta_\ell \subseteq f_\ell$}\}$$
\end{enumerate}
\end{Definition}

\begin{Definition and Remark}
\label{topfact}
 
The family $\{\BB_\eta:  \eta\in \fn(\gamma), \gamma < \kappa \}$
is a basis for a Hausdorff topology  on~$\AAA A $.   

For different choices of the family $(A_\gamma:\gamma< \kappa)$
we will of course get different topologies.   We call
each topology that is obtained in this way a 
{\em $\kappa$-topology}. 
\end{Definition and Remark}

\begin{Definition}
\label{meagerdef}
 Let $(X, \EE)$ be a
topological space.  We say that $Y \subseteq X$ is
$\kappa$-meager if $Y$ can be covered by $\kappa$
many nowhere dense sets (or equivalently, by
$\kappa$ many closed sets with empty interior).   We say that 
$Y \subseteq X$ is $\kappa$-residual (= $\kappa$-co-meager)
 if $X \setminus Y$ is 
$\kappa$-meager.
\end{Definition}

Clearly the $ \kappa $-meager sets form an ideal. (In  the 
general case this ideal may be improper, e.g.\ 
 if $ \kappa $ is too  large.  See \ref{tyremark} for a
less trivial  example.) 

\begin{Terminology}
Assume $\JJ$ is a proper ideal on a (nonempty) set $X$. 
Sets in $\JJ$ are considered to be ``negligible'' or 
``small'', while sets in the 
dual filter are considered to be ``large''. 

We express  this intuitive notion of small vs large  
also in the following way: 
  Let $p(\,\cdot\,)$ be any property.   We say
that ``$p(x) $ holds for $\JJ$-almost all $x \in X$''(or 
``$\JJ$-almost every ($\JJ$-a.e.)\ $x$ has property $p$'') iff 
$$ \{ x\in X: \hbox{$p(x)$ does not hold}\} \in \JJ.$$

This terminology is derived from measure theory: 
If $\mu$ is a measure, then the customary notion of 
``$\mu$-a.e.'' is in our language ``$\NN_\mu$-a.e.'', 
where $\NN_\mu$ is the ideal of $\mu$-null sets, i.e., 
$\NN_\mu =   \{Y \subseteq X: \mu(Y)=0\}$. 

If the definition of $\JJ$ is sufficiently ``natural'', then we may write 
``almost every'' instead of ``$\JJ$-almost every''.   
\end{Terminology}

Of course such a terminology would not be justified if $\JJ$ were
improper, i.e., if  $X\in \JJ$.   
The following lemma, a straightforward generalization of Baire's
theorem,  shows that all our ideals are proper. 

\begin{Lemma}
\label{baire}
 Let $\EE$ be a $\kappa $-topology on 
$\AAA A $.  Then $\AAA A $ is not $ \kappa  $-meager. 

Moreover,   no nonempty open set in  $\AAA A $  is 
$\kappa $-meager, i.e.,  the complement of any $\kappa$-meager 
set is still dense. 
\end{Lemma}

\begin{proof}
Let $\UU$ be an open set, and let $(\CC_\alpha:\alpha< \kappa)$ be
a family of closed nowhere dense sets.  
Let $\OO_\alpha := \AAA A \setminus \CC_\alpha$.  We have
to show that $\UU \cut \bigcap_{\alpha<\kappa } \OO_\alpha$ is 
not empty. 

Let $\eta_0= (\eta_{0, 1}, \ldots, \eta_{0, n})\in \fn(\gamma_0)$ 
be such that 
$\BB_{\eta_0} \subseteq \UU$. 
We will define sequences  $(\eta_\alpha:\alpha< \kappa)$ and 
$(\gamma_\alpha: \alpha  < \kappa )$, 
$\eta_\alpha = (\eta_{\alpha, 1}, \ldots, \eta_{\alpha, n})
\in \fn(\gamma_\alpha)$, with 
the following properties:
\begin{enumerate}
\item   $\forall \alpha\, \forall \beta :
        \alpha<\beta  \limpl \gamma _ \alpha < \gamma_ \beta $.
\item   $\forall \ell \, \forall \alpha\, \forall \beta :
        \alpha<\beta  \limpl \eta_{\alpha, \ell} \subset \eta_{\beta, \ell}$ 
        (hence $\BB_{\eta_\alpha} \supset \BB_{\eta_\beta}$).
\item   \label{continuous}
        $\forall \ell \, \forall \alpha$: If $\alpha$ is a
        limit ordinal, then $\eta_{\alpha, \ell} = \bigcup_{\beta<\alpha}
        \eta_{\beta, \ell}$ and 
        $ \gamma_\alpha = \sup\{\gamma_\beta: \beta < \alpha \}$.
\item  $ \forall \alpha $: $\BB_{\eta_{\alpha+1} }\subseteq \OO_\alpha$. 
\end{enumerate}
The construction of this sequence is straightforward.  
% (Strictly
% speaking, we apply here the induction theorem, see section \ref{induction}.) 
For limit steps, $\eta_\alpha$ is given by
\ref{continuous}, and in successor steps we have to
find $\gamma_{\alpha + 1 } $ and 
 $\eta_{\alpha+1} \in \fn(\gamma_{\alpha + 1 }) $ satisfying 
$\BB_{\eta_{\alpha+1} } \subseteq \OO_\alpha \cut  \BB_{\eta_\alpha}$.
This is possible because $\OO_\alpha$ is dense open and
$\BB_{\eta_\alpha}$ is open. 

Finally, let $f_\ell := \bigcup_{\alpha < \kappa }\eta_{\alpha, \ell} $.
Note that $\sup_{\alpha< \kappa  } {\gamma}_\alpha =
{\gamma} $, so $\dom(f_\ell) = \bigcup_{\alpha < \kappa }
A^{t_\ell}_\alpha  = A^{t_\ell}$, so 
$f_\ell    $ is a total function 
in $F^{{t}_\ell}(A)$.  Clearly  
$(f_1, \ldots , f_n) \in 
\bigcap_{\alpha < \kappa } \OO_\alpha \cut \UU$. 
\end{proof}

The following theorem shows that 
the condition $|A| = |A|^{{<}\kappa} $ is not
only necessary for an algebra on $A$ to have the $\kappa$-IP, but will
in ``most'' cases also be  sufficient. 

\begin{Theorem}
\label{general}
  Assume that $A$ is infinite, 
$\kappa$ an infinite  {\bf regular}
cardinal satisfying $|A| ^{{<}\kappa} = |A|$.  Then the set of
algebras on $A$ of type $\tau$    which have the
$\kappa$-interpolation property is $\kappa$-residual in any
$\kappa$-topology. 
\end{Theorem}

For example, choosing a set $A$ of size $ 2 ^{\aleph_0} $ and
$\kappa = {\aleph_1} $ we conclude that in any
${\aleph_1}$-topology on $A$, 
``almost all'' algebras on $A$ 
have the  property that all functions can be interpolated by a
polynomial on any countable set. 

\smallskip
{\small
Informally%
%\footnote{These  paragraphs can be skipped without loss of
%  continuity}%
,
 the main point of the proof is the following:
\\
  Fix a basic
set $\BB_\nu$, $\nu \in \fn(\alpha )$, 
$\nu = (\nu_1, \ldots, \nu_n)$.
   We have to find an $\eta= (\eta_1, \ldots, \eta_n)$ such that the
 basic set $\BB_\eta$ is a subset of $\BB_\nu$
and all algebras in $\BB_\eta$ have the
interpolation property with respect to sufficiently many partial
functions.  (For the details about bookkeeping see the formal proof below.)
It turns out that choosing $\eta_1$ appropriately will be sufficient
--- $\eta_2, \ldots, \eta_n$ can be chosen arbitrarily subject to the
requirement that they extend $\nu_2, \ldots, \nu_n$, respectively. 

   Assume first that we are only concerned with a single
partial unary function $ {\sigma} $. 
Recall that  $\nu _1:A_\alpha ^2 \to A$.
We can pick some element $c_{\sigma} \in A_{\alpha+1} \setminus
A_\alpha $ and 
extend $\nu_1$ to a function $\eta_1:A_{\alpha+1} ^2 \to A$ such that 
the function $x \mapsto \eta_1(c_{\sigma} , x)$ extends $ {\sigma} $. 
\\
Now
for any algebra $(A, f_1, f_2, \ldots\, )$ with  $f_1 $ extending
 $\eta_1$  the partial function $ {\sigma} $ will be
 the restriction of the
 polynomial $f_1(c_{\sigma} ,x)$.  

We can deal in this way  with many functions $ {\sigma} $
simultaneously, since $A_{\alpha +1} \setminus A_\alpha $ is quite
large. 

Now consider the case with a  function $ {\sigma} $ which is binary: 
the domain of $ {\sigma} $ is a set of pairs.  For each $a$ which
appears as a first coordinate in the domain of  $ {\sigma}  $ pick a
(distinct) constant $c_{ {\sigma} , a} \in A_{ \alpha +1}\setminus
A_\alpha $, and stipulate $\eta_1(c_{ {\sigma} , a}, b) =
{\sigma}(a,b)$ for all relevant $b$.  Then pick a new constant 
$c_{ {\sigma} } \in A_{ \alpha +1}\setminus A_\alpha $ and stipulate
$\eta_1(c, a) = c_{{\sigma}, a} $.\\
  Clearly, then 
$$ f_1( f_1(c, a), b) = f_1(c_{{\sigma}, a}, b) =
 {\sigma}(a,b) $$
for all $(a,b)\in \dom({\sigma})$ whenever $f_1$ is any function extending
$\eta_1$. 

  $k$-ary partial functions are treated
 similarly. 
This ends  our  informal description of the proof of theorem
\ref{general}.

}   % end \small
\smallskip

The proof of theorem \ref{general}
is based on the following lemma:

\begin{Lemma}
\label{isopen}
   Assume $|A|^{< \kappa }
= |A|$, and let $(A_\alpha:\alpha < \kappa)$ induce a
$\kappa$-topology on~$\AAA A$ as in \ref{defineu}. 

Let $\beta < \kappa$.  
Then the   set $$\UU_\beta  :=
\{(f_1, \ldots, f_n) \in \AAA A : 
        \p F_\kappa (A_\beta, A) \subseteq \p P(f_1, \ldots,  f_n)\}
$$ contains a dense open set. 
\end{Lemma}

(Note: $\UU_\beta$
 is the set of all algebras $\A$ such that, for any ${t}$, 
 every partial ${t}$-ary function whose domain is a 
subset of $A_\beta$ of
cardinality $< \kappa$ is the restriction of a polynomial
function over~$\A$.) 

\begin{proof}  First we need to define some notation: 
  If $f$ is a
binary function, then we define $f^{[2]}:= f$ 
and   $f^{[{t}+1]} (x_0, \ldots, x_{{t}} ) = 
f^{[{t}]}(f(x_0, x_1), x_2, \ldots, x_{t})$ for ${t} \ge 2 $. 

If $ \dom(g) \subseteq A^{t}$, $x \in A$, then we define the 
$({t}-1) $-ary
(partial)
function $g_{[x]}$ by 
$$ g_{[x]}(x_2, \ldots, x_{t}) := g(x, x_2, \ldots, x_{t})
\ \ \text{whenever $(x, x_2, \ldots, x_{t})\in \dom(g)$.}
 $$

\medskip

We will prove lemma \ref{isopen} by finding, for each basic
open set $\BB_\nu$, a basic open set  $\BB_\eta $ (i.e., we construct some
appropriate $\eta = \eta_\nu$ from $\nu$)
such that $\BB_\eta \subseteq \BB_\nu \cut \UU_\beta $.  (This is clearly
sufficient, as $\bigcup_{\nu} \BB_{\eta_\nu}$ is open, contained in
$\UU_{\beta} $, and meets every open set $\BB_\nu$.) 

So fix $\nu=(\nu_1, \ldots, \nu_n)$ with
$\dom(\nu_\ell)=A_\alpha^{n_\ell}$.
Wlog $\alpha \ge \beta$. 
  $\nu_1$ is a function from
$A_\alpha^2$ into~$A$. We will extend the function $\nu_1$
to a function $\eta_1$ on 
 $A_{\alpha+1 }^{2}$ such that 
\begin{itemize}
\item[$(**)$]
for every ${t}$ and for every 
${t}$-ary partial function 
$\sigma  
\in \p F^{t}_{\kappa}(A_\beta, A)$\\
\quad  there is a
$c$ in $A_{\alpha + 1} \setminus A_\alpha $ such that: \\
\quad \quad 
 for all 
$(x_1, x_2, \ldots, x_{t}) \in \dom(\sigma)$: 
  $\sigma (x_1, \ldots, x_{t}) = \eta_1^{[{{t}+1}]}(c, x_1, \ldots,
  x_{t})$. 

\end{itemize}

Before we construct $\nu_1$, let us notice that 
property $(**)$ is sufficient to ensure $\BB_\eta \subseteq \UU_{\beta}$:  
Indeed, let $(f_1, \ldots, f_n) \in \BB_\eta $ .  We have to show 
$(f_1, \ldots, f_n) \in \UU_{\beta} $, i.e., 
$\p F_\kappa(A_{\beta} , A) \subseteq \p P(f_1, \ldots, f_n)$. 

So let $
{\sigma} \in \p 
F_\kappa(A_{\beta} , A)$. Then $(**)$ guarantees that we can find some
$c$ such that 
$\sigma (x_1, \ldots, x_{t}) = \eta_1^{[{{t}+1}]}(c, x_1, \ldots, x_{t})$ for all 
$(x_1, x_2, \ldots, x_{t}) \in \dom(\sigma)$. Now the function
$f_1^{[t+1]}$   extends the partial function $\eta_1^{[t+1]}$, and
clearly the function 
$$(x_1, \ldots, x_n) \mapsto 
f_1^{[t+1]}(c, x_1, \ldots, x_n)$$ is a polynomial function. 
 This shows that $(**)$ will imply $\BB_ \eta \subseteq \UU_{\beta} $. 

Now we begin to define $\eta_1$:
 We will ``code'' 
partial functions in
$\p F_{\kappa}(A_\beta, A)  $ by elements of $A_{\alpha+1}\setminus
A_\alpha$. 
\relax From the assumption $|A|^{< \kappa } = |A|$ we get
$$| \p F_ \kappa (A_{\beta}, A) | \le |A|^{< \kappa } = |A| = 
|A_{\alpha + 1} \setminus A_\alpha |$$
(for the first inequality see \ref{arithmeticsection}.\ref{basic}, the
last equality is true by our choice of the sets $A_\alpha $, see
\ref{defineu}). 

So we can find   a   1-1 function 
$$T: \p F_{\kappa}(A_\beta , A) \to 
A_{\alpha + 1 } \setminus A_\alpha $$
There is a a function    $\eta_1:A_{\alpha + 1 }^2 
\to A$ satisfying the following properties:
\begin{itemize}
\itm a $\eta_1$ extends~$\nu_1$. 
\itm b $\eta_1(T(\sigma) , a) = \sigma(a) $  whenever $\sigma \in
        \p F^1_\kappa(A_\alpha, A)$, $a\in \dom(\sigma)$.
\itm c $\eta_1(T(\sigma) , a) = T(\sigma_{[a]}) $ if $\sigma \in
\bigcup_{{t} \ge 2}\p F_\kappa^{t}(A_\beta , A)$. 
\itm d $\eta_1(a, b) = $  arbitrary, otherwise.
\end{itemize}
(There are no contradictions between the requirements (b) and (c),
since $T$ is 1-1.  There are no contradictions between the
requirements (a) and (b) (or (a) and (c)), because $\dom(\nu_1)
\subseteq A^2_\alpha $, and $T({\sigma}) \notin A_\alpha $, so
$(T({\sigma}), a) \notin \dom(\nu_1)$.) 

Define $\eta_2$, \dots, $\eta_n$ arbitrarily extending $\nu_2$, 
\dots, $\nu_n$.   To prove property $(**)$, we show 
 that for all ${t}\ge 1$, 
all $\sigma \in \p F_\kappa^ {t}(A_\beta, A)$: 
$$ \eta_1^{[{{t}+1}]}(T(\sigma), a_1, \ldots, a_{t}) = 
\sigma( a_1, \ldots, a_{t}) 
\ \text {for all $(a_1, \ldots, a_{t})\in \dom(\sigma)$.}
$$
The proof is by induction on $t$: For  ${t}=1$ we have
$$ \eta^{[{t}+1]}_1(T(\sigma), a_1) =
        \eta_1(T(\sigma), a_1) = \sigma(a_1).$$
For ${t}>1$ we have:
\begin{eqnarray*}
\eta_1^{[{t}+1]}(T(\sigma), a_1, \ldots, a_{t})& =&
\eta_1^{[{t}]}(\eta_1(T(\sigma), a_1), \ldots, a_{t}) =
\\
\mbox{(by definition of $\eta_1$) }
&=&\eta_1^{[{t}]}(T(\sigma_{[ a_1]}), a_2, \ldots, a_{t}) =\\
\mbox{(by induction hypothesis) }
&=&
\sigma_{[a_1]}(a_2, \ldots, a_{t}) = 
\sigma(a_1, a_2, \ldots, a_{t}).
\end{eqnarray*}

\end{proof}

The following fact
explains the role that the regularity of $ \kappa $
plays: 
\begin{Fact}\label{regfact}
  If $(A_\alpha: \alpha < \kappa ) $ is increasing, $A =
\bigcup_{\alpha < \kappa } A_\alpha $, and $B \subseteq A^t$ has
cardinality $< cf(\kappa)$, then there is an $ \alpha < \kappa $
 such that $B
\subseteq A_\alpha ^t$.

In particular, if $ \kappa $ is regular then
every set set $ B \subseteq A^t $ of size $< \kappa $ is ``bounded'',
i.e. $B \subseteq A^t_\alpha $ for some $ \alpha < \kappa $. 
\end{Fact}
\begin{proof}
Define a function $f:B \to \o \kappa $ by 
$$ f(b_1, \ldots, b_t) =  \min\{ {\beta}: \{b_1,\ldots, b_t\}
\subseteq A_{\beta}\}$$
Then $\ran(f)$ cannot be cofinal in $\o \kappa $, so there is $
{\beta} < \kappa $ such that $ \forall b\in B: f(b) < {\beta} $. Thus,
$ \exists {\beta} < \kappa \, \forall (b_1,\ldots,b_t)  \in B\,\, 
 b_1, \ldots, b_t \in A_{f(b)} \subseteq A_{\beta} $, i.e., 
$B \subseteq A_ {\beta} $. 
 \end{proof}

% \medskip\noindent{\bf Proof of theorem \ref{general}:}
\begin{proof}[Proof of theorem \ref{general}]

Let $(\UU_\beta: \beta < \kappa)$ be the sets defined in \ref{isopen}.
The set 
$\bigcap_{\beta  < \kappa } \UU_\beta$ 
is $\kappa$-residual, so it is enough to show that every algebra in 
$\bigcap_{\beta  < \kappa } \UU_\beta$ 
has the $\kappa$-IP. 

Let $(A, f_1, \ldots, f_n)\in 
\bigcap_{\beta  < \kappa } \UU_\beta$ , and let $\sigma\in
 \p F^{t}_\kappa(A)$. Since $|\dom(\sigma)| < \kappa$, we can use the
 regularity of $ \kappa $ to conclude  
that 
 there is an  $\alpha$ such that 
$\dom( {\sigma} )  \subseteq A_\alpha^t$.

Hence $\sigma \in  \p F^{t}_\kappa(A_\alpha, A) \subseteq \p P(f_1, \ldots, 
f_n)$. \end{proof}

% Our next goal is to show that the set of algebras in $\AAA A$ 
% which even have the $\kappa ^+$-interpolation property is
% $\kappa$-meager.   As before, we fix an increasing continuous 
% sequence $(A_\alpha:\alpha < \kappa)$. 
% 
% 
% \begin{Definition}
% \label{fixdef}
% 
% \begin{enumerate}
% \item Let $f\in F^{t}(A)$, $a\in A$. We say that $a$ is a 
% {\em fixpoint}
% of $f$, if for all $b_2$, \dots, $b_{t}$ we have 
% $$ f(a, b_2, b_3\ldots, b_{t}) = 
%  f(b_2, a, b_3, \ldots, b_{t}) = 
% \cdots =
%  f(b_2, b_3, \ldots, b_{t}, a) = 
% a
% $$
% \item Let $f\in F^{t}(A)$, $a\in A_{\alpha+1}\setminus A_\alpha$.  
% We say that $a$ is a {\em local fixpoint} of $f$ if:
% of $F$, if for all $b_2$, \dots, $b_{t}$  in $A_{\alpha+1}$ we have 
% $$ f(a, b_2, b_3\ldots, b_{t}) = 
%  f(b_2, a, b_3, \ldots, b_{t}) = 
% \cdots =
%  f(b_2, b_3, \ldots, b_{t}, a) = 
% a
% $$
% \item 
% If $\A = (A, f_1, \ldots, f_n) \in \AAA A$, then we call an
%  element $a\in A$ a {\em [local] fixpoint}
%  of $\A$ if $a$ is a [local] fixpoint 
%  for every $f_\ell $, $\ell=1, \ldots, n$. 
% %  \item If $A = \bigcup_{\gamma  < \kappa } A_\gamma$ is an increasing
% %  union of sets, then we say that  $\A = (A, f_1, \ldots, f_n)$ has
% %  unboundedly many fixed points if the set of fixed points is not
% %  contained in any $A_\gamma$. 
% \item Let $L(\A)$ be the set of local fixpoints of $\A$.
% \end{enumerate}
% \end{Definition}
% 
% \begin{Fact}
% \label{fixfact}
%  If $a\in A$ is a fixpoint of $\A$, 
%  then for every
% nonconstant unary  polynomial $p(x)\in P^1(\A)$  we have $p(a)=a$. 
% 
% Moreover, if $a\in A_{\alpha+1}\setminus A_\alpha$ 
% is a local fixpoint of $\A$, then for every
% nonconstant unary  polynomial $p(x)\in P^1(\A)$  with coefficients 
% in $A_{\alpha+1} $ we have $p(a)=a$. 
% 
% \end{Fact}
% 
% \begin{Fact}
% \label{fixfact2}
% 
% If $a\in A_{\alpha+1}\setminus A_\alpha$ 
% is a local fixpoint of $\A$, 
% and $\eta_\ell = f_\ell\on A_{\alpha_1}^{{t}_\ell}$, 
% $\eta = (\eta_1, \ldots, \eta_n)$, then for any $\A'\in 
% \BB_\eta$ (see \ref{defineu}), $a\in L(\A')$ (see \ref{fixdef}). 
% \end{Fact}
% 
% 
% 
% 
% 
% 
% \begin{Theorem}
% \label{fixthm}
%  Let $\OO$ be a $\kappa$-topology on $A$, induced
% by $A=\bigcup_{\gamma < \kappa } A_\gamma $ as in \ref{01}. 
% Let $B:=\{b_\alpha : \alpha < \kappa \}$ be any set satisfying
% $b_\alpha \in A_{\alpha + 1 } \setminus A_\alpha$.  Then the set 
% $$M := 
% \{ \A: \exists \alpha L(\A) \cap B \subseteq A_\alpha \}$$
% is $\kappa$-meager, or equivalently, 
% $$ R:= \{\A: \forall \beta<\kappa\, \, \exists \alpha < \kappa:
% \beta <\alpha, L(\A)\cap B \cap (A_{\alpha+1}\setminus
% A_\alpha) \}$$
% is $\kappa$-residual. 
% \end{Theorem}
% 
% \begin{proof} 
% Let $\UU_{\gamma}:= 
% \{ \A: \exists \alpha\ge \gamma  
% \exists a\in L(\A) \cap B \cap ( A_{\alpha+1} \setminus A_\alpha)\}$.
% By \ref{fixfact2}, $\UU_\gamma$ is open, and it is easy to 
% see that $\UU_\gamma$ is dense.   Hence the set 
% $$R = \bigcup_{\gamma <\kappa} \UU_\gamma $$
% is $\kappa$-residual.   
% 
% \end{proof}
% 
% 
% 
% 
% \begin{Corollary}
% \label{fixcor}
%  In any $\kappa$-topology on $\AAA A $ the set of
% algebras which has the $\kappa$-IP but not the 
% $\kappa^+$-IP is
% $\kappa$-residual.
% \end{Corollary}
% \begin{proof} Let $(b_\alpha: \alpha < \kappa)$ and $R$ be as in the 
% theorem. 
% Let  $(c_\alpha: \alpha < \kappa)$ be a sequence satisfying
% $c_\alpha \not= b_\alpha$ for all $\alpha < \kappa$, and 
% let $f$ be the
% partial mapping $b_\alpha \mapsto c_\alpha$. 
% 
% $f$ is a function whose domain has size $\kappa$, and we claim 
% that $f$ cannot be extended to a polynomial function on any 
% algebra $\A\in R$.  
% 
% So fix $\A\in R$, and let $p\in P(\A)$, say with coefficients in 
% $A_\beta$. We can find $\alpha > \beta$ such that $b_\beta$
% is a local fixpoint of $\A$.  So $p(b_\beta)=b_\beta \not= c_\beta
% = f(b_\beta)$, hence $f \not \subseteq p$. 
% 
% \end{proof}

\section{The Baker-Pixley Theorem}
It is known that the $k$-IP and the $k'$-IP can  coincide 
 for natural numbers $k\not= k'$.  For example (see \cite{BP75})
\begin{Theorem}
Let $m:A^3 \to A$ be a majority function, i.e.: 
$$ \forall x, y \in A: \quad 
m(x, x, y)=m(x, y, x)=m(y, x, x) = x$$
 Then: 
\begin{quote}
If 
$\A:=(A, f_1, \ldots, f_n, m)$ has the 3-IP, then 
$\A$ has the $\aleph_0$-IP.
\end{quote}
\end{Theorem}

We now show that such an implication  $\kappa$-IP $\Rightarrow$
$\kappa'$-IP does not hold for infinite cardinals. 
(Except for the trivial cases: $\kappa \ge \kappa'$, or 
$\kappa > \kappa^*(A)$.)

We will need the following concept:

\begin{Definition}
Let $(A_{\gamma}: {\gamma} < \kappa)$ be as in \ref{defineu}, $f:A^t\to A$.
We say that $\alpha < \kappa$ is a {\em ceiling} for $f$ if for all 
$b \in A_{\alpha+1}\setminus A_\alpha$ and for  all 
$a_2, \ldots, a_t\in A_{\alpha+1}$ we have:
$$ \{f(b, a_2, \ldots, a_t), 
 f(a_2, b,  \ldots, a_t), \ldots, 
 f(a_2, a_3,  \ldots, b) \} \subseteq A_{\alpha +1}.$$

We say that $\alpha$ is a ceiling for $\A = (A, f_1, \ldots, f_n)$ if
$\alpha$ is a ceiling for each $f_\ell$.  We let 
$cl(\A)$ be the set of all ceilings for $\A$. 
\end{Definition}

\begin{Theorem}\label{no-baker-pixley}
Let $\tau = ({t}_1, \ldots, {t}_n)$ be a similarity type, ${t}_1=2$. 
\begin{enumerate}
\itm 1 
  In any $\kappa$-topology on $\AAA A $ the set of
 algebras which have the $\kappa$-IP but not the 
 $\kappa^+$-IP is
 $\kappa$-residual.
\itm 2 Moreover: Let $(A_\gamma: \gamma < \kappa)$ be as in 
\ref{defineu}, ${t}_0\in \omega$.  Let $m:A^{{t}_0}\to A$ be any function
satisfying $m[A_\alpha^{{t}_0}] \subseteq A_\alpha$ for all $\alpha$ 
(i.e., $m(a_1, \ldots, a_t)\in A_\alpha $ whenever $a_1, \ldots, a_t
\in A_\alpha $).  
\\ (It is easy to find a majority function $m:A^3\to A$ with this
property.)\\
Let $\kappa \le \kappa^*(A)$ (see \ref{cardarith2}). Then the set 
$$\bigl\{(f_1, \ldots, f_n) \in \AAA A : 
\text{$(A, m, f_1, \ldots, f_n)$ has the 
 $\kappa^+$-IP}\bigr\}$$ 
is $\kappa$-meager. 
\end{enumerate}
\end{Theorem}

\begin{proof}
By \ref{general}, (2) implies (1). 

First note that $cl(A, m, f_1, \ldots, f_n) = 
cl(A, f_1, \ldots, f_n) $ by our assumption on $m$. 

We have:
\begin{enumerate}
\item For every $\alpha<\kappa$, the set 
$ \{ \A: \alpha \in cl(\A)\}$
is clopen.\\ \relax
 [Why? If $\A=(f_1, \ldots, f_n) $ and 
  $\A'=(f'_1, \ldots, f'_n) $ agree up to $\alpha$, i.e., 
   $f_\ell\on A_\alpha^{{t}_\ell} = 
   f'_\ell\on A_\alpha^{{t}_\ell}$ for all $\ell $, then 
   $\alpha \in cl(\A)$ iff $\alpha \in cl(\A')$.]
\item The sets
$ {\mathcal D}_\alpha := \{ \A: \exists \beta > \alpha \, \, \, \beta
\in cl(\A)\}$ 
are open and dense. \\ \relax
  [Given $\eta\in \fn(\gamma)$, it is easy to find
an extension $\eta'$ such that $\BB_{\eta'} \subseteq
 {\mathcal D}_\alpha  $] 
\item The set $\{\A: 
\text{$cl(\A)$ is bounded in $\kappa $}\}$ is $\kappa$-meager
in $\AAA A$. 
\\ \relax
[Its complement  is equal to 
$\bigcap_{\alpha < \kappa}  {\mathcal D}_\alpha$.]
\end{enumerate}

  Now let $cl(\A)$ be unbounded.  We will show that 
$\A$ cannot have the  
             $\kappa^+$-\hskip0cm interpolation 
property:

For each $\alpha < \kappa$ pick $a_\alpha\in A_{\alpha+1} \setminus
A_\alpha$.

Let 
$f$ be the partial function that maps each 
 $a_\alpha $ to $a_{\alpha+1}$. 

If  $p$ is a nonconstant 
polynomial with coefficients in $A_\beta $, then we can
find $\alpha> {\beta}$ in $cl(\A)$. Clearly we must then have
$p(a_\alpha) \in A_{\alpha + 1}$, but 
$a_{\alpha+1} \in A_{\alpha+2} \setminus A_{\alpha+1}$, so $p(a_\alpha
) \not= a_{\alpha+1}$. 

\end{proof}

\section{The Tychonoff Topology}

Although the topologies presented in the previous section are very
convenient to work with, they are rather unnatural since they depend
on a specific arbitrary representation  $ A = \bigcup_\alpha
A_\alpha$.
In this section we will investigate $\AAA A $ with the natural
topology: 

\begin{Definition}
Consider $A$ as a discrete
topological space.  
The product (or ``Tychonoff'') topology on $\AAA A$
is generated by sets of the form
$$ \BB_\eta 
:=  \{(f_1, \ldots, f_n): \forall \ell \,\,
f_\ell \supseteq \eta_\ell\}$$
where $\eta$ ranges over the set 
$$\fun := 
\{\eta: \eta= (\eta_1, \ldots, \eta_n), \, \forall \ell\, \, 
\eta_\ell\in F^{{t}_\ell}_{{\aleph_0}} (A)\}, $$
i.e.,  over  all sequences of the form 
$\eta= (\eta_1, \ldots, \eta_n)$, where each 
$\eta_\ell$ is a partial
finite ${t}_\ell$-ary function. 
\end{Definition}

A set is {\em meager} (also called: of the first category) if it can
be covered by countably many [closed] nowhere dense sets, and a set is
{\em residual} (or co-meager) if it contains a countable intersection
of dense open sets. 

The following well-known  fact can be proved similarly to \ref{baire}.

\begin{Fact}
\label{tyfact}
 If $A$ is any (infinite) set, then no nonempty open set in
$\AAA A$  is  meager in the Tychonoff topology.
\end{Fact}

However, $\kappa$-meager sets are often trivial:

\begin{Remark}
\label{tyremark}
 If the continuum hypothesis holds, then for any
countable set $A$ we have $|\AAA A| = {\aleph_1}$, so $\AAA A$ is
trivially ${\aleph_1}$-meager. 

If $A$ has cardinality ${\aleph_1}$, 
then irrespective of the
underlying cardinal arithmetic, $\AAA A$ is ${\aleph_1}$-meager in the
Tychonoff topology.
\end{Remark}

\begin{proof}  The first remark is clear. 

To prove the second remark, let $A$ be of size $ \aleph_1 $. 
So we can  write $A$ as an increasing continuous union $A =
\bigcup_{\alpha  < \omega_1 } 
A_\alpha$, where each $A_\alpha $ is countable.

 For $\alpha  < \omega_1$ let 
$$ {\CC}_\alpha := \{(f_1, \ldots, f_n)\in \AAA A: 
\text {$A_\alpha$ is a subalgebra of $(A, f_1, \ldots, f_n)$}\}$$
We have to check that 
\begin{enumerate}
\item ${\CC}_\alpha $ is closed. 
\item ${\CC}_\alpha $ does not contain any nonempty open set, hence
  is nowhere dense. 
\item $\bigcup_{\alpha < {\omega_1} } {\CC}_\alpha = 
\AAA A$. 
\end{enumerate}

Proof of 1: Let $(f_1, \ldots , f_n) \notin  \CC_\alpha $.
 So there are 
 $\ell $ and
$a_1, \ldots, a_{t_\ell} \in A_\alpha $ with $f_\ell(a_1, \ldots,
a_{t_\ell}) \notin A_\alpha $. Define $\eta\in \fun$ by letting
$\eta_\ell$ have domain $\{ 
(a_1, \ldots, a_{t_\ell}) \} $ and range 
$\{ f_\ell(a_1, \ldots, a_{t_\ell}) \} $, and let $\eta_i  =
\emptyset$  for $i\not= \ell$. Then $\BB_\eta \cap
\CC_\alpha  = \emptyset$ and $(f_1, \ldots, f_n) \in \BB_\eta$,  so we have 
found a basic neighborhood of $(f_1, \ldots, f_n)$ disjoint from
$\CC_\alpha $.  This shows that the complement of $\CC_\alpha $ is
open. 

Proof of 2: We have to show that there is no $\eta$ such that $\BB_\eta
\subseteq \CC_\alpha $.  Easy.

Proof of 3: Let $\A =(A,f_1, \ldots, f_n)\in \AAA A$.   We have to find $
\alpha $ such that  $\A \in \CC_\alpha $. For each $ \alpha <
{\omega_1} $  and each $\ell \in \{1, \ldots, n\}$ we can find an
ordinal $ {\beta} =  {\beta} (\alpha, \ell) < \omega_1 $ such that 
$\ran(f\on A_\alpha^{t_\ell}) \subseteq A_{\beta} $ (since 
$\ran(f\on A_\alpha^{t_\ell})$ is countable).  Let 
$ {\beta}(\alpha):= \max ( \alpha+1, {\beta}(\alpha, 1), \ldots,
{\beta}(\alpha, n))$.  Define a countable 
sequence $ {\gamma}_0  < {\gamma}_1
< \cdots < {\omega_1}  $ by requiring $ {\gamma}_{n+1} =
{\beta}({\gamma}_n)$. Let $ {\gamma} = \sup \{ {\gamma}_0, {\gamma}_1,
\ldots \}$, then $ {\gamma} < {\omega_1} $ since $ {\omega_1} $ is
regular.    Now for each $n$  we have 
$\ran(f_\ell\on A_{{\gamma} _n}
^{t_\ell}) \subseteq A_{{\gamma}_{n+1}  } \subseteq  A_{{\gamma} } $, so 
$\ran(f_\ell\on A_{\gamma}^{t_\ell}) \subseteq A_{{\gamma} } $, which means
$\A \in \CC_{\gamma} $. 

\end{proof}

So how many algebras will have the $\kappa$-interpolation property?
\relax From 
our result in the previous section we can deduce the following
% trivial
corollary: 

\begin{Observation}
\label{denseOb}
Using the Tychonoff topology on $\AAA A$, we have:
 \begin{enumerate}
 \item Let $|A|^{< \kappa } = |A|$. Then the set of
algebras in $\AAA A$ that have the $\kappa$-IP is dense.
\item However, if $A$ is uncountable, then the set of algebras with 
the $2$-IP is  not residual.
\end{enumerate}
\end{Observation}
\begin{proof}  (1) The set of algebras with the $\kappa$-IP is dense in 
any $\kappa$-topology, so also dense in the (coarser) 
 Tychonoff topology.

\noindent  
(2)  
Let $\MM$ be a meager set in $\AAA A$, then we can find a family 
 $(\MM_i: i\in \omega) $ of closed sets  
 such that
$ \MM \subseteq \bigcup_i \MM_i$.  Define a sequence 
$(\eta_i: i \in \omega)$,  
$\eta_i\in \fun$, 
$\eta_i = (\eta_{i, 1}, \ldots, \eta_{i, n})$, 
 such that for all $i$:
\begin{itemize}
\item $\BB_{\eta_i}\cap \MM_i = \emptyset$
\item $\eta_{i, \ell} \subseteq  \eta_{i+1, \ell}$, 
        for $\ell=1, \ldots, n$ (i.e.,  $\BB_{\eta_i} \supseteq 
                        \BB_{\eta_{i+1}}$).
\end{itemize}
[Given $\eta_i$, it is possible to find the required $\eta_{i+1}$
 because $\MM_{i+1}$ is nowhere dense.]

Now let $B \subseteq A $ be a countable set such that for all
$i \in \omega$, all $\ell\in \{1, \ldots, n\}$ the range of 
$\eta_{i, \ell}$ is contained in $B$.  We can find an algebra
$\A = (f_1, \ldots, f_n)$ such that for all $\ell=1, \ldots, n$:
\begin{itemize}
  \item[--] For all $i\in \omega$: 
  $\eta_{i, \ell} \subseteq f_\ell$, 
  i.e., $\A \in \bigcap_{i\in \omega} \BB_{\eta_i}$. 
  \item[--]  $\ran (f_\ell) \subseteq B$. 
\end{itemize}
Now since $B$ is countable and $A$ is uncountable, $B \not=A$. 
But any nonconstant polynomial in $P(\A)$ takes only values in 
$B$, so clearly $\A$ does not have the IP; in fact, 
there are functions that cannot be interpolated on 2 points. 
 By construction, 
$\A \notin \MM$. 

\end{proof}

For countable sets $A$ the situation is different:

\begin{Theorem}
\label{countable}
 Let $A$ be a countable set.  Then the set of
algebras on $A$ which have  the interpolation property is residual
in the Tychonoff topology on~$\AAA  A $.
\end{Theorem}

\begin{proof}  Let $A = \bigcup_j A_j$, where the $A_j$ form an increasing 
sequence of finite sets satisfying 
$$| A_{j+1} \setminus A_j | > | F^{\le j}(A_j) | $$
(where 
$ F^{\le j}(A_j) = \bigcup_{m\le j}  F^{m}(A_j)$). 
Similarly to \ref{isopen} we can now show that each set 
$$ \UU_j:= 
\{(f_1, \ldots, f_n) \in \AAA A : 
        \p F^{\le j} (A_j) \subseteq \p P(f_1, \ldots,  f_n)\}
        $$
contains a dense open set, so the complement of 
$ \bigcap_j \UU_j $ is meager. 
Now let  $\A \in \bigcap_j \UU_j$, $\sigma \in F^{t}_i(A)$, $i< \omega$. 
Then there is some $n$ such that $\sigma\in 
  \p F^{\le j} (A_j) 
  $, so $\sigma\in \p P(\A)$.
\end{proof}

\begin{Remark}
One can argue that this topology does not capture the ``right'' notion
of smallness. After all, many interesting sets, for example 
$\AAA A \cap \VV$, for any nontrivial variety $\VV$, will be 
(closed and) 
nowhere dense. 
\end{Remark}

\section{Unary algebras}
\label{one}

If ${t}_1 = \cdots = {t}_n = 1$, then for any algebra of type 
$\tau = ({t}_1, \ldots, {t}_n) $, all polynomials will depend at most on 
one variable, so the best one can hope for is $F^1(A) \subseteq P(\A)$. 

Since there are, irrespective of the size of $A$,  at most countably many 
(unary) polynomial functions that are not constant, 
we will consider only countably infinite algebras. 

\begin{Definition}
We say that $a\in A$ is a fixpoint of 
$\A = (A, f_1, \ldots, f_n)$ iff $f_\ell(a)= a$ for 
$\ell=1, \ldots, n$. 
\end{Definition}

\begin{Observation}
\label{obser}
Let $A$ be countable, $\tau=(1, \ldots, 1)$. Then the set of algebras
with a fixpoint is open dense in the Tychonoff topology.   Hence
the set of algebras with the interpolation property 
is  nowhere dense. 
\end{Observation}

However, if we consider algebras with at least one injective function
without cycles, then the picture changes: Let $\tau= (1, \ldots, 1)$, 
with $n\ge 2$ many 1's. 

\begin{Definition}
\label{taufdef}
 Let $f_*:A \to A$. We define 
$$ \AAA {A, f_*} :=
\{(A, f_*, f_2, \ldots, f_n): f_2, \ldots f_n\in F^1(A)\}.$$
\end{Definition}

As a subset of $\AAA A$, 
$ \AAA {A, f_*}$ carries the induced topology.  Since we keep $A$ and
$f_*$ fixed, we identify 
$(A, f_*, f_2, \ldots, f_n)$ with $(f_2, \ldots, f_n)$.

\begin{Theorem}
\label{unary}
 Let $f _*: A \to A$ be 1-1 and without cycles.
Then the set of algebras in $\AAA{A, f_*} $
for which the inclusion $\p F^1_{ {\aleph_0} }(A) \subseteq P^1(\A)$
holds
 is residual in $\AAA{A, f^*}$.   \\
In other words:   Almost all algebras have the $ {\aleph_0}$-IP
with respect to unary functions. 
\end{Theorem}
\begin{proof}
For any $ \sigma \in \p F^1_{ {\aleph_0} }(A)$ let 
$$\UU(\sigma):= \{(f_2, \ldots, f_n): \sigma \notin \p P(A, f_*, f_2, 
\ldots, f_n)\}.$$
Note that $\UU(\sigma)$ is closed and that there are only countably many
possible values for~$\sigma$. Hence it is enough to show that
$\UU(\sigma)$ does not contain an open set. 

So fix $\nu_2$, \dots, $\nu_n$.  We will find $(f_2, \dots, f_n)\in 
\BB_{\nu_2, \ldots, \nu_n} \setminus  \UU(\sigma)$. 

We will write $f^{(j)}$ for the $j$-th iteration of $f$:
$f^{(1)}=f$, $f^{(j+1)}= f\circ f^{(j)}$. 
First find $j$ such that 
$\forall a \in \dom(\sigma): f_*^{(j)}(a)\notin \dom(\nu_2)$. 
Let $\eta_2:= \nu_2 \cup \{(f_*^{(j)}(a), \sigma(a)): a \in
\dom(\sigma)\}$.  $\eta_2$ is still a function, since $f_*^{(j)}$ is
1-1.  Clearly, for any $f_2 \supseteq \eta_2$ we have
$f_2 \circ f^{(j)}_* \supseteq \sigma$, and $f_2 \circ f_*^{(j)}$
is a polynomial function.
\end{proof}

\section{Appendix:  Set-theoretical Background}

We collect here a few notations,   definitions and results 
 from basic set theory
that can be helpful to understand the paper.  The reader is referred
to the first chapters of \cite{J} and \cite{kunen} for more
information.     We assume that the reader is familiar with the
concepts of cardinals and ordinals, as discussed in basic algebra
books (e.g.\ \cite[0.4]{graetzer}). 

\subsection{Ordinals, cardinals and cofinality}
\label{cfsection}

\begin{enumerate}
\item We let $\O$ be the class of all ordinals, $\o \alpha  = \{
  {\beta}\in \O: {\beta} < \alpha \}$. 
% \item
 We reserve the variables $ \alpha $, $ {\beta} $, $ {\gamma} $,
  $ {\delta} $, $ \varepsilon  $ to range over the class of ordinals
  (e.g., ``$ \forall \alpha\, \exists {\beta}: \ldots$'' is an
  abbreviation for $ \forall \alpha \in \O  \, \exists {\beta} \in \O:
  \ldots $'')
\item For every set $A$ there is an ordinal $ \alpha $ and a bijection 
  from $A$ onto $\o \alpha $. We let $|A|$, the cardinality of $A$, be
  the least $ \alpha $ with this  property. 
%  $$ |A| = \min \{ \alpha:    A \iso \o \alpha \} $$
% \item
 An ordinal $ \kappa$ is called a cardinal if $ \kappa =|A| $ for
  some $A$.  All infinite  cardinals are limit ordinals. 
%\item
 We will reserve the variables $ \kappa $, $ {\lambda} $, $\mu$
  for infinite cardinals. 
\item If $ \kappa $ is a cardinal, then we let $ \kappa ^ + $ be the
  smallest cardinal $> \kappa $ (the ``cardinal successor'') of $
  \kappa $: \label{successorcardinal}
  $$ \kappa ^ + = \min \{ {\lambda}:  {\lambda} \mbox{ is a
    cardinal},  {\lambda}   > \kappa  \, \} $$
\item $ {\lambda}  $ is called a ``successor cardinal'' if $ {\lambda} =
  {\kappa }^+$, for some (uniquely determined) cardinal $ \kappa  $,
  and ``limit cardinal'' otherwise.    
  % For example, the cardinal
  % $ \aleph_\omega :=
  %  \sup \{ {\aleph_0}, \aleph_1, \aleph_2, \ldots \}$ is the first
  % limit cardinal $> {\aleph_0} $. 
\item All the finite natural numbers are cardinals. 
  $ {\aleph_0} $ is the smallest infinite cardinal.
  We let $ \aleph_1 = ({\aleph_0})^+$, $ \aleph_2 = (\aleph_1)^+$,
  etc.   We may write $\omega_1$ for $\aleph_1$.  We write $ \omega $
  for the set of natural numbers. 
\item 
For any partial order $\A=(A, \le)$ we call a set $B \subseteq A$
``cofinal'' if $ \forall a \in A\, \exists b \in B: a \le b$.   
% A function $f: C \to A $ is called cofinal in $\A$ iff the range of $f$
% is cofinal  in $A$. 
% The cofinality of $\A$ is the smallest cardinality of a cofinal set. 
\item 
For any (wlog limit) ordinal $ \alpha $ we let $cf(\alpha)$ be the
cofinality of 
$\o \alpha $: 
$$ cf ( \alpha ) = \min \{ |B| : B \subseteq \o \alpha \hbox { is
  cofinal}\}$$
Equivalently, $cf(\alpha )$ is the smallest cardinal $ \kappa $ such
that there is a ((strictly) monotone) function 
$ f: (\o \kappa,\le) \to
(\o \alpha,\le) $
whose range is cofinal in  $ \o \alpha $. 
% \\
% $cf( \alpha )$ is only interesting for limit ordinals, as $cf (\alpha
% + 1)  = 1  $. 
\item 
We call an infinite cardinal $ \kappa$ ``regular'' if $ cf (\kappa ) =
\kappa $, and
``singular'' otherwise.   Equivalently,  $ \kappa $ is
singular iff there is $ {\lambda} < \kappa $ and a family $(A_ \alpha
:\alpha < {\lambda} )$ such that $|A_\alpha |< \kappa $ for all
$\alpha$,  and $|\bigcup_\alpha  A_\alpha | = \kappa $. 
\item  $ {\aleph_0} $  and all
successor cardinals (such as  $ \aleph_1$) are regular.
\end{enumerate}

\subsection{Cardinal Arithmetic}
\label{arithmeticsection}

\begin{enumerate}
\item Recall that for any sets $A$, $B$
  we defined  $\pre B^A$ to be the set of all functions
  from $A$ into $B$. 
\item 
For (finite or infinite)
cardinals $ \kappa $, $ {\lambda} $,  we let $ \kappa ^{\lambda} $
be the cardinality of the set $\pre{ \o \kappa } ^ {\o {\lambda} }$. 
Equivalently, choose any sets $K$, $L$ of cardinalities $ \kappa $ and
$ {\lambda} $, respectively, and let $ \kappa ^ {\lambda} = | \pre
K^L|$. 
\item 
We let $ \kappa ^ {< {\lambda} } = \sup\{ \kappa ^ \mu: \mu < {\lambda} \}$ 
(In particular, $ \kappa ^ {< {\lambda} ^+} = \kappa  ^ {\lambda} $.)
\item \label{konig}
Cantor's theorem tells us $2^{\lambda} > {\lambda} $, and K\"onig's
theorem says that even $ {\lambda} ^ {cf({\lambda})} > {\lambda} $
(for infinite $ {\lambda} $). In particular, $ {\lambda}  ^{<{\lambda}} >
{\lambda}  $ if $ {\lambda} $ is singular.
\item 
If $n$ is a finite cardinal, $ \kappa $ an infinite cardinal, then $
\kappa ^n = \kappa $, so $ \kappa ^{<\omega } = \kappa $. 
\item \label{hausdorff}
Let $\P(X)$ be the power set of $X$.   It is easy to see that $|\P(X)| =
2^{|X|}$.   If $ \kappa $ is infinite, we have moreover $2^ \kappa =
 \kappa ^ \kappa  $ and even $2^\kappa = (\kappa^+)^\kappa  $ (see
 also \ref{unions}.\ref{inc-d}).
\item \label{basic}
If $|L| = {\lambda} $ and  $|M| = \mu$ are infinite,
  $t$ a natural number $>0$, then 
$$ | F(L,M)|  = | F^t(L,M)|   = | F^1(L,M)|  = \mu^ {\lambda} $$
In particular, $ |F(L)| = {\lambda} ^ {\lambda} = 2 ^ {\lambda} $.
For  $ \kappa \le {\lambda}^+$ we have 
$ | \p F_\kappa (L,M)|  = {\lambda}^{<\kappa}\cdot \mu^{<\kappa}$,
in particular $|\p F_\kappa(L)| = {\lambda}^{<\kappa}$. 
\item 
$ \kappa $ is a limit cardinal iff $ {\lambda} ^+ < \kappa $ is true
for any $ {\lambda} < \kappa $.
We call a cardinal $ \kappa $ a ``strong limit cardinal'' iff
$2^{\lambda} < \kappa $ is true for any $ {\lambda} < \kappa $, or
equivalently, iff $2^{<{\kappa }}={\kappa } $.    
\item 
We call $ \kappa $ ``strongly inaccessible'' iff $ \kappa $ is an
uncountable regular strong limit cardinal.  
%      While it is easy to construct
% (arbitrarily large) regular cardinals and (arbitrarily large) strong
% limit cardinals,  it is not possible to prove
% (within the usual  mathematical framework, the ZFC axioms) that
% strongly inaccessible cardinals exist. 
\end{enumerate}

\subsection{Increasing unions}
\label{unions}
\begin{enumerate}
% If $G$ and $H$ are functions, $ {\delta} $ an ordinal, then there is a
% unique function $f$ with domain $\o {\delta} $ such that 
% the following holds:  
% 
% \begin{itemize}
% \item Whenever $ \alpha $ is a limit ordinal $< {\delta} $, then 
%   $ f(\alpha) = G( f \on (\o \alpha )  )$.
% \item Whenever $ \alpha + 1 < {\delta} $, then 
%     $ f( \alpha + 1) = H(f(\alpha))$.
%   \end{itemize}
% 
% Informally, this means that when we have to define a sequence
% $(a_{\beta}: {\beta} < {\delta} )$, it is enough to 
% \begin{itemize}
% \itm a define how $a_\alpha $ depends on $(  a_{\beta}: {\beta} <
% \alpha)$, for any limit ordinal $ \alpha < {\delta} $.
% \itm b define how $a_{\alpha+1}$ depends on $a_\alpha $, whenever $
% \alpha+1<{\delta} $. 
% \end{itemize}
\item                  \label{inc-a}
We say that a sequence $(A_\alpha: \alpha < {\delta} )$ of sets is
increasing iff $ \alpha < {\beta} < {\delta} $ implies $A_\alpha
\subseteq A_{\beta} $.   We call this sequence ``continuous'' iff 
$A_\alpha = \bigcup _{{\beta} < \alpha} A_{\beta}  $ whenever $
{\beta} $ is a limit ordinal $< {\delta} $. 
% Let ${\delta} $ be a limit ordinal for simplicity. 
% If $(A_\alpha: \alpha < {\delta} )$ is a continuous
% strictly  increasing
% sequence, $A = \bigcup_{\alpha < {\delta} } A_\alpha $, then the sets 
% $B_\alpha:=  A_{\alpha+1} \setminus A_\alpha $ (for $ \alpha <
% {\delta} $) form a partition of $A$.   Conversely, if $(B'_\alpha:
% \alpha < {\delta})$ is a partition of $A$, then the sequence  
% $(A'_\alpha: \alpha < {\delta})$, defined by $A'_\alpha:=
% \bigcup_{{\beta} < \alpha} B'_{\beta} $, is increasing, continuous,
% and satisfies $\bigcup_{\alpha< {\delta}} A'_\alpha = A$. 
\item   \label{inc-b}
If $(A_\alpha: \alpha < \kappa ) $ is increasing, $A =
\bigcup_{\alpha < \kappa } A_\alpha $, and $B \subseteq A$ has
cardinality $< cf(\kappa)$, then there is an $ \alpha < \kappa $
 such that $B \subseteq A_\alpha $.
(Since this fact is essential for our main theorem, we give the [easy] proof
in the main part of the paper.  See \ref{regfact}.)
\item \label{inc-c}
If $cf(\kappa)>\lambda $, then $ \kappa ^ \lambda = 
\sup\{ \mu^ \lambda : \mu < \kappa \}$. 
\\
Proof: Let $|K|= \kappa$, then we can write $ K$ as an increasing
union of $ \kappa $  many ``small'' sets:  $K = \bigcup_{i < \kappa }
K_i$, $|K_i| < \kappa $.  Let $|L|= \lambda $. 
 By \ref{unions}.\ref{inc-b}, the range of every function $f:L \to K$
 is contained in some $K_i$, so 
 $F^1(L, K) = \bigcup_{i < \kappa}  F(L, K_i)$. Hence  
$\kappa ^ \lambda = |F^1(L, K)| = \sup\{ \kappa_i^ \lambda : i <
\kappa \} =  \sup \{  \mu^ \lambda : \mu < \kappa \}$. 
\item \label{inc-d}
Consequently, 
$(\kappa^+)^\kappa = \kappa^\kappa$ for all $ \kappa $, as 
$ \kappa ^+ $ is always regular. 
\item \label{inc-e} 
If $ \kappa $ is a regular strong limit cardinal, then 
$ \kappa ^ {<\kappa } = \kappa $.   
\\ Proof: For all $\mu <  \kappa $ and all $ \lambda < \kappa $ we 
have $\mu^ \lambda < \kappa$, as $\kappa $ is a strong limit.   Hence
for every $\lambda < \kappa $ we have 
$\kappa ^ \lambda =
 \sup\{ \mu^\lambda : \mu < \kappa \} \le  \kappa $, 
so $\kappa ^{< \kappa } \le  \kappa $. 
\end{enumerate}
\bigskip\bigskip

\bibliographystyle{plain}
% \bibliography{others,listx}

\begin{thebibliography}{1}

\bibitem{BP75}
K.A. Baker and A.F. Pixley.
\newblock Polynomial interpolation and the chinese remainder theorem for
  algebraic systems.
\newblock {\em Math. Z.}, 143:165--174, 1975.

\bibitem{graetzer}
George Gr{\"a}tzer.
\newblock {\em Universal algebra}.
\newblock Springer-Verlag, 1979.

\bibitem{J}
T.~Jech.
\newblock {\em {Set theory}}.
\newblock Academic Press, New York, 1978.

\bibitem{kollar79}
J\'{a}nos Koll\'{a}r.
\newblock Interpolation property in semigroups.
\newblock {\em Semigroup Forum}, 17:337--350, 1979.

\bibitem{kunen}
K.~Kunen.
\newblock {\em Set Theory: An Introduction to Independence Proofs}, volume 102
  of {\em Studies in Logic and the Foundations of Mathematics}.
\newblock North-Holland, 1983.

\bibitem{mur}
V.~L. Murskii.
\newblock The existence of a finite basis of identities, and other properties
  of ``almost all'' finite algebras.
\newblock {\em Problemy Kibernet.}, 30:43--56, 1975.

\end{thebibliography}

\end{document}