Can someone please clear my doubts regarding a result concerning the axiom of choice:

Prove that (i) implies (ii) where:

(i) For every nonempty set whose elements are non empty sets there exists a choice function.

(ii) If $\{a_i\}$ is a family of nonempty sets indexed by a nonempty set $I$, then there exists a family $\{x_i\}$ with $i \in I$ such that $x_i \in a_i$ for each $i \in I$.

Here is the proof which is in my book: Let $A$ be a collection of disjoint sets. We have $A \subset \mathcal{P}(\cup_{i \in I}a_i)$. ($\mathcal{P}$ is the power set). By (i) there exists a choice function $f$ on $\mathcal{P}(\cup_{i \in I}a_i)$. Let $b$ be the image of $A$. Pick an element $a \in A, f(a) \in a \cap b$ since $f(a) \in a$. Let $y \in b$ where $y \neq f(a)$ thus we have $y = f(a')$ where $a'\neq a$, and thus $y \in a'$. Since $a$ and $a'$ are disjoint $y \notin a$. Thus the only element of $b \cap a$ is $f(a)$.

My doubts are:

  • Why do we need to prove this? Won't the choice function $f$ give us the family ${f(i)}$ anyway.

  • How is the existence of $A$ guaranteed?

  • The choice function $f$ has what domain and co-domain? If its co-domain is $\mathcal{P}(\cup_{i\in I} a_i)$ then how is that set indexed? Or is the indexing set $\mathcal{P}(\cup_{i\in I} a_i)$?

  • How does $b \cap a$ being $f(a)$ guarantee that (ii) holds.

Thanks a lot.

  • $\begingroup$ The "proof" is completely opaque to me. For one thing there seems to be no construction of $\{x_i\}$. $\endgroup$ – Marc van Leeuwen Sep 18 '12 at 14:09
  • $\begingroup$ I don't understand the proof properly myself. I will welcome an alternate proof. (I think b is the family $\{x_i\}$) $\endgroup$ – Shahab Sep 18 '12 at 14:14
  • $\begingroup$ What is a choice function in the setup of (i) anyway? I presume that if $S$ is a set such that $S\ne\emptyset$ and $\emptyset\notin S$ then a choice function is a function $f\colon S\to \bigcup S$ such that $f(x)\in x$ holds for all $x\in S$. This has nothing to do with "collection of disjoint sets"; that's another formulation pf AC: If $S$ is a set of pariwise disjoint nonempty sets then there exists a set $C$ such that for each $x\in S$ the set $x\cap C$ is a singleton. $\endgroup$ – Hagen von Eitzen Sep 18 '12 at 14:34
  • $\begingroup$ @Hagen von Eitzen: In the setup of (i) the choice function is precisely what you said, or as I understand if X is a nonempty set with nonempty elements the choice function is a member of the cartesian product (of those elements). Essentially my question 3 is whether $S=\mathcal{P}(\cup a_i)$. $\endgroup$ – Shahab Sep 18 '12 at 14:40
  • $\begingroup$ $S=\mathcal P(\ldots)$ makes no sense as then $\emptyset\in S$. $\endgroup$ – Hagen von Eitzen Sep 18 '12 at 14:42

Let $\{a_i\}_{i\in I}$ be a family of sets, indexed by the nonempty set $I$. Then by the Axiom Schema of Replacement, $S:=\{a_i\mid i\in I\}$ is a set. By assumption and $I\ne \emptyset$, the set $S$ is a nonempyty set of nonempty sets. By (i) there exists a choice function, i.e. a function $f\colon S\to \bigcup S$ such that $f(x)\in x$ for all $x \in S$. For $i\in I$ let $x_i=f(a_i)$. Then $\{x_i\}_{i\in I}$ is a family with the required properties.


The statement says, essentially, that if you can choose then you can choose in a somewhat one-to-one fashion.

The assertion (ii) seems a bit weird for me, perhaps you wish to include the assumption that the family is a family of pairwise disjoint sets? The proof seems to assume that...

About the proof, you assume that $A$ is given to you. Note that every set $A$ is a subset of $\mathcal P(\bigcup A)$, this is not hard to check. Using the assumption that every collection of non-empty sets admits a choice function we simply use a choice function on $\mathcal P(\bigcup A)\setminus\{\varnothing\}$, and by the assumption that $A$ is a collection of pairwise disjoint sets we have that $\{f(a_i)\}$ is our beloved family of singletons.


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.