Graph explorer

Universal Functions

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 revi