Results 1 to 2 of 2

Math Help - 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: (\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.
    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: (\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.
    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: January 11th 2010, 09:50 AM
  2. With or without Choice-axiom?
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: December 19th 2009, 08:08 PM
  3. axiom of choice
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 13th 2009, 03:01 PM
  4. Axiom of Choice
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 18th 2006, 02:52 PM

Search Tags


/mathhelpforum @mathhelpforum