Axiom of choice

**namelessguy** · February 17th 2009, 01:50 PM

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.

**aliceinwonderland** · February 18th 2009, 02:27 AM

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 = \{<X_i, x_i> | 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., $<x, C(x)> \in R$ . Thus, $C \subseteq R$ .

Thread: Axiom of choice

LinkBack

Thread Tools

Display

Axiom of choice

Similar Math Help Forum Discussions

Axiom of choice.

With or without Choice-axiom?

axiom of choice

Axiom of Choice

Search Tags