# Math Help - Axiom of choice

1. ## Axiom of choice

I am given two forms of the axiom of choice, and I need to show that they are equivalent. Can someone help?
Form 1: $(\forall R)$ $(R$ a relation $\rightarrow (\exists f)$ $[f$ a function and $f \subseteq R$ and $domf= domR])$
Form 2: $(\forall X)$[If $\forall y \in X$, y is not equal the empty set, then $\prod X$ is not equal the empty set.
Where $\prod X$ is the Cartesian product defined as the set of functions f with dom f=X and for all y in X, f(y) is in y.

2. Originally Posted by namelessguy
I am given two forms of the axiom of choice, and I need to show that they are equivalent. Can someone help?
Form 1: $(\forall R)$ $(R$ a relation $\rightarrow (\exists f)$ $[f$ a function and $f \subseteq R$ and $domf= domR])$
Form 2: $(\forall X)$[If $\forall y \in X$, y is not equal the empty set, then $\prod X$ is not equal the empty set.
Where $\prod X$ is the Cartesian product defined as the set of functions f with dom f=X and for all y in X, f(y) is in y.
Form 1 says that "For any relation R, there is a function $f \subseteq R$ with $dom f = dom R$".

Assume Form1.
We define a relation R such that $R = \{ | i \in I \bigwedge x_i \in C(X_i)\}$, where a choice function C is defined as $C:\{X_i\} \rightarrow \bigcup_{i \in I} X_i$ such that $C(X_i)$ is an element of $X_i$. Since $dom C = dom R$ and $C(X_i)$ is not empty, the existence of choice function C is followed from a Form1, satisfying the Form 2.

Conversely, assume Form 2.
Let $x = (x_i) \in \prod_{i \in I} X_i$; let $S = \bigcup_{i \in I} x_i$.
Now, we have $S \subseteq \bigcup_{i \in I} X_i$ and for each i, $S \cap X_i = x_i$.
That means, there exists a choice function $C:\{X_i\} \rightarrow \bigcup_{i \in I} X_i$ such that we retrieve $x_i = S \cap X_i$ for each $X_i$.
Now, consider any relation R. The existence of a choice function C provides us with a mapping from $dom R$ to $ran R$.
Then, $C(x) \in \{y | xRy\}$, i.e., $ \in R$. Thus, $C \subseteq R$.