7
$\begingroup$

I learned that Axiom of Choice states that the cartesian product of a family of non-empty sets $X_i$ indexed by a non-empty set $I$ is non-empty.

I think I can accept this axiom.

But I don’t understand how it guarantees that cartesian product can have more than one elements! It’s because ‘non-empty’ sounds to me ‘having at least one element’ here. So I think AC just implies that there exists at least one element in the product.

How do we insure that there exist all the possible functions from $I$ to $\cup X_i$?

Thanks in advance!

$\endgroup$
  • $\begingroup$ The set of all possible functions is precisely the cartesian product, so what you are asking is tautologically true, even if the cartesian product is empty! I think what you mean to ask is how to ensure that the cartesian product is big (infinite, or even uncountably infinite) in typical cases, when all that the axiom ensures is that it is nonempty. As an example, suppose $X$ is one of the sets $X_i$. Can you show that, if nonempty, the cartesian product has size at least $|X|$? $\endgroup$ – Andrés E. Caicedo Oct 9 at 17:49
  • $\begingroup$ @Andrés E. Caicedo I thought ‘the set of all possible functions is non-empty’ is needed because we don’t know such functions actually exist(if we know that they exist without anything else, we don’t need Axiom of Choice). My question is “Does ‘non-emptiness’ imply ‘the existence of all possible functions?’ I don’t know how to write my question clearly because my English isn’t good enough for that. I’m so sorry $\endgroup$ – anadad Oct 9 at 18:08
  • 1
    $\begingroup$ Again, the cartesian product is by definition the set of all possible functions. What is significant is that, in any typical situation, although the axiom only states the existence of one such function, this automatically implies, without further appeal to the axiom, the existence of many. $\endgroup$ – Andrés E. Caicedo Oct 9 at 18:54
  • $\begingroup$ Ahhh okay! Actually I was trying to prove that ,for $k \in I$, $π_k : Π_i X_i \to X_k$ is surjective. So I wanted to show, for each $a \in X_k$, there exists a function $f_a : I \to \cup X_i$ such that $f_a(i)=a$ if i=k, $f_a(i) \in X_i$ otherwise. And I was wondering if the fact that the cartesian product is non-empty guarantees the existence of f_a. And thank you for the help! Now I can write f_a exists in my note. $\endgroup$ – anadad Oct 9 at 19:21
  • 1
    $\begingroup$ Yes, you can ensure that such a function $f_a$ exists: Once you have a function $f$ in the Cartesian product, you can use it to define a function $f_a$ as you want: Simply change the value that $f$ assigns to $i$ to the value that you want it to have ($a$). That is, you can take $f_a=(f\smallsetminus\{(i,f(i))\})\cup\{(i,a)\}$. This is precisely what Chris was suggesting (in a more general way) to do in his answer. $\endgroup$ – Andrés E. Caicedo Oct 9 at 19:29
5
$\begingroup$

The set of choice functions of domain $\{X_i|i\in I\}$ satisfying $f(X_i)\in X_i$ for all $i\in I$ has cardinality $\prod_i|X_i|=|⨉_iX_i|$, because this set of functions has an obvious bijection with the Cartesian product $⨉_iX_i$, namely by pairing such a function $f$ with the ordered tuple with $i$th element $f(X_i)$. The axiom of choice is usually formulated as the claim that this set of choice functions is nonempty, but what you've read is that it can be equivalently stated as the claim that the equally large Cartesian product (itself a set of ordered tuples) is nonempty. Well, of course these statements are equivalent, as the sets are equinumerous.

We'd need further information to ensure there are multiple choice functions, because if each $X_i$ is a singleton there won't be. But our switch to focusing on Cartesian products doesn't cause any tuples or functions to "go missing".

