The Axiom of Choice: Proof Validity

Question

Synopsis

In Enderton's Element's of Set Theory, he introduces several forms of the Axiom of Choice. Currently, I've gotten through the first and second forms. Mainly:

(1) For any relation $R$, there is a function $H \subseteq R$ with dom $H$ = dom $R$

(2) For any set $I$ and any function $H$ with domain $I$, if $H(i) \neq \varnothing$ for all $i \in I$, then $\prod_{i \in I} H_i \neq \varnothing$.

After introducing the second form, he asks us to show that the two forms are equivalent. I would greatly appreciate it if you would check the validity of my attempt, and also perhaps give me an explanation for how you personally understand and think about the axiom of choice. I have a vague notion right now in my head, and I think an alternative explanation of the same concept my give me a deeper understanding. Now, onto the proof.

---

Proof

Suppose the first form is true. Define a relation $R$ as follows: $$R = I \times \bigcup_{i \in I} H(i).$$ By the first form of the axiom of choice, we can construct a function $f \subseteq R$ with dom $f$ = dom $R$ $= I$. This means that $f(i) = R(i)$ for all $i \in I$ and by definition of $R$, $f(i) \in H(i)$. Hence, $f \in \prod_{i \in I} H_i$.

Now for the converse, suppose the second form is true. Then for a relation $R$, let $I =$ dom $R$. Define a function $H: I \rightarrow \mathscr{P}(\text{ran } R)$ where $H(i) := \{x \in \text{ran } R \mid iRx \}$. By the axiom of choice, $\prod_{i \in I} H_i \neq \varnothing$, so there exists a function $f$ with $\text{dom }f = I$ such that $(\forall i \in I) f(i) \in H(i)$. That means $(\forall i \in I) iRf(i)$. So $f \in R$ and $\text{dom } f = \text{dom } R$.

Thus, the two forms are equivalent.

Q.E.D.

---

Thank you so much for your time, and I'll diligently pay attention to any comments or takes on how you understand the Axiom of Choice and/or how I can better my proof-writing abilities.

Answer 1

The first proof is not correct, the second one is fine with the exception of a typo saying $f\in R$ rather than $f\subseteq R$.

The problem with the first proof is that if I picked one $i$ and one $a\in H(i)$, then $f=I\times\{a\}$ is a function such that $f\subseteq R$ and they have the same domain. Instead you need to ensure that the relation captures the thing you're choosing from. This is the approach you're taking in the second proof, and it works just fine. You can correct this by taking $R=\bigcup_{i\in I}\{i\}\times H(i)$.

Your mistake lies in "this means", which is an unverified claim.

 

So, how can you do better? One way is to practice. With practice you develop a better intuition as to where you might be "cheating yourself out of a proof". You can go over your proof and question each statement that you made, and see how exactly it should follow, and if you can't convince yourself in full, assume there is a mistake, or at least a gap, until you've seen otherwise.

As for general intuition about the axiom of choice? That's easy. If you're choosing from infinitely many sets, and you haven't specified exactly what is the element you're choosing from which one, then you've used the axiom of choice. Just be wary that sometimes we delegate the use of the axiom to a background choice. Again, practice makes better, although it never makes perfect.

Answer 2

Error

My proof that (1) implies (2) was incorrect. Thanks to the help of @Asaf Karagila and his kindness in helping me understand my error, I think I've been able to provide a fix.

My error comes in me assuming too large a relation, meaning that the Axiom of Choice was not necessarily applicable in all situations. An example of this is the function Asaf mentioned of $f = I \times \{a\}$. This function does not depend on the Axiom of Choice, and so the relation it comes from cannot be used to prove anything relating to the Axiom of Choice.

To fix this, the relation had to be restricted by a rule that forced us to choose from elements of $H(i)$.

Correction

Suppose the first form is true. Define a relation $R$ as follows: $$R = \bigcup_{i \in I} \{i\} \times H(i).$$ By assumption, there exists a function $G \subseteq R$ with $\text{dom } G = \text{dom } R = I$. So for all $(a,x) \in G$, $a \in I$ and $x \in H(i)$. It follows that $G \in \prod_{i \in I} H(i)$, so $G \in \prod_{i \in I} \neq \varnothing$.

For the converse, suppose the second form is true. Then for a relation $R$, let $I =$ dom $R$. Define a function $H: I \rightarrow \mathscr{P}(\text{ran } R)$ where $H(i) := \{x \in \text{ran } R \mid iRx \}$. By the axiom of choice, $\prod_{i \in I} H_i \neq \varnothing$, so there exists a function $f$ with $\text{dom }f = I$ such that $(\forall i \in I) f(i) \in H(i)$. That means $(\forall i \in I) iRf(i)$. So $f \subseteq R$ and $\text{dom } f = \text{dom } R$.