Universal functions
Volume 227 / 2014
Abstract
A function of two variables $F(x,y)$ is universal if for every function $G(x,y)$ there exist functions $h(x)$ and $k(y)$ such that $$G(x,y)=F(h(x),k(y))$$ for all $x,y$. Sierpiński 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.
