I am reading a book on set theory and I got stuck on a simple step of a proof involving an equivalence of the axiom of choice.

Axiom of Choice (1) For every set $a\neq \emptyset$ there exists a function $f:\mathcal{P}\left (a\right )\setminus \left \{\emptyset\right \}\to a$ such that $f\left (b\right )\in b$ for every $b\subseteq a$, $b\neq \emptyset$

Axiom of Choice (2) Let $\left \{a_i\right \}_{i\in I}$ be a non-empty family of pairwise disjoint non-empty sets (i.e. $I\neq \emptyset$ and $a_i\cap a_j=\emptyset$ if $i\neq j$). Then there exists a set $d$ such that $d\cap a_i$ is a unit set for every $i\in I$.

I could understand the proof $\left (2\right )\Rightarrow \left (1\right )$, but I cannot understand the converse.

The proof starts by supposing that $\left (1\right )$ is true. We let $\left \{a_i\right \}_{i\in I}$ be a non-empty family of pairwise disjoint non-empty sets and define $a=\bigcup_{i\in I}a_i\neq \emptyset$. Therefore there exists a function $f:\mathcal{P}\left (a\right )\setminus \left \{\emptyset\right \}\to a$ be a function such that $f\left (b\right )\in b$ for every $b\in \mathcal{P}\left (a\right )\setminus \left \{\emptyset\right \}$. If $d$ is the image of $f$, then (the book says) we have $d\cap a_i=\left \{f\left (a_i\right )\right \}$. My question is: Why? It is obvious that one of the inclusions holds, but what about $\subseteq$?

  • $\begingroup$ Restrict $f$ to $\{a_i\} \subset \mathcal{P}(a)$. $\endgroup$ – Zach Teitler Oct 14 '17 at 15:36
  • $\begingroup$ @ZachTeitler: Eh? You don't need to use choice to choose from singletons. $\endgroup$ – Asaf Karagila Oct 14 '17 at 15:41
  • $\begingroup$ That would be a restriction to a unit subset of the domain of $f$, the only thing I should do is applying $f$ to $a_i$ and then I obtain that $f\left (a_i\right )\in d\cap a_i$ which gives us the trivial inclusion. What about the other one? $\endgroup$ – solomeo paredes Oct 14 '17 at 15:43
  • $\begingroup$ @AsafKaragila $a_i$ is not a singleton. Restrict $f$ to the collection $\{a_i\}_{i \in I}$. Version (1) provides a choice for every subset of $a$; we only care about the subsets $a_i$ for $i \in I$. $\endgroup$ – Zach Teitler Oct 14 '17 at 15:46
  • 1
    $\begingroup$ @solomeoparedes Perhaps they defined $d$ in that way after restricting $f$ from all of $\mathcal{P}(a)$ to the subcollection $\{a_i\}_{i \in I}$? (Which by the way, some people would sometimes denote $\{a_i\}$, leaving the indexing $i \in I$ implicit, especially in certain contexts like writing $(a_n)$ for a sequence, or when they are typing on their phones.) $\endgroup$ – Zach Teitler Oct 14 '17 at 15:52

Recall that $a=\bigcup_{i\in I}a_i$ is trivially a superset of each of the $a_i$'s. Therefore each $a_i$ is an element of $\mathcal P(a)$.

By assumption, no $a_i$ is empty, so $a_i$ is in the domain of the choice function. Now take $\{f(a_i)\mid i\in I\}$ to be $d$, and by the fact each $a_i$ is disjoint we get that $d\cap a_i$ is a singleton for all $i\in I$.

  • $\begingroup$ So, as I said on a previous comment: Should I assume that the book has an errata? Because the book defined $d$ as the whole image of $f$, not just the image of the $a_i$. $\endgroup$ – solomeo paredes Oct 14 '17 at 15:51
  • 1
    $\begingroup$ Always assume there is an errata, and if you tried and checked, and there is an obvious mistake, you can assume it's the obvious mistake. $\endgroup$ – Asaf Karagila Oct 14 '17 at 16:01

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.