# What is a universal function?

This question stems from Dick Lipton's recent blog post on the Axiom of Choice. I asked there but got no takers. I promise I'm not an inept Googler, but I couldn't find a satisfactory answer. I suspect universal in this context means computable by a universal Turing machine, or something close to that, but I'd like to know for sure.

-
I added the axiom-of-choice and set-theory tags. –  Joel David Hamkins Apr 19 '10 at 20:19

In that argument, he just means that g is defined on all the two-element subsets that may arise in the argument, that is, for a given family F of four-element sets, g(A) should be defined on any two-element set A that is a subset of a four-element set in F.

The reason he needs to assume that is that he cannot allow that we need to choose the choice function g itself to be used with each separate A. There are many choice functions that work for families of 2-element sets, and different choices of g will give rise to different functions on the families of four-element sets. The way the argument works is that you make one choice of the function g that works on all the two element sets that arise, and then you define the choice function on the given family of four-element sets by the clever construction in the article.

In particular, he is not using some technical meaning of universal.

-
Although an epsilon-term would do the trick as a universal choice operator. –  Harry Gindi Apr 19 '10 at 20:33
Harry, in that terminology, what the argument the questioner links to concerns is a proof that if you have an epsilon choice function defined on all pairs, then you can define from it (without any choice) a choice function that works on all families of four-element sets. (But interestingly, not families of three-element sets!) But actually, there is no need in the argument for the proper class degree of universality provided by the epsilon term idea, so it is a stronger result not to use this. –  Joel David Hamkins Apr 19 '10 at 20:40
I was just saying that is what a universal choice operator "usually" means. =) –  Harry Gindi Apr 19 '10 at 21:00