Results 1 to 2 of 2

Thread: Axiom of choice

  1. #1
    Member
    Joined
    Nov 2007
    Posts
    108

    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: $\displaystyle (\forall R)$$\displaystyle (R$ a relation $\displaystyle \rightarrow (\exists f)$$\displaystyle [f$ a function and $\displaystyle f \subseteq R$ and $\displaystyle domf= domR])$
    Form 2: $\displaystyle (\forall X)$[If $\displaystyle \forall y \in X$, y is not equal the empty set, then $\displaystyle \prod X$ is not equal the empty set.
    Where $\displaystyle \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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    Posts
    394
    Quote Originally Posted by namelessguy View Post
    I am given two forms of the axiom of choice, and I need to show that they are equivalent. Can someone help?
    Form 1: $\displaystyle (\forall R)$$\displaystyle (R$ a relation $\displaystyle \rightarrow (\exists f)$$\displaystyle [f$ a function and $\displaystyle f \subseteq R$ and $\displaystyle domf= domR])$
    Form 2: $\displaystyle (\forall X)$[If $\displaystyle \forall y \in X$, y is not equal the empty set, then $\displaystyle \prod X$ is not equal the empty set.
    Where $\displaystyle \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 $\displaystyle f \subseteq R$ with $\displaystyle dom f = dom R$".

    Assume Form1.
    We define a relation R such that $\displaystyle R = \{<X_i, x_i> | i \in I \bigwedge x_i \in C(X_i)\}$, where a choice function C is defined as $\displaystyle C:\{X_i\} \rightarrow \bigcup_{i \in I} X_i$ such that $\displaystyle C(X_i)$ is an element of $\displaystyle X_i$. Since $\displaystyle dom C = dom R$ and $\displaystyle 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 $\displaystyle x = (x_i) \in \prod_{i \in I} X_i $; let $\displaystyle S = \bigcup_{i \in I} x_i$.
    Now, we have $\displaystyle S \subseteq \bigcup_{i \in I} X_i$ and for each i, $\displaystyle S \cap X_i = x_i$.
    That means, there exists a choice function $\displaystyle C:\{X_i\} \rightarrow \bigcup_{i \in I} X_i$ such that we retrieve $\displaystyle x_i = S \cap X_i $ for each $\displaystyle X_i$.
    Now, consider any relation R. The existence of a choice function C provides us with a mapping from $\displaystyle dom R$ to $\displaystyle ran R$.
    Then, $\displaystyle C(x) \in \{y | xRy\}$, i.e., $\displaystyle <x, C(x)> \in R$. Thus, $\displaystyle C \subseteq R$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Axiom of choice.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Jan 11th 2010, 08:50 AM
  2. With or without Choice-axiom?
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: Dec 19th 2009, 07:08 PM
  3. axiom of choice
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Sep 13th 2009, 02:01 PM
  4. Axiom of Choice
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jan 18th 2006, 01:52 PM

Search Tags


/mathhelpforum @mathhelpforum