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!
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.