In previous post Is this Theorem equivalent to Axiom of Choice?, I asked whether it is possible to prove (the Theorem $\implies$ Axiom of Choice). I received a proof in Noah's answer. I have a question regarding his proof, but he seems to be busy and unable to respond to my doubts. As a result, I post a new thread here.
My questions:
For $S_a=\{A,B,C\}\cup \{(x,a)\}$ and $S_b=\{A,B,D\}\cup \{(y,b)\}$, but $(x,a)=D$ and $(y,b)=C$. Thus $S_a = S_b$, while $a \neq b$. How can "$S_a\not=S_b$ whenever $a\not=b$." as Noah said?
Please explain why Noah "Fix some $x$ such that $\langle x, a\rangle\not\in\bigcup\mathcal{F}$ for any $a\in\bigcup\mathcal{F}$". I think it should be $\langle x, a\rangle\not\in\mathcal{F}$ for any $a\in\bigcup\mathcal{F}$ so that $\langle x, a\rangle$ is not equal to any $f'\in \mathcal{F}$ and therefore $\langle x, a\rangle$ is a distinct indicator for $S_a$.
I also present two other proofs at the end. Please have a look at them and check whether they contain any error!
Thank you so much!
Axiom of Choice: Let $\mathcal{F}$ is a collection of non-empty disjoint sets. Then there exists a choice function $f:\mathcal{F} \to \bigcup \mathcal{F}$ such that $f(A) \in A$ for all $A \in \mathcal{F}$.
The Theorem: For any set $\mathcal{F}$, there exists a function $g:\bigcup \mathcal{F} \to \mathcal{F}$ such that $a \in g(a)$ for all $a \in \bigcup \mathcal{F}$.
Noah's verbatim answer:
Yes, the principle you've written is equivalent to AC.
Suppose I have a family $\mathcal{F}$ of nonempty disjoint sets for which I want to construct a choice function. Fix some $x$ such that $\langle x, a\rangle\not\in\bigcup\mathcal{F}$ for any $a\in\bigcup\mathcal{F}$. For $a\in\bigcup\mathcal{F}$, let $S_a=\{f\in\mathcal{F}: a\in f\}\cup\{\langle x, a\rangle\}$. Note that the second term here means $S_a\not=S_b$ whenever $a\not=b$.
Now consider the set $X=\bigcup_{a\in \bigcup\mathcal{F}}S_a$, and apply your principle to it to get a map $g$ sending each element of $X$ to some $S_a$ containing it. We now argue:
Each $f\in\mathcal{F}$ is in $X$.
For each $f\in\mathcal{F}$ there is exactly one $a$ such that $g(f)=S_a$. This is just the distinctness of the $S_a$s, which we brought about artificially above.
Let $h(f)$ denote that unique $a$. Then $h$ is a choice function for $\mathcal{F}$.
My first proof:
Let $W=\{\{\mathcal{F} \times A,a\} \mid a \in A \in \mathcal{F}\}$.
- $\mathcal{F} \times A \neq b$ for all $A \in \mathcal{F}$ and $b\in \bigcup \mathcal{F}$.
Assume that $\mathcal{F} \times A = b$ where $b \in B \in \mathcal{F}$, and that $a \in A$. Then $b \in B \in \{B\} \in \{\{B\},\{B,a\}\}=(B,a)\in \mathcal{F} \times A=b$. This contradicts to Axiom of Regularity.
- We generate function $f$ as follows:
Apply this Theorem, there exists a function $g:\bigcup W \to W$ such that $a \in g(a) \in W$.
$f:\mathcal{F} \to \bigcup \mathcal{F}$ such that $f(A)=g(\mathcal{F} \times A) \setminus \{\mathcal{F} \times A\}$ for all $A \in \mathcal{F}$. $$\tag*{$\blacksquare$}$$
My second proof:
Let $R(x)=\{A \in \mathcal{F} \mid x \in A\} \cup \{\mathcal{F} \times \{x\}\}$ and $W=\{R(x) \mid\ x \in \bigcup \mathcal{F}\}$.
- $\mathcal{F} \times \{x\} \neq A$ for all $A \in \mathcal{F}$ and $x \in \bigcup \mathcal{F}$.
Assume that $\mathcal{F} \times \{x\} = A$ where $A \in \mathcal{F}$ and $x \in \bigcup \mathcal{F}$. Then $A \in \{A\} \in (A,x) \in \mathcal{F} \times \{x\}=A$. This contradicts to Axiom of Regularity.
Thus $\mathcal{F} \times \{x\}$ is a distinct indicator of $R(x)$. As a result, $R(a) \neq R(b)$ whenever $a \neq b$, or equivalently $R(x)$ is injective for all $x \in \bigcup \mathcal{F}$.
- We generate function $f$ as follows:
Apply this Theorem, there exists a function $g:\bigcup W \to W$ such that $x \in g(x) \in W$. It is clear that $A \in W$ for all $A \in \mathcal{F}$.
Let $f(A)=R^{-1}(g(A))$ for all $A \in \mathcal{F}$. $$\tag*{$\blacksquare$}$$
To your questions : 1. You didn't choose $x$ well enough then. Note that the $x$ is uniform, i.e. it's the same for all $a$'s. See 2. for why a good choice of $x$ suffices.
You want $(x,a)\notin\mathcal{F}$ so that if $(x,a) \in S_b$, either $(x,a) = (x,b)$, in which case $a=b$, or $(x,a) = f$ for some $f\in \mathcal{F}$ such that $b\in f$; but in that second case $(x,a)\in \mathcal{F}$, which is not possible (due to the choice of $x$) : you are right this is probably a typo.
Your first proof seems correct (though it uses the axiom of regularity). For your second proof, note that it's not $R(x)$ that is injective, but rather $R$. Apart from that the second proof seems correct as well.