% LaTeX2e
% Universal Functions
% P.Larson, A. Miller, J.Stepr\={a}ns, W.Weiss
% Mar-June 2009 Nov 2010 last revised May 2014

\documentclass[12pt]{amsart}
\usepackage{amssymb,latexsym}
%,hyperref}

%%%%%%%%%%%%% DRAFT COMMANDS %%%%%%%%%%%%%%%%%%%%%%
% These commands produce the colour coded changes. To see what the final paper would
%  look like, replace 0=0 by 0=1 in the third line below.
\usepackage[usenames,dvipsnames,svgnames,table]{xcolor}
\usepackage{ifthen}
\ifthenelse{0=1}
{
\newcommand{\Changes}[1]{\textcolor{Blue}{#1}}
\newcommand{\Deletions}[1]{\textcolor{Red}{#1}}
\newcommand{\Additions}[1]{\textcolor{ForestGreen}{#1}}
\newcommand{\Explanation}{{\bf {\large New material appears in \textcolor{green}{green}, changes in \textcolor{blue}{blue} and deletions are highlighted in
\textcolor{red}{red}.}}}
}
{
\newcommand{\Changes}[1]{\textcolor{black}{#1}}
\newcommand{\Deletions}[1]{\relax}
\newcommand{\Additions}[1]{\textcolor{black}{#1}}
\newcommand{\Explanation}{\relax}
}

% if 0=1 or 0=0 it is still a bunch of:
\newcommand{\crap}[1]{\textcolor{Purple}{#1}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pagestyle{myheadings}
\def\header{Universal Functions \hfill}
\markboth\header\header

%\pagestyle{myheadings} \def\header{\today} \markboth\header\header

\newcommand{\angbr}[1]{\langle #1 \rangle}
\def\al{\alpha}
\def\be{\beta}
\def\cc{{\mathfrak c}}
\def\comb(#1,#2){ \left( \begin{array}{c} #1 \\ #2  \end{array} \right) }
\def\ctbl(#1){{{\rm Fn}(#1,2,\om_1)}}
\def\cube{{\mathcal C}}
\def\de{\delta}
\def\dom(#1){\mathrm{dom}(#1)}
\def\ff{{\mathcal F}}
\def\fin(#1){{{\rm Fn}(#1,2,\om)}}
%\def\forces{{\;\Vdash}}
\newcommand{\forces}[2]{\Vdash_{#1} \mbox{``} #2 \mbox{''}}
\def\ga{\gamma}
\def\graph{{\rm graph}}
\def\ka{\kappa}
\def\la{\langle}
\def\om{\omega}
\def\pair(#1,#2){\la #1, #2 \ra}
\def\picube(#1){{\bf \Pi}^0_{#1}(\cube)}
\def\pirec(#1){{\bf \Pi}^0_{#1}(\rec)}
\def\Poset{{\mathbb P}}
\def\poset{{\mathbb P}}
\def\pow(#1){{\mathcal P}(#1)}
\def\pp{\mathfrak p}
\def\proof{\par\noindent Proof\par\noindent}
\def\pr{\prime}
\def\qed{\par\noindent QED\par\bigskip}
\def\Rationals{{\mathbb Q}}
\def\ra{\rangle}
\def\rcantorpar{{(2^\om)}}
\def\rcantor{{2^\om}}
\def\Reals{{2^\om}}
\def\rec{{\mathcal R}}
\def\res{\mathord{\upharpoonright}}
\def\rmand{\mbox{ and }}
\def\rmforall{\mbox{ for all }}
\def\rmiff{\mbox{ iff }}
\def\rmif{\mbox{ if }}
\def\rr{{\mathbb R}}
\def\SetOf#1#2{\left\{#1 \ \left| \ #2 \right.\right\}}
\def\sicube(#1){{\bf \Pi}^0_{#1}(\cube)}
\def\sirec(#1){{\bf \Sigma}^0_{#1}(\rec)}
\def\si{\sigma}
\def\sm{\setminus}
\def\st{\;:\;} % such that
\def\su{\subseteq}
\def\text{\rm}

\newtheorem{theorem}{Theorem}[section]
% \newtheorem{theorem}{Theorem}
\newtheorem{theor}[theorem]{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{define}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{ques}[theorem]{Question}
\newtheorem{quest}[theorem]{Question}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}

\def\addresspaul{\begin{flushleft}
Paul B. Larson\\
larsonpb@miamioh.edu\\
http://www.users.miamioh.edu/larsonpb\\
Department of Mathematics\\
Miami University\\
Oxford, Ohio 45056\\
\end{flushleft}}

\def\addressarn{\begin{flushleft}
Arnold W. Miller \\
miller@math.wisc.edu \\
http://www.math.wisc.edu/$\sim$miller\\
University of Wisconsin-Madison \\
Department of Mathematics, Van Vleck Hall \\
480 Lincoln Drive \\
Madison, Wisconsin 53706-1388 \\
\end{flushleft}}

\def\addressjuris{\begin{flushleft}
Juris Stepr{\={a}}ns \\
steprans@yorku.ca \\
York University\\
Department of Mathematics\\
4700 Keele Street\\
Toronto, Ontario \\
Canada M3J 1P3\\
\end{flushleft}}

\def\addressbill{\begin{flushleft}
William A.R. Weiss\\
weiss@math.toronto.edu\\
Department of Mathematics\\
University of Toronto, Ontario\\
Canada M5S 3G3\\
\end{flushleft}}

\begin{document}

\begin{center}
{\large Universal Functions}
\end{center}

\begin{flushright}
Paul B. Larson\footnote{Research supported in part by NSF Grants
  DMS-0801009 and DMS-1201494. Much of the writing of the paper was done while all four authors attended
  the thematic program on Forcing and its Applications at the Fields Institute in Fall 2012.}\\
Arnold W. Miller\\
Juris Stepr\={a}ns\\
William A.R. Weiss
\end{flushright}

{\small \tableofcontents}






\begin{center}  Abstract\footnote{
 Mathematics Subject Classification 2000: 03E15 03E35 03E50
\par Keywords: Borel function, Universal, Martin's Axiom, Baire class,
cardinality of the continuum, Cohen real model.
\par Results obtained March-June 2009, November 2010.  Last revised 
May 2014.}
\end{center}



A function of two variables $F(x,y)$ is universal
if for every function $G(x,y)$ there exists functions $h(x)$ and
$k(y)$ such that $$G(x,y)=F(h(x),k(y))$$ for all $x,y$.
Sierpi\'nski showed that assuming the Continuum Hypothesis there exists
a Borel function $F(x,y)$ which is universal.
Assuming Martin's Axiom
there is a universal function of Baire class 2. A
universal function cannot be of Baire class 1.
Here we show that it is consistent that for each $\alpha$ with
$2\leq\alpha<\omega_1$  there is a universal function of class $\alpha$
but none of class $\beta<\alpha$. We show that it is consistent with
ZFC that there is no universal function (Borel or not) on the reals,
and we show that it is consistent that there is a universal function but no
Borel universal function.  We also prove some results concerning
higher-arity universal functions.  For example, the existence of
an $F$ such that for every $G$ there are $h_1,h_2,h_3$
such that for all $x,y,z$
$$G(x,y,z)=F(h_1(x),h_2(y),h_3(z))$$
is equivalent to the existence of a binary universal $F$, however
the existence of
an $F$ such that for every $G$ there are $h_1,h_2,h_3$
such that for all $x,y,z$
$$G(x,y,z)=F(h_1(x,y),h_2(x,z),h_3(y,z))$$
follows from a binary universal $F$ but is strictly weaker.



\section{Introduction}

%\begin{define}\label{defunivfcn}
A function $F:X \times X\to X$ is said to be \emph{universal} if
for any $$G:X \times X\to X$$ there is
$g:X\to X$ such that for all  $x,y\in X$
 $$G(x,y)=F(g(x),g(y)).$$
%\end{define}
In the Scottish book (problem 132, see Mauldin \cite{mauldin}) Sierpi\'nski asked if there always is a
Borel function which is universal, when $X$ is the real line.
He had shown that there is a Borel universal function assuming the
Continuum Hypothesis (Sierpi\'nski \cite{sier}).
This notion of universal function is also studied in
Rado \cite{rado} (see Theorem 6 there).


\begin{remark}\label{differentfunctions} Without loss of generality we may use different functions
on the $x$ and $y$ coordinates, i.e., $G(x,y)=F(g_0(x),g_1(y))$ in
the definition of universal function $F$.
To see this suppose we are given $F^*$ such that
for every $G$ we may find $g_0,g_1$ with $G(x,y)=F^*(g_0(x),g_1(y))$
for all $x,y$.  Then we can construct a universal $F$ which uses
only a single $g$.
Take a bijection, i.e., a pairing function, between
$X\times X$ and $X$, which write as: $(x_0,x_1)\mapsto\pair(x_0,x_1)$.
Define
$$F(\pair(x_0,x_1),\pair(y_0,y_1))=F^*(x_0,y_1).$$
Given any
$g_0,g_1$ define $g(u)=\la g_0(u),g_1(u) \ra$
and note that
$$F(g(x),g(y))=F^*(g_0(x),g_1(y))$$
for every $x,y$.

In the case $X=2^\om$ there is a pairing function
which is a homeomorphism and hence the Borel complexity
of $F$ and $F^*$ are the same.
For abstract universal $F$
a pairing function exists for any infinite $X$. For finite sets $X$, universal functions exist if
and only if $|X| \leq 1$.
\end{remark}

\begin{remark}\label{oneonerem}
The definition of universal function is not changed by requiring the function $g$ to be injective, as, given a function $\pi \colon X \to X$ for which
$|\pi^{-1}(x)| = |X|$ for all $x \in X$, we can replace a given $F(x,y)$ in the original sense with $F(\pi(x),\pi(y))$.
\end{remark}

The notion of universal function naturally generalizes to functions of the form $f \colon X \times Y \to Z$, as follows.
 
\begin{define}\label{defunivfcn}
Given sets $X, Y$ and $Z$, a function $F:X \times Y\to Z$ is \emph{universal} if
for each function $$G:X \times Y\to Z$$ there exist functions 
$h:X\to X$ and $k \colon Y \to Y$ such that for all  $(x,y) \in X \times Y$, 
 $$G(x,y)=F(h(x),k(y)).$$
\end{define} 
 
 We record a few simple observations about functions
of this type.

\begin{remark}\label{easyone} If $f \colon X \times Y \to Z$ is universal, $Z' \subseteq Z$ and $z_{0} \in Z'$, then the function
$f' \colon X \times Y \to Z'$ defined by setting
$$f'(x,y)=\left\{
\begin{array}{ll}
f(x,y) &\mbox{ if $f(x,y) \in Z'$} \\
z_{0} &\mbox{ otherwise }\\
\end{array}\right.$$
is also universal.
\end{remark}

%\begin{remark}\label{easyzero} If $f \colon X \times Y \to Z$ is a universal function, and the functions $h \colon X^{*} \to X$ and $k \colon %Y^{*} \to Y$ are bijections,
%then the function $f^{*} \colon X^{*} \times Y^{*} \to Z$ defined by setting $f^{*}(x,y) = f(h(x), k(y))$ is universal.
%\end{remark}

%\begin{remark}\label{easythree} Let $\kappa$ be a cardinal, and suppose that $f_{\alpha} \colon X_{\alpha} \times Y_{\alpha} \to Z_{\alpha}$ is
%a universal function,
%for each $\alpha < \kappa$. Then the function $$F \colon \prod_{\alpha < \kappa}X_{\alpha} \times \prod_{\alpha < \kappa} Y_{\alpha} \to %\prod_{\alpha < \kappa}
%Z_{\alpha}$$ defined by setting $$F( \langle x_{\alpha} : \alpha < \kappa \rangle, \langle y_{\alpha} : \alpha < \kappa %\rangle) = \langle f_{\alpha}(x_{\alpha},
%y_{\alpha}) : \alpha < \kappa \rangle$$ is universal.
%\end{remark}

The following observation shows that the existence of a universal function from $\rcantor \times \rcantor$ to $\rcantor$ is equivalent to the existence of a
 universal function from $\rcantor \times \rcantor \to 2$, even when one asks for a universal function in a particular complexity class.
 Similarly, for all infinite sets $X$ and $Y$, and any $n \in \omega$, the existence of a universal function from $X \times Y$ to $Z$ implies the existence of a
 universal function from $X \times Y$ to $Z^{n}$.

\begin{prop}\label{easytwo}
  If $\kappa$ is a cardinal, $f \colon X \times Y \to Z$ is a universal function, $|X^{\kappa}| = |X|$ and $|Y^{\kappa}| = |Y|$, then there is a universal
  function $F \colon X \times Y \to Z^{\kappa}$.
\end{prop}

\begin{proof}
  Fix bijections $\pi \colon X^{\kappa} \to X$ and $\nu \colon Y^{\kappa} \to Y$. For each $(x,y) \in X \times Y$, let $F(x,y)$ be $$\langle
  f(\pi^{-1}(x)(\alpha), \nu^{-1}(y)(\alpha)) : \alpha < \kappa \rangle.$$ To see that $F$ is universal, fix $G \colon X \times Y \to Z^{\kappa}$. For each
  $\alpha < \kappa$, define $g_{\alpha} \colon X \times Y \to Z$ by setting $g_{\alpha}(x,y) = G(x,y)(\alpha)$. By the universality of $f$, there exist functions
  $h_{\alpha} \colon X \to X$ and $k_{\alpha} \colon Y \to Y$ ($\alpha < \kappa$) such that for all $\alpha < \kappa$ and all $(x,y) \in X \times Y$,
  $g_{\alpha}(x,y) = f(h_{\alpha}(x), k_{\alpha}(y))$.
  Define $H \colon X \to X$ and $K \colon Y \to Y$ by setting $$H(x) = \pi(\langle h_{\alpha}(x) : \alpha < \kappa\rangle)$$ and $K(y) = \nu(\langle k_{\alpha}(y)
  : \alpha < \kappa \rangle)$.
  Then for all $(x,y) \in X \times Y$, $F(H(x),K(y)) = \langle f(h_{\alpha}(x), k_{\alpha}(y)) : \alpha < \kappa \rangle = \langle g_{\alpha}(x,y) : \alpha <
  \kappa \rangle = G(x,y)$.
\end{proof}
\qed

In Section \ref{boreluniv} we show that the existence
of a Borel universal function is equivalent under a
weak cardinality assumption to the statement that
every subset of the plane is in the $\si$-algebra generated
by the abstract rectangles.  We also show that a universal
function cannot be of Baire class 1.

In Section \ref{MA} we prove some results concerning Martin's
axiom and universal functions.  We show that
although MA implies that there is a universal function of
Baire class 2 it is consistent to have ${\text MA}_{\aleph_1}$
hold but no analytic universal functions.


In Section \ref{special} we consider universal functions of
special kinds, for example, $F(x,y)=k(x+y)$.
We also discuss special versions due to Todorcevic and
Davies.

In Section \ref{abstract} we consider abstract universal functions,
i.e., those defined on a cardinal $\ka$ with no notion of definability,
Borel or otherwise.   We show that if $2^{<\ka}=\ka$, then they
exist.  We also show that it is consistent that none exist for
$\ka=2^{\aleph_{0}}$, and we construct some
weak abstract versions of universal functions from the
assumption ${\text MA}_{\aleph_1}$.

In Section \ref{higher} we take up the problem of universal
functions of higher arity.  We show that there is a natural hierarchy
of such notions and we show that this hierarchy is strictly descending.

In Section \ref{mtu} we compare the notion of universal function with the
notional of universality from model theory.

\subsection{Cardinal characteristics}\label{ccssec}

The following definitions show up at various points in this paper.
We let $\mathfrak{c}$ denote the cardinality of the continuum, i.e., $2^{\aleph_{0}}$.
The cardinal $\pp$ is the psuedo-intersection number, the smallest cardinality of a collection
of infinite subsets of $\omega$ having the finite intersection property (i.e., all finite subcollections have nonempty intersection) but no pseudo-intersection
(i.e., no infinite subset of $\omega$ is contained mod-finite in each member of the collection). Equivalently, it is
the smallest cardinal for which Martin's Axiom
for $\si$-centered
posets fails.  This equivalence is due to Bell \cite{bell};
for the proof see also Weiss \cite{weiss}. The tower number $\mathfrak{t}$ is smallest cardinality of a collection of infinite subsets of $\omega$
linearly-ordered by mod-finite containment but having no pseudo-intersection. Evidently, $\mathfrak{p} \leq \mathfrak{t}$, but a recent result of Malliaris and
Shelah \cite{MaSh} shows that $\mathfrak{p} = \mathfrak{t}$ (in light of this fact, the hypotheses of Propositions \ref{proprao} and \ref{prophhm} are each
equivalent to $\mathfrak{p} = \mathfrak{c}$).
The cardinal $\mathfrak{b}$ is the smallest cardinality of a set $X \subseteq \omega^{\omega}$ such that for every $f \colon \omega \to \omega$ there exist a $g
\in X$ with
$\{ n \in \omega \mid g(n) \geq f(n) \}$ infinite. See pages 426-427 of \cite{Blass} for a proof that $\mathfrak{t} \leq \mathfrak{b}$.

The cardinal $\mathfrak{q}$ is the smallest cardinality of a set $X \subseteq 2^{\omega}$ which is not a $Q$-set, i.e., for which there exists a set $Y \subseteq
X$ such that $Z \cap X \neq Y$, for every $G_{\delta}$ set $Z \subseteq 2^{\omega}$. The inequality $\mathfrak{p} \leq \mathfrak{q}$ can be proved in ZFC. This is
due to Silver; see Section 5 of \cite{Millerbook}.
The cardinal characteristic $\mathfrak{ap}$ is defined to be the least cardinal $\kappa$ such that there exist
an almost disjoint family $\{ x_{\alpha} : \alpha < \kappa \}$ (i.e., each $x_{\alpha}$ is an infinite subset of $\omega$, and
for each distinct pair $\alpha, \beta < \kappa$, $x_{\alpha} \cap x_{\beta}$ is finite) and a set $A \subseteq \kappa$ such that for no
$y \subseteq \omega$ does it hold for all $\alpha < \kappa$ that $\alpha \in A$ if and only if $y \cap x_{\alpha}$ is infinite. Standard arguments show that
$\mathfrak{p} \leq \mathfrak{ap} \leq \mathfrak{q}$.

For any cardinal $\kappa$, MA$_{\kappa}$ implies that $\mathfrak{p} \geq \kappa$, which means that Martin's Axiom implies that $\mathfrak{p} = \mathfrak{b} =
\mathfrak{ap} = \mathfrak{q} = \mathfrak{c}$. See \cite{Blass} for more on cardinal characteristics of the continuum.




\section{Borel universal functions}\label{boreluniv}

\begin{define} \label{defrec}
We let $\rec$ denote the family of abstract rectangles,
$$\rec=\{A\times B\st  A,B\su 2^\om\}.$$
\end{define}

\begin{define}
  For $\alpha < \omega_{1}$, $\sirec(\al)$ and $\pirec(\al)$ are inductively defined by:
\begin{itemize}
\item $\sirec(0)=\pirec(0)=$ the set of finite boolean combinations
of sets from $\rec$,
\item $\sirec(\al)$ is the set of countable unions of
sets from $$\pirec(<\al)=\bigcup_{\be<\al}\pirec(\be),$$ and
\item $\pirec(\al)$ is the set of countable intersections of
sets from $\sirec(<\al)$.
\end{itemize}
\end{define}

\begin{define}
A Borel function $F:2^\om \times 2^\om\to 2^\om$ is at the
$\al$-level if
for any $n \in \omega$ the set $\{(u,v)\st F(u,v)(n)=1\}$ is
${\bf\Sigma}^0_\al$.
\end{define}

We write ``a function of level $\alpha$" for ``a function which is at the $\alpha$-th level".
A Borel function at level $\al$ is in
Baire class $\al$, but the converse does not hold.  In the context
of $2^\om$, a function is of Baire class $\al$ if the
preimage of every clopen set is ${\bf\Delta}_{\al+1}$.
For more on the classical theory
of Baire class $\al$, see Kechris \cite{kechris}, p. 190.

\begin{prop}
A universal function cannot be of Baire class 1.
\end{prop}

\proof
Suppose toward a contradiction that $F \colon \rcantor \times \rcantor \to \rcantor$ is a universal function of Baire class 1. Let $\{h_\xi\}_{\xi\in\mathfrak
c}$
enumerate all functions with domain a countable subset of $\rcantor$ and range dense
in itself.
Let $\{r_\xi\}_{\xi\in\mathfrak c}$ enumerate all of $\rcantor$.
For each $\xi \in \cc$, partition the domain of $h_\xi$ into $A_\xi$ and $B_\xi$
 such that $\overline{h_{\xi}[A_{\xi}]} = \overline{h_{\xi}[B_{\xi}]}$.
% $$\overline{\SetOf{h_\xi(x)}{x\in A_\xi}} =
% \overline{\SetOf{h_\xi(x)}{x\in B_\xi}}.$$
Let $G:{(\rcantor)}^2 \to \rcantor$ be any function such that for each $\xi \in \cc$
and $r \in \rcantor$,
$G(r_\xi,r) = 1$ if $r \in A_\xi$ and $G(r_\xi,r) = 0$ if $r \in B_\xi$.

Now suppose that $h:\rcantor\to \rcantor$ witnesses the universality of $F$ with respect to the
function $G$. The range of $h$ must be uncountable; otherwise there would be a countable collection
$\{ \{C_{i}, D_{i}\} : i < \omega \}$ of partitions of $2^{\omega}$ such that for each $\xi \in \cc$
there exists an $i \in \omega$ such that $\overline{h_{\xi}[C_{i} \cap \dom(h_{\xi})]} =
\overline{h_{\xi}[D_{i} \cap \dom(h_{\xi})]}$, and it not hard to build a counterexample to this.
Hence, there is
$\xi$ such that $h_\xi\subseteq h$, and for all
$r \in A_{\xi} \cup B_{\xi}$,
$G(r_\xi,r) = F(h(r_\xi),h_\xi(r))$.

If $f$ is the function defined by setting $f(y) = F(h(r_\xi),y)$, then $f$
must be Baire class 1 and, in particular, letting $C = \overline{h_{\xi}[A_{\xi}]}$ (which is equal to
$\overline{h_{\xi}[B_{\xi}]}$),
%$$C = \overline{\SetOf{h_\xi(r)}{r\in A_\xi}} =
%\overline{\SetOf{h_\xi(r)}{r\in B_\xi}}
%$$
it follows that
$f\restriction C$ is Baire class 1. However,
$$f(h_\xi(r)) = F(h(r_\xi),h_\xi(r)) =
G(r_\xi,r) = 1 \mbox { for }r \in A_\xi.$$
Similarly $f(h_\xi(r)) = 0$
for $ r\in B_\xi$.
This is impossible for any Baire class 1 function on the perfect set $C$.
\qed


%Following convention, we let $\mathfrak{c}$ denote the cardinality of the
%continuum (i.e., $2^{\aleph_{0}}$).


\begin{theorem}\label{mainthm}
If $2^{<\cc}=\cc$, then the following are equivalent.
\begin{enumerate}
\item There is a Borel function $F:2^\om \times 2^\om\to 2^\om$
which is universal.
\item Every subset of the plane $2^\om \times 2^\om$ is
in the $\si$-algebra generated by the abstract rectangles, $\rec$.
\end{enumerate}
Furthermore, for any ordinal $\alpha$, $\pow(2^\om\times 2^\om)=\sirec(\al)$
if and only if there is a universal function from $2^{\omega} \times 2^{\omega}$ to
$2^{\omega}$ at the $\al$-level.
\end{theorem}

\proof

$(1)\to (2)$.

\noindent
Suppose that there is a Borel universal
$F:2^\om \times 2^\om\to 2$.
Let $A\su 2^\om\times 2^\om$ be arbitrary and suppose that
$g:2^\om\to 2^\om$ has the property that
$$\forall x,y\;\;\;\;(x,y)\in A \Leftrightarrow F(g(x),g(y))=1.$$
Let $B$ be the Borel set $F^{-1}[\{1\}]$. Then for all $(x,y) \in 2^{\om} \times 2^{\om}$,
$(x,y)\in A$ if and only if $(g(x),g(y))\in B$.

The set $B$ is generated by countable unions
and intersections from sets of the form $C \times D$, for $C$, $D$ clopen subsets
$2^{\om}$.
%Let $A_n\su 2^\om$ for $n<\om$ be any sequence of sets
%containing all preimages of clopen sets under $g$.
Define $h$ on $2^{\omega} \times 2^{\omega}$ by setting $h(x,y)=(g(x),g(y))$, and note that
$$h^{-1}[C\times D] = g^{-1}[C]\times g^{-1}[D]$$
for all sets $C, D \subseteq 2^{\om}$.
Since preimages pass over countable unions and intersections, for each $\alpha < \omega_{1}$, the
$h$-preimage of each ${\bf \Sigma}^{0}_{\alpha}$ set is in $\sirec(\alpha)$.
%Since
%$$A=h^{-1}[B],$$
%and
%it follows that $A$ is in the $\si$-algebra of abstract
%rectangles. Furthermore
In particular, if $\alpha < \omega_{1}$ is such that $B$ is ${\bf \Sigma}^0_\al$, then
$A = h^{-1}[B]$ is $\sirec(\al)$.

\bigskip

$(2)\to (1)$.

\noindent
We show first that there exists an $X\su 2^\om$ of cardinality
$\cc$ which has the property that every $Y\su X$ of cardinality
strictly smaller than $\cc$ is Borel relative to $X$,
i.e., is the intersection of a
Borel set with $X$. The following argument is modeled after the one in Bing, Bledsoe, and Mauldin \cite{bbm}.
Let $A\su\cc\times\cc$ be such that for every $B\in[\cc]^{<\cc}$
there exists a $\delta<\cc$ such that
$$B=A_{\delta}=^{def}\{\gamma < \cc \st (\delta,\gamma)\in A\}.$$
This is possible, as $2^{<\cc}=\cc$.  Fix $\alpha < \omega_{1}$ such that
$A$ is in $\sirec(\alpha)$, and fix
%Since $A$ is in
%the $\si$-algebra generated by the abstract rectangles, there exists
a sequence $\langle B_n : n \in \omega \rangle$ of subsets of $\cc$
such that $A$ is generated in $\alpha$ many steps from the sets
$$\{B_n\times B_m\st n,m<\om\}.$$  Let
$f:\cc\to 2^\om$ be the Marczewski characteristic function for
the sequence $\langle B_n:n<\om\rangle$, i.e.,
$$f(\delta)(n)=
\left\{
\begin{array}{ll}
0 & \mbox{ if } \delta\notin B_n \\
1 & \mbox{ if } \delta\in B_n
\end{array}\right.$$
Define the function $f^{2} \colon \cc \times \cc \to 2^{\om} \times 2^{\om}$ by
setting $f^{2}(\alpha, \beta) = (f(\alpha), f(\beta))$.
Each set of the form $B_{n} \times B_{m}$ is the $f^{2}$-preimage of the clopen set
$$\{ x \in 2^{\om} \mid n \in x\} \times \{ x \in 2^{\om} \mid m \in x\}.$$
Again using the fact that preimages pass over countable unions and
intersections, we can find a ${\bf \Sigma}^{0}_{\alpha}$ set $Z \subseteq 2^{\om} \times 2^{\om}$
whose $f^{2}$-preimage is $A$.

Let $X=f[\cc]$. Let us check that $X$ has the required property.
Let $Y$ be a subset of $X$ of cardinality less than $\cc$, and let
$B$ be a subset of $\cc$ of cardinality less than $\cc$ such that
$Y = f[B]$. Then $Y$ will be a
section of $Z$, intersected with $X$, i.e.,
$$Y=f[A_{\delta}] = \{ (x,y) \in Z \mid x = f(\delta), y \in X\},$$ where $\delta < \cc$ is such that
$B = A_{\delta}$.
%Also note that if $A$ is $\sirec(\al)$, then every subset of $X$ of cardinality strictly smaller than $\cc$
It follows then that $Y$ is ${\bf\Sigma}_\al^0$ relative to $X$.

Now let $U\subseteq 2^\om\times 2^\om$ be a universal ${\bf\Sigma}_\al^0$
set.  Define $G:2^\om\times 2^\om\to 2^\om$ by setting
%$$\forall n \;\;\;\;(G(x,y)(n)=1 \rmiff (x_n,y)\in U)$$
$G(x,y)(n)=1 \Leftrightarrow (x_n,y)\in U,$
where $x\stackrel{\Phi}{\mapsto}\langle x_n:n<\om \rangle\in (2^\om)^\om$ is a homeomorphism.
Let $k \colon \cc \to X$ be a bijection.

Let $f_1:\cc \times \cc\to 2^\om$ be an arbitrary function with the property
that if $\gamma < \delta < \cc$, then
$f_1(\delta, \gamma)=\vec{0}$ (the identically zero map).
We claim that there exists a function $h_1 \colon \cc\to 2^\om$ such that
$$f_1(\delta, \gamma)=G(h_1(\gamma),k(\delta)) \rmforall (\delta, \gamma)\in \cc \times \cc.$$
%Let $h_2(\delta)=x_{\delta}$ for all $\delta < \cc$.
To see this, note that for each $n < \omega$ and each $\gamma < \cc$ the set
$$Y_n=^{def}\{k(\delta) : f_1(\delta, \gamma)(n)=1\}$$
is a subset of $X$ of cardinality less that $\cc$, so
there exists a $y_n\in 2^\om$ such that
$Y_n=X\cap U_{y_n}$.  Let  $h_1(\gamma)=y$ be chosen such that the
homeomorphism $\Phi$ sends $y$ to the sequence $\langle y_n:n<\om \rangle$.

By an analogous argument, if $f_2:\cc \times \cc \to 2^\om$ is an arbitrary
map with the property that $\cc > \gamma > \delta$ implies $f_2(\delta, \gamma)=\vec{0}$,
then there exists a functions $h_{2}:\cc\to 2^\om$
such that
%$k_{2}(\gamma) = x_{\gamma}$ for all $\gamma < \cc$, and
$$f_2(\delta, \gamma)=G(h_{2}(\delta),k(\gamma))\rmforall (\delta, \gamma)\in \cc \times \cc .$$


Now define $F:2^\om\times 2^\om\to 2^\om$ by letting
$\pair(x,y)$ be a pairing function (a homeomorphism) from $ 2^\om\times 2^\om$ to $2^\om$
and setting
$$F(\pair(x_1,y_1),\pair(x_2,y_2))=\max(G(x_2,x_1),G(y_1,y_2)),$$
where
$\max:2^\om\times 2^\om \to 2^\om$ is the pointwise maximum, i.e.,
$\max(u,v)=w$, where $w(n)$ is the maximum of $u(n)$ and $v(n)$ for each $n<\om$. Then
$F(\pair(x_1,y_1),\pair(x_2,y_2))(n)=1$ if and only if
$1\in  \{ G({x_2,x_1})(n), G({y_1,y_2})(n)\}$.

We show that $F$ is universal.
Given an arbitrary $f:\cc\times\cc\to 2^\om$ we can
find $f_1$ and $f_2$ as above so that
$$f(\delta, \gamma)=\max(f_1(\delta, \gamma),f_2(\delta, \gamma))$$ for all $(\delta, \gamma)\in \cc \times \cc$.
For each $\delta, \gamma < \cc$, set
$l_1(\delta)={\angbr{k(\delta),h_{2}(\delta)}}$ and $l_2(\gamma)=
{\angbr{h_1(\gamma),k(\gamma)}}$.
Then, for all $\delta, \gamma< \cc$,
$f(\delta, \gamma)=F(l_1(\delta),l_2(\gamma))$.

Also, $F$ is at the $\al$-level, i.e.,
for any $n$ the set $$\{(u,v)\st F(u,v)(n)=1\}$$ is in
${\bf\Sigma}^0_\al$.

\qed

\begin{remark}
  By Proposition \ref{easytwo}, part (1) of Theorem \ref{mainthm} is equivalent to the alternate version where the range of $F$ is $2$ instead of $2^{\omega}$.
  This variation allows for an alternate, possibly simpler, proof of the reverse direction of Theorem \ref{mainthm}.
\end{remark}

\begin{cor}
For each $\al$ with $2\leq\al<\om_1$ there is a c.c.c. forcing extension in which there is a universal
function of level $\al$ but none of level $\be<\al$.
There is a c.c.c. forcing extension in which there is a universal function but no Borel
universal function.
\end{cor}

\proof
The first part follows from the corresponding results about
the $\si$-algebra of abstract rectangles, see Miller \cite{miller},
Theorems 37 and 52 ($\cc^{<\cc}=\cc$ in the models
from these theorems).
For the second, the existence of an abstract universal function follows
from $\cc^{<\cc}=\cc$ by Theorem \ref{existuniv}, and this holds
in many models in which not every subset of the plane is in the
$\sigma$-algebra generated by the abstract rectangles. For example,
Kunen in his Ph.D. thesis \cite{kunenthesis} showed this is true after a finite support
iteration of Cohen forcing of length $\omega_{2}$ over a model of GCH.
%The third part follows from Proposition \ref{proprao}.
\qed

\begin{remark}
  Theorem \ref{stevosthrm} and Proposition \ref{proprao} each show that if $\pp = \cc$, then there is a universal function at level 2.
\end{remark}

\begin{ques}
Suppose that there is a universal function of Baire class $\al$. Then
is there a universal function of level $\al$?
\end{ques}




The techniques of Miller \cite{millergensous} can be
used to produce models with an analytic universal function (that is, a universal function which is analytic),
but no Borel universal function.

\section{Universal functions and Martin's Axiom}\label{MA}

Proposition \ref{proprao} below shows that if Martin's Axiom holds then there are universal
functions on the reals of Baire class 2.
Here we show that the axiom MA$_{\aleph_{1}}$ (the restriction of MA to collections of $\aleph_{1}$ many
dense sets) is not strong enough for this result.

%The following lemma applies to any continuum-sized class of functions from $\rcantor \times \rcantor$ to $\rcantor$ (for instance, the Borel
%functions or the analytic functions).

The following lemma will be our tool for showing that a given function is not universal.


\begin{lemma}\label{l:m}
Let $F \colon \rcantor \times \rcantor \to \rcantor$ be a function, and suppose that there exist $S_{y,z} \subseteq \rcantor$ $(y,z \in \rcantor)$ such that
\begin{enumerate}
\item each $S_{y,z}$ is a subset of $\rcantor$ containing $\{y,z\}$ and closed under $F$;
\item no $S_{y,z}$ contains $\rcantor$;
\item for each function $h \colon \Reals \to \Reals$ there exist $y,z \in \rcantor$ such that $\{h(y),h(z)\}\subseteq S_{y,z}$.
\end{enumerate}
Then $F$ is not universal.
\end{lemma}

\begin{proof}
%Fix $x \in \rcantor$ and let $F$ be the function on $\rcantor \times \rcantor$ defined by setting $F(y,z) = U(x,y,z)$ for all $y,z \in %\rcantor$.
Let $G \colon \rcantor \times \rcantor \to \rcantor$ be such that each value $G(y,z)$ is an element of $\Reals \setminus S_{y,z}$. Then for each $h \colon
\Reals\to \Reals$ it is possible to find reals $y$ and $z$ such that $\{h(y),h(z)\}\subseteq  S_{y,z}$. Since $S_{y,z}$ is closed under $F$, $F(h(y),h(z))\in
S_{y,z}$. Since $G(y,z)\notin S_{y,z}$, it follows that $F(h(y),h(z))\neq G(y,z)$, so $F$ is not universal.
\end{proof}
\qed

Combined with Lemma \ref{l:m}, Theorem \ref{t:p} below shows that if there is a model of set theory then there is a model of set theory in which there is no
analytic universal function on the reals. First we note a general combinatorial fact, which is a generalization of one of Sierpi\'nski's characterizations of the
failure of the Continuum Hypothesis (see \cite{sierch}). In our first application of the lemma, $\delta$ will be $\omega$; in the second it will be an arbitrary
uncountable cardinal. We let $\mathcal{P}_{\kappa}(\lambda)$ denote the collection of subsets of $\lambda$ of cardinality less than $\kappa$.

\begin{lemma}\label{clem} Suppose that $\delta$ and $\kappa$ are cardinals with $\kappa > \delta^{+}$, and let $f \colon \kappa \times \kappa \to \kappa$ be
injective.
  Then for each function $H \colon \kappa \to \mathcal{P}_{\delta^{+}}(\kappa)$ there exist $\alpha < \delta^{+}$ and $\beta \in \kappa$ such that $f(\alpha,
  \beta) \not\in H(\alpha) \cup H(\beta)$.
\end{lemma}

\begin{proof}
Choose $\beta \in \kappa$ such that, for all $\alpha < \delta^{+}$, $f(\alpha, \beta) \not \in H(\alpha)$.
Now choose $\alpha < \delta^{+}$ such that $f(\alpha, \beta) \not\in H(\beta)$.
\end{proof}
\qed

The proofs of following theorems apply to any class of functions with the property that for each $F$ in the class there exists a set of ordinals $x$ of
cardinality less than $\kappa$ with the property that every inner model with $x$ as a member is closed under $F$.

\begin{theor}\label{t:p}
Suppose that $\kappa > \omega_{1}$ is a cardinal of uncountable cofinality.
Then there is no analytic universal function on $\rcantor$ in any model obtained by forcing with a finite support product of $\kappa$ many nontrivial c.c.c.
partial orders.

\end{theor}
\begin{proof}
Let $\Poset_\alpha$ be a c.c.c. partial order for each $\alpha \in \kappa$ and suppose
that $$G\subseteq \prod_{\alpha\in \kappa}\Poset_\alpha$$
is generic over $V$. Since infinite finite-support products of nontrivial partial orders add reals, by grouping together products of countably many
$\Poset_\alpha$'s we may assume that each $\Poset_\alpha$ adds a real. We work in $V[G]$. Let $F \colon \rcantor \times \rcantor \to \rcantor$ be analytic, and
let $x \in \rcantor$ be a code for $F$.

For each $\beta \in \kappa$, let $G^{*}_{\beta}$ denote the restriction of $G$ to $\prod_{\alpha\in \kappa \setminus \{\beta\}}\Poset_\alpha$.
Since $\prod_{\alpha\in \kappa}\Poset_\alpha$ is c.c.c., each real is in $V[G^{*}_{\beta}]$ for all but countably many $\beta \in \kappa$.
Fix $X \subseteq \rcantor$ with $|X| = \kappa$, and let $f \colon X \times X \to \kappa$ be injective with the property that
$\{ x, y, z\} \subseteq V[G^{*}_{f(y,z)}]$ for each pair $(y,z) \in X \times X$.
%$V_\Gamma$ denote the model $V[G\cap \prod_{\alpha\in \Gamma}\Poset_\alpha]$.
%For each $x\in \Reals$ in $V[G]$ let $\mu(x)$ be the least ordinal $\mu$ such that $x \in V[G_{\mu}]$.  and $\kappa$ has uncountable cofinality, each $\m(x)$ is
%less than $\kappa$.
Define $S_{y,z} \subseteq \rcantor$ for each $y,z \in \rcantor$ by setting $$S_{y,z} = \rcantor \cap V[G^{*}_{f(x,y)}]$$ whenever $(y,z) \in X \times X$, and
letting $S_{y,z} = \{y,z\}$ otherwise. Then item (1) of Lemma~\ref{l:m} clearly holds, and item (2) follows from the fact that each $\Poset_{\alpha}$
adds a real.

%Given  $(x,y,z)\in \rcantorpar^3$ suppose first that there is no $\theta\in \kappa$ such that $\mu(y) = \mu(x) + \theta$. In this case
% define ${\mathfrak M}_{(x,y,z)} = V_\xi$ where $\xi$ is the largest of $\mu(x)$, $\mu(y)$ and $\mu(z)$. The c.c.c. guarantees that $\xi< \kappa^+$ and the new
%reals added ensure that  (1) and (2) of Lemma~\ref{l:m} hold. Otherwise, let $\theta(x,y)\in \kappa$ be
%such that $\mu(y) = \mu(x) + \theta(x,y)$. Let $\Gamma_{(x,y,z)} = \mu(z) + \theta(x,y) \cup (\kappa^+\setminus (\mu(z) + \kappa))$ and let $
%{\mathfrak M}_{(x,y,z)} = V_{\Gamma_{(x,y,z)}}$. It is again clear that (1) and (2) of Lemma~\ref{l:m} hold.

%\Changes{Given  $(x,y,z)\in \rcantorpar^3$ for which it fails to be the case that $\mu(x)\leq \mu(y)\in \mu(z)$ and $\mu(z)$ is a limit ordinal %of uncountable
%cofinality,
% define ${\mathfrak M}_{(x,y,z)} = V_\xi$ where $\xi$ is the largest of $\mu(x)$, $\mu(y)$ and $\mu(z)$.}

%For each triple $(x,y,z) \in \rcantorpar^{3}$, let ${\mathfrak M}_{(x,y,z)} = V_\xi$ where $\xi$ is the largest of $\mu(x)$, $\mu(y)$ and %$\mu(z)$.



%The c.c.c. guarantees that $\xi< \kappa^+$ and the new reals added ensure that  (1) and (2) of Lemma~\ref{l:m} hold.
%\Changes{ Otherwise, let $\Gamma_{(x,y,z)} = \kappa^+\setminus [\mu(z)+\mu(y),\mu(z)\cdot 2)$ and let ${\mathfrak M}_{(x,y,z)} = %V_{\Gamma_{(x,y,z)}}$. It is
%again clear that (1) and (2) of Lemma~\ref{l:m} hold because the interval $[\mu(z)+\mu(y),\mu(z)\cdot 2)$ is not %empty.}

To see that (3) holds, fix a function $h\colon\Reals \to \Reals$.
Applying the c.c.c. of $\prod_{\alpha\in \kappa}\Poset_\alpha$ we can find a function $H \colon X \to \mathcal{P}_{\aleph_{1}}(\kappa)$ such that, for each $y \in
X$, $h(y) \in V[G \upharpoonright \prod_{\alpha \in H(y)}\Poset_{\alpha}]$. Applying Lemma \ref{clem}, we can find $y, z \in X$ such that $f(y,z) \not \in H(y)
\cup H(z)$, which means that $\{ h(y), h(z)\} \subseteq S_{y,z}$.
\end{proof}
\qed

%\Deletions{For each $\eta\in \kappa$ let $y_\eta\in \Reals$ be such that $\mu(y_\eta) = \mu(x) + \eta$. In other words, $\theta(x,y_\eta) = %\eta$. }
%\Changes{ Using the c.c.c., find a limit ordinal $\beta>\mu(x)$ of uncountable cofinality such that
%for each $\eta < \beta$ there is some $y_\eta$ such that $\mu(y_\eta) =\eta$ and
%$h(y)\in V_\beta$. Now let $z\in \Reals$ be such that $\mu(z) = \beta$ and find $\eta\in \beta$ large enough that
%if $h(z) \in V_{\Gamma}$ where $\Gamma = \kappa^+\setminus [\beta+\eta,\beta\cdot 2)$.}
%It follows that ${\mathfrak M}_{x,y_\eta,z} = V_\Gamma$ and hence
%$\{h(y_\eta),h(z)\}\subseteq {\mathfrak M}_{x,y_\eta,z} $. Hence (3) of Lemma~\ref{l:m} is also satisfied and the result now follows from %Lemma~\ref{l:m}.
%\end{proof}

%The following theorem shows that if there is a model of set theory then there is a model of set
%theory in which ${\text MA}_{\aleph_1}$ holds but there is no
%Borel universal function.

\begin{theor}
Suppose that $\lambda$ and $\kappa$ are uncountable cardinals such that $\lambda^{+} < \kappa$, $\kappa^{\lambda} = \kappa$ and $\kappa$ has uncountable
cofinality.
Then there is a c.c.c. forcing extension in which $\mathfrak{c} = \kappa$, MA$_{\lambda}$ holds and there is no analytic universal function.
\end{theor}

\begin{proof}
Let $\Poset$ be a finite support product of c.c.c. partial orders $\Poset_{\alpha}$ ($\alpha < \kappa$), such that
each $\Poset_{\alpha}$ has cardinality at most $\lambda$ and adds a real. Let $G \subseteq \Poset$ be a $V$-generic filter, and, for each $X \subseteq \kappa$,
let
$G_{X}$ be the restriction of $G$ to $\prod_{\alpha \in X} \Poset_{\alpha}$. For each $\alpha < \kappa$, let $G^{*}_{\alpha}$
denote $G_{\kappa \setminus \{\alpha\}}$, and
let $a_{\alpha}$ be an element of $(\rcantor\cap V[G]) \setminus V[G^{*}_{\alpha}]$.

Working in $V[G]$, let $\Rationals$ be the direct limit of a finite support iteration $\langle \mathbb{Q}_{\alpha}, \dot{R}_{\alpha} : \alpha < \kappa \rangle$ of
c.c.c. partial orders on $\lambda$, such that $\mathbb{Q}$ forces MA$_{\lambda}$.
For each $X \subseteq \kappa$, let $\mathbb{Q}_{X}$ be the subiteration of $\Rationals$ consisting of those $\dot{R}_{\alpha}$'s which depend only on
$\prod_{\alpha\in X}\Poset_{\alpha}$ (as opposed to all of $\Poset$) and the initial
segment of $\mathbb{Q}_{X}$ before stage $\alpha$.
Since $\Poset * \Rationals$ is in $V$, each $\mathbb{Q}_{X}$ is in $V[G_{X}]$ and regularly embeds
into $\Rationals$. Furthermore, each $\dot{R}_{\alpha}$ (and each countable set of $\dot{R}_{\alpha}$'s) is part of $\mathbb{Q}_{X}$ for some $X \subseteq \kappa$
of cardinality $\lambda$.
%We may assume that for each $X \subseteq \kappa$, the subiteration of $\Rationals$ induced by those names
%depending only on

Let $K$ be $V[G]$-generic filter for $\Rationals$, and for each $X \subseteq \kappa$, let $K_X$ be the
restriction of $K$ to $\Rationals_{X}$.
For each $\alpha \in \kappa$, let $K^{*}_{\alpha}$ denote
$K_{\kappa \setminus \{\alpha\}}$.
Then every element of $\rcantor$ in $V[G][K]$ is in $V[G_X][K_X]$ for some $X \subseteq
\kappa$ of cardinality $\lambda$.
By mutual genericity, no $a_{\alpha}$ is in $V[G^{*}_{\alpha}][K^{*}_{\alpha}]$.

Now suppose that $F$ is an analytic function in $V[G][K]$, coded by some $x \in \rcantor$. Fix $X \subseteq\kappa$ of cardinality $\lambda$ such that
$x$ is in $V[G_X][K_X]$.
Let $$i \colon \{a_{\alpha} : \alpha \in \kappa\}^{2} \to \{ a_{\alpha} : \kappa \setminus X\}$$ be an injection such that
$\{ a_{\alpha}, a_{\beta}\} \subseteq V[G^{*}_{i(a_{\alpha}, a_{\beta})}][K^{*}_{i(a_{\alpha}, a_{\beta})}]$ for all $\alpha, \beta \in \kappa$.
% and extend $i$ to any function from $\rcantor \times \rcantor$ to $\rcantor$.
Let $S_{y,z} = \rcantor \cap V[G^{*}_{i(y,z)}][K^{*}_{i(y,z)}]$, for each pair $(y,z) \in \{a_{\alpha} : \alpha \in \kappa\}^{2}$, and let $S_{y,z} = \{y,z\}$ for
all other pairs $(y,z)$ from $\rcantor \times \rcantor$. Then items (1) and (2) of Lemma \ref{l:m} are clearly satisfied.

Fix a function $h \colon \rcantor \to \rcantor$. For each $\alpha \in \kappa$, we have a set
$H(\alpha) \subseteq \kappa$ of size $\lambda$, containing $X$, such that $h(\alpha)$ is in
$V[G_{H(\alpha)}][K_{H(\alpha)}]$.
By Lemma \ref{clem}, there are $\alpha$ and $\beta$ in $\kappa$ such that $i(a_{\alpha}, a_{\beta})$ is not equal to
$a_{\gamma}$ for any $\gamma \in H(\alpha) \cup H(\beta)$. It follows that $\{h(a_{\alpha}), h(a_{\beta})\} \subseteq S_{a_{\alpha},a_{\beta}}$.
%$i(a_{\beta}, a_{\gamma})$ is not in
%$V[G_{H(\beta) \cup H(\gamma)}][K_{H(\beta) \cup H(\gamma)}]$.
Then item (3) of Lemma \ref{l:m} is satisfied, showing that $F$ is not universal in $V[G][K]$.
\end{proof}
\qed

\Deletions{\begin{theor}
If $\cc = \aleph_{1}$ and $2^{\aleph_{1}} = \aleph_{2}$, then there is a c.c.c. forcing extension in which
${\text MA}_{\aleph_1}$ holds but there is no
Borel universal function.
\end{theor}

\begin{proof}
%Obtain the model of ${\text MA}_{\aleph_1}$ by iterating to $\omega_3$
% with c.c.c. partial orders of size $\aleph_1$ over a model of the Continuum Hypothesis.
%Since $2^{\aleph_{1}}= \aleph_{2}$, there is a c.c.c. forcing extension in which  ${\text MA}_{\aleph_1}$ holds.
Let $\Rationals_{\alpha}, \Poset_\alpha$ ($\alpha\in \omega_{3}$) be such that each $\Rationals_\alpha$ is the finite support limit of $\{\Rationals_{\xi},
\Poset_{\xi} : \xi < \alpha\}$  and each $\Poset_\alpha$ is a $\Rationals_\alpha$ name for a c.c.c. partial order of cardinality $\aleph_1$. Call a set
$\Gamma\subseteq \omega_3$ {\em full} if
  for each $\gamma\in \Gamma$ all the conditions in the name $\Poset_\gamma$
  have support contained in $\Gamma\cap \gamma$ (restricting for each $\gamma$ to a set of $\aleph_{1}$-many $\Rationals_{\alpha}$-names giving rise to the
  elements of $\Poset_{\alpha}$). If $\Gamma$ is full, let $\Rationals_\Gamma$ be the iteration of only the partial orders $\Poset_\gamma$ for $\gamma\in \Gamma$.
  Let $\mathcal{E}$ be the set of full $\Gamma \in [\omega_{3}]^{\aleph_{1}}$ for which $\Rationals_{\Gamma}$ is completely embedded in
  $\Rationals_{\omega_{3}}$.

   The Continuum Hypothesis and the c.c.c. of $\Rationals_{\omega_{3}}$ imply together that for any subset of $\Rationals_{\omega_3}$ of cardinality $\aleph_1$ is
   contained in $\Rationals_\Gamma$ for some $\Gamma \in \mathcal{E}$.
   %\Deletions{Even more,
  %for any $\xi\in \omega_3$ if $W\subseteq \Rationals_{\omega_3}$ is such that
  %$W\setminus \Rationals_\xi$ has cardinality $\aleph_1$ it is possible to find
 %a full $\Gamma$ such that $\Gamma \setminus \Rationals_\xi$ has cardinality $\aleph_1$ and $\Rationals_\Gamma$ is completely embedded in
 %$\Rationals_{\omega_3}$.}
  Using this, it is possible to mimic the proof of Theorem~\ref{t:p}.

Let $G\subseteq \Rationals_{\omega_3}$ be generic. We work in $V[G]$, in which $\cc = \aleph_{3}$. For each $\Gamma \in \mathcal{E}$, let $G_{\Gamma}$ be the
restriction of $G$ to $\Rationals_{\Gamma}$. Let $F \colon \rcantor \times \rcantor \to \rcantor$ be Borel, and let $x \in \rcantor$ be a code for $F$. Let $f
\colon \rcantor \times \rcantor \to \omega_{3}$ be such that for each pair $y,z \in \rcantor$,
there is a $\Gamma \in \mathcal{E}$ such that $\{ x,y,z\} \subseteq V[G_{\Gamma}]$.


For any full $\Gamma\subseteq \omega_3$ such that $\Rationals_\Gamma$ is completely embedded in $\Rationals_{\omega_3}$ let $V_\Gamma = V[G\cap
\Rationals_\Gamma]$.
 For any $x\in \Reals$ in $V[G]$ let $\mu(x)$ be the least ordinal such that $x \in V_{\mu(x)}$.

 Given  $(x,y,z)\in \rcantorpar^3$ for which it fails to be the case
 that $\mu(x)\leq \mu(y)\in \mu(z)$ and $\mu(z)$ is a limit ordinal of
 cofinality $\omega_2$, define ${\mathfrak M}_{(x,y,z)} = V_\xi$ where $\xi$ is
 the largest of $\mu(x)$, $\mu(y)$ and $\mu(z)$. The c.c.c. guarantees that $\xi<
 \omega_3$ and the new reals added ensure that  (1) and (2) of Lemma~\ref{l:m}
 hold.

 Otherwise, for each $\alpha\in\omega_3$ let $\Sigma_\alpha$ be a full set of
 size $\aleph_1$ containing the ordinal $\alpha$. Note that the finite support
 of the iteration ensures that full sets are closed under unions. Hence for any
 set $X\subseteq \omega_3$ the set $\Sigma_X=\bigcup_{\alpha\in X}\Sigma_\alpha$
 is full and contains $X$. If  $\mu(x)\leq \mu(y)\in \mu(z)$ and $\mu(z)$ is a
 limit ordinal of  cofinality $\omega_2$ then define  $\Gamma_{(x,y,z)} =\mu(z)
 + \mu(y) \cup \Delta_{y,z}$ where
 $$\Delta_{y,z}=
 \bigcup
 \SetOf{\Sigma_\alpha}{\alpha>\mu(z)\cdot 2 \text{ \ \ and\ \  }
 \Sigma_\alpha\cap [\mu(z) + \mu(y),\mu(z)\cdot 2) = \emptyset}$$
 and note that $\Gamma_{(x,y,z)}$ is full.


%Given  $(x,y,z)\in \rcantorpar^3$ suppose first that there is no $\theta\in \omega_2$ such that $\mu(y) = \mu(x) + \theta$. In this case
% define ${\mathfrak M}_{(x,y,z)} = V_\xi$ where $\xi$ is the largest of $\mu(x)$, $\mu(y)$ and $\mu(z)$.  Otherwise, let $\theta(x,y)\in \omega_2$ be
%such that $\mu(y) = \mu(x) + \theta(x,y)$.
%There is some $\Gamma_{(x,y,z)}\subseteq \omega_3$ such that
%\begin{enumerate}
%\item $\mu(z)+ \theta(x,y)\subseteq \Gamma_{(x,y,z)}$
%\item $| \Gamma_{(x,y,z)}\setminus \mu(z)| = \aleph_1$
%\item  $\Gamma_{(x,y,z)}$ is full
%\item $\Rationals_{\Gamma_{(x,y,z)}}$ is completely embedded in $\Rationals_{\omega_3}$.
%\end{enumerate}
%The let ${\mathcal G}$ be the family of all $\Gamma\subseteq \omega_3$ such that
%\begin{enumerate}
%\item $\Gamma \cap \mu(z) + \omega_2 = \Gamma_{(x,y,z)}\cap \omega_2$
%\item  $\Gamma$ is full
%\item $\Rationals_{\Gamma}$ is completely embedded in $\Rationals_{\omega_3}$.
%\end{enumerate}
%Let  ${\mathfrak M}_{(x,y,z)} = \bigcup_{G\in\mathcal G}V_{\Gamma}$ and note that it is a model of sufficiently much set theory to code Borel sets by reals.
% It is again clear that (1) and (2) of Lemma~\ref{l:m} hold.

To see that (3) holds suppose that $h:\Reals \to \Reals$ and $x\in \Reals$ are in $V[G]$.
For each $\eta\in \Changes{\omega_3}$ let $y_\eta\in \Reals$ be such that \Changes{$\mu(y_\eta) =  \eta$}.  Using the c.c.c., find $\beta$ \Additions{ of
cofinality $\omega_2$ }so large that
$h(y_\eta)\in V_\beta$ for each $\eta \in \Changes{\beta}$.  Now let $z\in \Reals$ be such that $\mu(z) = \beta$ and find \Changes{$\eta\in \beta$} large enough
that $h(z) \in V_{\Gamma_{(x,y_\eta,z)}}$.
It follows that ${\mathfrak M}_{x,y_\eta,z} \supseteq V_{\Gamma_{(x,y_\eta,z)}}$ and hence
$\{h(y_\eta),h(z)\}\subseteq {\mathfrak M}_{x,y_\eta,z} $. Hence (3) of Lemma~\ref{l:m} is also satisfied and the result now follows from Lemma~\ref{l:m}.
\end{proof}
}


\section{Universal functions of special kinds} \label{special}

Elementary functions in the calculus of two variables can
be obtained from addition, the elementary functions of one variable
and closing under composition.  For example, $xy={\frac12}((x+y)^2-x^2-y^2)$.
We might ask if there could be a universal function which uses addition.

\begin{prop}
Suppose that $U:2^\om\times 2^\om\to 2^\om$ is a universal function.
%i.e, for every $f:2^\om\times 2^\om\to 2^\om$ there are
%$g,h$ with $f(x,y)=U(g(x),h(y))$ all $x,y\in 2^\om$.
Then there is a universal function
$F(x,y)=k(x+y)$,
where $k:2^\om\to 2^\om$ has the same Borel complexity as $U$ and
$x+y$ refers to pointwise addition in $2^\om$.
\end{prop}
\proof
Given
any $u\in 2^\om$ let $u_0$ be $u$ shifted onto the even
coordinates, i.e, $u_0(2n)=u(n)$ and $u_0(2n+1)=0$.  Similarly
for $v\in 2^\om$ let $v_1$ be $v$ shifted onto the odd coordinates.
Note that $(u,v)$ is easily recovered from $u_0+v_1$.
Hence we can define $k$ by $k(w)=U(u,v)$ where $w=u_0+v_1$. Then, given
$H:2^\omega\times 2^\omega \to 2^\omega$ there is $g:2^\omega\to 2^\omega$ such that
$H(u,v) = U(g(u),g(v))$. Let $g_0(x) = (g(x))_0$ and $g_1(x) = (g(x))_1$. Then
$H(u,v) = U(g(u),g(v)) = k( (g(u))_0 + (g(v))_1) = F(g_0(u),g_1(v))$. Now apply Remark~\ref{differentfunctions}.
\qed

Proposition \ref{binop} gives a generalization of the result above which applies, for
example, to any Borel subgroup of a Polish group or even a Borel subsemigroup of a
Polish cancellation\footnote{A semigroup is a cancelation semigroup if it satisfies that for all $a$, $b$ and $c$, if $ac = bc$ then $a=b$.} semigroup. First we prove a general result about
Borel binary operations. We
say that a binary operation * on a set $B$ is \emph{separately one-to-one} if
for every
$x,y,z\in B$, if $x*y=x*z$ or $y*x=z*x$ then $y=z$.

\begin{lemma}\label{binclaim}
  Suppose that $*$ is a Borel binary operation on an uncountable Borel $B \subseteq \rcantor$, and that
  $*$ is separately one-to-one. Then there exist perfect subsets $P_1,P_2$ of $B$ such that $*$ is one-to-one and continuous on
  $P_{1} \times P_{2}$.
\end{lemma}

\begin{proof}
Let $Q\su B$ be a perfect set. Let $M$ be the transitive collapse of a countable elementary substructure
$X$ of $H(\cc^{+})$ which contains reals coding $Q$ and $(B,*)$.
Let $T\su 2^{<\om}$ be the tree whose infinite branches are
the elements of $Q$. Forcing with $T$ is equivalent to forcing
with the poset $2^{<\om}$. It is well-known (see \cite{brendle}, where it is credited to Folklore) that there is a
countable partial order forcing a perfect set $P\su Q$ with the property
that every finite sequence of distinct elements $(x_1,\ldots,x_n)$ of $P$ is
$T^n$-generic.
%Let $Q$ and $(B,*)$ have Borel
%codes in a countable transitive model $M$ of a sufficiently
%large finite fragment of $ZFC$.
Let $P$ be such a generic set over $M$, and let $P_1$ and $P_2$ be any pair
of disjoint perfect subsets of $P$.

To see that $*$ is continuous on $P_1\times P_2$
suppose that $(x_1 * x_2)\res n= s$.  Then there must be
$m$ such that
$(x_1\res m,x_2\res m)$ forces in $T^{2}$ that $(g_{1} * g_{2})\res n= s$ where
$g_{1}$ and $g_{2}$ are the generic reals added by $T^{2}$.
It follows that $(x_1^\pr * x_2^\pr)\res n= s$ for all $(x_1^\pr,x_2^\pr)$ in
$P_1\times P_2$ which agree with $(x_1,x_2)$ up to $m$.

To see that $*$ is one-to-one on $P_1\times P_2$, suppose that
$$z = x_1 * x_2 = x_1^\pr * x_2^\pr.$$  Since $P_1$ and $P_2$ are disjoint and $*$ is
separately one-to-one, either $(x_{1}, x_{2})$ and $(x_{1}',x_{2}')$ are the same pair or
all four reals are distinct.  If all four are distinct, then
$((x_1,x_2),(x_1^\pr,x_2^\pr))$ is $T^2\times T^2$-generic over
$M$. A well-known lemma on product forcing (see page 13 of Solovay \cite{solovay})
gives that in this case,
$$M[x_1,x_2]\cap M[x_1^\pr,x_2^\pr]=M,$$
so $z\in M$.  Then there exists an
$n\in \omega$ such that
$(x_1\res n,x_2\res n)$ forces in $T^{2}$ that $g_1 * g_2= z$.
Since $P_{2}$ is perfect, there exists a $y \in P_{2} \setminus \{x_{2}\}$ for
which $y \res n = x_{2} \res n$. This contradicts our assumption that $*$ is separately one-to-one.
%which would contradict our assumption on * since it easy to
%find $y\in P_2$ not equal to $x_2$
% but with $y\res n=x_2\res n$,
%then by forcing and absoluteness get that $f(x_1,x_2)=f(x_1,y)$.
\end{proof}
\qed

\begin{prop}\label{binop}
Suppose that $U:2^\om\times 2^\om\to 2^\om$ is a universal function,
and $(B,*)$ consists of
an uncountable Borel set with a Borel binary operation
* on $B$ which is separately one-to-one.
Then there exists a function $F:B\to 2^\om$ such that for each $g:\cc\times \cc\to 2^\om$
there exist $h,k$ mapping $\cc$ to $B$ with
$$g(\al,\be)=F(h(\al)*k(\be))\;\; \mbox{ for all }\al,\be\in \cc$$
Furthermore, if $U$ is Borel then $F$ can be taken to have the same Borel rank as $U$.
\end{prop}

\proof
%Lemma \ref{binclaim} shows that the Borel rank of $(B,*)$ is irrelevant.
Fix $P_{1}$ and $P_{2}$ as in the conclusion of Lemma \ref{binclaim}.
%\bigskip\noindent {\bf Claim}.
%There exists perfect $P_1,P_2$ subsets of $B$ such that
%$f:P_1\times P_2\to B$ defined by $f(x,y)=x*y$ is one-to-one
%and continuous.
%\proof
%This proves the Claim.
%\qed
Let $R$ be the range of the binary operation $*$, so that
$*:P_1\times P_2\to R$ is a homeomorphism.
Let $f_1,f_2$ be the
continuous functions with domain $R$ such that
$f_1(x*y)=x$ and $f_2(x*y)=y$.
Since $P_1$ and $P_2$ are each homeomorphic to $2^\om$ we
may assume without loss of generality that $U:P_1\times P_2\to 2^\om$.
Define $F \colon B \to \rcantor$ by setting $F(z)=U(f_1(z),f_2(z))$ if $z\in R$ and $F(z)=0$
otherwise. Then $F(x*y)=U(x,y)$ for each $(x,y)\in P_1\times P_2$. To verify that $F$ is universal, fix an
arbitrary function
$g:\cc\times \cc\to 2^\om$.
Since $U$ is universal there are
$h:\cc\to P_1$ and $k:\cc\to P_2$ such that $g(\al,\be)=U(h(\al),k(\be))$ for all
$\al,\be\in\cc$.
Then $F(h(\al)*k(\be))=U(h(\al),k(\be))=g(\al,\be)$ for all such $\alpha, \beta$.
\qed

The following proposition shows that functions which are universal with respect to symmetric functions
can have a simpler form.

\begin{prop}
Suppose that $F:2^\om\times 2^\om\to 2^\om$ is a universal function.
Then there exists a function
$f:2^\om\to 2^\om$ such that for each symmetric function
$H:2^\om\times 2^\om\to 2^\om$
there exists a function $g:2^\om\to 2^\om$ such that $H(x,y)=f(g(x)+g(y))$
for every two distinct $x,y\in 2^\om$.  Furthermore if $F$ is
Borel, then $f$ can be taken to be Borel.
\end{prop}

\proof
Let $P_s\su\om$ for $s\in 2^{<\om}$ partition $\om$ into infinite
sets.  Given $s \in 2^{<\omega}$, we say that $y:P_s\to 2$ codes $x:\om\to 2$ if
$y(a_n)=x(n)$ where $a_0<a_1<a_2<\ldots$ is the increasing
listing of $P_s$.

Define $q \colon \rcantor \to \rcantor$ by letting $q(x)$ be such that
$q(x)\res P_{x\res n}$ codes $x$ for
every $n<\om$ and $q(x)\res P_s$ is identically 0 for
any $s$ which is not an initial segment of $x$.

Notice that it is possible to recover $u$ and $v$ from $q(u)+q(v)$ as long as neither $u$ nor $v$ is the constant 0 function.  To see this
let
$$\Sigma=\{s\in 2^{<\om}: \exists n\in P_s \;\;(q(u)+q(v))(n)\neq 0\}.$$
Suppose that $u(m)\neq v(m)$ and recall that neither $u$ nor $v$ is identically
zero.
Then for every $s\in\Sigma$ of length greater than $m$, exactly one of the following must hold:
\begin{itemize}
\item $q(v)\res P_s$
is identically zero and $(q(u)+q(v))\res P_s$ codes $u$;
\item $q(u)\res P_s$
is identically zero and $(q(u)+q(v))\res P_s$ codes $v$.
\end{itemize}
In other words, for sufficiently large values of $s$ the uncoding of $$(q(u)+q(v))\res P_s$$
will take on only one of two possible values and these two values will be $u$ and $v$.

Using this,  $f(w)$ is defined as follows. If there are distinct, non-zero,  $u$ and $v$ such that $w= q(u)+q(v)$ then these are unique.
In this case define $f(w) = F(u,v)$ where $u<v$ (for the sake of avoiding arbitrary choices in the definition).
Otherwise, define $f(w)$ to be the constant 0 function.
If $F$ is Borel, then $f$ can be defined in a Borel way, although its rank might increase.

To see that this definition works, let a symmetric function $$H:2^\om\times 2^\om\to 2^\om$$ be given.
By assumption there exists
$h$ such that $$H(x,y)=F(h(x),h(y))$$ for all $x,y\in 2^\om$.
Without loss of generality we may assume
that $h$ is one-to-one and $h(x) $ is not equal to the constant 0 function for any $x$.
To see this, note that we may replace any $h$ with $\hat{h}(x)=\langle 1^{\frown}x,h(x)\rangle$ and
then alter $F$ so that it ignores the first coordinate of $\hat{h}(x)$; that is,
define $$F_0(\langle u_0,u_1\rangle,\langle v_0,v_1\rangle)=F(u_1,v_1).$$

Now let  $g = q \circ h$. Then $f(g(x) + g(y)) = f(q(h(x))+q(h(y)))$ and keep in mind that $h(x)$ and $h(y)$ are non-zero and distinct. Hence
$f(q(h(x))+q(h(y))) = F(h(x),h(y)) = H(x,y)$ as required. Note that the symmetry of $H$ allowed the
arbitrary choice of ordering of $u$ and $v$ in the definition of $f$.
\qed

The proof of the following result is similar to Mansfield and Rao's proof
\cite{mansfield,mansfield2,rao2} that
the universal analytic set in the plane is not in the $\si$-algebra
generated by rectangles with measurable sides.  See also
Miller \cite{millerrectang}.

\begin{prop}
There does not exist a Borel function $$F:2^\om\times 2^\om\to 2^\om$$
such that for every Borel $G:2^\om\times 2^\om\to 2^\om$ there
exist functions $h$ and $k$ from $2^\om$ to $2^\om$ such that $k$ is Borel and
$$G(x,y)=F(h(x),k(y))$$
for all $x,y\in 2^\om$.
\end{prop}

\proof
Let $F \colon 2^\om\times 2^\om\to 2^\om$ be a Baire class $\al$ function, let
$U\su 2^\om\times 2^\om$ be a universal ${\bf\Sigma}_{\al+1}^0$
set and let $G$ be the characteristic function of $U$. Suppose that $h$ and $k$
are functions from $2^\om$ to $2^\om$ such that $k$ is Borel and
$$G(x,y)=F(h(x),k(y))$$
for all $x,y\in 2^\om$.
Let $P\su 2^\om$ be a perfect set on which
$k$ is continuous, and fix $x_0$ so that $U_{x_0}\su P$ and $U_{x_{0}}$ is
not ${\bf \Delta}_{\al+1}^0$.  If we define
$q:P\to 2^\om$ by setting $q(y)=F(h(x_0),k(y))$, then
then $q$ is Baire class $\al$ and $U_{x_0}=q^{-1}(1)$,
giving a contradiction.
\qed

%Louveau's Theorem \cite{louv} may be relevant for the following question.

\begin{remark}
The second author has recently shown that consistently the Borel subsets of
the plane are not in contained any bounded level of the $\sigma$-algebra generated by the
abstract rectangles. The proof of Theorem \ref{mainthm} shows that in this situation, there does not 
exist a Borel function $$F:2^\om\times 2^\om\to 2^\om$$
such that for every Borel $H:2^\om\times 2^\om\to 2^\om$ there
exist functions $g$ and $h$ from $2^\om$ to $2^\om$ such that
$$H(x,y)=F(g(x),h(y))$$
for all $x,y\in 2^\om$. The proof is a modification of arguments in \cite{miller}.
\end{remark}


The following type of universal function was introduced by Stevo Todorcevic.




\begin{define} Given a cardinal $\kappa$ and  $k \in \omega$, a sequence of continuous functions $$F_n\colon (2^\om)^{k} \to 2^\om\,\, (n<\om)$$
is $\kappa$ \emph{limit-universal} if for each $X \subseteq \rcantor$ of cardinality at most $\kappa$ and
each function $G\colon X^{k}\to 2^\om$ there
exists an injective function $h\colon X \to 2^\om$ such that for all $x_{1},\ldots,x_{k} \in X$,
$$G(x_{1},\ldots,x_{k})=\lim_{n\to\infty}F_n(h(x_{1}),\ldots,h(x_{k})).$$
\end{define}

%Todorcevic has proved the following theorem.

\begin{theorem}[Todorcevic \cite{todorcevic}]\label{stevosthrm}
  For each $k \in \omega$, there exists a $\pp$ limit-universal sequence of functions $F_{n} \colon (\rcantor)^{k} \to \rcantor$, for
  $n < \omega$.
\end{theorem}

\begin{remark} In the model from Theorem \ref{t:p}, $\pp = \aleph_{2}$ and $\cc = \aleph_{3}$.
\end{remark}

%Note that in the definition of Rothberger universal function there is no claim that the limit
%$\lim_{n\to\infty}F_n(h(\al),h(\be))$ exists for all $\alpha$ and
%$\beta$. Also observe that there is no contradiction here with Theorem~\ref{t:p}
%because $2^{\aleph_0} = \aleph_3$ in the model of that theorem, but
%$\mathfrak{p} = \aleph_2$.

Recall that a function $F \colon \rcantor \times \rcantor \to \rcantor$ being of level 2 means that for every $n \in \omega$ the
set $\{(x,y)\;:\; F(x,y)(n)=1\}$ is $F_\si$.
The following proposition shows that the existence of a $\cc$ limit-universal sequence of functions is equivalent
to the existence of a level 2 universal function.

\def\csqr{2^\om\times 2^\om}

\begin{prop}
For any cardinal $\ka$ the following are equivalent:

(1) There exists continuous functions $F_n:\csqr\to 2^\om$ $(n<\om)$ with the property that for each function $G:\ka\times\ka \to 2^\om$ there
exists a function $h:\ka\to 2^\om$ such that
$$G(\al,\be)=\lim_{n\to\infty}F_n(h(\al),h(\be))$$ for all
$\al,\be \in \ka$.

(2) There exists a level 2 function $F:\csqr\to 2^\om$
with the property that for each function $G:\ka\times\ka \to 2^\om$ there
exists a function $h:\ka\to 2^\om$ such that
$$G(\al,\be)=F(h(\al),h(\be))$$ for all $\al,\be \in \ka$.

\end{prop}

\proof

\noindent $(1)\rightarrow (2)$. Given the sequence of continuous functions
$F_n:\csqr\to 2^\om$ $(n<\om)$
define $F:\csqr\to 2^\om$ by setting
$F(x,y)(k)=1$ if and only if $F_n(x,y)(k)=1$ for all but finitely many $n<\om$.


\bigskip
\noindent $(2)\rightarrow (1)$.
{
Using a continuous pairing function $\pair(\cdot,\cdot)$ on $\rcantor \times \rcantor$,
define for each $k \in \omega$ the pair of (nondisjoint) $F_\si$ subsets of $\rcantor$,
$P^0_{k}$ and $P^{1}_{k}$, by setting
$$(\pair(u_0,u_1),\pair(v_0,v_1))\in P^i_{k}$$ if and only if $F(u_i,v_i)(k)=1$.
By the reduction property for $F_{\sigma}$ sets, for each $k \in \omega$ there exist disjoint $F_\si$ sets
$Q^0_{k}, Q^1_{k}$ with
$Q^i_{k}\su P^i_{k}$ and $Q^0_{k}\cup Q^1_{k} =  P^0_{k}\cup P^1_{k}$.
Write each $Q^i_{k}$ as an increasing sequence of closed sets
$Q^i_{k}=\bigcup_{n \in \omega} C^i_{k,n}$. For each $n, k \in \omega$, $C^0_{k,n}$ and $C^1_{k,n}$
are disjoint closed sets, so there exists a clopen set $D_{k,n}$
with $C^0_{k,n}\su D_{k,n}$ and $C^1_{k,n}$ disjoint from
$D_{k,n}$.
}

{
Define the continuous map $F_n \colon \rcantor \times \rcantor \to \rcantor$ by setting
$$F_n(u,v)(k)=1$$ if and only if $(u,v)\in D_{k,n}$.
}
Now we verify that this works.  Given $G \colon \kappa \times \kappa \to \rcantor$,
let $G_{0}$ be $G$ and define $G_{1} \colon \kappa \times \kappa \to \rcantor$ by setting
$G_1(\al,\be)(n)=1-G_0(\al,\be)(n)$ (that is, we switch
$0$ and $1$ on every coordinate of the output).
Let $h_{0}$ and $h_{1}$ be the results of applying (2) to $G_{0}$ and $G_{1}$, respectively.
%
%take $h_0$ and $h_1$
%as above and define .
%{
%For any $G$ let $G_0$ be $G$ and define $G_1$ by
%.  T.
%It follows that we have $h_0$ and $h_1$
%{(defined for $G_0$ and $G_1$ respectively)}  such that
%for ever $\al,\be<\ka$ and $n<\om$}
%
We have then that for every $k \in \omega$ and all $\alpha, \beta < \kappa$,
\begin{itemize}
\item $G(\al,\be)(k)=1 $ implies
\par $F(h_0(\al),h_0(\be))(k)=1$ and $F(h_1(\al),h_1(\be))(k)=0$
\item $G(\al,\be)(k)=0 $ implies
\par $F(h_0(\al),h_0(\be))(k)=0$ and $F(h_1(\al),h_1(\be))(k)=1$
\end{itemize}

Define $h \colon \rcantor \to \rcantor$ by setting $h(\ga)=\la h_0(\ga),h_1(\ga)\ra$. { Then
for all $\al,\be < \kappa$ and all $k \in \omega$ the following hold.}
\begin{itemize}
\item If $G(\al,\be)(k)=1$, then ${( h(\al),h(\be))}\in P_k^0\sm P_k^1$
so  ${( h(\al),h(\be))}\in Q_k^0$ and
$F_n({( h(\al),h(\be))})(k)=1$ for all but finitely many
$n$.

\item If $G(\al,\be)(k)=0$, then ${( h(\al),h(\be))}\in P_k^1\sm P_k^0$
so  ${( h(\al),h(\be))}\in Q_k^1$ and
$F_n({( h(\al),h(\be))})(k)=0$ for all but finitely many
$n$.
\end{itemize}
\qed

Davies \cite{davies} showed that the Continuum Hypothesis
{is equivalent to the assertion that } the function
$$F(\vec{x},\vec{y})=\sum_{n<\om} x_ny_n$$
has {the following } universal property:
for every $H:\rr\times\rr\to \rr$ there
are functions $f_n,g_n$ for $n<\om$ such that
$$H(x,y)=\sum_{n<\om}f_n(x)g_n(y)$$
for all $x,y\in \rr$.  Moreover, the functions $f_{n}$ and $g_{n}$ $(n < \omega)$ can be
taken so that the sum $\sum_{n<\om}f_n(x)g_n(y)$ has only finitely
many nonzero terms.
{If this requirement is relaxed to ordinary convergence of the
infinite sum, then the function $F(\vec{x},\vec{y})=\sum_{n<\om} x_n y_n$ is still universal
under the assumption $\pp = \cc$ (Shelah \cite{shelahciel}). However, it is not
universal after adding $\aleph_{2}$ many Cohen reals with finite support (\cite{shelahciel}).
%after adding $\omega_{2}$ many Cohen reals to a model of GCH \cite{roslan}.
%Moreover, Shelah \cite{roslan} remarks that in Cohen's model for the
%failure of the continuum hypothesis  in this
%weaker sense.}.
{These considerations suggest the following context for
studying universal functions. Let $(\mathbb{B},\cdot)$ be a Banach
algebra and $\psi\in \mathbb{B}^*$. The linear functional $\psi$
can be said to be $\kappa$-\emph{universal} if for every
$f:\kappa\times\kappa\to\rr$ there are
$h:\kappa\to\mathbb{B}$ and $g:\kappa\to\mathbb{B}$ such that
$f(\alpha,\beta) = \psi(h(\alpha)\cdot g(\beta))$. This will be
examined elsewhere.}

\section{Abstract universal functions}\label{abstract}

This section considers the question of universal functions without
regard to any definability properties.
The notion of universal function naturally generalizes to functions of the
form $F:\al\times\be\to\gamma$.

\begin{theorem}\label{existuniv}
If $\alpha$ and $\kappa$ are cardinals such that $\al^{<\kappa} = \kappa$, then there is a
universal function from $\kappa \times \kappa$ to $\al$.
\end{theorem}

\proof

Let $\mathcal{F}$ be the set of functions $f \colon \kappa \to \al$ for which
$\{ \ga < \kappa \mid f(\ga) \neq 0\}$ is a bounded subset of $\kappa$.
Then $|\mathcal{F}| = \al^{<\kappa}=\kappa$. Define
$U \colon (\kappa \times \mathcal{F})^{2}\to \al$ by setting
$$U((\ga, f_{1}),(\beta,f_{2}))=\left\{
\begin{array}{ll}
f_{1}(\beta) & \mbox{ if }\beta < \ga\\
f_{2}(\ga)& \mbox{ if }\ga \leq \beta\\
\end{array}\right.$$

By Remark \ref{differentfunctions}, it is enough to show that for each
$g \colon \kappa \times \kappa \to \al$ there exist $h \colon \kappa
\to (\kappa \times \mathcal{F})$ and $k \colon \kappa \to (\kappa
\times \mathcal{F})$ such that $$U(h(\ga),k(\beta)) =
g(\ga,\beta)$$ for all $\ga, \beta$ in $\kappa$. Fix $g \colon
\kappa \times \kappa \to \al$.  Define $h \colon \kappa \to (\kappa \times
\mathcal{F})$ by setting $h(\ga) = (\ga, f_{1,\ga})$, where
$f_{1,\ga} \colon \kappa \to \al$ is such that
$f_{1,\ga}(\beta)$ is $g(\ga, \beta)$ for all $\beta < \ga$
and $0$ for all $\beta \geq \ga$. Define $k \colon \kappa \to
(\kappa \times \mathcal{F})$ by setting $k(\beta) = (\beta,
f_{2,\beta})$, where $f_{2,\beta} \colon \kappa \to \al$ is such
that $f_{2,\beta}(\ga)$ is $g(\ga, \beta)$ for all $\ga \leq
\beta$ and $0$ for all $\ga > \beta$.

Now fix $\ga, \beta$ in $\kappa$. If $\ga > \beta$, then
$U(h(\ga),k(\beta)) = f_{1,\ga}(\beta) = g(\ga, \beta)$. If $\ga
\leq \beta$, then $U(h(\ga),k(\beta)) = f_{2,\beta}(\ga) = g(\ga,
\beta)$.
\qed


It follows from Theorem \ref{existuniv} that if $\ka^{<\ka}=\ka$,
then there is a universal function $U:\ka\times\ka\to\ka$.  So, for example,
there is a universal function from $\om \times \om$ to $\om$.
If $\ka^{<\ka}=\ka$, then $\ka$ must be a regular cardinal.
Theorem \ref{existuniv} implies that if $\ka$ is strong limit cardinal, then for every
$\al<\ka$ there is a universal function from $\ka \times \kappa$ to $\al$.
However we don't know the answer to the following question:

\begin{ques}\label{ques52}
If $\ka$ is a singular strong limit cardinal, does there
exist a universal function from $\ka\times\ka$ to $\ka$?
\end{ques}

\begin{prop}
Suppose that $\ka$ is a singular strong limit cardinal and
that $\al<\ka$. Then there is a universal function $U:\ka\times\al\to \ka$
if and only if  $\al$ is less than the cofinality of $\ka$.
\end{prop}
\proof
Let $\tau$  be the cofinality of   $\ka$.
If  $\al < \tau$, then there are only $\ka$ many maps
from $\al$ into $\ka$,  so $U$ just needs to list all of them
as a cross section $U_\be(\cdot)=U(\be, \cdot)$ for $\be<\ka$.

If  $\al \geq \tau$, we can diagonalize against any $U$ by eventually
avoiding the range of any cross section.  To see this
suppose $U:\ka\times\al\to \ka$ is any map.   Let $\ka_\de$ for
$\de<\tau$ be increasing and cofinal in $\ka$.
Construct a map
$d:\tau\to\kappa$
so that
$$d(\de)\in\ka\sm \{\;U(\be,\ga)\;:\; \be<\ka_\de,\;\ga<\al\}.$$
The map $f:\ka\times\tau\to\ka$ defined by
$f(\be,\de)=d(\de)$ witnesses that $U$ is not universal.
\qed

The following proposition, which also applies to singular cardinals,
shows that a negative answer to Question \ref{ques52} for
$\ka=\aleph_\om$
must use maps with domain at least $\om_1\times\om$. Its proof is similar to the proof
of Theorem \ref{existuniv}.

\begin{prop}\label{propomega}
For each infinite cardinal $\ka$ there exists
a function $U:\ka\times\ka\to\ka$ such that for each
$G:\om\times\om\to\ka$ there exists a function $h:\om\to\ka$ such that
$G(n,m)=U(h(n),h(m))$ for all $n, m \in \omega$.
\end{prop}

\proof
Let $$\ff=\{F:\om\to\ka \;:\; \forall^\infty n \;F(n)=0\}$$
Define $U:(\om\times\ff)^2\to\ka$ by
$$U((n,F_1),(m,F_2))=\left\{
\begin{array}{ll}
F_1(m) & \mbox{if } n>m\\
F_2(n) & \mbox{if } n\leq m\\
\end{array}\right.$$
Given any $G$ define $h(n)=(n,F_n)$ where $F_n\in\ff$ has
the property that $F_n(m)=G(n,m)$ whenever $m\leq n$.  Define
$k(m)=(m,F^\pr_m)$ where $F_m^\pr\in\ff$ has the property
that $F_m(n)=G(n,m)$ whenever $n\leq m$.  Then
\begin{itemize}
\item for any $n\leq m$ $U(h(n),k(m))=F_m^\pr(n)=G(n,m)$ and

\item for any $n> m$ $U(h(n),k(m))=F_n(m)=G(n,m)$.
\end{itemize}
As usual we may encode distinct $h,k$ into a single map.
\qed

The following theorem shows that it is relatively consistent with ZFC
that there is no universal function $F \colon \cc \times \cc \to 2$.
Given sets $X$, $Y$ and a cardinal $\kappa$, the partial order $\mathrm{Fn}(X, Y, \kappa)$
consists of partial functions from $X$ to $Y$ of cardinality less than $\kappa$, ordered by inclusion.


\begin{theorem}\label{follthrm} If $\cc = \aleph_{1}$ and $2^{\aleph_{1}} = \aleph_{2}$, then the
partial order $$\ctbl(\om_3) \times \fin(\om_2)$$ forces that $\cc = \aleph_{2}$ and that there is no $F\colon\om_2\times\om_2\to 2$
with the property that for every $f:\om_2\times\om_1\to 2$
there exists $g_1:\om_2\to\om_2$ and $g_2:\om_1\to\om_2$
such that $f(\al,\be)=F(g_1(\al),g_2(\be))$ for every $\al<\om_2$
and $\be<\om_1$.
\end{theorem}

\proof
%In our model $\cc=\om_2$ and there is no $F:\om_2\times\om_2\to 2$
%with the property that for every $f:\om_2\times\om_1\to 2$
%there exists $g_1:\om_2\to\om_2$ and $g_2:\om_1\to\om_2$
%such that $f(\al,\be)=F(g_1(\al),g_2(\be))$ for every $\al<\om_2$
%and $\be<\om_1$.

%Let $M$ be a countable transitive model of ZFC in which
Suppose that $\cc = \aleph_{1}$ and $2^{\aleph_{1}} = \aleph_{2}$.
Force with $\ctbl(\om_3)$ followed by $\fin(\om_2)$.
Let $G$ be $\ctbl(\om_3)$-generic over $V$ and
$H$ be $\fin(\om_2)$-generic over $V[G]$.  We will
show there is no such $F$ as above in the model $V[G][H]$.

By standard arguments\footnote{Kunen\cite{kunen} p.253,
Solovay \cite{solovay} p.10}
involving iteration and product forcing we may regard
$V[G][H]$ as being obtained by forcing with $\ctbl(\om_3)^{V}$ over
the ground model $V[H]$.  Of course, in $V[H]$ the
poset $\ctbl(\om_3)^V$ is not countably closed but it
still must have the $\om_2$-cc.  Hence for
any $F:\om_2\times\om_2\to 2$ in $V[G][H]$ we may find
$\ga<\om_3$ such that $F\in V[H][G\res\ga]$.

Use $G$ above $\ga$ to define $f:\om_2\times\om_1\to 2$, i.e.,
$$f(\al,\be)=G(\ga+\om_1\cdot\al+\be).$$
Suppose towards a contradiction that in $V[G][H]$ there were
functions $g_1:\om_2\to\om_2$ and $g_2:\om_1\to\om_2$
such that $f(\al,\be)=F(g_1(\al),g_2(\be))$ for every $\al<\om_2$
and $\be<\om_1$.
Using the $\om_2$-chain condition of $\ctbl(\om_3) \times \fin(\om_2)$, there would be an $I\su\om_3$
in $V$ of size $\om_1$ such that $g_2\in V[H][G\res(\ga\cup I)]$.
Choose $\al_0<\om_2$ so that
$\ga\cup I$ is disjoint from $$D=\{\ga+\om_1\cdot\al_0+\be\st \be<\om_1\}.$$

It easy to see by a density argument that the function
$G\res D$ is not in $V[H][G\res(\ga\cup I)]$.  But
this is a contradiction, since $G\res D$ is easily defined
from the function $f(\al_0,\cdot)$,
$f(\al_0,\be)=F(g_1(\al_0),g_2(\be))$ for all $\be$,
and $F,g_2$ are in $V[H][G\res(\ga\cup I)]$.
\qed

\begin{ques}
Is it consistent with $2^{<\cc}>\cc$ to have a universal
function $F:2^\om \times 2^\om\to 2^\om$?  What about a Borel $F$?
\end{ques}



The two following propositions illustrate two cases where a universal function with range $\kappa$ can be lifted
to one with range $\kappa^{+}$.

%\pagebreak

\begin{prop}\label{equiv}
For any infinite cardinal $\kappa$, there is a universal $$F:\kappa^{+}\times\kappa^{+}\to \kappa^{+}$$ if and only if
there is a universal function $G:\kappa^{+}\times\kappa^{+}\to \kappa$.
\end{prop}

\proof
The forward direction follows from Remark \ref{easyone}. For the reverse direction, suppose that we are given a universal $G:\kappa^{+}\times\kappa^{+}\to \kappa$.
For each $\al<\kappa^{+}$ let $b_{\alpha} \colon \kappa \to \alpha$ be a bijection.
%$\{\delta^{\alpha}_{\xi}\;:\; \xi <\kappa\}$ be an enumeration of $\al$.
Define $F:\kappa^{+}\times\kappa^{+}\to \kappa^{+}$ by setting
$$F(\pair(\al_1,\al_2,\al_3),\pair(\be_1,\be_2,\be_3))=\left\{
\begin{array}{ll}
b_{\be_3}(G(\al_2,\be_2)) & \mbox{ if }\al_1\leq \be_1\\
b_{\al_3}(G(\al_2,\be_2))& \mbox{ if }\al_1 > \be_1 \\
\end{array}\right.$$
where $\langle a,b,c\rangle$ represents  a bijection between an infinite set and its triples, or, equivalently,
$\langle a,b,c\rangle $ is defined to be $\langle  \langle  a,b \rangle ,c\rangle$.
%$$F(\pair(\al_1,\al_2,\al_3),\pair(\be_1,\be_2,\be_3))=\ga$$ if, letting
%$\xi = G(\al_2,\be_2)$, either $\al_1\leq \be_1$ and $\delta^{\be_3}_{\xi}=\ga$
%or $\al_1 > \be_1$ and $\delta^{\al_3}_{\xi}=\ga$.
To see that $F$ is universal, fix a function $f:\kappa^{+}\times\kappa^{+}\to \kappa^{+}$.
Let $j:\kappa^{+}\to\kappa^{+}$
be such that $f(\al,\be)<j(\max(\al,\be))$ for all $\al,\be < \kappa^{+}$.
Define $f^*:\kappa^{+}\times\kappa^{+}\to \kappa$ by setting
$f^*(\al,\be)=\xi$, where $\xi<\kappa$ is such that
$f(\al,\be)=b_{j(\max(\al,\be))}(\xi)$.
As $G$ is universal, there exists a function  $h \colon \kappa^{+} \to \kappa^{+}$ such that
$$f^*(\al,\be)=G(h(\al),h(\be))$$ for all $\al,\be<\kappa^{+}$.
This means that for all $\alpha, \beta < \kappa^{+}$,
$$f(\al,\be)=b_{j(\max(\al,\be))}(G(h(\al),h(\be))).$$
%if and only if $$G(h(\al),h(\be))=n \rmand j(\max(\al,\be))_n=\ga.$$
It follows that for all $\al,\be < \kappa^{+}$,
$$f(\al,\be)=F(\la\al,h(\al),j(\al)\ra,\;\la\be,h(\be),j(\be)\ra).$$
\qed


\begin{prop}\label{lambdaplus} For any pair of infinite cardinals $\kappa > \lambda$,
there is a universal function from $\kappa \times \lambda$ to $\lambda$ if and only if there is one from $\kappa \times \lambda$ to $\lambda^{+}$.
\end{prop}

\proof
Again, the reverse direction follows from Remark \ref{easyone}. For the forward direction,
let $F:\kappa\times\lambda \to \lambda$ be a universal function  and
fix bijections $j_\al:\lambda\to\al$, for each $\alpha$ in the interval $[\lambda, \lambda^{+})$.
Construct $F^\pr$ with the property that for each pair
$\al \in \kappa,\be \in \lambda^{+}$ there exists a $\ga<\kappa$ such
that $F_\ga^\pr=j_\be\circ F_\al$, i.e.,
$$F^\pr(\ga,\delta)=j_\be(F(\al,\delta)) \mbox{ for all } \delta < \lambda.$$
Now we verify that $F^\pr$ is universal.  Let
$f^\pr : \kappa \times \lambda \to \lambda^{+}$ be arbitrary. For each $\alpha < \kappa$, let
$$\iota_\al=\lambda+\sup \{f^\pr(\al,\delta)+1\st \delta < \lambda\}.$$
Define $f$ into $\lambda$ by $f(\al,\delta)=j_{\iota_\al}^{-1}(f^\pr(\al,\delta))$.
Since $F$ is universal there exist $g,h$ with
$$F(g(\al),h(\delta))=f(\al,\delta)=j_{\iota_\al}^{-1}(f^\pr(\al,\delta))$$
for all $(\alpha, \delta) \in \kappa \times \lambda$.
By our definition of $F^\pr$ we may construct $g^\pr$ so
that
$$F^\pr(g^\pr(\al),h(\delta))=j_{\iota_\al}(F(g(\al),h(\delta)))$$
for all $(\alpha, \delta) \in \kappa \times \lambda$.
Then we are done, since
$$j_{\iota_\al}(F(g(\al),h(\delta)))=f^\pr(\al,\delta)$$
for all $(\alpha, \delta) \in \kappa \times \lambda$.

\qed

%\begin{prop}\label{equiv}
%There is a universal $F:\om_1\times\om_1\to \om_1$ if and only if
%there is a universal $G:\om_1\times\om_1\to \om$.
%\end{prop}
%\proof
%Suppose we are given a universal $G:\om_1\times\om_1\to \om$.  For each $\al<\om_1$ let
%$\al=\{(\al)_n\;:\; n<\om\}$ be an enumeration of $\al$.
%Define $F:\om_1\times\om_1\to \om_1$ by setting
%$F(\pair(\al_1,\al_2,\al_3),\pair(\be_1,\be_2,\be_3))=\ga$ if
%$G(\al_2,\be_2)=n$ and either $\al_1\leq \be_1$ and $(\be_3)_n=\ga$
%or $\al_1 > \be_1$ and $(\al_3)_n=\ga$.

%Given
%any function $f:\om_1\times\om_1\to \om_1$ choose $j:\om_1\to\om_1$
%so that $f(\al,\be)<j(\max(\al,\be))$ for all $\al,\be$.
%Define $f^*:\om_1\times\om_1\to \om$ by setting
%$f^*(\al,\be)=n$, where $n<\om$ is such that
%$f(\al,\be)=(j(\max(\al,\be)))_n$.
%Now by our assumption on $G$ there is $h$ with
%$f^*(\al,\be)=G(h(\al),h(\be))$ for all $\al,\be<\om_1$.
%This means that for all $\alpha, \beta, \gamma < \omega_{1}$,
%$f(\al,\be)=\ga$ if and only if $$ G(h(\al),h(\be))=n \rmand j(\max(\al,\be))_n=\ga.$$
%It follows that for every $\al,\be < \omega_{1}$,
%$$f(\al,\be)=F(\la\al,h(\al),j(\al)\ra,\;\la\be,h(\be),j(\be)\ra).$$
%\qed

The following theorem connects the existence of universal functions on $\kappa \times \kappa$
with finite range to the existence of universal graphs.


\begin{theorem}\label{sixeq}
For any infinite cardinal $\kappa$ the following are equivalent:
\begin{enumerate}
\item For each $n\in \mathbb{N}$ there is a
 universal function from $\kappa\times\kappa$ to $n$.
\item For some $n\in \mathbb{N}$ with $n\geq 2$ there is a
 universal function from $\kappa\times\kappa$ to $n$.
\item There is a symmetric, irreflexive function from
 $\kappa\times\kappa$ to $2$ universal for all
 symmetric, irreflexive functions from $\kappa\times\kappa$ to $2$; in other words, there is a symmetric, irreflexive function
 $U:\kappa\times\kappa \to 2$ such that for any  symmetric, irreflexive function
 $f:\kappa\times\kappa \to 2$ there   is $h:\kappa\to\kappa$ such that $f(\xi,\eta)= U(h(\xi),h(\eta))$ for all $\xi$ and $\eta$.
\item There is a universal graph on $\kappa$; in other words, there is a graph $G$ whose vertex set is $\kappa$ such that for any other
graph $G^* $ with  vertex set  $\kappa$ there is a graph embedding of $G^*$ into $G$.
\end{enumerate}
\end{theorem}
\proof
Statement (1) clearly implies statement (2); (2) implies (1) by Remark \ref{easyone} and Proposition
\ref{easytwo} (with finite exponent).
To get from (2) to (3),  given a universal function $U:\ka\times\ka\to n$, define
$$V(\al,\be)=\left\{
\begin{array}{ll}
1 &\mbox{ if $\al\neq\be$ and either $U(\al,\be)=1$
or $U(\be,\al)=1$} \\
0 &\mbox{ otherwise }\\
\end{array}\right.$$
Then $V$ is universal in the sense of (3).

\noindent Statements (3) and (4) are equivalent since the characteristic function
of a graph is symmetric and irreflexive and Remark~\ref{oneonerem} is still in effect.

%\pagebreak

It remains only to show that one of (3) and (4) implies one of (1) and (2).
We give a proof of (1) from (3). Fix $n \in \omega$ with $n \geq 2$, and
let $\Psi:  \kappa\to [\kappa]^{n}$ be a bijection.
If $U:\kappa\times \kappa\to 2$ is a function universal for
symmetric functions, define
$U^*:\kappa\times \kappa\to n$ by letting
$U^*(\alpha,\beta)$ be
 $$\left(\max_{\xi\in \Psi(\alpha)}\sum_{\eta\in\Psi(\beta)} U(\xi,\eta)\right) - 1$$
 if this quantity is nonnegative, and $0$ otherwise.
To see that $U^*$ is universal for functions from $\kappa\times\kappa$ to $n$,
fix $F \colon \kappa \times \kappa \to n$. Let  $\{E_\xi\}_{\xi\in\kappa}$ be a partition
of $\kappa$ into sets of size $n$. We construct a symmetric function $F^{*}$
from $\kappa\times \kappa$ to $2$ so that for each $\alpha, \be\in\ka$
$$F(\al,\be)=\left(\max_{\xi \in E_\al}\sum_{\eta\in E_\be} F^*(\xi,\eta)\right) - 1.$$
We can realize $F^*$ as the characteristic function of a graph.
For each $\alpha \in \kappa$, let $\al^*$ denote $\min(E_\al)$.  Construct the graph on each of
the pairwise disjoint pieces
$E_\al\times E_\be$ by connecting $\al^*$ to
$F(\al,\be)+1$
elements of $E_\be$ including $\be^*$
and connecting $\be^*$ to exactly
$F(\be,\al)+1$ elements of $E_\al$.  The ``plus one'' is so that the
two minimum elements can always be connected.

Let $g:\kappa \to \kappa$ be one-to-one
(see Remark \ref{oneonerem}) such that
$$U(g(\alpha),g(\beta)) = F^*(\alpha,\beta)$$ for all
$\alpha, \beta$ in $\kappa$. Define
$H:\kappa\to \kappa$ by setting each
$H(\xi) = \Psi^{-1}g[E_\xi]$. Then for each $\alpha, \beta$ in $\kappa$,
$$F(\al,\be)=
(\max_{\xi \in E_\al}\sum_{\eta\in E_\be} F^*(\xi,\eta)) - 1
=(\max_{\xi \in E_\al}\sum_{\eta\in E_\be} U(g(\xi),g(\eta))) - 1,$$
which, as $g$ is one-to-one, is equal to $(\max_{\xi \in g[E_\al]}\sum_{\eta\in g[E_\be]} U(\xi,\eta)) - 1$.
Since this last term is nonnegative, it is equal to $U^*(H(\al),H(\be))$.
%To get the second line, use the fact that $g$ is one-to-one.
\qed

%All that is left to be proved is that (3) implies (1).
%Given $n$ let $\Psi:  \kappa\to [\kappa]^n$ be a bijection.
%If $U:\kappa\times \kappa\to 2$ is a function universal for
%symmetric functions, define
%$U^*:\kappa\times \kappa\to n$ by
%$$U^*(\alpha,\beta) =
% \sup_{\xi\in \Psi(\alpha)}\sum_{\eta\in\Psi(\beta)} U(\xi,\eta) - 1  .$$
%To see that $U^*$ is universal for functions from $\kappa\times\kappa$ to $n$
%let $F$ be any such a function. Let  $\{E_\xi\}_{\xi\in\kappa}$ be a partition
%of $\kappa$ into sets of size $n+1$. Construct a symmetric function $F^{*}$
%from $\kappa\times \kappa$ to $2$ so that for each $\alpha, \be\in\ka$
%$$F(\al,\be)=\sup_{\xi \in E_\al}\sum_{\eta\in E_\be} F^*(\xi,\eta) - 1.$$

%We can realize $F^*$ as the characteristic function of a graph.
%Let $\al^*=\min(E_\al)$.  Construct the graph on each of
%the pairwise disjoint pieces
%$E_\al\times E_\be$ by connecting $\al^*$ to
%$F(\al,\be)+1$
%elements of $E_\be$ including $\be^*$
%and connecting $\be^*$ to exactly
%$F(\be,\al)+1$ elements of $E_\al$.  The ``plus one'' is so that the
%two minimum elements can always be connected.

%Then if $g:\kappa \to \kappa$ is one-to-one
%(see Remark \ref{oneonerem}) such that
%$$U(g(\alpha),g(\beta)) = F^*(\alpha,\beta)$$ for all
%$\alpha, \beta$ in $\kappa$ then define
%$H:\kappa\to \kappa$ such
%that $H(\xi) = \Psi^{-1}g(E_\xi)$ and note that

%$$F(\al,\be)=
%\sup_{\xi \in E_\al}\sum_{\eta\in E_\be} F^*(\xi,\eta) - 1
%=\sup_{\xi \in E_\al}\sum_{\eta\in E_\be} U(g(\xi),g(\eta)) - 1 = $$
%$$ \sup_{\xi \in g(E_\al)}\sum_{\eta\in g(E_\be)} U(\xi,\eta) - 1
%= U^*(H(\al),H(\be))$$
%To get the second line, use the fact that $g$ is one-to-one.
%\qed

\begin{ques}
Does the existence of a universal $F:\om_1\times\om_1\to 2$
imply that there is a universal function $G:\om_1\times\om_1\to \om$?
\end{ques}

The rest of this section concerns universal functions on $\omega_{1} \times \omega_{1}$.


\begin{remark}\label{shelahuniv}
Shelah \cite{shelah,shelahsmall,shelahcorrection} proved that it is consistent
with $\cc > \aleph_{1}$ that there is a universal graph on $\om_1$.
By Theorem~\ref{sixeq}, in his model there are
universal functions from $\om_1 \times \om_1$ to $n$ for each $n<\om$.
\end{remark}

Shelah's result was
generalized in Mekler (\cite{MR1056364}, Theorem 2).
In Mekler's terminology, a 3-\emph{amalgamation class} $K$ is a class of models
of a universal theory in a relational language which satisfies the following amalgamation
property: if $\{ M_{a} : a \in \mathcal{P}^{-}(3)\}$ are structures in $K$ for which
$M_{a} \cap M_{b} = M_{a \cap b}$ for all $a, b \in \mathcal{P}^{-}(3)$, then there is an
$M \in K$ such that $M_{a} \subseteq M$ for each $a \in \mathcal{P}^{-}(3)$, where
$\mathcal{P}^{-}(3)$ denotes the set $\mathcal{P}(3) \setminus \{3\}$.

%\begin{theor}[Mekler \cite{MR1056364}] Suppose that $T$ is a theory in a relational language
%which has universal axioms,
%only countably
%many finite models up to isomorphism, and satisfies 3-amalgamation.
%Then is consistent with the negation of the continuum hypothesis that
%$T$ has a model of size $\om_1$ such that
%every model of $T$ of size $\om_1$ is isomorphic to a substructure
%of it.
%\end{theor}

\begin{theor}[Mekler \cite{MR1056364}]\label{Meklerthrm} If $2^{\aleph_{1}} = \aleph_{2}$, then there
is a c.c.c. partial order forcing that that $\mathfrak{c} = \aleph_{2}$ and that
for every 3-amalgamation class $K$ having only countably many finite models up to isomorphism,
there is a model $M$ in $K$ of cardinality $\aleph_{1}$ such that every model in $K$ of cardinality
$\aleph_{1}$ is isomorphic to a substructure of $M$.
\end{theor}


The following theorem is a corollary of Mekler's result.


\begin{theor}\label{t:mek}
It is consistent that  $2^{\aleph_0} > \aleph_1$ and there is a
universal function from $\om_1 \times \om_1$ to $\om_1$.
\end{theor}

\proof
By Proposition \ref{equiv} it is enough to find a universal
function from $\om_1 \times \om_1$ to $\om$.  Let $L$ be the language with
countably many binary predicate symbols $R_n(x,y)$.  Let
$T$ be the theory with countably many axioms:
$$\forall x,y \;\; (R_n(x,y)\to \neg R_m(x,y))$$
for each $n\neq m$.  Note that $T$ has only countably many
finite models up to isomorphism and is axiomatized by universal
sentences.

To verify that the class of models of $T$ satisfies the amalgamation
property of 3-amalgamation classes, note that if $M_{a}$ ($a \in
\mathcal{P}^{-}(3)$) are models of $T$ such that $M_{a} \cap M_{b} =
M_{a \cap b}$ for all $a,b \in \mathcal{P}^{-}(3)$, then
$\bigcup\{M_{a} : a \in \mathcal{P}^{-}(3)\} \models T$.

%Note that $T$ satisfies $n$-amalgamation
%for every $n<\om$.  For example, for $n=3$, any three models
%$A,B,C$ of $T$ which can be amalgamated in pairs can be simultaneously
%amalgamated.  We can take $R_n=R_n^A\cup R_n^B\cup R_n^C$.
%then $(A\cup B\cup C, R_n)_{n<\om}$ will be a model of $T$.

Suppose now that $(\om_1,\{R_n\}_{n<\om})$ is a universal model of $T$.
Define a function $U:\om_1^2\to\om$ by
$$U(\al,\be)=\left\{
\begin{array}{ll}
n & \mbox{ if }R_n(\al,\be)\\
0 & \mbox{ if } \forall n \; \neg R_n(\al,\be)\\
\end{array}\right.$$
Now given any $g:\om_1^2\to\om$ define $R^g_n(\al,\be)$
if and only if $g(\al,\be)=n$.  The structure
$(\om_1,\{R^g_n\}_{n<\om})$ is a model of $T$.  An embedding of
this structure into our universal model gives a map
$h:\om_1\to\om_1$ such that $g(\al,\be)=U(h(\al),h(\be))$
for all $\al,\be<\om_1$.

\qed

We take up the question of model-theoretic universality in
section \ref{mtu}.
Next we consider the problem of universal functions
on $\om_1$ assuming Martin's Axiom.



\begin{theorem}
Assume MA$_{\om_1}$.  Then there exists
$F:\om_1\times\om\to\om_1$ which is universal.
\end{theorem}

\proof

By Proposition \ref{lambdaplus} we need only
produce a universal $F:\om_1\times\om\to\om$.

Standard arguments show that there exists a family $h_\al:\om\to\om$
for $\al<\om_1$ of independent functions, i.e., for
any $n$, $\al_1<\al_2<\cdots<\al_n<\om_1$ and $s:\{1,\ldots,n\}\to\om$ there
are infinitely many $k<\om$ such that
$$h_{\al_1}(k)=s(1)$$
$$h_{\al_2}(k)=s(2)$$
$$\vdots$$
$$h_{\al_n}(k)=s(n).$$
Define $H:\om_1\times\om\to\om$ by $H(\al,n)=h_\al(n)$.
We show that $H$ is universal mod finite, in sense which will
be made clear.
Given any $f:\om_1\times\om\to\om$ define the following
poset $\poset$.  A condition $p=(s,F)$ is a pair
such that $s\in\om^{<\om}$ is one-to-one
and $F\in [\om_1]^{<\om}$.
We define $p\leq q$ if and only if
\begin{enumerate}
\item $s_q\su s_p$,
\item $F_q\su F_p$, and
\item $f(\al,n)=h_\al(s_p(n))$
for every $\al\in F_q$ and $n\in\dom(s_p)\sm\dom(s_q)$.
\end{enumerate}
The poset $\poset$ is c.c.c., and in fact $\si$-centered,
since any two conditions with the same $s$ are compatible.
Since the family $\{h_\al :\al<\om_1\}$ is independent,
for any $p\in\poset$ there are extensions of $p$ with arbitrarily
long $s$ part.   It follows from MA$_{\om_1}$ that there exists
$h:\om\to\om$ with the property that for every $\al<\om_1$
for all but finitely many $n$ that $f(\al,n)=h_\al(h(n))$.

To get a universal map $F:\om_1\times\om\to\om$, simply take
any $F$ with the property that for every $\al<\om_1$
and any $h^\pr=^*h_\al$ (equal mod finite)
there is $\be$ such that $F(\be,n)=h^\pr(n)$ for every $n$.
Since the function $h$ is one-to-one, it easy to find
$k:\om_1\to\om_1$ such that $F(k(\al),h(n))=f(\al,n)$ for
all $\al$ and $n$.

\qed

Theorem \ref{MAnoU} below shows that the existence of
a universal function for $\om_1$ does not follow from Martin's Axiom.
First we have the following lemmas, the first of which follows from a simple modification
of the Sierpi\'nski partition sending pairs of
reals to some rational between.

\begin{lemma}
There exists $S:[\omega_{1}]^2\to\omega$ such that
\begin{itemize}
\item for all uncountable $X\subseteq \omega_1$ and
$j\in\omega$ there is an uncountable $Z\subseteq X$ such
that $S(p)>j$ for all $p\in [Z]^2$
\item for all $\xi$ the restriction of the mapping
$\eta \mapsto S(\{\xi,\eta\})$ to $\xi$ is one-to-one.
\end{itemize}
\end{lemma}
\proof
Let $\{r_\xi\}_{\xi\in\omega_1}$ enumerate any uncountable set of reals and let $\mathbb Q = \{q_n\}_{n\in\omega}$.
Any function $S:[\omega_{1}]^2\to\omega$ satisfying $q_{S(\xi,\eta)}$
falls between $r_\xi$ and $r_\eta$ will satisfy the first requirement because, given $j$ and $X$ there is a $\subseteq$-minimal interval $J$
with endpoints in $\{q_i,q_2,\ldots q_j\}$ such that $Z=J\cap X$ is uncountable. It is immediate that  $S(p)>j$ for all $p\in [Z]^2$.
Any easy inductive argument then yields an $S$ satisfying both requirements.
\qed

\begin{lemma}\label{lemmahechler}
For each $r \in \rcantor$, let $G_{r} \colon \omega_{1} \times \omega_{1} \to \omega$ be defined
by setting $G_r(\eta,\xi)=r(S(\{\eta,\xi\}))$.
Fix $U:\omega_1\times\om_1\to\omega$, and let $H \in \rcantor$ be Hechler generic over a model
$V$ containing $U$. Then, in $V[H]$, any partial order $\Poset$
such that
$$1\forces{\Poset}{(\exists h:\omega_1\to\omega_1)
 (\forall \eta) (\forall \xi\neq \eta)\ U(h(\eta),h(\xi)) =
 G_H(\eta,\xi)}$$
contains an uncountable antichain.
\end{lemma}

\proof
Let $h$ be a name such that
$$1\forces{\Poset}{ (\forall \eta) (\forall \xi\neq \eta)\ U(h(\eta),h(\xi)) = G_H(\eta,\xi)}.$$ For each $\xi \in \omega_{1}$, choose a
condition $(t_\xi,F_\xi)$ in Hechler forcing $\mathbb{H}$, a name $p_\xi$ for an element of $\Poset$ and an ordinal $\alpha_\xi$ such that
$$((t_\xi,F_\xi),p_\xi)\forces{\mathbb{H}\star \Poset}{h(\check{\xi}) = \check{\alpha}_\xi}.$$ Let $t:n\to\omega$ be such that there is an uncountable set $X\subseteq \omega_1$ such that $t_\xi = t$ for all $\xi \in X$. Let $Z\subseteq X$ be uncountable such that $S(w)>n$ for all $w\in [Z]^2$.

For each $\xi \in \omega_1$ let $D_\xi$ be the partial function from $\omega$ to $\omega$ with domain $\{ S(\{\xi, \eta\}) : \eta < \xi \}$ defined by setting
$$D_\xi(S(\{\xi,\eta\})) = U(\alpha_\xi, \alpha_\eta)+ 1.$$ This is well defined by the one-to-one property of $S$. By extending
the second coordinate of $(t_\xi,F_\xi) = (t,F_\xi)$ it may be assumed that $F_\xi(j)\geq D_\xi(j)$ for all $j\in \dom(D_\xi)\cap\dom(F_\xi)$.  Now if $\xi$ and $\eta$ belong to $Z$ and $\eta< \xi$ then $((t,F_\xi),p_\xi)$ and $((t,F_\eta),p_\eta)$ are incompatible.

To see this suppose that a condition $((s,F),p)$ were stronger than both $((t,F_\xi),p_\xi)$ and $((t,F_\eta),p_\eta)$. By extending $(s,F)$, it may be assumed that $S(\{\xi,\eta\})\in \dom(s)$. Since $\{ \xi, \eta\} \subseteq Z$, each value $S(\{\xi,\eta\}) > n$, so $S(\{\xi,\eta\})\in \dom(s)\setminus \dom(t)$. Hence,
$((s,F),p)$ as an element of ${\mathbb{H}\star \Poset}$ forces the following
$$s(S(\{\xi,\eta\})) \geq F_\xi(S(\{\xi,\eta\})) \geq D_\xi(S(\{\xi,\eta\})) > U(\alpha_\xi, \alpha_\eta) $$
$$= U(h(\xi), h(\eta)) = G_H(\xi,\eta) = H(S(\{\xi,\eta\})) = s(S(\{\xi,\eta\}))$$
yielding a contradiction. Since $\mathbb{H}$ has the c.c.c. it follows that $\Poset$ does not.
\qed

Lemma \ref{lemmahechler} implies the following.

\begin{theorem}\label{MAnoU}
In the standard model of MA obtained by forcing over a model of GCH with a finite support iteration of length $\omega_2$
of c.c.c. posets, there is no universal function from
$\omega_{1} \times \om_1$ to $\omega$.
\end{theorem}

\subsection{Property R}

We conclude this section by connecting the existence of universal functions from $\omega_{1} \times \omega_1$ to $\omega$ with
the existence of certain functions on pairs from $\omega_{1}$.


\begin{define} A function $\Phi \colon [\omega_{1}]^{2} \to \omega$ has \emph{Property R} if
\begin{itemize}
\item whenever $k \in \omega$ and $\{\{a_\xi,b_\xi\} : \xi\in\omega_1\}$ is a family of disjoint pairs from $\omega_{1}$ with each $a_\xi\leq b_\xi$, there are distinct $\xi$ and $\eta$ such that $\Phi(\{a_\xi,a_\eta\}) \geq  \Phi(\{b_\xi,b_\eta\}) \geq k$;
\item for each $\xi\in\omega_1$ and $k\in \omega$ there are only finitely many $\eta \in \xi$ such that $\Phi(\{\xi,\eta\}) = k$.
\end{itemize}
\end{define}

Functions with similar properties appear in Theorem~6 of \cite{ShSt}.

%Since the set $\SetOf{\Phi(\{\beta_i, \beta_{t^\frown k}\})}{k\in\omega}$ is infinite for each $t$ and $i$, it is now easy to inductively choose $t\in %\omega^{<j}$ such that
% $\Phi(\{\beta_i , \beta_{t\restriction n}\})> \Phi( \{\alpha' ,\alpha \})$ if $\{\alpha' ,\alpha \}\in [ B\cap \mathfrak{M}\cup \{\beta_{t\restriction %1},\beta_{t\restriction 2}, \ldots \beta_{t\restriction (n-1)}\}]^2$. It follows that
% $$(B \cup \{\beta_{t\restriction 1},\beta_{t\restriction 2}, \ldots \beta_{t\restriction (|t|)}\}, N \cup \{\mathfrak{M}_{t\restriction %1},\mathfrak{M}_{t\restriction 2}, \ldots \mathfrak{M}_{t\restriction (|t|)}\})$$ belongs to $\mathbb{P}(\Phi)$ and, by the definition of $t\restriction (|t|)$, %it follows that this condition belongs to $D$.
%\end{proof}

 %There are then $(\beta^*_t, \mathfrak{M}_t)$ for $t\in \omega^{<j}$ such that:
 %\begin{itemize}
 %\item $\beta_{t^\frown k} > \beta_t$ for all $t^\frown k \in \omega^{<j}$
 %\item $\beta_{t^\frown k} > \beta_{t^\frown m} $ if $k>m$
 %\item $\beta_\emptyset > \alpha$ for all $\alpha \in B\cap \mathfrak{M}$
 %\item $\Phi( \{\beta_{t} ,\alpha \})> \Phi( \{\alpha' ,\alpha \})$ if $\{\alpha' ,\alpha \}\in [ B\cap \mathfrak{M}\cup \{\beta_\emptyset,\beta_{t\restriction %1}, \ldots \beta_{t\restriction (|t|-1)}\}]^2$
 %\item $(B\cap \mathfrak{M} \cup \{\beta_\emptyset,\beta_{t\restriction 1}, \ldots \beta_{t\restriction (|t|)}\}, N\cap \mathfrak{M} \cup %\{\mathfrak{M}_\emptyset,\mathfrak{M}_{t\restriction 1}, \ldots \mathfrak{M}_{t\restriction (|t|)}\})$ belongs to the dense set  $ D$.
 %\end{itemize}
 % This follows from the fact that the $\beta_i$ are separated by elements of $N$.

 %It is now easy to choose $t\in \omega^{<j}$ such that
 %$(B \cup \{\beta_\emptyset,\beta_{t\restriction 1}, \ldots \beta_{t\restriction (|t|)}\}, N \cup \{\mathfrak{M}_\emptyset,\mathfrak{M}_{t\restriction 1}, \ldots %\mathfrak{M}_{t\restriction (|t|)}\})$ belongs to $\mathbb{P}(\Phi)$
%\end{proof}
\vspace{\baselineskip}

Given a sequence $\langle \sigma_{\alpha} : \alpha < \omega_{1} \setminus \omega \rangle$ such that each $\sigma_{\alpha}$ is an infinite set of pairwise disjoint pairs from $\alpha$, one can recursively define a function $\Phi \colon [\omega_{1}]^{2} \to \omega$ with the property that for each $\eta < \omega_{1}$,
\begin{itemize}
\item for all distinct $\zeta, \rho < \eta$, $\Phi(\{\zeta, \eta\}) \neq \Phi(\{\rho, \eta\})$;
\item for all $\zeta \in [\omega, \eta)$, all
$\alpha \in [\omega, \zeta]$ and all $k \in \omega$, there exist $\delta < \gamma$ such that $\{ \delta, \gamma\} \in \sigma_{\alpha}$ and
$\Phi(\{\delta, \zeta\}) = \Phi(\{\gamma, \eta\}) \geq k$.
\end{itemize}
It follows that if $\Diamond$ holds, and is exemplified by $\langle \sigma_{\alpha} : \alpha < \omega_{1} \setminus \omega \rangle$, then functions with Property R exist.
It can be verified in a straightforward manner that functions with Property R are preserved by
forcing by partial orders satisfying Knaster's condition (i.e., for which every uncountable set of conditions has an uncountable pairwise compatible subset).
The existence of a function with Property R is then consistent with the statement $\mathfrak{b} > \aleph_{1}$.


\begin{prop}\label{nuftom}
If $\mathfrak{b}>\aleph_1$ and there exists a function $\Phi \colon [\omega_{1}]^{2} \to \omega$ with Property R then there is no
universal function from $\omega_1 \times \omega_1$ to $\omega$.
\end{prop}

\proof
Let $U:\omega_1 \times \omega_{1} \to\omega$ be given.
%Let $\Phi:[\omega_1]^2 \to \omega$ be the function defined in Theorem~6 of \cite{ShSt} satisfying the following key property (Property R):
%If $\{a_\xi,b_\xi\}_{\xi\in\omega_1}$ is a family of disjoint pairs with $a_\xi\leq b_\xi$ and $k\in \omega$ then there are distinct $\xi$ and %$\eta$ such that $\Phi(\{a_\xi,a_\eta\}) \geq  \Phi(\{b_\xi,b_\eta\}) \geq k$.
%It will, furthermore, be assumed that  (This is justified by examining the proof of Theorem~6 of \cite{ShSt}.)
Define $F_\xi:\omega\to\omega$ for each $\xi < \omega_{1}$
by setting $F_\xi(m)$ to be the largest member of the finite set
$$\{ U(\xi,\eta) + 1 \mid \eta< \xi \,\wedge\, \Phi(\{\xi,\eta\}) = m\}\cup\{0\}.$$
%and observe that the maxmimum is always defined.
Let $F:\omega\to\omega$ be a non-decreasing function such that $F\geq^* F_\xi$ for all $\xi$.
Define $G:\omega_1 \times \omega_{1} \to\omega$ by setting $G(\xi,\eta)= F(\Phi(\{\xi,\eta\}))$.
Fixing an injection $h \colon \omega_{1} \to \omega_{1}$, we will find $\xi$ and $\eta$ in $\omega_{1}$ such that
$G(\xi, \eta) \neq U(h(\xi), h(\eta))$.

%Suppose towards a contradiction that $h:\omega_1\to\omega_1$ is an injective function such that
%$G(\xi, \eta) = U(h(\xi), h(\eta))$ for all $\xi, \eta \in \omega_{1}$.

Let $Z\in [\omega_1]^{\aleph_1}$ be such that $h(\xi)\geq \xi$ for all $\xi \in Z$. Choose $k$ and $X\in [Z]^{\aleph_1}$ such that $F(j)\geq F_{h(\xi)}(j)$ for all $\xi\in X$ and $j\geq k$.
%Then choose $Y\in [X]^{\aleph_1}$ such that $\Phi(\{h(\xi),h(\eta)\})>k$ for all $\{\xi,\eta\}\in [Y]^2$.
Since $h(\xi)\geq \xi$ for all $\xi \in X$, it is possible to choose $\xi > \eta$ in $X$ such that $h(\xi) > h(\eta)$ and $k \leq\Phi(\{h(\xi),h(\eta)\}) \leq \Phi(\{\xi,\eta\})$.
% --- indeed, it is possible to get equality in the place of $\leq$.
It follows that
$$G(\xi,\eta) = F(\Phi(\{\xi,\eta\}))\geq F(\Phi(\{h(\xi),h(\eta)\})),$$
and that
$$F(\Phi(\{h(\xi),h(\eta)\}))\geq
F_{h(\xi)}(\Phi(\{h(\xi),h(\eta)\}) > U(h(\xi),h(\eta)),$$ contradicting that $h$ is an embedding.
\qed

%It should be noted that it is easy to get the consistency of a function with Property~R and $\mathfrak{b} > \aleph_1$. We conjecture that such %a function exists assuming only  AC though.

%We conclude this section with an argument, due to Justin Moore, which shows that under the Proper Forcing Axiom there are no functions with property R.\footnote{We thank Alan Dow for discussions clarifying this argument.} We begin by introducing some notation.
%
%Given a function $\Phi \colon [\omega_{1}]^{2} \to \omega$, a finite set $F\subseteq \omega_1$ and $k\in \omega$, we let
%$B_k(\Phi,F)$ denote the set $$\SetOf{\beta\in \omega_1}{(\forall \alpha \in F) \ \Phi(\{\alpha,\beta\})>k}.$$
%
%
%\begin{lemma}\label{lowbound}
%Suppose that $\Phi \colon [\omega_{1}]^{2} \to \omega$ is a function with Property R. Then for each $k\in \omega$ there exists an $\alpha < \omega_{1}$ such that $F \cap \alpha$ is nonempty, for each finite $F \subseteq \omega_{1}$ for which
%$B_k(\Phi,F)$ is countable.
%\end{lemma}
%
%\begin{proof}
%Otherwise, there exist infinitely many pairwise disjoint $F$ for which
%$B_k(F)$ is countable. Then there exist $\beta \in \omega_1$ and an infinite pairwise disjoint family of finite sets $F$ for which $F\subseteq \beta$ and  $\beta\notin B_k(F)$. This yields infinitely many $\xi\in\beta$ such that $\Phi(\{\beta,\xi\})\leq k$ contradicting that $\Phi$ satisfies Property~R.
%\end{proof}
%\qed
%
%Applying Lemma \ref{lowbound}, we can find for any function $\Phi$ with Property R a minimal ordinal $\alpha(\Phi)$ with the property that for any
%$k \in \omega$ and any finite $F \subseteq \omega$ with $B_{k}(\Phi, F)$ countable, $F \cap \alpha(\Phi)$ is nonempty.
%
%Given a function $\Phi \colon [\omega_{1}]^{2} \to \omega$ with Property~R let $\mathbb{P}(\Phi)$ be the partial order consisting pairs $(A,M)$ such that:
%\begin{itemize}
%\item $A$ is a finite subset of pairs from $\omega_1 \setminus \alpha(\Phi)$, and for all distinct $a, b \in A$, $a \subseteq \min(b)$ or $b \subseteq \min(a)$;
%\item $M$ is a finite $\in$-chain of elementary submodels of $H(\aleph_2)$, each having $\Phi$ as a member.
%\item For all $a \in A$, there is $\mathfrak{M}\in M$ such that $$|\mathfrak{M}\cap a| = 1.$$
%\item For all distinct $a,b$ from $A$, $$\Phi(\{\min(a), \min(b)\}) < \Phi(\{\max(a), \max(b)\}).$$
%%\item There is $\mathfrak{M}^*\in M$ such that $\mathfrak{M}^*\cap A = \emptyset$.
%\end{itemize}
%The ordering on $\mathbb{P}(\Phi)$ is : $(A,M) \leq (B, N)$ if $B \subseteq A$, $N \subseteq M$ and, for all $\mathfrak{M} \in N$ and all $a \in A$, if $|\mathfrak{M} \cap a| = 1$, then $a \in B$.
%
%%Note that of $G$ is $\mathbb{P}(\Phi)$ generic and $A_G=\bigcup_{(A,M)\in G}A$ then any disjoint collection of increasing pairs from $A_G$ will witness the %failure of Property~R.
%
%The partial order $\mathbb{P}(\Phi)$ adds an uncountable set of pairs from $\omega_{1}$ witnessing the failure of Property R for $\Phi$.
%
%
%
%
%
%\begin{claim}
%Given any $(A,M)\in \mathbb{P}(\Phi)$ and $\xi\in\omega_1$ there exists a condition $(A',M')\leq (A,M)$ such that $A'\setminus \xi \neq \emptyset$.
%\end{claim}
%
%\begin{proof}
%By adding a model to the top of $M$ if necessary, we may assume that there is $\mathfrak{M}\in M$ such that $A\in \mathfrak{M}$ and
%$\xi < \omega_{1} \cap \mathfrak{M}$.
%Let $\gamma$ be any element of $\omega_{1}$ greater than $\omega_{1} \cap \mathfrak{M}$, and extend $M$ to $M'$ by adding an elementary submodel $\mathfrak{M}'$ on top
%with $\gamma < \omega_{1} \cap \mathfrak{M}'$.
%Let $k>\Phi(\{\alpha,\beta\})$ for all distinct $\alpha, \beta$ from $A \cup \{\gamma\}$. Then $B_k(A \cup \{\gamma\})$ is uncountable, since $(A \cup \{\gamma\}) \cap \alpha(\Phi) = \emptyset$.
%%otherwise by the previous claim it would have to be the case that $\mathfrak{M}^{*} \cap A \neq \emptyset$.
%Let $\delta\in B_k(A)\setminus \mathfrak{M}'$. Then $(A\cup\{\{\gamma, \delta\}\},M')\in \mathbb{P}(\Phi)$.
%\end{proof}
%
%\begin{claim}
%$\mathbb{P}(\Phi)$ is proper.
%\end{claim}
%\begin{proof}
%Let $(A,M)\in \mathbb{P}(\Phi)$ and $(A,M)\in \mathfrak{M}\prec H(\aleph_2)$. It will be shown that $(A,M\cup \{\mathfrak{M}\})$ is $ \mathbb{P}(\Phi)$-generic for $\mathfrak{M}$. To see this, let $D\in \mathfrak{M}$ be a dense subset of $\mathbb{P}(\Phi)$ and suppose that $(B,N) \in D$ is such that $(B,N)\leq (A,M\cup \{\mathfrak{M}\})$. Since there is no $a \in A$ with $|a \cap \mathfrak{M}| = 1$, there is no $b \in B$ with $|b \cap \mathfrak{M}| = 1$, by the definition of the order on $\mathbb{P}(\Phi)$. Let $\{b_1, \ldots, b_j\}$ enumerate $B\setminus \mathfrak{M}$ in such a way that $\min(b_{i})$ increases with $i$, and for
%each $i \in \{1,\ldots,j\}$, let $\beta_{2i+1} = \min(b_{i})$ and $\beta_{2i+1} = \max(b_{i})$.
%
%
%Let $S$ be the set of increasing sequences of ordinals $\langle \gamma_{1},\ldots,\gamma_{2j}\rangle$ such that
%\begin{enumerate}
%\item $\gamma_{1}$ is greater than every member of $\bigcup (B \cap \mathfrak{M})$;
%\item\label{samepattern} letting $\pi \colon \bigcup B \to (\bigcup (B \cap \mathfrak{M})) \cup \{\gamma_{1},\ldots,\gamma_{2j}\}$ be an order-preserving bijection, $\Phi(\{\alpha_{1}, \alpha_{2}\}) = \Phi(\{\pi(\alpha_{1}), \pi(\alpha_{2})\})$ for all $\alpha_{1} < \alpha_{2}$ from $\bigcup B$;
%\item for some $N'$ containing $\mathfrak{M} \cap N$, $$((B \cap \mathfrak{M}) \cup \{\{\gamma_{2i+1},\gamma_{2i+2}\} : i \in j\}, N')$$ is an element of $D$.
%\end{enumerate}
%Let $T_{0}$ be the tree consisting of all initial segments of members of $S$. Then $T_{0} \in \mathfrak{M}$, and since $T_{0} \in H(\aleph_{2})$, $T_{0}$ is an element of every model of $N$ containing $\mathfrak{M} \cap H(\aleph_{2})$. Since $\langle \beta_{1}, \ldots,\beta_{j} \rangle \in S$, and since each $\beta_{2i+1}$ is separated by elementary submodels in $N$ from $\beta_{2i+1}$, $T_{0}$ can be thinned (in $\mathfrak{M}$) to a tree $T_{1}$, still containing $\langle \beta_{1},\ldots,\beta_{j} \rangle$, such that every node of $T_{1}$ on an odd level (where the least level is the 1st level) has uncountably many immediate successors. Finally, still in $\mathfrak{M}$, thin $T_{1}$ to a tree $T$, still of height $j$, such that each node of $T$ on an odd level has infinitely many immediate successors.
%
%We wish to pick a sequence $\langle \gamma_{1},\ldots,\gamma_{2j}\rangle$ from $T$ such that, for some $N'$ containing $N$,
%$(B \cup \{\{\gamma_{2i+1},\gamma_{2i+2}\} : i \in j\}, N')$ is a condition. We pick the $\gamma_{i}$'s recursively, picking any available ordinal
%when $i$ is odd. When $i$ is even, we need to pick $\gamma_{i}$ so that, for each $b \in B \setminus \mathfrak{M}$
%$\Phi(\{ \gamma_{i-1}, \min(b)\}) < \Phi(\{\gamma_{i}, \max(b)\})$. Since $B$ is finite, and we have infinitely many possibilities for $\gamma_{i}$, we can
%meet this condition, using the finite-to-one property of $\Phi$.
%\end{proof}


The argument of Proposition~\ref{nuftom}  shows that if $\mathfrak b > \aleph_1$ and Property R holds then there are no universal functions   from $\omega_1\times\omega_1 \to \omega$, but it does not rule out the existence of a universal functions from $\omega_1\times\omega_1 \to 2$. The following result of Saharon Shelah addresses this  question.

\begin{define}
A graph $(V,E)$ is said to be universal (for \,$\aleph_1$) if given any graph $(U,F)$ such that $|U|=\aleph_1$ there is a function $\Phi:U\to V$ such that $\{x,y\} \in F$ if and only if $\{\Phi(x),\Phi(y)\} \in E$. The function $\Phi$ will be called an embedding in this case.
\end{define}

\begin{theor}[Shelah]\label{shmain}
Assuming the following two hypotheses:
\begin{enumerate}
\item For every $\mathcal F\subseteq [\omega_1^{\omega_1}]^{2^{\aleph_0}}$
there exist two functions $f$ and $g$ in $\mathcal F$ such that $\SetOf{\xi\in\omega_1}{f(\xi)=g(\xi)}$ is stationary.

\item There exist $f_\xi$ for every limit ordinal $\xi\in\omega_1$ such that
\begin{itemize}
\item   $f_\xi:\omega \to \xi$  is increasing and cofinal in $\xi$
\item for every club $C\subseteq \omega_1$ there is a club $X$ such that
for each $\xi \in X$ there is some $n$ such that $f_\xi(k)\in C$ for all $k\geq n$.
\end{itemize}
\end{enumerate}
there is no universal graph on $\omega_1$.
\end{theor}
\begin{proof}
Suppose that $U$ is a universal graph on $\omega_1$. For any $r:\omega\to 2$ define the graph $G_r$ to consist of all edges $\{\xi,\eta\}$ such that there exists $n\in \omega$ such that $r(n) = 1$ and
$f_\eta(n) \leq \xi < f_\eta(n+1)$. Since $U$ is universal there exist embeddings $h_r:\omega_1 \to \omega_1$ of $G_r$ into $U$.

Now let $A\subseteq 2^\omega$ be any set of size $2^{\aleph_0}$ consisting of reals any two of which differ on an infinite set. The first hypothesis yields $r$ and $s$ in $A$ such that that
$E= \SetOf{\xi \in \omega_1}{h_r(\xi) = h_s(\xi)}$ is stationary. Then let $C$ be any club such that if $\alpha$ and $\beta$ are in $C$ and $\alpha \in \beta $ then $E\cap [\alpha, \beta) \neq \emptyset$.

The second hypothesis then yields $\xi \in E$ and $n\in\omega$ such hat $f_\xi(k) \in C$ for all $k\geq n$.
Choose $k\geq n$ such that $r(k) =1\neq s(k)$ and let $\eta \in E$ be such that  $f_\xi(k) \leq \eta  < f_\xi(k+1)$.
Then $\{\eta,\xi\}$ is an edge of $G_r$ but not of $G_s$ contradicting that $h_s(\eta) = h_r(\eta)$ and $h_s(\xi) = h_r(\xi)$.
\end{proof}

\begin{cor}
It is consistent with MA that there is no universal graph on $\omega_1$.
\end{cor}
\begin{proof}
Begin with model of $\lozenge$ and GCH and force with ccc partial order $\Poset$ of cardinality $\aleph_4$ to obtain a model of MA and $2^{\aleph_0} = \aleph_4$. The second hypothesis of Theorem~\ref{shmain} is true because it holds in the ground model satisfying  $\lozenge$ and clubs in the forcing extension contain clubs in the ground model.

To see that the first hypothesis is true, let $\{\dot{f}_\mu\}_{\mu \in \omega_4}$ be $\Poset$-names for  functions from $\omega_1$ to ${\omega_1}$.
For each $\mu \in \omega_4$ choose a function $w_\mu:\omega_1 \to \omega_1$ and conditions
 $p_{\mu,\xi}\in \Poset$ such that $$p_{\mu,\xi}\forces{\Poset}{\dot{f}_\mu(\xi) = w_\mu(\xi)}$$ for all $\xi \in \omega_1$.
 For each pair $\mu\neq \theta$ let $\dot{C}_{\mu,\theta}$ be a $\Poset$-name for a club such that
$1\forces{\Poset}{(\forall \xi\in \dot{C}_{\mu,\theta}) \dot{f}_\mu(\xi) \neq \dot{f}_\theta(\xi)}$.
 Because $\Poset$  is  ccc there is a club $D_{\mu,\theta}$ in the ground model such that
 $1\forces{\Poset}{D_{\mu,\theta}\subseteq \dot{C}_{\mu,\theta}}$.

First let $E\subseteq \omega_4$ be of cardinality $\aleph_4$ such that there is a function $w$ such that
$w_\mu = w$ for all $\mu \in E$.
Since the ground model satisfies $\aleph_4 \rightarrow [\aleph_1]^2_{\aleph_2}$ it follows that there  is an uncountable set $B\subseteq E$  and a club $D$ such that $D_{\mu,\theta} = D$ for $\{\mu,\theta\} \in [B]^2$.
Let $\delta \in D$. Then since $\Poset$ is ccc there are distinct $\mu$ and $\theta$ in $B$ such that there is $p\in \Poset$ such that $p \leq p_{\mu,\delta}$ and 
$p \leq p_{\theta,\delta}$. This contradicts that $\delta \in D$ and 
$p\forces{\Poset}{ w(\xi) = w_\mu(\xi) = \dot{f}_\mu(\xi) \neq \dot{f}_\theta(\xi) = w_\theta(\xi)= w(\xi)}$.

\end{proof}



\begin{remark}
 Justin Moore has shown that under the Proper Forcing Axiom there are no functions with property R --- his argument is included in the appendix to this article.
Justin Moore and Stevo Todorcevic have independently indicated to the authors that the existence of a function with Property R follows from
the assumption that $\mathfrak{b} = \aleph_{1}$.
\end{remark}




\section{Higher dimensional universal functions}\label{higher}

\def\cantor{{2^\om}}
%\begin{define}
%Given a set $X$ and a $k \in \omega$, a $k$-dimensional universal function on $X$ is a function $$F\colon X^k \to X$$
%such that for each function $G\colon X^k \to X$ there exists a function
%$h\colon X \to X$ such that
%$$G(x_1,x_2,\ldots,x_k) = F(h(x_1),h(x_2),\ldots,h(x_k))$$
%for all $(x_1,x_2,\ldots,x_k) \in X^k$.
%\end{define}

\begin{define}
Given $k \in \omega$ and sets $X_{i}$ ($i < k$) and $Z$, a function $F \colon \prod_{i < k}X_{i} \to Z$ is \emph{universal} if for each 
function $G \colon \prod_{i < k}X_{i} \to Z$ there exist functions $h_{i} \colon X_{i} \to X_{i}$ ($i < k$) such that 
$$G(x_{0},\ldots,x_{k-1}) = F(h_{0}(x_{0}),\ldots,h_{k-1}(x_{k-1}))$$ for all $(x_{0},\ldots,x_{k-1}) \in \prod_{i < k}X_{i}$.
\end{define}

As in Remark \ref{differentfunctions}, in the case where the $X_{i}$'s are all the same set $X$, 
the existence of a universal function is not changed by requiring that the functions $h_{i}$ are all the same. 

%one gets an equivalent statement by asking only for the existence of functions
%$h_{1},\ldots,h_{k}$ such that $G(x_1,x_2,\ldots,x_k) = F(h_{1}(x_1),\ldots,h_{k}(x_k))$
%for all $(x_1,x_2,\ldots,x_k) \in X^k$. Universal functions of the form $F \colon \prod_{i < k}X_{i} \to Z$ are
%defined similarly.

Given a set $X$ and a $k \in \omega$, we call a universal function $F \colon X^{k} \to X$ a $k$-\emph{dimensional universal function on} $X$.
The following proposition shows that the existence of a 2-dimensional universal function on an infinite set $X$ is
equivalent to the existence of a $k$-dimensional universal function,
for any $k>1$.  Note however that the Baire complexity of
$F(F(x,y),z)$ can be higher than that of $F$.

\begin{prop}\label{multiu}
Let $X$, $Y$ be sets such that $|X \times Y| = |X|$. If $$F \colon X \times Y \to X$$ is a universal function, then the function
$F'\colon X \times Y \times Y \to X$ defined by setting $F'(x,y,z) = F(F(x,y),z)$ is
a universal function.
\end{prop}

\proof
Fix functions $\pi_{0} \colon X \to X$ and $\pi_{1} \colon X \to Y$ such that the function $\pi \colon X \to X \times Y$ defined by
setting
$\pi(x) = (\pi_{0}(x), \pi_{1}(x))$ is a bijection.
Given $G \colon X \times Y \times Y \to X$, define $G_{0} \colon X \times Y \to X$ by setting $G_0(x,z)=G(\pi_{0}(x),\pi_{1}(x),z)$.  By the universality of $F$
there exist functions
$g \colon X \to X$ and $h \colon Y \to Y$ such that $G_0(u,z)=F(g(u),h(z))$ for all $(u,z) \in X \times Y$.
Again by the universality
of $F$ there are functions $g_0\colon X \to X$ and $g_1\colon Y \to Y$ such that
$$g(\pi^{-1}(x,y))=F(g_0(x),g_1(y))$$ for all $(x,y) \in X \times Y$.
Then for all $(x,y,z) \in X \times Y \times Y$, $$G(x,y,z)=G_{0}(\pi^{-1}(x,y),z) = F(g(\pi^{-1}(x,y)),h(z)),$$
which is equal to $F(F(g_0(x),g_1(y)),h(z))$.
\qed

One may also consider universal functions $F$ where the parameterizing
functions take in more than one variable, for
example, a function $F \colon X^{3} \to Y$ such that
for all $G \colon X^{3} \to Y$ there exist functions $g, h$ and $k$ from $X^{2}$ to $X$ such that
$G(x,y,z) = F(g(x,y),h(y,z),k(x,z))$ for all $x,y,z$ in $X$.
%$$\forall G\;\exists g,h,k\;\forall x,y,z\;\;\;
%G(x,y,z)=F(g(x,y),h(y,z),k(z,x)).$$
A 3-dimensional universal function is universal in this sense, since $g$, $h$ and $k$ can be chosen
to each depend on only one variable. However, we do not know if a universal function in this sense implies
the existence of a 3-dimensional universal function.
%Although the existence of such a universal
%function easily
%follows from the existence of a 3-dimensional universal function (since for a , we
%do not know if it is equivalent.

The reader will easily be able to imagine many variants.
For example,
\begin{itemize}
\item $G(x,y,z)=F(g(x,y),h(y,z))$;

\item $G(x_1,x_2,x_3,x_4)=F(g_1(x_1,x_2),g_2(x_2,x_3),g_3(x_3,x_4),g_4(x_4,x_1))$;
\end{itemize}
\noindent where we have omitted quantifiers for clarity.
These two variants are each equivalent to the existence of
2-dimensional universal function.  To see this in the
first example put $y=0$ and
get

$$G(x,z)=F(g(x,0),h(0,z)).$$

\noindent In the second example put $x_2=x_4=0$ and get

$$G(x_1,x_3)=F(g_1(x_1,0),g_2(0,x_3),g_3(x_3,0),g_4(0,x_1)).$$

\noindent
More generally, suppose that $F$ and the $\vec{x_k}$'s have the property that
for every $G$ there are $g_k$'s such that for all $\vec{x}$
$$G(\vec{x})=F(g_1(\vec{x}_1),\ldots,g_n(\vec{x}_n)).$$
Suppose that there are two variables $x$ and $y$ from $\vec{x}$ which
do not simultaneously belong to any $\vec{x}_k$.  Then we
get a universal 2-dimensional function simply by setting
all of the other variables equal to zero.

For the rest of this section we will often leave implicit the domains of our universal functions, for
notional ease. When we talk of the complexity of universal functions, however, the underlying domain space
is taken to be $\rcantor$.


\begin{define} Given $n \in \omega \setminus \{0,1\}$, an $(n,2)$-dimensional universal
function is an $\comb(n,2)$-ary function $F$ such that for every $n$-ary function $G$ there is a binary function
$h$ with $$G(x_1,x_2,\ldots,x_n)=F(\la h(x_i,x_j):1\leq i<j\leq n\ra)$$
for all $x_1,x_2,\ldots,x_n$.
\end{define}

\begin{prop}\label{pairfunctions}
If there  is a $(3,2)$-dimensional universal function,
%i.e., an $F(x,y,z)$
%such that for every $G$ there is $h$ with
%$$G(x,y,z)=F(h(x,y),h(y,z),h(z,x))\mbox{ for all }x,y,z$$
then for every $n>3$ there is a $(n,2)$-dimensional universal
function $F$.
%i.e., $F$ is $\comb(n,2)$-ary.
Conversely, if there is a $(n+1,2)$-dimensional universal
function for some $n\geq 3$, then there is an $(n,2)$-dimensional universal
function.
\end{prop}


\proof
Suppose that $F$ is a $(3,2)$-dimensional
universal function and $F'$ is an $(n,2)$-dimensional universal function, for
some $n \geq 3$.
Given an $(n+1)$-ary function $G(x_{1},\ldots, x_{n+1})$, for each
fixed $w$ we get a function $h_w(x_{1},\ldots,x_{n})$ with
$$G(x_{1},\ldots,x_{n},w)=F'(\la h_{w}(x_i,x_j):1\leq i<j\leq n\ra)$$
for all $x_{1},\ldots,x_{n}$.
Now, considering $h(y_{1},y_{2},y_{3})=h_{y_{3}}(y_{1},y_{2})$ we get a function
$k(s,t)$ with $h(y_{1},y_{2},y_{3})=F(\la k(y_{i},y_{j}):1\leq i<j\leq 3\ra)$ for all $y_{1},y_{2},y_{3}$.
Then, for all $x_{1},\ldots,x_{n+1}$, $G(x_{1},\ldots,x_{n+1})= $
$$F'(\la F(k(x_{i},x_{j}), k(x_{i}, x_{n+1}),
k(x_{j}, x_{n+1})):1\leq i<j\leq n\ra).$$
From this one gets an $(n+1, s)$-dimensional universal function,
with $k$ playing the role of
$h$ in the definition.


%Consider the case for $n=4$.

%Suppose that $F$ is a $(3,2)$-dimensional
%universal function.  Given a 4-ary function $G(x,y,z,w)$ for each
%fixed $w$ we get a function $h_w(u,v)$ with
%$$G(x,y,z,w)=F(h_w(x,y),h_w(y,z),h_w(z,x))\mbox{ for all } x,y,z.$$
%But now considering $h(u,v,w)=h_w(u,v)$ we get a function
%$k(s,t)$ with $h(u,v,w)=F(k(u,v),k(v,w),k(w,u))$.
%Note that

%\noindent $\;\;\;\;\;\;G(x,y,z,w)=$

%$\;\;\;\;\;\;F(F(k(x,y),k(y,w),k(w,x)),$

%$\;\;\;\;\;\;\;\;\;\;\;\;F(k(y,z),k(z,w),k(w,y)),$

%$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;F(k(z,x),k(x,w),k(w,z))).$

%\noindent Note that
%$k(s,t)$ and $k(t,s)$ can
%be combined by pairing and unpairing into a single function $k_1(s,t)$.
%From this one can define a $(4,2)$-dimensional
%universal function.

For the converse, suppose that $F$ is an $(n+1,2)$-dimensional
universal function. Consider $F$ as a function of variables $p_{i,j}$ $(1 \leq i < j \leq n+1)$,
and, fixing a tripling function $\langle \cdot,\cdot,\cdot \rangle$, let $u_{1}$, $u_{2}$ and $u_{3}$ be
functions so that $u_{i}(\langle x_{1},x_{2},x_{3}\rangle) = x_{i}$ for all $x_{1}, x_{2}, x_{3}$ and $i \in \{1,2,3\}$.
Let $K$ be the function which takes in a sequence $$\langle q_{i,j} : 1 \leq i < j \leq n\rangle$$
and returns the sequence $$\langle p_{i,j} : 1 \leq i < j \leq n + 1 \rangle$$ for which
$p_{i,j}$ is
\begin{itemize}
\item $u_{1}(q_{i,j})$ if $j \leq n$;
\item $u_{2}(q_{i,i+1})$ if $i < n$ and $j = n+1$;
\item $u_{3}(q_{n-1,n})$ if $i = n$ and $j = n+1$.
\end{itemize}
Define $F'$ by setting $$F'(\langle q_{i,j} : 1 \leq i < j \leq n\rangle) =
F(K(\langle q_{i,j} : 1 \leq i < j \leq n\rangle)).$$
Given an $n$-ary function $G$, there exists a binary
function $h$ with
$$G(x_{1},\ldots,x_{n})=F(\la h(x_i,x_j):1\leq i<j\leq n + 1\ra)$$
for all $x_{1},\ldots,x_{n+1}$.
Fix a domain element $w$, and define a function $h'$ by setting
$h'(x,y) = \langle h(x,y), h(x,w), h(y,w) \rangle$.
Then $$G(x_{1},\ldots,x_{n}) =
F'(\la h'(x_i,x_j):1\leq i<j\leq n\ra)$$
for all $x_{1},\ldots,x_{n}$.
%But note that, for example, $h(x,y)$ and $h(x,0)$ can
%be combined into a single function of $h_1(x,y)$.  Hence
%we can get a $(3,2)$-dimensional
%universal function.
\qed



Next we state a generalization of these ideas.

\begin{define}\label{def29}
Let $X$ be a set, and $n$ an element of $\omega$.
Suppose that $\Sigma\su \pow(\{0,1,2,\ldots,n-1\})=\pow(n)$ (the power set of $n$).
We let
$U(X,n,\Sigma)$ be the assertion that there exists a function
$F:X^{\Sigma}\to X$ such that
for every $G:X^n\to X$ there are $h_Q:X^{Q}\to X$
for $Q\in\Sigma$
such that
$$G(x_0,x_1,\ldots,x_{n-1})=F\left(\la h_Q(\la x_j:j\in Q \ra):Q\in\Sigma\ra\right)$$
for all $x_{0},\ldots,x_{n-1}\in X$.
\end{define}

Propositions \ref{multiu} and \ref{pairfunctions} can be generalized as follows. The proofs of the first two parts of Proposition \ref{propmn} are similar to the
corresponding proofs from Proposition \ref{pairfunctions}.




\begin{prop}\label{propmn}
For any infinite set $X$ and any positive integer $n$,
\begin{enumerate}
\item $U(X,n+1,[n+1]^n)$ implies $\forall m>n\;\; U(X,m,[m]^n)$;
\item $\exists m>n\;\; U(X,m,[m]^n)$ implies $U(X,n+1,[n+1]^n)$;
\item $U(X,n+1,[n+1]^n)$ implies $U(X,n+2,[n+2]^{n+1})$.
\end{enumerate}
\end{prop}


\begin{proof}
  For the first part, we follow the proof of the first part of Proposition \ref{pairfunctions}, inducting on $m$. Fix $m > n$, and suppose that $F_{0}$ witnesses
  the statement
  $U(X, n+1, [n+1]^{n})$ and $F_{1}$ witnesses $U(X, m, [m]^{n})$. Given $G \colon X^{m+1} \to X$, we can find for each $w \in X$ functions
  $h^{w}_{Q}$ ($Q \in [m]^{n}$) such that, for all $x_{0},\ldots,x_{m-1}\in X$, $$G(x_{0},\ldots,x_{m-1},w) = F_{1}\left ( \la h^{w}_Q(\la x_j:j\in Q \ra):Q\in
  [m]^{n}\ra\right).$$
Furthermore, there are functions $k_{R}$ $(R \in [n+1]^{n})$ such that (abusing notation slightly on the left side of the equality) $$h^{x_{n}}_{Q}(\langle x_i :
i < n \rangle) = F_{0}(\langle k_{R}(\langle x_i : i \in R \rangle) : R \in [n+1]^{n} \rangle)$$ for all $x_{0},\ldots,x_{n} \in X$. The functions $k_{R}$ witness
in this instance then that the function $F_{1}(\langle F_{0}(\langle y_{R} : R \in [Q \cup \{m\}]^{n} \rangle )  : Q \in [m]^{n} \rangle)$ witnesses
$U(X,m+1,[m+1]^{n})$.

%\pagebreak

For the second part, we follow the proof of the second part of Proposition \ref{pairfunctions}. Suppose that $F$ witnesses $U(X, m, [m]^{n})$.
Fix a bijection $\pi \colon X^{([m]^{n})} \to X$, and let $p_{R}$ ($R \in [m]^{n}$) be the functions from $X$ to $X$ such that
$\pi^{-1}(x) = \langle p_{R}(x) : R \in [m]^{n}\rangle$.
 Let $H \colon [m]^{n} \to [n+1]^{n}$ be such that $R \cap (n+1) \subseteq H(R)$ for all $R \in [m]^{n}$.
%For each $R \in [m]^{n}$, let $\sigma(R)$ be the subset of $n$ such that, letting $H(R) = \{ i_{0},\ldots,i_{n-1} \}$ (listed in increasing order), $R \cap (n+1)
%= \{ i_{j} : j \in \sigma(R)\}$.
Let $K$ be the function which takes in a sequence $$\langle y_{Q} : Q \in [n+1]^{n}\rangle$$ from $X$
and returns the sequence $$\langle p_{R}(y_{H(R)}) : R \in [m]^{n} \rangle.$$
%for which each $z_{R}$ is $p_{R}(y_{H(R)})$.
%\begin{itemize}
%\item $Q$ if $R \subseteq n+1$;
%\item $n$ if $R \not\subseteq n+1$.
%\item $u_{2}(q_{i,i+1})$ if $i < n$ and $j = n+1$,
%\item $u_{3}(q_{n-1,n})$ if $i = n$ and $j = n+1$.
%\end{itemize}
Define $F' \colon X^{([n+1]^{n})} \to X$ by setting $$F'(\langle y_{Q} : Q \in [n+1]^{n}\rangle) =
F(K(\langle y_{Q} : Q \in [n+1]^{n}\rangle)).$$
To see that this works, fix $G \colon X^{n+1} \to X$. Since $F$ witnesses $U(X, m, [m]^{n})$, there exist functions $h_{R} \colon X^{R} \to X$ ($R \in [m]^{n}$)
such that
$$G(x_{0},\ldots,x_{n})=F(\la h_{R}(\langle x_{i} : i \in R \rangle) : R \in [m]^{n}\ra)$$
for all $x_{0},\ldots,x_{m-1} \in X$.
Fix $w \in X$. For each $Q \in [n+1]^{n}$,
%let $e_{Q} : Q \to n$ be an order-preserving bijection, and
let $k_{Q} \colon X^{Q} \to X$ be defined by setting $k_{Q}(\langle x_{i} : i \in Q\rangle)$ to be
$$\pi(\langle h_{R}(\langle t_{i} : i \in R \rangle) : R \in [m]^{n} \rangle),$$ where each $t_{i}$ is $x_{i}$ if $i \in Q$, and $w$ otherwise.
%Then for all $x_{0},\ldots,x_{m-1}$ in $X$, $F'(\langle k_{Q}(\langle x_{j} : j \in Q\rangle) : Q \in [n+1]^{n}\rangle)$ is equal to
To check that the functions $k_{Q}$ witness that $F'$ is as desired, it suffices to see that for all $x_{0},\ldots,x_{m-1}$ in $X$ for which $x_{i} = w$ for all
$i \in \{n+1,\ldots,m-1\}$, and all $R \in [m]^{n}$,
$h_{R}(\langle x_{i} : i \in R \rangle)$ is equal to $p_{R}(k_{H(R)}(\langle x_{i} : i \in H(R)\rangle))$. Now,  $p_{R}(k_{H(R)}(\langle x_{i} : i \in
H(R)\rangle))$ is
$h_{R}(\langle t_{i} : i \in R \rangle)$, where each $t_{i}$ is $x_{i}$ if $i \in H(R)$ and $w$ otherwise. Since $R \cap (n + 1) \subseteq H(R)$,
$\langle t_{i} : i \in R\rangle = \langle x_{i} : i \in R \rangle$, as desired.



%For each $Q \in [n+1]^{n}$ and $R \in [m]^{n}$, For each $Q \in [n+1]^{n}$, let , where $z(Q,R,i)$ is $x_{i}$ if $i \in R \cap (n+1)$ and $w$ otherwise.

% and define a function $h'$ by setting
%$h'(x,y) = \langle h(x,y), h(x,w), h(y,w) \rangle$.
%Then $$G(x_{0},\ldots,x_{n}) =
%F'(\la h'(x_i,x_j):1\leq i<j\leq n\ra)$$
%for all $x_{0},\ldots,x_{n} \in X$.

For the third part, we follow (loosely) the proof of Proposition \ref{multiu}. Suppose that $F$ witnesses $U(X, n+1, [n+1]^{n})$.
Let $F' \colon X^{([n+2]^{n+1})} \to X$ be such that $$F'(\langle z_{Q} : Q \in [n+2]^{n+1}\rangle) = F(\langle y_{R} : R \in [n+1]^{n}\rangle),$$ where
each $y_{R} = z_{R \cup \{n+1\}}$.
Fix functions $\pi_{0} \colon X \to X$ and $\pi_{1} \colon X \to X$ such that the function $\pi \colon X \to X \times X$ defined by
setting
$$\pi(x) = (\pi_{0}(x), \pi_{1}(x))$$ is a bijection.
Given $G \colon X^{n+2} \to X$, define $G_{0} \colon X^{n+1} \to X$ by setting $$G_0(x_{0},\ldots,x_{n})=G(x_{0},\ldots,x_{n-1},\pi_{0}(x_{n}), \pi_{1}(x_{n})).$$
By the universality of $F$ there exist functions $h_{R}$ ($R \in [n+1]^{n}$) such that
$$G_{0}(x_{0},\ldots,x_{n}) = F(\langle h_{R}(\langle x_{i} : i \in R\rangle) : R \in [n+1]^{n} \rangle)$$ for all $x_{0},\ldots,x_{n}$ from $X$.
Let $k_{n+1}$ be any function from $X^{n+1}$ to $X$, and let $k_{n \cup \{n+1\}} \colon X^{n+1} \to X$ be such that $$k_{n \cup \{n+1\}}(x_{0},\ldots,x_{n}) =
h_{n}(x_{0},\ldots,x_{n-1})$$ for all $x_{0},\ldots,x_{n}$ from $X$. For each $Q \in [n+2]^{n+1}$ containing $\{ n,n+1\}$, let $k_{Q} \colon X^{n+1} \to X$ be
the
function defined by setting $$k_{Q}(x_{0},\ldots,x_{n}) = h_{Q \cap (n+1)}(x_{0},\ldots,x_{n-2},\pi^{-1}(x_{n-1},x_{n})).$$
Then for all $x_{0},\ldots,x_{n+1}$, $$G(x_{0},\ldots,x_{n+1}) = G_{0}(x_{0}, \ldots, x_{n-1},\pi^{-1}(x_{n}, x_{n+1})),$$ which is equal to
$F(\langle h_{R}(\langle y_{i} : y \in R \rangle) : R \in [n+1]^{n}\rangle)$, where $y_{i} = x_{i}$ for all $i < n$, and $y_{n} = \pi^{-1}(x_{n}, x_{n+1})$.
Furthermore, $$F(\langle h_{R}(\langle y_{i} : i \in R \rangle) : R \in [n+1]^{n}\rangle)$$ is equal to $$F'(\langle k_{Q}(\langle x_{i} : i \in Q\rangle) : Q \in
[n+2]^{n+1}\rangle),$$
as $h_{R}(\langle y_{i} : i \in R \rangle) = k_{R \cup \{n+1\}}(\langle x_{i} : i \in R \cup \{n+1\} \rangle)$ for each $R \in [n+1]^{n}$.
\end{proof}
\qed

%Again by the universality
%of $F$ there are functions $g_0\colon X \to X$ and $g_1\colon Y \to Y$ such that
%$$g(\pi^{-1}(x,y))=F(g_0(x),g_1(y))$$ for all $(x,y) \in X \times Y$.
%Then for all $x_{0},\ldots,x_{n+1}$ from $X$, $$G(x_{0},\ldots,x_{n+1})=G_{0}(x_{0},\ldots,x_{n-1},\pi^{-1}(x_{n},x_{n+1})) =
%F(g(\pi^{-1}(x,y)),h(z)),$$
%which is equal to $F(F(g_0(x),g_1(y)),h(z))$.


In the following definition, $n$ is the arity of
the inside parameter functions. The arity of the universal function
is less important.

\def\minf{\,\cdot\,}

\begin{define}\label{defU}
For any infinite set $X$, and any $n \in \omega$, we define $U(X,n)$ to be any of the equivalent
propositions $U(X,m,[m]^n)$ for $m$ in $\omega \setminus (n+1)$.
\end{define}

Proposition \ref{sig} and Theorem \ref{mm} show that the $U(\ka, n)$'s are the only generalized
multi-dimensional universal functions properties.
Clause (3) of Proposition \ref{propmn} says that $U(\ka, n)$ implies $U(\ka, {n+1})$
and we will show in Corollary \ref{cor35} that none of these
implications can be reversed.

\begin{prop}\label{sig}
Let $X$ be an infinite $X$, $n\in \omega \setminus 2$, and $\Sigma,\Sigma_0,\Sigma_1$
subsets of $\pow(n)$.
\begin{enumerate}
\item If $\Sigma_0\su \Sigma_1$, then
$U(X,n,\Sigma_0)$ implies $U(X,n,\Sigma_1)$.
\item If $Q_0\su Q_1\in\Sigma$, then
$U(X,n,\Sigma)$ is equivalent to $$U(X,n,\Sigma\cup\{Q_0\}).$$
\item Suppose that $\Sigma$ is closed under taking subsets,
every element of $n$ is in some element of $\Sigma$, and
$n=\{0,1,2,\ldots,n-1\}\notin\Sigma$.  Let $m+1$ be the size
of the smallest subset of $n$ not in $\Sigma$.
Then $U(X,n,\Sigma)$ is equivalent to $U(X,m)$.
\end{enumerate}
\end{prop}
\proof
$\;\;\;\;$
(1) This follows from the fact that the $F$ which works for $\Sigma_0$ also works
for $\Sigma_1$ by ignoring the values of $h_Q$ for $Q\in \Sigma_1\sm\Sigma_0$.

(2) One direction follows from part (1). For the other suppose that $F \colon X^{\Sigma \cup \{ Q_{0}\}} \to X$ witnesses
$U(X, n, \Sigma \cup \{ Q_{0}\})$. Let $\pi \colon X \to X \times X$ be a bijection, and let $\pi_{0} \colon X \to X$ and $\pi_{1} \colon X \to X$ be
such that $\pi(x) = (\pi_{0}(x), \pi_{1}(x))$ for all $x \in X$. Define $F' \colon X^{\Sigma} \to X$ by setting $F'(\langle x_{Q} : Q \in \Sigma\rangle)$ to
 be $F(\langle y_{R} : R \in \Sigma \cup \{Q_{0}\}\rangle)$, where $y_{Q_{0}} = \pi_{0}(x_{Q_{1}})$, $y_{Q_{1}} = \pi_{1}(x_{Q_{1}})$ and $y_{R} = x_{R}$ if $R
 \not\in \{Q_{0}, Q_{1}\}$. Fix $G \colon X^{n} \to X$, and let $h_{R}$ ($R \in \Sigma \cup \{Q_{0}\})$ be as in the definition of $U(X, n, \Sigma \cup \{
 Q_{0}\})$. For each $Q \in \Sigma \setminus \{Q_{1}\}$, let $h'_{Q} = h_{Q}$. Let $h'_{Q_{1}}$ be such that
 $$h'_{Q_1}(\langle x_j:j\in Q_1\rangle)=
\pi(h_{Q_0}(\la x_j:j\in Q_0 \ra),h_{Q_1}(\la x_j:j\in Q_1 \ra))$$ for all $x_{0},\ldots,x_{n-1}$ from $X$.
Then $h'_{Q}$ ($Q \in \Sigma$) are as desired.

%This follows from the fact that given $h_{Q_0},h_{Q_1}$, we can define
%a new $\hat{h}_{Q_1}$ by outputting the pairing


(3) First suppose that $U(X,n,\Sigma)$ holds.
Choose $R\su\{0,1,\dots n-1\}$ not in $\Sigma$ with $|R|=m+1$.
By the choice of $m$ all subsets of $R$ of size $m$ are in $\Sigma$.
By restricting to the case where $x_i=0$ for $i\notin R$, we see that $U(X, m, [m]^{m+1})$ holds.
%$U(\ka, m)$ holds.

Now assume that $U(\ka, m)$ holds.
%By part (1) of Proposition \ref{propmn} we have that
Then $U(\ka,n,[n]^m)$ holds.
%where $\Sigma_0=[n]^m$.
Since $[n]^m\su \Sigma$, part (1) implies that  $U(\ka,n,\Sigma)$
holds.
\qed

Proposition \ref{sig} gives the following. The first two statements in the theorem are trivial.

\begin{theorem}\label{mm}
For any $n \in \omega$, any infinite cardinal $\kappa$ and any $\Sigma\su \pow(n)$, if
$$\bigcup\Sigma\neq n=\{0,1,2,\ldots,n-1\}$$
then  $U(\ka,n,\Sigma)$ fails.  If
$n\in\Sigma$, then $U(\ka,n,\Sigma)$ holds.
If neither of these is true, then by the Proposition \ref{sig}
there exists $m$ with
$U(\ka,n,\Sigma)$ equivalent to $U(\ka, m)$.
\end{theorem}

The following fact will be used in the proof of Proposition \ref{prop33}. Recall that a linear preorder on a set $X$ is a binary relation $\preceq$ on
$X$ which is reflexive, transitive and total (i.e., for all $x,y \in X$, at least one of $x \preceq y$ and $y \preceq x$ holds). Every linear preorder is a
superset of a linear order.

\begin{prop}\label{33lem} Let $\kappa$ be an infinite cardinal and let $m < n$ be integers, with $m \geq 2$.
Suppose that $F_{0} \colon \kappa^{([n]^{m})} \to \kappa$ has the property that for each $G \colon \kappa^{n} \to \kappa$ there exist $h_{Q} \colon \kappa^{Q}
\to
\kappa$ ($Q \in [n]^{m}$) such that $$G(y_{0},\ldots,y_{n-1}) = F(\langle h_{Q}(\langle x_{i} : i \in Q\rangle) : Q \in [n]^{m}\rangle)$$
for all nondecreasing $\langle y_{0},\ldots,y_{n-1}\rangle \in \kappa^{n}$.
Then $U(\kappa, n, [n]^{m})$ holds.
%is equal to its restriction where $\vec{x}$ is assumed to be in nondecreasing order.
\end{prop}

\proof
Let $\kappa$, $m$ and $n$ be as given. As in Remark \ref{differentfunctions}, we may assume that $F_{0}$ has the property that for each $G \colon \kappa^{n} \to
\kappa$ there exists a single function $h \colon \kappa^{Q} \to
\kappa$ such that $$G(y_{0},\ldots,y_{n-1}) = F(\langle h(\langle x_{i} : i \in Q\rangle) : Q \in [n]^{m}\rangle)$$
for all nondecreasing $\langle y_{0},\ldots,y_{n-1}\rangle \in \kappa^{n}$.


Let $P$ be the set of all permutations of $n$. Let $\pi \colon \kappa \to \kappa^{P}$ be a bijection, and let $F = \pi \circ F_{0}$.
%has the same cardinality as $\kappa$, there exists a function $F \colon \kappa^{([n]^{m})} \to \kappa^{P}$ such that
Then for each $G \colon \kappa^{n} \to \kappa^{P}$ there exist an $h \colon \kappa^{Q} \to
\kappa$ such that $$G(y_{0},\ldots,y_{n-1}) = F(\langle h(\langle x_{i} : i \in Q\rangle) : Q \in [n]^{m}\rangle)$$
for all nondecreasing $\langle y_{0},\ldots,y_{n-1}\rangle \in \kappa^{n}$.
%the existence of such an $F$ follows from our assumption.



Let $L$ be the set of all linear preorders on members of $[n]^{m}$. Let $r \colon L \times \kappa \to \kappa$ be a
bijection. Let $e$ be a function taking linear preorders on $n$ to linear orders contained in them.
% and fix $s_{0} \colon \kappa \to L$, $s_{1} \colon \kappa \to \kappa$ such that $p(s_{0}(\alpha), s_{1}(\alpha)) =
%\alpha$ for all $\alpha < \kappa$.
%Let $r$ be a function which takes in $\langle l_{Q} : Q \in \Sigma \rangle$, where each $l_{Q}$ is
%a linear order on $Q$, and returns the unique linear order on $n$ whose restriction to each $Q \in \Sigma$ is $l_{Q}$, if such a linear order %exists.
%Let $P = \langle \pi_{i} : i < n!\rangle$ list all permutations of $n$. Let $q \colon \kappa \to \kappa^{P}$
%be a bijection.

Let $F^{*} \colon \kappa^{([n]^{m})} \to \kappa$ be the function which takes in a sequence $$\langle r(l_{Q}, \alpha_{Q}) :
Q \in [n]^{m}\rangle,$$ where each $l_{Q}$ is a linear preorder on $Q$ and each $\alpha_{Q}$ is in $\kappa$, and returns a value in $\kappa$ defined as follows.
If $\bigcup\{ l_{Q} : Q \in [n]^{m}\}$ is not a linear preorder, then let $F^{*}$ take any value in $\kappa$. Otherwise, let $$l = e(\bigcup\{ l_{Q} : Q \in
[n]^{m}\}),$$ and let $s \colon n \to n$ be the function that
takes each $i \in n$ to its $l$-rank. For each $Q \in [n]^{m}$, let $\beta_{Q}$
be $\alpha_{s^{-1}[Q]}$.
Finally, let $$F^{*}(\langle r(l_{Q}, \alpha_{Q}) :
Q \in [n]^{m} \rangle) = F(\langle \beta_{Q} : Q \in [n]^{m}\rangle)(s^{-1}).$$


Let us see that this $F^{*}$ works. Fix a function $G^{*} \colon \kappa^{n} \to \kappa$.
%For each $p \in P$, let $p^{*}\colon \kappa^{n} \to \kappa^{n}$ be the
%function defined by letting $$p^{*}(y_{0},\ldots,y_{n-1}) = (y_{p(0)},\ldots,y_{p(n-1)}).$$
Let $G \colon \kappa^{n} \to \kappa^{P}$ be the function defined by letting
$$G(y_{0},\ldots,y_{n-1}) = \langle G^{*}(y_{p(0)},\ldots,y_{p(n-1)}) : p \in P\rangle.$$ Let $h \colon \kappa^{Q} \to
\kappa$ be such that $$G(y_{0},\ldots,y_{n-1}) = F(\langle h(\langle y_{i} : i \in Q\rangle) : Q \in [n]^{m}\rangle)$$
for all nondecreasing $\langle y_{0},\ldots,y_{n-1}\rangle \in \kappa^{n}$. For each $Q \in [n]^{m}$, define $h^{*}_{Q} \colon \kappa^{Q} \to \kappa$ by setting
$h^{*}_{Q}(\langle x_{i} :
 i\in Q\rangle)$ to be $$r(l_{Q}(\langle x_{i} : i \in Q\rangle) ,h(\langle z_{i} : i \in Q\rangle)),$$ where $l_{Q}$ is the linear order on $Q$ induced by
 $\langle x_{i} : i \in Q\rangle$ and $\langle z_{i} : i \in Q\rangle$ lists $\{ x_{i} : i \in Q \}$ in nondecreasing order.

Now each $\langle x_{0},\ldots,x_{n-1} \rangle \in \kappa^{n}$ is $\langle y_{p(0)},\ldots,y_{p(n-1)}\rangle$ for some $p \in P$ and a unique nondecreasing
$\langle y_{0},\ldots,y_{n-1}\rangle$ in $\kappa^{n}$. Furthermore, $p$ can be taken to be $s^{-1}$, where $l = e(\bigcup\{l_{Q} : Q \in [n]^{m}\})$, each $l_{Q}$
is the linear order on $Q$ given by $\{x_{i} : i \in Q\}$ and $s$ is the function taking each element of $n$ to its $l$-rank. Then $G^{*}(x_{0},\ldots,x_{n-1}) =
G(y_{0},\ldots,y_{n-1})(p)$, which is $$F(\langle h(\langle y_{i} : i \in Q\rangle) : Q \in [n]^{m}\rangle)(p).$$
Finally, each $\langle y_{i} : i \in Q\rangle= \langle x_{i} : i \in s^{-1}[Q]\rangle$, so that
$$F(\langle h(\langle y_{i} : i \in Q\rangle) : Q \in [n]^{m}\rangle)(p)$$ equals $$F^{*}(\langle (r(l_{Q}(\langle x_{i} : i \in Q\rangle) ,h(z_{i} : i \in Q)): Q
\in [n]^{m}\rangle)$$
(where $\langle z_{i} : i \in Q \rangle$ is $\langle x_{i} : i \in Q \rangle$ listed in increasing order), which is equal to $$F^{*}(\langle h^{*}_{Q}(\langle
x_{i} : i \in Q\rangle) : Q \in [n]^{m}\rangle).$$
\qed

Since $|\om^{<\om}|=\om$, $U(\om, 1)$ follows from
Theorem \ref{existuniv}. The following proposition allows us to propagate this fact, showing for instance that $U(\om_n, {n+1})$ holds for every $n \in \omega$.

%\begin{prop} \label{prop33}
%The following are true in ZFC.
%\begin{enumerate}
%\item $U(\om, 1)$
%\item $U(\om_1, 2)$
%\item For any infinite cardinal $\kappa$, $U(\ka, 1)$ implies $U(\ka^+, 2)$.
%\item For any infinite cardinal $\kappa$, $U(\ka, n)$ implies $U(\ka^+, {n+1})$
%\item $U(\om_n, {n+1})$, every $n\geq 0$.
%\end{enumerate}
%\end{prop}

\begin{prop}\label{prop33}
For any infinite cardinal $\kappa$, and any $n \in \omega$, $U(\ka, n)$ implies $U(\ka^+, {n+1})$
\end{prop}
\proof

%We prove (4), from which the other parts follow.

Let $\Sigma = \{ a \cup \{n+1\} : a \in [n+1]^{n}\}$. Applying Proposition \ref{33lem}, and the idea behind the first part of Proposition \ref{sig}, it suffices
to produce a function $$F \colon (\kappa^{+})^{\Sigma} \to \kappa^{+}$$ such that for every
$G \colon (\kappa^{+})^{n+2} \to \kappa^{+}$ there exist $$H_{Q} \colon (\kappa^{+})^{n+1} \to \kappa^{+}\text{ }
(Q \in \Sigma)$$ for which $G(\xi_{0},\ldots,\xi_{n+1}) = F(\langle H_{Q}(\langle \xi_{i} : i \in Q\rangle) : Q \in \Sigma\rangle)$ for
all nondecreasing sequences $\langle \xi_{0},\ldots,\xi_{n+1}\rangle$ from $\kappa^{+}$.

Suppose that $f:\kappa^{([n+1]^{n})}\to\kappa$ witnesses
$U(\kappa,n+1,[n+1]^{n})$.  For each $\alpha \in [\kappa, \kappa^{+})$, let $B_{\alpha} \colon \alpha \to \kappa$ be a bijection. Let $r\colon \kappa \times
\kappa^{+} \to \kappa^{+}$ be a bijection.

Let $F$ be a function which takes in a sequence $\langle r(\alpha_{Q}, \beta_{Q}) : Q \in \Sigma \rangle$ and returns a value in $\kappa^{+}$
as follows. If $\beta_{Q}$ is not the same value for all $Q$, then $F$ returns any value. Otherwise, letting $\beta$ be this constant value, and letting
$\gamma_{R}$ be $\alpha_{R \cup \{n+1\}}$ for each $R \in [n+1]^{n}$, $F$ returns the value $$B_{\beta}^{-1}(f(\langle \gamma_{R} : R \in
[n+1]^{n}\rangle)).$$

Let us check that this definition works. Suppose we are given $$G \colon (\kappa^{+})^{n+2} \to \kappa^{+}.$$ For each $\delta < \kappa^{+}$, let $k(\delta)$ be
$\sup(G[(\delta+1)^{n+2}]) + 1$. For each $\delta < \kappa^{+}$ there exist $h_{R}^{\delta} \colon \kappa^{n} \to \kappa$ ($R \in [n+1]^{n}$) such that
$$f(\langle h^{\delta}_{R}(\langle  B_{\delta + 1}(\alpha_{i}) : i \in R\rangle) :R \in [n+1]^{n}\rangle) =
B_{k(\delta)}(G(\alpha_{0},\ldots,\alpha_{n},\delta))$$ for all $\alpha_{0},\ldots,\alpha_{n} \leq \delta$.

For each $Q \in \Sigma$, let $H_{Q}\colon (\kappa^{+})^{n+1} \to \kappa^{+}$ be defined as follows. Given $\langle \zeta_{i} : i \in Q \rangle$ from $\kappa^{+}$,
if $\zeta_{n+1} < \zeta_{i}$ for some $i \in Q$, then let $H_{Q}(\langle \zeta_{i} : i \in Q \rangle)$ take any value in $\kappa^{+}$. Otherwise, let
$H_{Q}(\langle \zeta_{i} : i \in Q \rangle)$ take the value $r(\alpha_{Q}, k(\zeta_{n+1}))$, where $$\alpha_{Q} = h^{\zeta_{n+1}}_{Q \cap (n+1)}(\langle
B_{\zeta_{n+1} + 1}(\zeta_{i}) : i \in Q \cap (n+1) \rangle).$$

Now let $\xi_{0},\ldots,\xi_{n+1}$ be a nondecreasing sequence from $\kappa^{+}$.
Then
$G(\xi_{0},\ldots,\xi_{n+1})$ is equal to $$B_{k(\xi_{n+1})}^{-1}(f(\langle  h^{\xi_{n+1}}_{R}(\langle  B_{\xi_{n+1} + 1}(\xi_{i}) : i \in R\rangle) :R \in
[n+1]^{n}\rangle)).$$ Then we are done, since, as written above, each $\gamma_{R}$ is $\alpha_{R \cup \{n+1\}}$, which is $h^{\xi_{n+1}}_{R}(\langle B_{\xi_{n+1}
+ 1}(\xi_{i}) : i \in R\rangle)$.
\qed

%Applying Proposition \ref{33lem}, we need to produce a function $F \colon (\kappa^{+})^{([n+2]^{n+1})} \to \kappa^{+}$ such that for every
%$G \colon (\kappa^{+})^{n+2} \to \kappa^{+}$ there exist $h_{Q} \colon (\kappa^{+})^{n+1} \to \kappa^{+}$
%($Q \in [n+2]^{n+1}$) for which $G(\alpha_{0},\ldots,\alpha_{n+1}) = F(h_{Q}(\{\alpha_{i} : i \in Q\}) : Q \in [n+2]^{n+1})$ for
%all nondecreasing $\alpha_{0},\ldots,\alpha_{n+1} \in \kappa^{+}$.

%First note that it suffices to produce such an $F$ which works for all $G$ when the inputs $\alpha_{0},\ldots,\alpha_{n+1}$ are taken to
%be in nondecreasing order. For given such an $F$, we can let $F \colon (\kappa^{+})^{([n+2]^{n+1})} \to \kappa^{+}$ be a function which takes %in a pair from
%$(n+1)! \times \kappa^{+}$ in each coordinate

%and $G \colon (\kappa^{+})^{n+2} \to \kappa^{+}$ is given,
%let $G^{*} \colon (\kappa^{+})^{n+2} \to \kappa^{+}$ be the function which (under a fixed bijection between $\kappa^{+}$ and %$(\kappa^{+})^{(n+2)!}$ returns the
%values taken by $G$ on all permutations of the input sequence $\alpha_{0},\ldots,\alpha_{n+1}$.
%Then let ...
%Finally

%Suppose that $f:\kappa^{([n+1]^{n})}\to\kappa$ witnesses
%$U(\kappa,n+1,[n+1]^{n})$.  For each positive ordinal $\de < \kappa^{+}$ let
%$\{ \xi^{\delta}_{\alpha} : \alpha < \kappa\}$ enumerate $\delta$, possibly with repetition. Define
%$$F_0(\de,\alpha, \beta)=\de_{f(\alpha, \beta)}.$$

%Define $F$ as follows:

%\medskip
%\noindent
%$F(\al,\be,\ga,\al^*,\be^*,\ga^*,n_1,m_1,n_2,m_2,n_3,m_3)=$
%$$
%\left\{
%\begin{array}{ll}
%F_0(\ga^*,n_1,m_1) & \rmif \al,\be\leq\ga \\
%F_0(\be^*,n_2,m_2) & \rmif \ga < \be \rmand \al\leq\be \\
%F_0(\al^*,n_3,m_3) & \rmif \be,\ga < \al \\
%\end{array}\right.
%$$

%Now suppose that we are given $G:\kappa^{n+2}\to\kappa$.  For each $\delta < \kappa^{+}$, let
%$$k(\de)=\sup(G[\delta^{n+2}])+1.$$
%%For any $\ga<\om_1$ let $\ga^*=k(\ga)$.
%Let $g_{\delta}:\kappa^{n+1}\to (n+1)$ be such that
%$$G(\xi^{\delta + 1}_{\alpha_{0}},\ldots,\xi^{\delta + 1}_{\alpha_{n+1}},\delta)=k(\delta)_{g(\alpha_{0},\ldots,\alpha_{n+1})}$$
%for all $\alpha_{0},\ldots,\alpha_{n+1} < \kappa$.
%By the universality property of $f$ there exists
%$h^{\delta}_{Q}:\kappa^{n} \to \kappa$  for $Q \in [n+1]^{n}$ with
%$$g_{\delta}(\alpha_{0},\ldots,\alpha_{n+1})=f(\{h^{\delta}_{Q}(\{\alpha_{i} : i \in Q}) : Q \in [n+1]^{n}\})$$
%for every $\alpha_{0},\ldots,\alpha_{n+1} < \kappa$.

%For $\de\leq \ga$
%define
%$h_1(\de,\ga)=h(k)$ where $\de=(\ga+1)_k$.   Then we have
%that
%$$\forall \al,\be\leq\ga<\om_1\;\;\;
%G(\al,\be,\ga)=F_0(k(\ga),h_1(\al,\ga),h_1(\be,\ga)).$$



%Then given $G$ we can find $k,h_1,h_2,h_3$ so that

%\noindent $G(\al,\be,\ga))=$

%$F(\al,\be,\ga,k(\al),k(\be),k(\ga),$

%$\;\;\;\;\;\;\;\;\; h_1(\al,\ga),h_1(\be,\ga),\;\;
%h_2(\al,\be),h_2(\ga,\be),\;\; h_3(\be,\al),h_3(\ga,\al)).
%$

%\qed

%We prove (2) and leave 3-5 to the reader.

%Suppose that $f:\om^2\to\om$ witnesses
%$U(\om,2,1)$.  For any countable ordinal $\de>0$ let
%$\de=\{\de_i:i<\om\}$. Define
%$$F_0(\de,n,m)=\de_{f(n,m)}.$$
%Now suppose $G:\om_1^3\to\om_1$.  Define
%$$k(\de)=\sup\{G(\al,\be,\ga)\;:\;\al,\be,\ga\leq\de\}+1$$
%For any $\ga<\om_1$ let $\ga^*=k(\ga)$.
%Define $g:\om^2\to\om$ by
%$$G((\ga+1)_n,(\ga+1)_m,\ga))=\ga^*_{g(n,m)}.$$
%By the universality property of $f$ there exists
%$h:\om\to\om$ with
%$$g(n,m)=f(h(n),h(m)) \mbox{ for every } n,m\in\om.$$
%For $\de\leq \ga$
%define
%%$h_1(\de,\ga)=h(k)$ where $\de=(\ga+1)_k$.   Then we have
%that
%$$\forall \al,\be\leq\ga<\om_1\;\;\;
%G(\al,\be,\ga)=F_0(k(\ga),h_1(\al,\ga),h_1(\be,\ga)).$$

%Define $F$ as follows:

%\medskip
%\noindent
%$F(\al,\be,\ga,\al^*,\be^*,\ga^*,n_1,m_1,n_2,m_2,n_3,m_3)=$
%$$
%\left\{
%\begin{array}{ll}
%F_0(\ga^*,n_1,m_1) & \rmif \al,\be\leq\ga \\
%F_0(\be^*,n_2,m_2) & \rmif \ga < \be \rmand \al\leq\be \\
%F_0(\al^*,n_3,m_3) & \rmif \be,\ga < \al \\
%\end{array}\right.
%$$

%Then given $G$ we can find $k,h_1,h_2,h_3$ so that

%\noindent $G(\al,\be,\ga))=$

%$F(\al,\be,\ga,k(\al),k(\be),k(\ga),$

%$\;\;\;\;\;\;\;\;\; h_1(\al,\ga),h_1(\be,\ga),\;\;
%h_2(\al,\be),h_2(\ga,\be),\;\; h_3(\be,\al),h_3(\ga,\al)).
%$

%\qed

%The $\ka$-Cohen real model is any model of ZFC obtained
%by forcing with the poset of finite partial functions from $\ka$ to
%2 over a countable transitive ground model satisfying ZFC.

%\begin{prop}\label{prop34}
%In the $\om_2$-Cohen real model
%we have that
%$U(\om_1,1)$ fails.  Similarly, $U(\om_2,2)$
%fails in the $\om_3$-Cohen real model.
%More generally, we have that
%$U(\ga,n)$ fails in the $\ka$-Cohen real model
%when $\ka>\ga\geq \om_n$.
%\end{prop}

%\pagebreak

%In Proposition \ref{prop34} we let $\mathbb{P}(n,\kappa)$ denote the partial order which
%adds a function from $\kappa^{n}$ to $2$ by finite conditions, for any $n \in \omega$ and any cardinal $\kappa$.


The partial order $\mathrm{Fn}(X,Y,\kappa)$ was defined before Theorem \ref{follthrm}.
For any $n \in \omega$ and any infinite cardinal $\kappa$, the partial order $\mathrm{Fn}(\kappa^{n}, 2, \aleph_{0})$ is forcing-equivalent to the partial order
which adds a subset of $\kappa$ by finite conditions.

\begin{prop}\label{prop34}
Suppose that $n \in \omega \setminus \{0\}$ and that $\gamma < \kappa$ are cardinals with $\aleph_{n} \leq \gamma$.
Then $U(\gamma, n)$ fails after forcing with $\mathrm{Fn}(\kappa^{n+1}, 2, \aleph_{0})$.
%$\mathbb{P}(n+1,\kappa)$.
\end{prop}

\proof
Let $G \subseteq \mathrm{Fn}(\kappa^{n+1}, 2, \aleph_{0})$ be a $V$-generic filter, and fix a function
$$F \colon \gamma^{n+1} \to \gamma$$ in $V[G]$. Since $\mathrm{Fn}(\kappa^{n+1}, 2, \aleph_{0})$ is c.c.c.,
we may fix an $\eta <\kappa$ such that $F$ is in $V[G \restriction \eta^{n+1}]$.
%Define $H \colon \prod_{i < n+1}\omega_{i} \to 2$ by setting $H(\alpha_{0},\ldots,\alpha_{n})$ to be
%$G(\alpha_{0},\ldots,\alpha_{n-1},\eta + \alpha_{n})$.
Supposing toward a contradiction that $F$ witnesses $U(\gamma, n+1, [n+1]^{n})$ in $V[G]$, there exist functions
$$h_{i} \colon (\prod_{j \in (n+1) \setminus \{i\}}\omega_{j}) \to
\gamma\hspace{.2in} (i < n+1)$$ such that for all $(\alpha_{0},\ldots,\alpha_{n}) \in \prod_{i < n+1}\omega_{i}$,
$G(\alpha_{0},\ldots,\eta + \alpha_{n})$ is equal to $$F(h_{0}(\alpha_{1},\ldots,\alpha_{n}), h_{1}(\alpha_{0}, \alpha_{2},\ldots,\alpha_{n}),\ldots,
h_{n}(\alpha_{0},\ldots,\alpha_{n-1})).$$ Again applying the fact that $\mathrm{Fn}(\kappa^{n+1}, 2, \aleph_{0})$ is c.c.c., there exists a
$\delta_{n} < \omega_{n}$ such that $h_{n} \in V[G^{\{n\}}]$, where $G^{\{n\}}$ is the restriction of $G$ to those members of $\kappa^{n+1}$ whose last element is
not $\eta + \delta_{n}$. For each $i < n$, let $h^{\{n\}}_{i}$ be the function on $\prod_{j \in n \setminus \{i\}}\omega_{j}$ defined by setting
$$h^{\{n\}}_{i}(\alpha_{0},\ldots,\alpha_{i-1},\alpha_{i+1},\ldots,\alpha_{n-1})$$ to be
$$h_{i}(\alpha_{0},\ldots,\alpha_{i-1},\alpha_{i+1},\ldots,\alpha_{n-1},\eta + \delta_{n}).$$ Applying the c.c.c. of $\mathrm{Fn}(\kappa^{n+1}, 2,
\aleph_{0})$ again, we can find a $\delta_{n-1} < \omega_{n-1}$ such that, letting $G^{\{n-1,n\}}$ be the restriction of $G$ to those members of $\kappa^{n+1}$
whose last two elements are not $\delta_{n-1}$ and $\eta + \delta_{n}$, $h^{\{n\}}_{n-1} \in V[G^{\{n-1,n\}}]$.  For each $i < n$,
let $h^{\{n-1,n\}}_{i}$ be the function on $$\prod_{j \in (n-1) \setminus \{i\}}\omega_{j}$$ defined by setting
$$h^{\{n-1,n\}}_{i}(\alpha_{0},\ldots,\alpha_{i-1},\alpha_{i+1},\ldots,\alpha_{n-2})$$ to be
$$h_{i}(\alpha_{0},\ldots,\alpha_{i-1},\alpha_{i+1},\ldots,\alpha_{n-2},\delta_{n-1},\eta + \delta_{n}).$$
Continuing in this fashion, we can find
$(\delta_{1},\ldots,\delta_{n-1}) \in \omega_{1} \times \ldots \times \omega_{n-1}$ such that,
\begin{itemize}
\item letting $G^{\{1,\ldots,n\}}$ be the restriction of
$G$ to those elements of $\kappa^{n+1}$ whose last $n$ elements are not $\delta_{1},\ldots,\delta_{n-1},\eta + \delta_{n}$, and
\item letting, for each positive $i < n$,
$h^{\{1,\ldots,n\}}_{i}$ be the function on $\omega$ whose value at $n$ is $h_{i}(n,\delta_{1},\ldots,\delta_{i-1},\delta_{i+1},\ldots,\delta_{n-1},\eta +
\delta_{n})$,
\end{itemize}
each $h^{\{1,\ldots,n-1\}}_{i}$ is in $V[G^{\{1,\ldots,n\}}]$.

Finally, we see that the function $g \colon \omega \to 2$ defined by setting $g(n) = G(n,\delta_{1},\ldots,\delta_{n-1},\eta + \delta_{n})$ is Cohen-generic over
$V[G^{\{1,\ldots,n\}}]$. However, as $h_{0}(\delta_{1},\ldots,\delta_{n-1},\eta + \delta_{n})$ is a fixed member of $\omega_{2}$, our assumptions on $F$ and
$h_{0},\ldots,h_{n}$ give that $g$ is an element of $V[G^{\{1,\ldots,n\}}]$.
\qed

% $A \subseteq \kappa$ of cardinality less than $\omega_{n}$ such that, letting $G^{**}$ be the union of $G^{*}$ with the restriction of $G$ to those elements of
%$\kappa^{n+1}$ whose first $n$ members are elements of $A$, $\{ h'_{i} : i < n \} \in V[G^{**}]$.


%\proof
%We show that $U(\om_2,2)$
%fails in the $\om_3$-Cohen real model, leaving the rest
%to the reader.

%Let $M$ be a countable transitive model of ZFC and
%in $M$ define

%\proof
%Let $\poset$ be the poset of finite partial
%maps from $\kappa\times\kappa\times\kappa$ into 2.

%\proof
%Let $\phi(n)$ be the following statement : whenever $\gamma < \kappa$ are cardinals with $\aleph_{n} \leq \gamma$,
%$G \subseteq \mathbb{P}(n, \kappa)$ is a $V$-generic filter, and $F$ is a function from $\omega_{n}^{n+1}$ to $\omega_{n}$
%in $V[G]$, there exists an $\eta < \kappa$ such that the function $H \colon \prod_{i < n+1} \omega_{i} \to 2$ defined by setting
%$$H(\alpha_{0},\ldots,\alpha_{n}) = G(\alpha_{0},\ldots,\alpha_{n-1},\eta + \alpha_{n})$$
%%for all $(\alpha_{0},\ldots,\alpha_{n}) \in \prod_{i < n+1} \omega_{i}$
%gives a counterexample to $F$ witnessing $U(\gamma, n)$ in $V[G]$.

%For the case $n=1$, let $G \subseteq \mathbb{P}(2,\kappa)$ be a $V$-generic filter.
%Fix a function $F \colon \omega_{n}^{2} \to \omega_{n}$ in $V[G]$.
%Since $\mathbb{P}(2,\kappa)$ is c.c.c., we may find an $\eta < \kappa$ with $F$ in $V[G\res\eta^{2}]$.
%Let $H \colon \omega \times \omega_{1} \to 2$ be defined as in the statement of $\phi(1)$, with respect to $\eta$.
%%$$H(\alpha_{0},\ldots,\alpha_{n}) = G(\alpha_{0},\ldots,\alpha_{n-1},\eta + \alpha_{n})$$ for all
%%$(\alpha_{0},\ldots,\alpha_{n}) \in \prod_{i < n+1} \omega_{i}$.
%Supposing toward a contradiction that $H$ is not a counterexample to $F$ witnessing $U(\gamma, 2, [2]^{1})$, there
%exist functions $h_{0} \colon \omega \to \omega_{2}$ and $h_{1} \colon \omega_{1} \to \omega_{2}$ such that
%$$H(n, \alpha)=F(h_{0}(n), h_{1}(\alpha))$$
%for all $(n,\alpha) \in \omega \times \omega_{1}$.

%Again applying the fact that $\mathbb{P}(2,\kappa)$ is c.c.c., there exists a $\delta < \omega_{1}$ such that
%$h_{0} \in V[G^{*}]$, where
%%By the c.c.c. we can choose
%%$\ga_1<\om_2$ such that $h_1\in M[G^*]$ where
%$G^*$ is $G$ restricted to those $(\alpha_{0}, \alpha_{1}) \in \kappa \times \kappa$
%for which $\alpha_{1} \neq \eta + \delta$.
%%$\{(\al,\be,\rho)\in\om^3\;:\;\rho\neq \ga_0+\ga_1\}$.
%Define $g:\omega\to 2$ by setting
%$$g(n)=G(n,\eta + \delta).$$
%%Note that we have that $F,h_1\in M[G^*]$,
%Then $g$ is Cohen generic over $V[G^*]$-generic for $\mathbb{P}(n,\kappa)$, and
%$$g(n)=F(h_{0}(n),h_1(\eta + \delta))$$ for all $n\in \omega$.
%Since $F$ and $h_{0}$ are in $V[G^{*}]$, this means that $g$ is in $V[G^{*}]$, giving a contradiction.


%Now, supposing that $\phi(n)$ holds, we prove $\phi(n+1)$.
%Let $G \subseteq \mathbb{P}(n+2,\kappa)$ be a $V$-generic filter.
%Fix a function $F \colon \omega_{n+1}^{n+2} \to \omega_{n+1}$ in $V[G]$.
%Since $\mathbb{P}(n+2,\kappa)$ is c.c.c., we may find an $\eta < \kappa$ with $F$ in $V[G\res\eta^{n+2}]$.
%Let $H \colon \prod_{i < n+2} \omega_{i} \to 2$ be as in the statement of $\phi(n+1)$, with respect to $\eta$.
%%defined by setting
%%$$H(\alpha_{0},\ldots,\alpha_{n}) = G(\alpha_{0},\ldots,\alpha_{n-1},\eta + \alpha_{n})$$ for all
%%$(\alpha_{0},\ldots,\alpha_{n}) \in \prod_{i < n+1} \omega_{i}$.
%Supposing toward a contradiction that $F$ witnesses $U(\gamma, n+2, [n+2]^{n+1})$, there
%exist functions $$h_{Q} \colon \prod_{i \in Q}\omega_{i} \to \omega_{n}\hspace{.2in} (Q \in [n+2]^{n+1})$$ such that
%$$H(\alpha_{0},\ldots,\alpha_{n+1})=F(\langle h_{(n+2 \setminus \{i\}}(\langle \alpha_{j} : j \in (n+2) \setminus \{i\} \rangle) : i < n+2 \rangle)$$
%for all $(\alpha_{0},\ldots,\alpha_{n+1}) \in \prod_{i < n+2} \omega_{i}$.

%We there is
%no map $F:\om_2\times\om_2\times\om_2\to \om_2$
%which is (3,2)-universal for maps
%of the form $H:\om\times\om_1\times\om_2\to 2$.
%Suppose for contradiction that $F$ is such a map.


%Hence we may find maps $h_1:\om\times\om_1\to\om_3$,
%$h_2:\om\times\om_2\to\om_3$, and
%$h_3:\om_1\times\om_2\to\om_3$ such that

%Since $\mathbb{P}(n+2,\kappa)$ is c.c.c., there exists a $\delta < \omega_{n+1}$ such that
%$h_{n+1} \in V[G^{*}]$, where
%%By the c.c.c. we can choose
%%$\ga_1<\om_2$ such that $h_1\in M[G^*]$ where
%$G^*$ is $G$ restricted to those $(\alpha_{0},\ldots,\alpha_{n+1}) \in \prod_{i < n+2} \omega_{i}$
%for which $\alpha_{n+1} \neq \eta + \delta$.
%%$\{(\al,\be,\rho)\in\om^3\;:\;\rho\neq \ga_0+\ga_1\}$.
%Define $g:\prod_{i < n+1}\to 2$ by setting
%$$g(\alpha_{0},\ldots,\alpha_{n})=G(\alpha_{0},\ldots,\alpha_{n},\eta + \delta).$$
%%Note that we have that $F,h_1\in M[G^*]$,
%Then $g$ is $V[G^*]$-generic for $\mathbb{P}(n+1,\kappa)$, and $V[G^{*}][g] = V[G]$.
%Fix $\xi \in [\omega_{n}, \omega_{n+1})$ containing the range of $h_{n+1}$ and also $$\bigcup \{ h_{Q}[\prod_{i < n+1}\omega_{1} \times \{\eta + \delta\}] \mid Q
%\in [n+2]^{n+1},\, n \in Q\}.$$ Let $\langle \cdot, \cdot \rangle$ be a pairing function on $\xi$.

%Define $F' \colon \xi^{n+1} \to \omega_{n+1}$ by setting $F'(\langle \alpha_{0},\beta_{0}\rangle,\ldots, \langle \alpha_{n}, \beta_{n} \rangle)$ to be
%$$F(\beta_{0},\ldots,\beta_{n},
%(h_{n+1}(\alpha_{n},\alpha_{0},\ldots, \alpha_{n-1}))).$$
%For each $R \in [n+1]^{n}$, let $h'_{R} \colon \prod_{i\in R} \omega_{i} \to \xi$ be defined by setting $$h'_{R}(\alpha_{0},\ldots,\alpha_{n-1}) =
%\langle \alpha_{i^{*}}, h_{R \cup \{n+1\}}(\alpha_{j_{R}},\ldots,\alpha_{n},\eta + \delta)\rangle.$$
%where $j_{R}$ is the unique element of $n+1 \setminus R$ for $R \neq n$, and $j_{n} = 0$.
%Then the functions $h'_{R}$ witness $U(\kappa, n+1, [n+1]^{n})$ in $V[G^{*}][g]$ for $F'$ and $g$, giving a contradiction.
%\qed

%$$g(\alpha_{0},\ldots,\alpha_{n-1})=F(h_1(n,\al),h_2(n,\ga_0+\ga_1),h_3(\al,\ga_0+\ga_1)).$$

%Since the extension by $g$ is c.c.c., we may find $\al_0<\om_1$
%such that
%$$h_2\in M[G^*][g\res (\om\times\al_0)]=^{def}N.$$
%But this is
%a contradiction because $g_{\al_0}$ defined by $g_{\al_0}(n)=g(n,\al_0)$
%is Cohen generic over $N$.
%But $F,h_1,h_2\in N$ and for any $\ga_2<\om_2$ the map $k$ defined by
%$$k(n)=F(h_1(n,\al_0),h_2(n,\ga_0+\ga_1),\ga_2)
%\mbox{ for all } n<\om$$
%is in $N$, so can never be equal to $g_{\al_0}$.
%Thus $h_3(\al_0,\ga_0+\ga_1)=\ga_2$ cannot be defined.
%\qed

Putting together Propositions \ref{prop33} and \ref{prop34}, we have the following.

\begin{cor}\label{cor35}
Let $\gamma < \kappa$ be cardinals, with $\aleph_\om\leq\ga$. After forcing to add a subset of
$\kappa$ by finite conditions, we have that
$$U(\om_n,n+1)+\neg U(\om_n,n) + \neg U(\ga,n),$$
for all positive $n \in \omega$.
\end{cor}

%\begin{remark}
If we start with a model $M_1$ of GCH and force with the set of countable
partial functions from $\ka=\aleph_{\om+1}$ into $2$, then in
the resulting model $M_2$ we have CH so
$U(\om_1,1)$ holds by Theorem \ref{existuniv}.
Proposition \ref{prop33} then gives $U(\om_n,n)$ for all positive $n \in \omega$.  By
an argument similar to Proposition \ref{prop34}
but raised up one cardinal, we have $\neg U(\om_n,n-1)$
for $n\geq 2$.  If we then add $\ka=\om_3$ Cohen reals to $M_2$ to
get $M_3$, then we will have in $M_3$ that $|2^\om|=\om_3$
and $\neg U(\om_3,2)$ by the argument of Proposition \ref{prop34}
lifted by one cardinal. By Proposition \ref{prop33}, $U(\om_3,4)$ is true in ZFC.
This leaves open the question of whether $U(\omega_{3}, 3)$ holds in $M_{3}$.
%\end{remark}


\begin{define} For Borel universal functions of higher dimensions, we let $U({\rm Borel}, \Sigma, n)$ and $U({\rm Borel}, n)$ denote
the versions of Definition \ref{def29} and \ref{defU} where $X$ is $\rcantor$ and $F$ is required to be Borel.
\end{define}

%\begin{define}
%In the case of Borel universal functions of higher dimensions,
%we use $U({\rm Borel},n)$ to mean
%the analogous thing as in Definition \ref{defU} only we require
%that the universal map $F$ be Borel.
%\end{define}

The following proposition follows from the proofs of part (3) of Propositions~\ref{propmn} and \ref{sig}, using the fact that the composition of Borel functions is Borel,
and the  fact that there exist continuous pairing and unpairing functions. The reader interested in constructing a complete proof will also have to verify that the universal functions constructed in Propositions~\ref{multiu} and~\ref{pairfunctions} are Borel assuming the functions in the hypothesis are, thus yielding the same conclusion for Proposition~\ref{propmn} and~\ref{sig}.

\begin{prop}
The following hold for any $n \in \omega$.
\begin{enumerate}
\item $U(Borel, n)$ implies $U(Borel, n+1)$
\item $U(Borel, \Sigma, n)$ is equivalent to
$U(Borel, m)$ for $m+1$ the size of the smallest
subset of $n$ not in the downward closure of $\Sigma$.
\end{enumerate}
\end{prop}



We can further refine $U({\rm Borel},n)$
in the special case that our universal
function $F$ is a level $\al$ Borel function.
The composition of level $\al$-functions is
not necessarily level $\al$, i.e., $F(F(x,y),z)$ need  be at
the level $\al$ just because $F$ is.  Hence it is not immediately
obvious that the binary case of the next proposition implies
the n-ary case. The proof here is similar to that
of Rao \cite{rao}. Recall from Subsection \ref{ccssec} that the hypothesis of the proposition
is implied by Martin's Axiom. The hypotheses on cardinal characteristics in Proposition \ref{proprao} 
(and Proposition \ref{prophhm}) are used only to get a set of reals of cardinality $\mathfrak{c}$ which 
is wellordered by a Borel relation. 

\begin{prop}\label{proprao}
Suppose that $\mathfrak{t} = \mathfrak{q} = \mathfrak{c}$. Then for every
$n>1$ there is a level 2 Borel function $F:(2^\om)^n\to 2^\om$
which is universal, i.e., such that for every $G:(2^\om)^n\to 2^\om$
there exist $h_i:2^\om\to 2^\om$ ($1 \leq i \leq n$) such that for every $x$ in $(2^\om)^n$
$$G(x_1,\ldots,x_n)=F(h_1(x_1),\ldots,h_n(x_n))$$
\end{prop}



\proof
%Recall from Subsection \ref{ccssec} that $\mathfrak{p} \leq \min\{\mathfrak{t}, \mathfrak{q}\}$.
By Proposition \ref{easytwo} and the remarks before, it suffices to find an
$F_{\sigma}$ set $H \subseteq (2^{\omega})^{n}$ such that for each $A \subseteq
\cc^{n}$ there exists an $h \colon \cc \to 2^{\omega}$ such that for all
$(\alpha_{0}, \ldots, \alpha_{n-1}) \in \cc^{n}$,
$(\alpha_{0},\ldots,\alpha_{n-1}) \in A$ if and only if
$(h(\alpha_{0}),\ldots,h(\alpha_{n-1}))\in H$.

%For simplicity we prove it for $n=3$.
Let $F\su (2^{\omega})^{n+1}$ be
an $F_\si$ set with the property that for every $F_\si$ set
$K\su  (2^\om)^{n}$ there exists $x\in 2^\om$ with
$K=F_{x}$, i.e., the set of $(y_{1},\ldots,y_{n})$ in $(2^{\omega})^{n}$ with
$(x, y_{1},\ldots,y_{n-1}) \in F$.

Define the binary relation $\leq^{*}$ on $2^{\omega}$ by setting $x \leq^{*} y$ if
$$x^{-1}[\{1\}] \setminus y^{-1}[\{1\}]$$ is finite.
Let $g:\cc\to 2^\om$
be an injection such that for each pair $\alpha, \beta$ from $\cc$,
$\alpha \leq \beta$ if and only if $g(\alpha) \leq^{*} g(\beta)$.
%$g(\alpha)^{-1}[\{1\}] \setminus g(\beta)^{-1}[\{1\}]$ is infinite and
%$g(\beta)^{-1}[\{1\}] \setminus g(\alpha)^{-1}[\{1\}]$ is finite.
The existence of such a function follows from the statement $\mathfrak{t} = \cc$.
%Such a function exists, as Martin's Axiom implies that $\mathfrak{t} = \cc$.

For each $\beta < \cc$, let $D_{\beta}$ be the set of
$(\alpha_{0},\ldots,\alpha_{n-1}) \in \cc^{n}$ such that
$\max\{\alpha_{0},\ldots,\alpha_{n-1}\} \leq \beta$.
%$$D_1=\{(\al,\be,\ga)\st \al,\be\leq\ga<\cc\}$$
Since $\mathfrak{q} = \mathfrak{c}$, every set $X\su 2^\om$ with
$|X|<\cc$ is a $Q$-set (see Subsection \ref{ccssec}).
% i.e., every $Y\su X$ is a relative
%$F_\si$.
Thus given $A \subseteq \cc^{n}$, there exists a function $k :\cc\to 2^\om$
with the property that for each $\beta < \cc$ and every $(\alpha_{0},\ldots,\alpha_{n-1})$ in $D_{\beta}$,
$(\alpha_{0},\ldots,\alpha_{n-1}) \in A$ if and only if $$(k(\beta), g(\alpha_{0}),\ldots, g(\alpha_{n-1}))\in F.$$

%Similarly let
%$$D_2=\{(\al,\be,\ga)\;:\; \al,\ga\leq \be<\cc\}
%\rmand
%D_3=\{(\al,\be,\ga)\;:\; \ga,\be\leq \al<\cc\}$$
%Now given any $A\su D_2$ or $A\su D_3$, we
%can obtain $h_2$, and $h_3$ with the
%analogous property.

%Note that we may determine which case ($D_i$)
%in an $F_\si$ way as follows.

%Let $\geq^{*}$ be the relation on
%$\omega^{\omega}$ given by setting $x \geq^{*} y$ if and only if
%$$\{n \in \omega \mid y(n) < x(n)\}$$ is finite. Let $k:\cc\to \om^\om$ be
%a scale, i.e., so that $\alpha \leq \beta$ if and only if
%$k(\beta) \geq^{*} k(\alpha)$.   Such an object exists
%assuming Martin's Axiom.

%We claim now that there exists
%an $F_\si$ set $H \subseteq (2^{\omega})^{n}$ as desired.

Let $\langle \cdot, \cdot \rangle$ be the pairing function on $2^{\omega}$ such that $\langle x,y \rangle(2n) =x(n)$ and $\langle x,y \rangle (2n+ 1) = y(n)$, for
each $n \in \omega$. Now let $H$ be the set of $(\langle x_{0}, y_{0}\rangle,\ldots,\langle x_{n-1}, y_{n-1}\rangle) \in (2^{\omega})^{n}$ such that, for
some $i < n$, $x_{j} \leq^{*} x_{i}$ for all $j < n$, and
$(y_{i},x_{0},\ldots,x_{n-1}) \in F$. Then $H$ is $F_{\sigma}$.




Given $A \subseteq \cc^{n}$, for each $\alpha < \cc$, let $h(\alpha)$ be $\langle g(\alpha), k(\alpha) \rangle$, where $k$ is as
above with respect to $A$.
\qed

%with the property that for
%each $A\su \cc^{n}$ there exists
%$h:\cc\to 2^\om$ such that for all $(\alpha_{0},\ldots,\alpha_{n-1}) \in \cc^{n}$,
%$(\alpha_{0},\ldots,\alpha_{n-1}) \in A$ if and only if
%%$$\forall \al,\be,\ga\;\; (\al,\be,\ga)\in A \rmiff
%$(h(\alpha_{0}),\ldots,h(\alpha_{n-1}))\in H$.

%To do this, find $h$ and $H$ so that $(h(\alpha_{0}),\ldots, h(\alpha_{n-1})) \in H$ if and only if for some $i < n$,
%$k(\alpha_{i}) \geq^{*} k(\alpha_{j})$ for each $j < n$, and
%$$(h(\alpha_{i}), g(\alpha_{0}),\ldots,g(\alpha_{i-1}), g(\alpha_{i+1}),\ldots g(\alpha_{n-1}))\in F.$$
%\qed


%at least one of the following three statements holds.
%$$k(\gamma) \geq^{*} k(\alpha) \wedge k(\gamma) \geq^{*} k(\beta) \wedge (g(\alpha), g(\beta), h_{1}(\gamma)) \in F$$
%$$k(\beta) \geq^{*} k(\alpha) \wedge k(\beta) \geq^{*} k(\alpha) \wedge (g(\alpha), h_{2}(\beta), g(\gamma)) \in F$$
%$$k(\alpha) \geq^{*} k(\beta) \wedge k(\alpha) \geq^{*} k(\gamma) \wedge (h_{3}(\alpha), g(\beta), g(\gamma)) \in F$$

%To see how to do this note that the function $k$ can tell
%us which case we are in $D_1$, $D_2$, or $D_3$.  Then the
%function $h$ codes up $k$ and the $h_1,h_2,h_3$.

%Then, as in the proof of Theorem \ref{mainthm}, we get
%an $F:(2^\om)^{n} \to 2^\om$ which
%is a level 2 universal Borel map.
%qed

\section{Model-theoretic universality}\label{mtu}


In this section we consider the relationship between the existence
of abstract universal functions and the existence of universal
models. The key difference is that if one were to consider a
universal function as the model of some theory, then embedding would
require embedding the range as well as the domain of the function.
This is different than the notion of universality being considered
here since the values in the range remain fixed. Nevertheless, there
is insight to be gained from the model theoretic perspective. It is
well known that saturated models are universal in the sense of
elementary substructures and that saturated models of cardinality
$\kappa$ exist if $\ka^{<\ka}=\ka$, see Chapter 5 of Chang and Keisler \cite{ck},
for instance.

\begin{define}
For any cardinal $\kappa$ let $\mathcal{L}_\kappa$ be the first order language
consisting of a single binary function symbol $\Phi$ and constant symbols
$\{c_\gamma\}_{\gamma\in\kappa}$ for distinct constants. Let
$\mathcal{T}_\kappa$ be the $\mathcal{L}_\kappa$-theory consisting of the
sentences $c_\gamma\neq c_\beta$ for $\gamma\neq \beta$ and
the sentences $\Phi(c_\ga,c_\be)=c_0$ for all $\ga,\be$.
\end{define}

There is some overlap between the following proposition and Theorem \ref{existuniv}.

\begin{prop}
If $\mathcal{T}_\kappa$ has a model of cardinality
$\kappa$ which is universal in the model theoretic sense,
then there is a universal function
$F:\ka \times \ka\to \ka$.
\end{prop}

\proof
Let $(X,\Phi,c_\al)_{\al<\ka}$ be a universal $\mathcal{T}_\kappa$ model
of cardinality $\ka$, and let $C = \{c_{\alpha} : \alpha < \kappa\}$.
Universality implies that $Y=X\sm C$
has cardinality $\ka$.  Let $\langle d_\al:\al<\ka\rangle$ enumerate $Y$.
Define $F:\ka^2\to\ka$ by setting $F(\al,\be)$ to be the unique $\ga$ such that $\Phi(d_\al,d_\be)=c_\ga$,
if one exists, and $0$ otherwise.
Given an arbitrary $f:\ka \times \ka\to\ka$, construct a $\mathcal{T}_\kappa$
model $(\{b_\al:\al<\ka\}\cup C,\Phi_f,c_\al)_{\al<\ka}$
where $\{b_\al:\al<\ka\}$ is disjoint from
$C$
and $\Phi_f(b_\al,b_\be)=c_\ga$ if and only if $f(\al,\be)=\ga$.  Since a
model theoretic embedding fixes the constant symbols, we get
an $h$ showing that $f(\al,\be)=F(h(\al),h(\be))$ for all $\alpha, \beta \in \kappa$.
\qed

In this section we will use the term \emph{Sierpi\'nski universal} for the notion
of universal function which is the subject of this paper, to distinguish it from
model theoretic universality.


\begin{define}
A function $U:\ka\times\kappa\to\ka$ is Sierpi\'nski universal if for every
$f:\ka\times\kappa\to\ka$ there exists $h:\ka\to\ka$ such that
for all $\al,\be\in\ka$,
$$f(\al,\be)=U(h(\al),h(\be)).$$
\end{define}

\begin{define}
A function $U:\ka\times \kappa\to\ka$ is model theoretically universal if for every
$f:\ka\times\kappa\to\ka$ there exists $h:\ka\to\ka$ one-to-one such that
for all $\al,\be\in\ka$,
$$h(f(\al,\be))=U(h(\al),h(\be)).$$
\end{define}

In other words, a function $U \colon \kappa \times \kappa \to \kappa$ is model theoretically
universal if and only if every structure $(X,f)$ where $f:X^2\to X$ and
$|X|=\ka$ is isomorphic to a substructure of $(\ka,U)$.

We define a common weakening of these notions, as follows.

\begin{define}
A function $U:\ka\times\kappa\to\ka$ is weakly universal if for every
$f:\ka\times\kappa\to\ka$ there exist $h:\ka\to\ka$ and $k:\ka\to\ka$ one-to-one
such that
for all $\al,\be\in\ka$,
$$k(f(\al,\be))=U(h(\al),h(\be)).$$
\end{define}

\begin{remark}\label{wucodo}
The existence of a weakly universal function on $\kappa \times \kappa$ is not changed if we allow the codomains of $U$ and
$k$ to be any set of cardinality $\kappa$.
\end{remark}

\begin{remark}
Model theoretically universal functions are weakly universal with $h = k$, and Sierpi\'nski universal functions are weakly
universal with $k$ the identity function. implies weakly universal.
For maps into 2 (or binary relations)
all three notions are equivalent.
\end{remark}

\begin{ques}\label{q:101}
Is the existence of a model theoretically universal function from $\kappa \times \kappa$ to
$\kappa$ equivalent to the existence of a Sierpi\'nski universal one?
Does the existence of either one imply the existence of the other?
\end{ques}

\begin{prop}\label{modeluniv}
If $\ka$ is a singular strong limit cardinal then there is a
model theoretically universal function from $\kappa\times\kappa$ to
$\kappa$.
\end{prop}

\proof
Let $\gamma$ be the cofinality of $\kappa$, and let $\langle \kappa_{\alpha} :
\alpha < \gamma \rangle$ be an increasing sequence of cardinals cofinal in
$\ka$. Let $G$ be the set of functions $g$ from $\kappa \times \kappa$ to $\kappa$ such that
$g[\kappa_{\alpha} \times \kappa_{\alpha}] \subseteq \kappa_{\alpha}$ for each $\alpha < \gamma$.
For any function $f \colon \kappa \times \kappa \to \kappa$, there exist a
bijection $h \colon \kappa \to \kappa$ and a
function $g \in G$ such that for all $\beta, \delta < \kappa$,
$h(f(\beta, \delta)) = g(h(\beta), h(\delta))$ (that is, $(\kappa, f)$ is isomorphic to $(\kappa, g)$ via $h$).
%First of all note that $(X,f)$ is isomorphic to a structure $(\ka,g)$ where
%$g(k_{\alpha}^2)\su \ka_\al$ for each $\alpha < \gamma$.
This follows from the
fact that we can write $\kappa$ as a continuous increasing union of a sequence of sets
$X_{\alpha}$, each closed under $f$ and having size $\ka_{\alpha}$.

It suffices then to find a $U \colon \kappa \times \kappa \to \kappa$ which is model theoretically
universal with respect to functions in $G$. Since $\kappa$ is a strong limit cardinal, we
can recursively build $U$ so that for each $\alpha < \gamma$ and each function $f \colon \kappa_{\alpha}
\times \kappa_{\alpha} \to \kappa_{\alpha}$ there exist $X_{f} \subseteq \kappa$ and a bijection $h_{f} \colon
\kappa_{\alpha} \to X_{f}$ such that $h(f(\beta, \delta)) = U(h(\beta), h(\delta)$ for all $\beta, \delta$ in
$\kappa_{\alpha}$. Furthermore, we can build $U$ so that for all $\alpha < \alpha' < \gamma$ and all $f \colon
\kappa_{\alpha'} \times \kappa_{\alpha'} \to \kappa_{\alpha'}$ such that $f[\kappa_{\alpha} \times \kappa_{\alpha}]
\subseteq \kappa_{\alpha}$, $h_{f \restriction \kappa_{\alpha} \times \kappa_{\alpha}} = h_{f} \restriction \kappa_{\alpha}$.

Then for each $g \in G$, $\bigcup\{h_{g \restriction \kappa_{\alpha} \times \kappa_{\alpha}} : \alpha , \gamma\}$ is the desired function $h$ witnessing
that $U$ is model theoretically universal with respect to $g$.
\qed

%So we only have to worry about functions $g$ like this. But now we can invoke a
%simple counting argument since each $\ka_{\alpha}^{\ka_{\alpha}}<\ka$.
%Construct $V$ by induction on $\alpha$ so that for any $X\su\ka_{\alpha}$ which
%is closed under $V$ and any structure $(Y,h)$ with $X\su Y$ and
%$|Y|=\ka_{\alpha}$, if $h\res X^2=U\res X^2$, then there exists $Z\supseteq X$
%which is a bounded subset of $\ka$ and an isomorphism $(Y,h)\simeq (Z,V)$ which
%is the identity on $X$.

%Then the ``forth" part of a ``back and forth'' argument will show
%that every structure $(\ka,g)$ is isomorphic to a substructure of
%$(\ka,V)$.
%\qed

\begin{ques}
Suppose that $\ka=\aleph_\om$ is a strong limit cardinal.
For each $\al<\ka$ we have a Sierpi\'nski universal $U:\ka^2\to\al$
universal for all maps of the same type, by Theorem \ref{existuniv}.
By Proposition \ref{propomega}
we have a map $U:\ka^2\to\ka$ which is Sierpi\'nski universal
for all maps of the form $G:\om^2\to\ka$.  By Proposition \ref{modeluniv}
we have $U:\ka^2\to\ka$ which is model-theoretically universal
for all maps of the same type.  Is there a Sierpi\'nski
universal $U:\ka\times\ka\to\ka$
for maps of type $G:\om\times\om_1\to \ka$?
\end{ques}



Let ${\mathcal E}_4$ be the theory in the language of a single
4-ary relation $A$ that is an equivalence relation between the
first two and last two coordinates. In other words, it has the
following axioms:
\begin{itemize}
  \item $A(a,b,c,d) \rightarrow A(c,d,a,b)$
  \item $A(a,b,a,b)$
  \item $A(a,b,c,d)\  \&\ A(c,d,e,f) \rightarrow A(a,b,e,f)$
\end{itemize}
The transitivity condition on $A$ implies that $\mathcal{E}_{4}$ does not have the 3-amalgamation property, so
Mekler's argument of \cite{MR1056364} (see Theorem \ref{Meklerthrm}) can not be applied to
produce a universal model for this theory of cardinality
$\aleph_1$ along with $2^{\aleph_0} > \aleph_1$.
Nevertheless, the following observation highlights the connection between Sierpi\'nski universality and model
theoretic universality.

\begin{prop}
There is a universal model for ${\mathcal E}_4$ of cardinality $\kappa$ if
and only if there is a function $U:\kappa\times\kappa\to\kappa$ which is
weakly universal.
\end{prop}

\proof

Let $(\kappa,A)$ be a universal model of ${\mathcal E}_4$. Let $E$ be the  equivalence relation on $\kappa\times\kappa$ induced by $A$ and let
$\{E_\xi\}_{\xi\in\kappa}$ enumerate the equivalence classes of $E$.
Define $U:\kappa\times\kappa\to\kappa \times 2$ by setting $U(\alpha,\beta) = (\xi,0)$ if and only if $(\alpha,\beta) \in E_\xi$. We will show that
$U$ is weakly universal (using Remark \ref{wucodo}).

Given $g\colon \kappa \times \kappa \to \kappa$ let $G$ be the 4-ary relation defined by letting $G(\alpha,\beta,\delta,\gamma)$ hold if and only if
$g(\alpha,\beta) = g(\delta,\gamma)$. It is clear that $G$ satisfies the axioms of ${\mathcal E}_4$ hence there exists an injective $h:\kappa\to\kappa$ such that
$G(\alpha,\beta,\delta,\gamma)$ holds if and only if $A(h(\alpha),h(\beta),h(\delta),h(\gamma))$ does.
It follows that $g(\alpha,\beta) = g(\delta,\gamma)$ if and only if $U(h(\alpha),h(\beta)) = U(h(\delta),h(\gamma))$.
Then any injection $k \colon \kappa \to \kappa \times 2$ such that $k(g(\alpha, \beta)) = U(h(\alpha), h(\beta))$ for all $\alpha, \beta < \kappa$ is as desired.
%It is then easy to find an injective $j \colon \kappa \to \kappa$ such that
%$$j(g(\xi,\eta))) = U(h(\xi),h(\eta))$$ for all $\xi$ and $\eta$, letting $j$ take values in $\kappa \times \{1\}$ at all points not in the range of $g$.

The converse is proved by running the preceding argument backwards --- given a Sierpi\'nski universal function $U:\kappa\times\kappa\to\kappa$
satisfying the hypothesis, define $A(\alpha,\beta,\gamma,\delta)$ to hold precisely when $U(\alpha,\beta) = U(\gamma,\delta)$.
\qed

%\pagebreak

The next three propositions concern Borel universal functions.

\begin{prop}\label{boreltwoone}
There exists a Borel $U:2^\om\times 2^\om\to 2^\om$ which
is model theoretically universal with respect to all $F:\om_1\times\om_1\to\om_1$.
\end{prop}

\proof
We first describe $U$.  We use some
Borel encoding of the structures below for which the exact
details are not important.


%\bigskip Input $a,b\in 2^\om$. \bigskip

Suppose that we are given $a, b \in 2^{\omega}$. There are four cases: \bigskip

\noindent {\bf Case 1.} $a$ codes a pair $(n,x)$, and $b$ codes a pair $(m,x)$,
where $n, m \in \omega$ and $x \in 2^{\omega}$ codes a tuple $(f, B, <, \langle c_{k} : k \in B \rangle)$,
where $f$ is a function from $\omega \times \omega$ to $\omega$, $B$ is subset of $\omega$, $<$ is a linear order on
$\omega$ and each $c_{k}$ is in $2^{\omega}$;

\smallskip

%$x=(f:\om^2\to\om,B\su\om, (c_k\in 2^\om:k\in B))$

\noindent {\bf Case 2.} Case 1 fails and
$a$ codes a pair $(n,x)$, where $n \in \omega$, $x \in 2^{\omega}$ and $x$ codes a tuple $(f, B, <, \langle c_{k} : k \in B \rangle)$
as in Case 1, with $b = c_{m}$ for some $m \in B$;

\smallskip


\noindent {\bf Case 3.}
Cases 1 and 2 fail, and $b$ codes a pair $(m,x)$, where $m \in \omega$, $x \in 2^{\omega}$ and $x$ codes a tuple $(f, B, <, \langle c_{k} : k \in B \rangle)$
as in Case 1, with $a = c_{n}$ for some $n \in B$;

\smallskip


\noindent {\bf Case 4.} none of the previous cases hold.

\bigskip



%$a=(n,x)$, $x=(f:\om^2\to\om,B\su\om, (c_k\in 2^\om:k\in B))$,
%and $b=c_m$.

%\noindent {\bf Case 3.}
%$b=(m,x)$, $x=(f:\om^2\to\om,B\su\om, (c_k\in 2^\om:k\in B))$,
%and $a=c_n$.

%\bigskip

In the first three cases,
if $f(n,m)=k$ and $k\in B$, then we let $U(a,b) = c_k$, otherwise we let it be (a code for) $(k,x)$.
In the fourth case we let $U(a,b) = 0$.

%If something goes wrong, i.e., none of the cases
%above holds or more than one holds, then output zero.
%Remember we will be choosing nice inputs for $U$ so it doesn't matter
%what $U$ outputs
%for ones that we aren't going to choose anyway.

\smallskip
Now we verify that this works.
Given $F:\om_1\times\om_1\to\om_1$, let $C$ be a closed
unbounded subset of the countable limit ordinals, such that
$F[\alpha \times \alpha] \subseteq \alpha$, for each $\al\in C$.   We recursively
define $h \colon \omega_{1} \to \omega_{1}$ by assuming that we have
$h \restriction \alpha$ as desired, for some $\alpha \in C \cup \{0\}$, and defining
$h \restriction \min(C \setminus (\alpha + 1))$. Fix such an $\alpha$, and let
$\alpha^{+}$ denote the least member of $C$ above $\alpha$.
%construct sequences $\langle a_\be\in 2^\om:\be<\al \rangle$, for each $\al \in C$.
%Suppose that $\al^+$ is the next element of $C$ greater than $\al$.
Let $j:\om \to \al^+$ be a bijection.
Define $f:\om\times\om\to\om$ by setting $f(n,m) = j^{-1}(F(j(n), j(m))$, and the binary relation
$<$ on $\omega$ by setting $n < m$ if and only if $j(n) < j(m)$.
%be defined so that $j(f)=F\res\al^+$, i.e., $f(n,m)=k$ if and only if $F(j(n),j(m))=j(k)$.
Let $B = j^{-1}[\alpha]$, and, for each $k \in B$, let $c_{k} = a_{j(k)}$.
%Define $B$ by $\{j(k):k\in B\}=\al$ and for $k\in B$ let $c_k=a_{j(k)}$.
Let $x \in 2^{\omega}$ be a code for the tuple $(f, B, <, \langle c_{k} : k \in B\rangle)$.
For each $\beta \in [\alpha, \alpha^{+})$, let $h(\beta)$ be (a code for) the pair $(j^{-1}(\beta), x)$.
%In the case $\al^+$ is the least element of $C$, just take $B$ to
%be the empty set.

Now suppose that we are given $\beta, \gamma < \omega_{1}$. Fix $\alpha \in C \cup\{0\}$ such that
$\max(\beta, \gamma)$ is in $[\alpha, \min(C \setminus (\alpha + 1)))$, and let $\alpha^{+} =
\min(C \setminus (\alpha + 1))$ as above. If $\{ \beta, \gamma\} \subseteq [\alpha, \alpha^{+})$, then the
pair $(h(\beta), h(\gamma))$ is in Case 1 above.
If $\beta = \max(\beta, \gamma)$ and
$\gamma < \alpha$, then $(h(\beta), h(\gamma))$ is in Case 2, and if $\gamma= \max(\beta, \gamma)$ and
$\beta < \alpha$, then $(h(\beta), h(\gamma))$ is in Case 3. In any case, $U(h(\beta), h(\gamma))$ will be $h(F(\beta, \gamma))$.
\qed

%We now check that for any
%$\al,\be,\ga,\in\om_1$,
%$$U(a_\al,a_\be)=a_\ga \rmiff F(\al,\be)=\ga.$$
%The basic idea is that when we are inputting a pair there is
%a least $C$ interval  $[\al,\al^+)$ where the maximum input appears
%and the output will either be in the same interval encoded
%by a $(n,x)$ with $n\notin B$ or below
%$\al$ in which case it will be encoded in $x$ as a $c_k$
%for some $k\in B$.
%\qed


%Thm. If there is a Borel Sierpinski universal and $2^{\less\mathfrak{c}}=\mathfrak{c}$,
% then there is a Borel map $H:2^\om\times 2^\om\to 2^\om$ such that for every cardinal $\kappa < \mathfrak{c}$
% and for every $G\colon \kappa \times \kappa \to \kappa$ there are $x_i$ ($i<\kappa$) in the Cantor space
% such that $G(i,j)=l$  if and only if $H(x_i,x_j)=x_l$. 

%I don't know about k=c. 

\begin{remark}
The second author has recently shown that the version of Proposition \ref{boreltwoone} with $\omega_{2}$ in place of 
$\omega_{1}$ can consistently hold. Moreover, he has shown the following: if there is a Borel Sierpinski universal function and 
$2^{<\mathfrak{c}}=\mathfrak{c}$, then there is a Borel map $H:2^\om\times 2^\om\to 2^\om$ such that for every cardinal $\kappa < \mathfrak{c}$, 
and for every function $G\colon \kappa \times \kappa \to \kappa$, there exist $x_{\alpha}$ ($\alpha<\kappa$) in the Cantor space
such that for all $\al,\be,\ga<\om_2$ $G(\alpha,\beta)=\gamma$ if and only if $H(x_{\alpha},x_{\beta})=x_{\gamma}$. Whether this can hold for 
$\kappa = \mathfrak{c}$ is still open, as far as we know. 
\end{remark} 

%If we replace $\om_1$ by $\om_2$ in Proposition \ref{boreltwoone}, is the existence of such a $U$ consistent?
%For example, is it consistent to have a Borel
%function $B:2^\om\times 2^\om\to 2^\om$ and $\{x_\al\;:\; \al<\om_2\} \subseteq 2^{\omega}$
%such that for all $\al,\be,\ga<\om_2$,
%$B(x_\al,x_\be)=x_\ga$ if and only if $\al+\be=\ga$?
%\end{ques}

Given an ordinal $\gamma$, say that a function $f \colon \gamma \times \gamma$ \emph{weakly pushes down} if
$f(\alpha, \beta) < \max(\alpha, \beta)$ for all $\alpha, \beta < \gamma$.

\begin{prop}\label{prophhm}
%Assume MA.
%There exists a Borel weakly model theoretically universal.
%That is,
If $\mathfrak{t} = \mathfrak{ap} = \cc$, then there is a Borel function $U:2^\om\times 2^\om\to 2^\om$ such that
for every $f:\cc \times \cc\to \cc$ which weakly pushes down,
%i.e., %f(\al,\be)<\max(\al,\be)$ all $\al,\be$,
%$(\cc,f)$ is isomorphic to
%a substructure of $(2^\om, U)$, equivalently,
there exists a one-to-one
$h:\cc\to 2^\om$ such that $h(f(\al,\be))=U(h(\al),h(\be))$
for all $\al,\be<\cc$.
\end{prop}

\proof
Assuming $\mathfrak{ap} = \cc$, by the standard almost-disjoint forcing technique
%see
%for example, Hjorth, Humphrey, Miller \cite{hhm} Lemma 3.7,
there exists a Borel function $F:2^\om\times 2^\om\to 2^\om$ such
that for every function $g:X\to 2^\om$ with $X\su 2^\om$ and
$|X|<\cc$, there exists $y\in 2^\om$
with $g(x)=F(x,y)$ for all $x\in X$ (see Lemma 3.7, of \cite{hhm}, for instance).

As in the proof of Proposition \ref{proprao}, since $\mathfrak{t} = \mathfrak{c}$ we may fix an injection $h:\cc\to 2^\om$
such that for each pair $\alpha, \beta$ from $\cc$,
$\alpha \leq \beta$ if and only if $h(\alpha) \leq^{*} h(\beta)$.


%\pagebreak

%Another well-known consequence
%MA is the existence of a $\cc$-scale, i.e., $(s_\al\in \om^\om\;:\;\al<\cc)$
%which under eventual dominance is isomorphic to the well-order $(\cc,<)$.
%For convenience we may regard the $s_\al$ as elements of $2^\om$.

Now given any $f:\cc \times \cc\to \cc$ which pushes down, recursively
choose $x_\al\in 2^\om$ so that $x_\al=\pair(y_\al,z_\al,h(\alpha),t_\al)$
where
\begin{enumerate}
\item $t_\al$ is $\langle 0, x_{f(\alpha, \alpha)}\rangle$ if  $f(\al,\al) < \alpha$ and $\langle 1, 1\rangle$ otherwise;
\item for all $\be<\al$,
\begin{itemize}
\item if $f(\alpha, \beta) < \alpha$, then $F(x_\be,z_\al)= \langle 0, x_{f(\al,\be)} \rangle$;
\item if $f(\beta, \alpha) < \alpha$, then $F(x_\be,y_\al)= \langle 0, x_{f(\be,\al)} \rangle$;
\item if $f(\alpha, \beta) = \alpha$, then $F(x_{\beta},z_{\alpha}) = \langle 1,1 \rangle$;
\item if $f(\beta, \alpha) = \alpha$, then $F(x_{\beta},y_{\alpha}) = \langle 1, 1 \rangle$.
\end{itemize}
%we have that:
%$$F(x_\be,y_\al)= x_{f(\be,\al)} \rmand F(x_\be,z_\al)= x_{f(\al,\be)}.$$
\end{enumerate}
Let $\pi_{0}$ and $\pi_{1}$ be such that $x = \langle \pi_{0}(x), \pi_{1}(x)\rangle$ for all $x \in 2^{\omega}$. Using this we may define the Borel function $U$
by setting $U(x,x')$, where $x = \pair(y,z,s,t)$ and $y = (y',z',s',t')$ to be
%$U(\pair(y,z,s,t),\pair(y^\pr,z^\pr,s^\pr,t^\pr))$ to be
\begin{itemize}
\item $\pi_{1}(F(x,y'))$ if $s <^{*} s'$ and $\pi_{0}(F(x,y')) = 0$;
\item $\pi_{1}(F(x',z))$ if $s' <^{*} s$ and $\pi_{0}(F(x',z)) = 0$;
\item $x'$ if $s <^{*} s'$ and $\pi_{0}(F(x,y')) = 1$;
\item $x$ if $s <^{*} s'$ and $\pi_{0}(F(x',z)) = 1$;
\item $x$ if $x = x'$ and $\pi_{0}(F(x,x)) = 1$;
\item $t$ otherwise.
\end{itemize}

%\left\{
%\begin{array}{ll}
%F(x,y^\pr) & \mbox{ if } s<^*s^\pr \\
%F(x^\pr,z) & \mbox{ if } s^\pr<^*s  \\
%t          & \mbox{ otherwise }\\
%\end{array}\right.$$
One can now verify that $f(\al,\be)=\ga$ if and only if $U(x_\al,x_\be)=x_\ga$ for all $\alpha, \beta, \gamma < \mathfrak{c}$ by
considering the cases $\al<\be$, $\be<\al$, and $\al=\be$.

\qed

%\begin{remark}
%It is easy to modify the argument of the proposition to handle
%functions $f:\cc \times \cc\to \cc$ which weakly push down:
%$f(\al,\be)\leq\max(\al,\be)$ all $\al,\be$.
%\end{remark}


%\begin{remark}
The identity function satisfies the analogous notion of Sierpi\'nski universality for unary maps.
The corresponding result for model theoretic universality appear to be
more difficult.
%\end{remark}

%\pagebreak

\begin{prop}
Define $\pi:2^\om\to 2^\om$ by setting
$\pi(x)=y$ if and only if $\forall n \;y(n)=x(2n)$.  Then
$\pi$ is a model theoretically universal for all maps
$f:\cc\to\cc$.
\end{prop}

\proof
Any function $g \colon X \to X$ from a set $X$ to itself induces a partition $\{ Q(x) : x \in X\}$ of $X$, where
each $Q(x)$ is the smallest subset of $X$ closed under $g$-images and $g$-preimages with $x$ as a member. We will refer to the sets $Q(x)$
as $g$-\emph{components}. For each $x \in X$, the \emph{pre-image tree of} $x$ (according to $g$) is the tree of height at most
$\omega$ whose root is $x$, and for which the immediate successors of each node $y$ are the members of $g^{-1}[\{y\}]$. Let
$T_{g}(x)$ denote the set of nodes of this tree. A $g$-component $Q$ either contains a unique cycle of length $n$, for some positive $n \in \omega$, or it
contains none. In the former case, $Q$ consists of the union of the sets $T_{g}(x)$, for each member $x$ of the cycle, and we say that the component has
\emph{type} $n$. In the latter case, for each $x$ in $Q$, $Q = \bigcup \{ T_{g}(g^{i}(x)) : x \in \omega\}$, and we say that the component has type $\omega$.


Fix a function $f \colon \cc \to \cc$. We seek a function $h \colon \cc \to 2^\omega$ such that
$h(f(\alpha)) = \pi(h(\alpha)$ for all $\alpha \in \cc$. Since the $\pi$-preimage of each singleton from $2^{\omega}$ has size continuum, the analysis of the
previous paragraph shows that it suffices to prove that there are continuum many $\pi$-components of type $n$, for each positive $n \in \omega$, and continuum
many $\pi$-components of type $\omega$, as then the components of $f$ can be embedded into distinct $\pi$-components.

For each $x \in 2^{\omega}$, and all $i,n \in \omega$, $\pi^{n}(x)(i) = x(2^{n}(i))$. Given a positive $n \in \omega$, $x$ is then part of a cycle of length $n$
if $x(2^{n}i) = x(i)$ for all $i \in \omega$. There are continuum many such $x$, as the values $x(i)$ can be chosen freely for each odd $i \in \omega$. Since each
component of type $n$ contains exactly $n$ such $x$'s, there are continuum many $\pi$-components of type $n$.

On the other hand, one can build by recursion an increasing sequence of natural numbers $\langle p_{i} : i < \omega \rangle$ and a collection of sequences
$t_{\sigma} \in 2^{p_{|\sigma|}}$ for each $\sigma \in 2^{<\omega}$ such that for each pair $n,m \in\omega$ there exists an $i \in \omega$ such that for each pair
$\sigma, \sigma' \in 2^{i}$, if either $n \neq m$ or $\sigma \neq \sigma'$ then
there exists $j \in \omega$ such that $2^{n}j, 2^{m}j < p_{i}$ and $t_{\sigma}(2^{m}j) \neq t_{\sigma'}(2^{n}j)$. Then the sets $\bigcup\{ t_{y \restriction
p_{i}} : i < \omega\}$ ($y \in 2^{\omega}$) are members of distinct $\pi$-components of type $\omega$.
\qed

%For each $\alpha \in \cc$, let
%$Q(\alpha)$ be the smallest subset of $\cc$ containing $\alpha$ and closed
%under $f$-images and $f$-preimages. The sets $Q(\alpha)$ form a partition of
%$\cc$; we will call the members of the partition \emph{components}.

%Given any abstract map $f:\cc\to\cc$ partition the structure
%$(\cc,f)$ into components.  The component of any element of
%$\cc$ is the
%smallest subset closed under both images and pre-images of $f$.

%Suppose $Q\su \cc$ is a component of $f$.
%Then there are two possibilities.   $Q$ could contain
%an $N$-cycle.  A distinct sequence $C=\al_0,\ldots,\al_{N-1}$
%where $f(\al_i)=\al_{i+1}$ for $i<N-1$ and $f(\al_{N-1})=\al_0$.
%Then attached to
%each $\al_i$ would be the pre-images of $\al_i$ not in $C$
%and attached to each of these their preimages, and so on.
%In this way we could build a pairwise disjoint $\leq \cc$ splitting trees
%$T_i$ with root $\al_i$ and
%we might think of $f$ as mapping each child to its parent.
%The other type of component which $f$ might have is one
%on which $f$ has no cycles.  Taking any point $\al_0$,
%the sequence $\al_0,\al_1,\dots,$ where $\al_{i+1}=f(\al_i)$
%would all be distinct and together with $f$ form an
%isomorphic copy of $\om$ with the successor function.  As
%in the other case we then attach trees $T_i$ at each $\al_i$.
%We refer to this type of component as an $\om$-sequence.\

%In the case of $\pi$ the  trees will be $\cc$-splitting since
%$\pi$ $\cc$-to-one.  So for example, an $N$-cycle component of $f$
%could always be embedded into an $N$-cycle component of $\pi$
%and similarly for an $\om$-sequence component.

%Hence to prove that $\pi$ is model theoretically universal it suffices
%to show that for each $N$ that $\pi$ has continuum many $N$-cycles, and
%continuum many disjoint $\om$-sequence.  (Note that
%disjoint $\om$-sequences determine distinct components.)

%Given $x_0\in 2^\om$ define
%$x_{n+1}=\pi(x_n)$.  Note that for any $n\geq 0$
%$$\forall k\;\; x_n(k)=x_0(k2^n).$$

%Our first goal is to show that $\pi$ has continuum many
%$N$-cycles.  So fix $N\geq 1$.
%Call $s\in 2^{<\om}$
%which satisfy $s(k)=s(k2^N)$ for all $k$ with $k2^N<|s|$ good.
%If the $|s|=k2^N$, then
%we must extend $s$ by $s(k)$.  However,
%if $|s|=k2^n$, $n<N$ and $k$ is odd, then we may extend $s$ by
%either $0$ or $1$ and it will still be good.  So given
%any good $s$ and pair $n_1<n_2<N$, choose an odd $k$ such that
%$|s|<k2^{n_1}<k2^{n_2}$.  By taking one
%step at a time extend $s$ to a good $t\supset s$
%where $t(k2^{n_1})=0$ and
%$t(k2^{n_2})=1$.  If follows that for any $x\in 2^\om$ with
%$t\su x$ that $x_{n_1}(k)\neq x_{n_2}(k)$.  Hence there
%is a good $t$ guaranteeing that all good $x$ with $t\su x$
%are an $N$-cycle.

%By a similar argument it is easy to construct continuum many
%pairwise disjoint $\om$-sequences for $\pi$.
%\qed

%\pagebreak

%\begin{define}
Finally, we indicate another possible distinction between Sierpi\'nski universal functions and model theoretically universal ones.
Let us say that a function $f:\kappa\times\kappa\to\kappa$ is {\em Sierpi\'nski universal for regressive functions} if for every function
$g:\kappa\times\kappa\to\kappa$
such that $g(\alpha,\beta) < \max(\alpha,\beta)$ for all $\al,\be$ (other than
$\al=\be=0$) there exists $h:\kappa\to\kappa$
such that $f(h(\alpha),h(\beta)) = g(\alpha,\beta)$ for all $\alpha, \beta$ in
$\kappa$.
%\end{define}

\begin{prop}\label{weak}
If $\kappa$ is regular, then every $f \colon \kappa \times \kappa \to \kappa$ which is Sierpi\'nski universal for regressive functions
is Sierpi\'nski universal.
\end{prop}

\proof
Let  $f:\kappa\times\kappa\to\kappa$ be Sierpi\'nski universal for regressive functions and fix $g:\kappa\times\kappa\to\kappa$.
Let  $j:\kappa\to\kappa$ be an increasing function such that $g(\xi,\eta) < j(\alpha)$ for all $(\xi,\eta)\in (\alpha+1)^2$, and let $$g^*(\xi,\eta)=
\begin{cases}
 g(j^{-1}(\xi),j^{-1}(\eta)) & \text{if \ }\xi
 \text{ \ and \ } \eta \text{ \ are \  in \  the \  range  \ of \ } j \\
  0    & \text{otherwise}.
\end{cases}$$
Since $g^*(\alpha,\beta) $ is either 0 or equal to $ g(j^{-1}(\alpha),j^{-1}(\beta)) < \max(\alpha,\beta)$
 and $f$ is  weakly Sierpi\'nski universal there exists an $h:\kappa\to\kappa$ such that $f(h(\alpha),h(\beta)) = g^*(\alpha,\beta)$ for all
 $\alpha, \beta$ in $\kappa$.
Then $f(h(j(\alpha)),h(j(\beta))) = g^{*}(j(\alpha), j(\beta)) = g(\alpha,\beta)$ for all $\alpha, \beta$ in $\kappa$, so $h\circ j$ is the required embedding.
\qed

\begin{ques}
Is Proposition \ref{weak} is true for the analogous notion of model theoretically universal for regressive functions?
\end{ques}

In the proof of Proposition \ref{weak}, the given function $g$ was embedded into the regressive function $g^{*}$.
Note however that if $g:\kappa\times\kappa\to\kappa$ is such that
$g(\alpha,\beta) < \max(\alpha,\beta)$ for all $\al,\be$ (aside from $\al=\be=0$), then
no substructure of $(\ka,g)$ is isomorphic to the positive integers under
addition.  To see this, suppose toward a contradiction that
$\pi:\om\to\ka$ is one-to-one and
$\forall n,m,k>0$
$$ n+m=k \rmiff g(\pi(n),\pi(m))=\pi(k)$$
then
$$\pi(2n)=\pi(n+n)=g(\pi(n),\pi(n))<\pi(n)$$
and therefore $(\pi(2^n):n<\om)$ is an infinite descending sequence
of ordinals.

\section{Appendix}

We conclude this section with an argument, due to Justin Moore, which shows that under the Proper Forcing Axiom there are no functions with property R.\footnote{We thank Alan Dow for discussions clarifying this argument.} We begin by introducing some notation.

Given a function $\Phi \colon [\omega_{1}]^{2} \to \omega$, a finite set $F\subseteq \omega_1$ and $k\in \omega$, we let
$B_k(\Phi,F)$ denote the set $$\SetOf{\beta\in \omega_1}{(\forall \alpha \in F) \ \Phi(\{\alpha,\beta\})>k}.$$


\begin{lemma}\label{lowbound}
Suppose that $\Phi \colon [\omega_{1}]^{2} \to \omega$ is a function with Property R. Then for each $k\in \omega$ there exists an $\alpha < \omega_{1}$ such that
for each finite $F \subseteq \omega_{1}$
either $F \cap \alpha \neq \emptyset$ or
$B_k(\Phi,F)$ is uncountable.
\end{lemma}

\begin{proof}
Otherwise, there exist infinitely many pairwise disjoint $F$ for which
$B_k(\Phi, F)$ is countable. Then there exist $\beta \in \omega_1$ and an infinite pairwise disjoint family of finite sets $F$ for which $F\subseteq \beta$ and  $\beta\notin B_k(\Phi, F)$. This yields infinitely many $\xi\in\beta$ such that $\Phi(\{\beta,\xi\})\leq k$ contradicting that $\Phi$ satisfies Property~R.
\end{proof}
\qed

Applying Lemma \ref{lowbound}, we can find for any function $\Phi$ with Property R a minimal ordinal $\alpha(\Phi)$ with the property that for any
$k \in \omega$ and any finite $F \subseteq \omega_1$ either   $F \cap \alpha(\Phi)\neq \emptyset$  or $B_{k}(\Phi, F)$ is uncountable.

Given a function $\Phi \colon [\omega_{1}]^{2} \to \omega$ with Property~R let $\mathbb{P}(\Phi)$ be the partial order consisting of pairs $(A,M)$ such that:
\begin{itemize}
\item $A$ is a finite set of pairs from $\omega_1 \setminus \alpha(\Phi)$, and for all distinct $a, b \in A$, $a \subseteq \min(b)$ or $b \subseteq \min(a)$;
\item $M$ is a finite $\in$-chain of elementary submodels of $H(\aleph_2)$, each having $\Phi$ as a member.
\item For all $a \in A$, there is $\mathfrak{M}\in M$ such that $|\mathfrak{M}\cap a| = 1$.
\item For all $a \in A$ and $b\in A$ such that $a\subseteq \min(b)$, there is $\mathfrak{M}\in M$ such that $a\subseteq \mathfrak{M} $ and $b\cap \mathfrak{M} = \emptyset$.
\item For all distinct $a,b$ from $A$, $$\Phi(\{\min(a), \min(b)\}) < \Phi(\{\max(a), \max(b)\}).$$
%\item There is $\mathfrak{M}^*\in M$ such that $\mathfrak{M}^*\cap A = \emptyset$.
\end{itemize}
The ordering on $\mathbb{P}(\Phi)$ is : $(A,M) \leq (B, N)$ if $B \subseteq A$, $N \subseteq M$ and, for all $\mathfrak{M} \in N$ and all $a \in A$, if $|\mathfrak{M} \cap a| = 1$, then $a \in B$.

%Note that of $G$ is $\mathbb{P}(\Phi)$ generic and $A_G=\bigcup_{(A,M)\in G}A$ then any disjoint collection of increasing pairs from $A_G$ will witness the %failure of Property~R.

The partial order $\mathbb{P}(\Phi)$ adds an uncountable set of pairs from $\omega_{1}$ witnessing the failure of Property R for $\Phi$.





\begin{claim}
Given any $(A,M)\in \mathbb{P}(\Phi)$ and $\xi\in\omega_1$ there exists a condition $(A',M')\leq (A,M)$ such that $\left( \bigcup A'\right ) \setminus \xi \neq \emptyset$.
\end{claim}

\begin{proof}
By adding a model to the top of $M$ if necessary, we may assume that there is $\mathfrak{M}\in M$ such that $A\in \mathfrak{M}$ and
$\xi < \omega_{1} \cap \mathfrak{M}$.
Let $\gamma$ be any element of $\omega_{1}$ greater than $\omega_{1} \cap \mathfrak{M}$, and extend $M$ to $M'$ by adding an elementary submodel $\mathfrak{M}'$ on top
with $\gamma < \omega_{1} \cap \mathfrak{M}'$.
Let $k>\Phi(\{\alpha,\beta\})$ for all distinct $\alpha, \beta$ from $(\bigcup A) \cup \{\gamma\}$. Then $B_k(\Phi, (\bigcup A) \cup \{\gamma\})$ is uncountable since $((\bigcup A) \cup \{\gamma\}) \cap \alpha(\Phi) = \emptyset$.
%otherwise by the previous claim it would have to be the case that $\mathfrak{M}^{*} \cap A \neq \emptyset$.
Let $\delta\in B_k(\Phi, \bigcup A)\setminus \mathfrak{M}'$. Then $(A\cup\{\{\gamma, \delta\}\},M')\in \mathbb{P}(\Phi)$.
\end{proof}

\begin{claim}
$\mathbb{P}(\Phi)$ is proper.
\end{claim}
\begin{proof}
Let $(A,M)\in \mathbb{P}(\Phi)$ and $(A,M)\in \mathfrak{M}\prec H(\kappa)$ for some uncountable $\kappa$.
Since  $\mathfrak M\cap H(\aleph_2) \prec H(\aleph_2)$ it suffices to show that $(A,M\cup \{\mathfrak M\cap H(\aleph_2)\})$ is $ \mathbb{P}(\Phi)$-generic for $\mathfrak{M}$. To see this, let $D\in \mathfrak{M}$ be a dense subset of $\mathbb{P}(\Phi)$ and suppose that $(B,N) \in D$ is such that $(B,N)\leq (A,M\cup \{\mathfrak{M}\})$. Since there is no $a \in A$ with $|a \cap \mathfrak{M}| = 1$, by the definition of the order on $\mathbb{P}(\Phi)$ , there is also no $b \in B$ with $|b \cap \mathfrak{M}| = 1$. Let $\{b_1, \ldots, b_j\}$ enumerate $(\bigcup B)\setminus \mathfrak{M}$ in such a way that $\min(b_{i})$ increases with $i$, and for
each $i \in \{1,\ldots,j\}$, let $\beta_{2i+1} = \min(b_{i})$ and $\beta_{2i+2} = \max(b_{i})$.


Let $S$ be the set of increasing sequences of ordinals $\langle \gamma_{1},\ldots,\gamma_{2j}\rangle$ such that
\begin{enumerate}
\item $\gamma_{1}$ is greater than every member of $\bigcup (B \cap \mathfrak{M})$;
\item\label{samepattern} letting $\pi \colon \bigcup B \to (\bigcup (B \cap \mathfrak{M})) \cup \{\gamma_{1},\ldots,\gamma_{2j}\}$ be an order-preserving bijection, $\Phi(\{\alpha_{1}, \alpha_{2}\}) = \Phi(\{\pi(\alpha_{1}), \pi(\alpha_{2})\})$ for all $\alpha_{1} < \alpha_{2}$ from $\bigcup B$;
\item \label{g3}for some $N'$ containing $\mathfrak{M} \cap N$, $$((B \cap \mathfrak{M}) \cup \{\{\gamma_{2i+1},\gamma_{2i+2}\} : i \in j\}, N')$$ is an element of $D$.
\end{enumerate}
Notice that while the Condition~\ref{samepattern} mentions an object outside $\mathfrak M$, this object is finite and so the condition can be described by a first order formula in $\mathfrak M\cap H(\aleph_2)$.
Since the theory $H(\aleph_2)$ can be coded by a real in transitive models, the existence of $N'$ posited in
Condition~\ref{g3} can also be described in  $\mathfrak M\cap H(\aleph_2)$.

As a consequence, if  $T_{0}$ is defined to be the tree consisting of all initial segments of members of $S$,
then, since $T_{0} \in H(\aleph_{2})$, $T_{0} \in \mathfrak{M}$ and $T_{0}$ is an element of every model of $N$ containing $\mathfrak{M} \cap H(\aleph_{2})$. Since $\langle \beta_{1}, \ldots,\beta_{j} \rangle \in S$, and since each $\beta_{2i+1}$ is separated by elementary submodels in $N$ from $\beta_{2i+2}$, $T_{0}$ can be thinned (in $\mathfrak{M}$) to a tree $T_{1}$, still containing $\langle \beta_{1},\ldots,\beta_{j} \rangle$, such that every node of $T_{1}$ on an odd level (where the least level is the 1st level) has uncountably many immediate successors. Finally, still in $\mathfrak{M}$, thin $T_{1}$ to a tree $T$, still of height $j$, such that each node of $T$ on an even level has infinitely many immediate successors.

We wish to pick a sequence $\langle \gamma_{1},\ldots,\gamma_{2j}\rangle$ from $T$ such that, for some $N'$ containing $N$,
$(B \cup \{\{\gamma_{2i+1},\gamma_{2i+2}\} : i \in j\}, N')$ is a condition. We pick the $\gamma_{i}$'s recursively, picking any available ordinal
when $i$ is odd. When $i$ is even, we need to pick $\gamma_{i}$ so that, for each $b \in B \setminus \mathfrak{M}$
$\Phi(\{ \gamma_{i-1}, \min(b)\}) < \Phi(\{\gamma_{i}, \max(b)\})$. Since $B$ is finite, and we have infinitely many possibilities for $\gamma_{i}$, we can
meet this condition, using the finite-to-one property of $\Phi$.
\end{proof}




\begin{thebibliography}{99}

\bibitem{bell} Bell, Murray G.;
On the combinatorial principle $P({\cc})$.
Fund. Math. 114 (1981), no. 2, 149-157.

\bibitem{Blass} Blass, Andreas;
\newblock Combinatorial cardinal characteristics of the continuum.
\newblock Handbook of Set Theory, Foreman, Kanamori, eds.,
Springer, 2010

\bibitem{bbm}
Bing, R. H.; Bledsoe, W. W.; Mauldin, R. D.;
Sets generated by rectangles.
Pacific J. Math. 51 (1974), 27-36.

\bibitem{brendle}
Brendle, J.; Mutual generics and perfect free subsets.
Acta Math. Hungar. 82 (1999), no. 1-2, 143-161.

\bibitem{ck} Chang, C. C.; Keisler, H. J.;  Model theory. Third
edition. Studies in Logic and the Foundations of Mathematics, 73. North-Holland
Publishing Co., Amsterdam, 1990. xvi+650 pp. ISBN: 0-444-88054-2

\bibitem{davies} Davies, Roy O.; Representation of functions of two variables as
sums of rectangular functions. I. Fund. Math.  85  (1974), no. 2, 177--183.

\bibitem{hhm} Hjorth, Greg; Humphries, Leigh; Miller, Arnold;
Universal sets for pointsets properly on the $n$th level of the
projective hierarchy, Journal of Symbolic Logic 78 (1), 2013, 237--244

\bibitem{kechris} Kechris, Alexander S.; Classical descriptive set
theory. Graduate Texts in Mathematics, 156. Springer-Verlag,
New York, 1995. xviii+402 pp. ISBN: 0-387-94374-9

\bibitem{kunenthesis} Kunen, Kenneth;
Inaccessibility properties of cardinals. Ph.D. Thesis, Stanford University. 1968

\bibitem{kunen} Kunen, Kenneth; Set
Theory. An introduction to independence proofs. Reprint of the 1980 original.
Studies in Logic and the Foundations of Mathematics, 102. North-Holland
Publishing Co., Amsterdam, 1983. xvi+313 pp. ISBN: 0-444-86839-9

\bibitem{louv} Louveau, Alain;
A separation theorem for $\Sigma ^{1}_{1}$ sets.
Trans. Amer. Math. Soc. 260 (1980), no. 2, 363--378.

\bibitem{mansfield} Mansfield, Richard; The solution of one of Ulam's problems
concerning analytic rectangles. 1971 Axiomatic Set Theory (Proc. Sympos. Pure
Math., Vol. XIII, Part I, Univ. California, Los Angeles, Calif., 1967) pp.
241--245 Amer. Math. Soc., Providence, R.I.

\bibitem{mansfield2} Mansfield, Richard;
The solution to one of Ulam's problems concerning analytic sets. II.
Proc. Amer. Math. Soc. 26 1970 539--540.

\bibitem{MaSh} Malliaris, Maryanthe; Shelah, Saharon;
\newblock Cofinality spectrum theorems in model theory, set theory, and general topology.
\newblock preprint, 2012.

\bibitem{mauldin} Mauldin, R. Daniel (Editor), Mathematics from the Scottish
Cafe. Including selected papers presented at the Scottish Book Conference held
at North Texas State University, Denton, Tex., May 1979. Edited by  Birkhauser,
Boston, Mass., 1981. xiii+268 pp. (2 plates). ISBN: 3-7643-3045-7

\bibitem{MR1056364}
Mekler; Alan H.;
\newblock Universal structures in power {$\aleph_1$}.
\newblock {\em J. Symbolic Logic}, 55(2):466--477, 1990.

\bibitem{miller} Miller, Arnold W.; On the length of Borel hierarchies. Ann.
Math. Logic 16 (1979), no. 3, 233--267.

%\url{http://www.math.wisc.edu/~miller/res/hier.pdf}

\bibitem{millergensous}
Miller, Arnold W.;
Generic Souslin sets.
Pacific J. Math. 97 (1981), no. 1, 171--181.

%\url{http://www.math.wisc.edu/~miller/res/gensous.pdf}

\bibitem{millerrectang}
Miller, Arnold W.;
Measurable rectangle.
Real Anal. Exchange 19 (1993/94), no. 1, 194--202.

\bibitem{Millerbook}
Miller, Arnold W.;
\newblock Descriptive set theory and forcing.
\newblock Lecture Notes in Logic, 4. Springer-Verlag, Berlin, 1995



\bibitem{rado} Rado, R.;
Universal graphs and universal functions.
Acta Arith. 9 1964 331--340.

\bibitem{rao} Rao, B. V.; On discrete Borel spaces and projective sets.  Bull.
Amer. Math. Soc.  75  1969 614--617.


\bibitem{rao2} Rao, B. V.; Remarks on analytic sets. Fund. Math. 66 1969/1970
237--239.


%\bibitem{roslan} Ros{\l}anowski, Andrzej; Shelah, Saharon; The yellow cake.
%Proc. Amer. Math. Soc. 129 (2001), no. 1, 279--291.

\bibitem{shelah} Shelah, Saharon;
On universal graphs without instances of CH.
Ann. Pure Appl. Logic 26 (1984), no. 1, 75--87.

\bibitem{shelahsmall}
Shelah, S.;
A graph which embeds all small graphs on any large set of vertices.
Ann. Pure Appl. Logic 38 (1988), no. 2, 171--183.


\bibitem{shelahcorrection} Shelah, Saharon;
Universal graphs without instances of ${\rm CH}$: revisited.
Israel J. Math. 70 (1990), no. 1, 69--81.

\bibitem{shelahciel} Shelah, Saharon;
On Ciesielski's Problems. J Applied Analysis 3 (1997) 191--209

\bibitem{ShSt}
Shelah, Saharon; Stepr\={a}ns, Juris,
Extraspecial p-groups.
Ann. Pure Appl. Logic 34 (1987), no. 1, 87--97

\bibitem{sier} Sierpi\'nski, Waclaw; Sur une function universelle de deux
variables reelles, Bull Acad Sci Cracovie A(1936), 8--12.

\bibitem{sierch} Sierpi\'nski, Waclaw; Hypoth\`{e}se du continu. Monogr. mat. 4. Warszawa-Lwow: Subwencji Funduszu Kultur. Narodowej.
V, 192 S. , 1934.

\bibitem{solovay} Solovay, Robert M.;
A model of set-theory in which every set of reals is Lebesgue measurable.
Ann. of Math. (2) 92 1970, 1--56

\bibitem{todorcevic} Todorcevic, Stevo;
A universal sequence of continuous functions.
The Teaching of Mathematics 14 (2011) 2, 71–-76


\bibitem{weiss} Weiss, William; Versions of Martin's axiom. Handbook of
Set-Theoretic Topology, 827, North-Holland, Amsterdam, 1984.


\end{thebibliography}

\bigskip

\addresspaul

\bigskip

\addressarn

\bigskip

\addressjuris

\bigskip

\addressbill

\end{document}