Universal Functions
Paul B. Larson
Arnold W. Miller
Juris Steprans
William A.R. Weiss
Abstract
A function of two variables F(x,y)is universal iff for every other
function G(x,y) there exists functions h(x) and k(y) with
G(x,y) = F(h(x),k(y))
Sierpinski 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. We show that it
is consistent that for each countable ordinal alpha>2 there is a
universal function of class alpha but none of smaller class.
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 unary h,k,j such that
G(x,y,z) = F(h(x),k(y),j(z))
is equivalent to the existence of a 2-ary universal F.
However the existence of an F such that for every G there are
h,k,j such that
G(x,y,z) = F(h(x,y),k(x,z),j(y,z))
follows from a 2-ary universal F but is strictly weaker.
Results obtained Mar-June 2009, Nov 2010.
Last revised May 2014
LaTex2e: 28 pages
Latest version at: www.math.wisc.edu/~miller