When you talk about functions from $I$ to $\cup X_i$, you presumably mean the ones satisfying $f(i)\in X_i$ for all $i\in I$. As I noted above, the "existing" functions are the ones whose associated tuples "exist". How many of these there are depend on the model of ZF. (For example, a model of $ZF\neg C$ implies the existence of $X_i$ for which zero of either exist.)

$\endgroup$
  • $\begingroup$ Oh..! What I was curious about was if I can assume that there exists a choice function $C:P(\cup X_i) \to \cup X_i$ such that $C(X_i)=x_i$. Because, in my textbook, it just says that every set has a choice function. (I’m not good at English so I don’t know how to interpret ‘a choice function’. So I’m confusing because I don’t know whether it means ‘at least one’ or ‘all possible choice functions from the collection of all non-empty subsets into the set’ $\endgroup$ – anadad Oct 9 at 17:51
  • $\begingroup$ @anadad A choice function on $S$ is a function $f$ of domain $S\setminus\{\emptyset\}$ satisfying $f(x)\in x$ for all $x\in\operatorname{dom}f$. Your textbook was either asserting the axiom of choice or explaining what it asserts; I'd need to see the exact words to know which. But yes, "a" means "at least one" in this case (or just about any "exists a" statement in mathematics; if uniqueness is intended, it's usually mentioned). $\endgroup$ – J.G. Oct 9 at 18:20
  • $\begingroup$ @anadad When you write "there exists a choice function such that $C(X_i)=x_i$" (presumably, "for all $i\in I$"), this really makes no sense, because you haven't told us what $x_i$ is. If you have access to some means of specifying an element $x_i$ for each $i\in I$, then you actually have access to a choice function. $\endgroup$ – Andrés E. Caicedo Oct 9 at 18:57
  • $\begingroup$ @anadad There is a subtlety here, since set theory deals with consistency results, and with diverse models of the set-theoretic axioms. It may very well be that we are studying a model $M_1$ of set theory. In that model we know that there are choice functions for some family of sets. It may be that in some other model $M_2$ there is some specific choice function $f$ for that same family, and that that specific function is not a member of $M_1$. That happens. It doesn't mean that it is not true in $M_1$ that we do not have the set of all possible choice functions for that family. (Cont.) $\endgroup$ – Andrés E. Caicedo Oct 9 at 19:01
  • 1
    $\begingroup$ I thank you several more times. $\endgroup$ – Sebastiano Oct 9 at 21:47
5
$\begingroup$

It sounds like you want to prove the following statement:

  • Given a partial function $f:I\to\cup X_i$, there exists a (total) function $F:I\to\cup X_i$ that extends $f$.

Can you see how to define such an $F$, given the existence of some function $C:I\to\cup X_i$?

$\endgroup$
  • $\begingroup$ Sorry, I don’t know what partial function is! I want to prove that for each $x_i \in X_i$, there exists a function $f:I \to \cup X_i$ defined by $f(i)=x_i$. $\endgroup$ – anadad Oct 9 at 17:36
  • $\begingroup$ @anadad Do you mean 'for each set of $x_i\in X_i$'? Right now your statement is a little light on the formalization. and if you attempt to properly formalize it you may discover that it trivializes... $\endgroup$ – Steven Stadnicki Oct 9 at 17:41
  • $\begingroup$ @anadad It's just a function of a subset of $I$. See en.wikipedia.org/wiki/Partial_function $\endgroup$ – Chris Culter Oct 9 at 17:51
  • $\begingroup$ Umm.. I don’t understand why $C: I \to \cup X_i$ is choice function. I learned that a choice function of A set S is a function from a collection of all non-empty subset of S into S itself. But $I$ doesn’t seem to the collection of all non-empty subset of $\cup X_i$. Sorry but could you explain it more? $\endgroup$ – anadad Oct 9 at 18:01
  • $\begingroup$ Okay, $C$ isn't a choice function in that sense. Edited. The point is, you have one such function, as described in your question, and you want more of them. $\endgroup$ – Chris Culter Oct 9 at 18:16

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.