3
$\begingroup$

First: My apologies for the probably imprecise way I am phrasing this question, to the point where I expect I will be told it is actually meaningless as presented here.

The axiom of choice can be restated as 'the Cartesian product of a collection of non-empty sets is non-empty'.

But '... non-empty' seems to only ensure that at least one element from each set is selected in the process, while usually, when talking about Cartesian products, we seem to expect that all elements are eventually selected in the process, e.g. the Cartesian product of sets A, B is the set of all ordered pairs (a, b) s.t. a is in A, b is in B.

My question is then: is there a "stronger" form of the axiom of choice, that ensures that each element in each set of a family of sets is selected? And if that would be in fact a stronger requirement: is there any mathematical use or motivation for such a stronger version of the axiom?

In a probably related question to my own, I found the following reply:

But what about Cartesian product of three sets? ... What objects do you have when you take the product of infinitely many sets? ... it turns out that the Cartesian product of sets is actually the set of choice functions from them. The axiom of choice assures that every family of non-empty sets has a choice function, and therefore the Cartesian product of any family of non-empty sets is non-empty

If I understand it correctly, in order to even ask a meaningful question, I need to reformulate as follows:

The axiom of choice assures that every family of non-empty sets has a choice function. Is there a (non-paradoxical) way to speak about a set of all possible choice functions, given any family of non-empty sets? If so, would that be a stronger version of the axiom of choice? If so, would there be any use for it?

$\endgroup$
  • $\begingroup$ The problem is, that your analysis is external to set theory. The axioms of ZFC aren't aware that they are possibly "missing" choice functions. $\endgroup$ – James Feb 9 '15 at 19:48
  • $\begingroup$ The set of all possible choice functions IS the cartesian product. If you want to build up new choice functions with additional properties, you can use more than once the axiom of choice. $\endgroup$ – Crostul Feb 9 '15 at 19:51
  • $\begingroup$ @James Does that mean that my vague idea of a stronger form of the axiom of choice ("... all possible choice functions") cannot even be formulated to be added as an axiom for ZF, instead of the "regular" axiom of choice? $\endgroup$ – Bert Zangle Feb 9 '15 at 19:53
  • $\begingroup$ Well, by definition, "all possible choice functions" are possible in ZFC. In any event, choice lets you assert lots more elements in the cartesian product. For example, If $T$ is a set of non-empty sets, and $S\subseteq T$, then any choice function on $S$ can be extended to a choice function on $T$. $\endgroup$ – Thomas Andrews Feb 9 '15 at 19:56
  • $\begingroup$ @Crostul I think I understand. I use the axiom of choice again to find a choice function demanding that it is different from the previous one I found through the axiom. Is that correct? $\endgroup$ – Bert Zangle Feb 9 '15 at 19:57
2
$\begingroup$

You want to ask about the following formulation, I'm guessing:

For every family of non-empty sets, $X$, and for every $Y\in X$ and $y\in Y$, there is a choice function from $X$, such that $F(Y)=y$.

I claim that this is in fact equivalent to the axiom of choice. It's clear why the axiom of choice follows from this.

In the other direction, fix $f$ to be a choice function on $X$, and pick some $y\in Y$, for some $Y\in X$. Now define $f_y=(f\setminus\{(Y,f(y))\})\cup\{(Y,y)\}$. It is not hard to verify that $f_y$ is also a choice function on $X$, and $f_y(Y)=y$.

In any case, the set of all choice functions of $X$ is denoted often by $\prod X$, or $\prod_{Y\in X}Y$. We can talk about this set without the axiom of choice as well. The axiom of choice guarantees that it is non-empty, and we can prove from the axiom of choice that not only this set is not empty, it is in fact very very big in most cases.

$\endgroup$
  • $\begingroup$ Thank you very much. It is now becoming a lot clearer to me what I am actually asking. I follow the initial paragraphs, but am not sure about the last one: I can see the equivalence of AC and "For every family of non-empty sets, X, and for every Y∈X and y∈Y, there is a choice function from X, such that F(Y)=y", but my intuition fails to see how we can define the set of all such functions without running into similar problems like those that require the axiom in the first place. $\endgroup$ – Bert Zangle Feb 9 '15 at 20:25
  • $\begingroup$ It's easy, $X$ is a set, so $\bigcup X$ is a set; a choice function is a subset of $X\times(\bigcup X)$ which satisfies certain properties which we can express in the language of set theory. Therefore $\prod X$ is a subset of $\mathcal P(X\times(\bigcup X))$ defined as all those subsets which satisfy the property of being a "choice function for $X$". $\endgroup$ – Asaf Karagila Feb 9 '15 at 20:28
  • $\begingroup$ Thanks again. I finally understood the difference between the question about the axiom and the one about the set of all choice functions. The former allows us to make certain assertions about the latter, given some X. $\endgroup$ – Bert Zangle Feb 9 '15 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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