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$ Commented 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$ Commented 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$ Commented Apr 19, 2010 at 20:40
  • $\begingroup$ I was just saying that is what a universal choice operator "usually" means. =) $\endgroup$ Commented Apr 19, 2010 at 21:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .