# Set Theory: Equivalency of Axiom of Choice and Choice Function

This is the first part of the first half of the a proof in the Axiom of Choice. The proof that the Axiom of Choice is equivalent to the choice function. REsources: Keith Devlin's Joy of Sets: pg. 58. F.R. Drake and Singh Intermediate Set Theory: pg. 110).

I am confused on proving disjointness and will ask further questions of proof once I get this first part v. clear for myself.

AC1: Let $\mathcal F$ be a family of pairwise disjoint, non-empty sets. Then there is a set $\mathcal M$ that consists of precised one element from each member of $\mathcal F$

AC2: For every family $\mathcal F$ of non-empty sets, there is a choice function $\mathcal f$. (I.e. $\mathcal f(X)$ is a member of X, for each X in $\mathcal F$.

Disjointness: Two sets are disjoin if Q $\cap$ R = $\emptyset$. Meaning that they have zero elements in common. These sets do not overlap.

Show: AC1 $\leftrightarrow$ AC2

(1) ($\rightarrow$) Let $\mathcal F$ be a set of nonempty sets.

(2)For each X $\in$ $\mathcal F$, let $X^*$ = (X $\times$ {X}) = {(x, X) | x $\in$ X})

(3) Show Disjointness.

An outline of how book proves disjointness:

(a) if u = {(X $\times$ {X}) | x $\in$ X} then u is of the form $\lt z, t \gt$ where z = X and t=x, i.e. x $\in$ X.

(b) then if u $\in$ ({X} $\times$ x) $\cap$ ({Y} $\times$ Y) $\rightarrow$ u = $\lt z, t \gt$ with z = X and z=Y, i.e. X=Y. Which means ({X} $\times$ x) = ({Y} $\times$ y).

Questions: (1) Apparently we cannot prove disjointness in $\mathcal F$ but must prove in a different set. If so, why is that?

(2) why is the case that if u $\in$ ({X} $\times$ X) $\cap$ ({Y} $\times$ Y) then z =X and z=Y? I am not following that step at all.

(3) why does the axiom of choice have to do with ordered pairs? Why are we setting X $\in$ $\mathcal F$, let $X^*$ = (X $\times$ {X})?

Thank you!

• You are not assuming that the family $\mathcal{F}$ you get in AC2 is disjoint; so you cannot "prove" that it is a disjoint family because it doesn't have to be! But since AC1 requires your family to be disjoint in order to be able to get a conclusion, what you do is create a different family, not exactly equal to $\mathcal{F}$, to which you can apply AC1, but "close enough" that it will allow you to reach conclusions about $\mathcal{F}$ itself. (2) Yes, they messed up; it should be $z=x$ and $t=X$ with $x\in X$. (cont) Oct 27, 2017 at 19:29
• (3): Here's what's happening: AC1 is about families of disjoint sets. AC2 is about arbitrary families that need not be disjoint. So, if you are given an arbitrary family that need not be disjoint, how to do get to apply AC1? Answer: you just "paint" each set a different color, so that they are now disjoint. So, if your sets were $\{1,2\}$ and $\{2,3\}$, not disjoint, now they are $\{\text{red }1, \text{red 2}\}$ and $\{\text{blue }2,\text{blue }3\}$, and now they are disjoint. An easy way to "paint" the sets different colors is to take direct products with singletons (cont) Oct 27, 2017 at 19:31
• (cont) since an element of $X\times\{1\}$ can never be equal to an element of $Y\times\{2\}$, no matter what $X$ and $Y$ are. And the simplest singleton you can use to "paint" the set $X$ is the singleton $\{X\}$. So you do that to the elements of $\mathcal{F}$ to make sure they are all painted "different colors", so that they are now disjoint, so that now you can apply AC1 to the new "painted" family. Oct 27, 2017 at 19:32
• Do my eyes deceive me? Is @Arturo answering something on MSE? Oct 28, 2017 at 13:21
• @AndreasBlass: True; but perhaps emphasising the cleverness to someone who is having trouble grasping the point of it all in the first place might confuse more than enlight. Oct 28, 2017 at 20:16

The point is that we assume one form of $\sf AC$, and prove another. The form $\sf AC_1$ is a statement only applied to families of pairwise disjoint families, but $\sf AC_2$ is about any family of non-empty sets.

So we start with an arbitrary family of non-empty sets, and now we want to appeal to $\sf AC_1$, so we need to find a family of pairwise disjoint sets.

Given just two sets $A$ and $B$, the simplest way of making them pairwise disjoint is to replace them by $\{0\}\times A$ and $\{1\}\times B$. Why are these disjoint? Because the elements of $\{0\}\times A$ are ordered pairs of the form $\langle 0,a\rangle$; and similarly the elements of $\{1\}\times B$ are ordered pairs of the form $\langle 1,b\rangle$.

By the properties of ordered pairs, it is impossible that $\langle 0,a\rangle=\langle 1,b\rangle$, since $0\neq 1$.

The idea now is similar. We replace each $X$ by $\{X\}\times X$. So now if we have any $X,Y$ in the original family $\cal F$, then $(\{X\}\times X)\cap(\{Y\}\times Y)$ is not empty if and only if $X=Y$ by the same argument showing that $\{0\}\times A$ is disjoint from $\{1\}\times B$.

So we can apply $\sf AC_1$ to $\cal F^*$, and obtain a set which happens to be a function.

So to your question, the axiom of choice itself has nothing to do with ordered pairs. They are just a very useful way of making a family of sets into a family of pairwise disjoint sets, and by planning well, we can also obtain the choice function that we are looking for from $\cal F$ with minimal effort.