3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I added the axiom-of-choice and set-theory tags. $\endgroup$ Apr 19, 2010 at 20:19

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Although an epsilon-term would do the trick as a universal choice operator. $\endgroup$ Apr 19, 2010 at 20:33
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 19, 2010 at 20:40
  • $\begingroup$ I was just saying that is what a universal choice operator "usually" means. =) $\endgroup$ Apr 19, 2010 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.