Results 1 to 5 of 5

Math Help - Question regarding a Lemma on axiom of choice

  1. #1
    Newbie
    Joined
    Jan 2012
    Posts
    7

    Question Question regarding a Lemma on axiom of choice

    Hello all,

    I am currently reading a book on set theory "Joy of Sets" by Keith Delvin. In page 58 he proves a lemma which is stepping stone for proving that axiom of choice(AC) and 'Every set can be well ordered' (WO) are equivalent. The lemma goes something like this

    (AC') Every set of nonempty sets has a choice function
    Assume AC'. Let A by any set. Then there is a function f: P(A) -> A U {A} such that
    1. f(A) = A
    2. f(X) belongs to A-X, whenever X is subset of A

    (P(A) means power set of A, and symbol U means union)
    Proof: Let
    B = {A-X| X is subset of A}

    By AC', let g be a choice function for B. Thus g:B -> U B and g(Y) belongs to Y for all Y belongs to B. Define
    f: P(A) -> A U {A}
    by
    f(A) = A,
    f(X) = g(A-X), if X is subset of A.
    Clearly, f is as required
    Now, I took an example of A = {x,y,z}, now
    AU{A} is {x,y,x,{x,y,z}}
    and P(A) is {{},{x},{y},{y},{z},{x,y},{y,z},{z,x},{x,y,z}}

    I understand f(X) can be a result from choice function g(A-X), but I dont understand how f(A) = A.
    Also, is the methodology applied to prove the lemma is correct?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Question regarding a Lemma on axiom of choice

    Note that in the proof
    Quote Originally Posted by skanur View Post
    Let B = {A-X| X is subset of A}
    the set B should be {A - X | X is proper subset of A}. Otherwise, B includes the empty set (in fact, B = P(A)) and AC' is not applicable to B.

    Quote Originally Posted by skanur View Post
    I understand f(X) can be a result from choice function g(A-X), but I dont understand how f(A) = A.
    We can define f to be what we want on A. On proper subsets, f returns an element from the complement. On A itself, it may return some special flag indicating that g is not applicable to A. (Since everything is a set, the flag has to be a set as well.) In this case, one chose the flag to be A itself.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2012
    Posts
    7

    Exclamation Re: Question regarding a Lemma on axiom of choice

    Yes, X is indeed a proper set of A. Now I have major understanding conflict between various definitions in sets with regard to this lemma. Kindly clarify them
    1. In the definition of B, it does not say 'for all X'. So X is a single random occurrence and using my previous example B could be "any one" of these sets
    {x};{y};{z};{x,y};{y,z};{x,y,z}
    2. U B is now union of all the possible occurences of B, which is P(A)-{} i.e {{x},{y},{z},{x,y},{y,z},{x,y,z}}
    3. What does A U {A} mean? Does it mean successor of A (or something like that). What is the significance of choosing AU{A} for proof of this lemma?
    4. Assuming lemma is correct, if I apply function to a set {x} in P(A), then f({x}) should be {x,y} which is clearly not present in AU {A}, even though choice function g(A-X) is true.

    So what is going on? Where are the flaws in my understanding?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Question regarding a Lemma on axiom of choice

    Quote Originally Posted by skanur View Post
    1. In the definition of B, it does not say 'for all X'. So X is a single random occurrence and using my previous example B could be "any one" of these sets
    {x};{y};{z};{x,y};{y,z};{x,y,z}
    The set builder notation {x | Φ(x} denotes "the set of all individuals in the universe of discourse satisfying the formula Φ(x), that is, the set whose members are every individual x such that Φ(x) is true." Therefore, in your example B = {{x}, {y}, {z}, {x,y}, {y,z}, {x,y,z}}, i.e., \mathcal{P}(A)-\{\emptyset\}. ( \emptyset is another notation for {}.)

    Quote Originally Posted by skanur View Post
    2. U B is now union of all the possible occurences of B, which is P(A)-{} i.e {{x},{y},{z},{x,y},{y,z},{x,y,z}}
    No, \bigcup B is the union of the elements of B, i.e., {x} ∪ {y} ∪ {z} ∪ {x,y} ∪ {y,z} ∪ {x,y,z} = {x,y,z}.

    Quote Originally Posted by skanur View Post
    3. What does A U {A} mean?
    It's the union of two sets: A and a set with a single element A, i.e., it's the result of adding A itself to A. Think about a drawer containing pencils. Then take a bigger drawer, put the same pencils in it and then put in the first drawer.

    Sets containing sets containing sets, etc. is one of the confusing aspects of set theory. Fortunately, in the standard set theory, the chain of containments ∈ is always finite.

    Quote Originally Posted by skanur View Post
    Does it mean successor of A (or something like that).
    Yes, this is the standard definition of successor on natural numbers and, more generally, on von Neumann ordinals. However, there are other definitions of natural numbers in set theory. In any case, this does not seem to be relevant to the OP.

    Quote Originally Posted by skanur View Post
    What is the significance of choosing AU{A} for proof of this lemma?
    Quote Originally Posted by emakarov View Post
    We can define f to be what we want on A. On proper subsets, f returns an element from the complement. On A itself, it may return some special flag indicating that g is not applicable to A. (Since everything is a set, the flag has to be a set as well.) In this case, one chose the flag to be A itself.
    Maybe the fact that f(A) = A is important in the rest of the proof of the equivalence of different forms of AC, but not in this lemma.

    Quote Originally Posted by skanur View Post
    4. Assuming lemma is correct, if I apply function to a set {x} in P(A), then f({x}) should be {x,y} which is clearly not present in AU {A}, even though choice function g(A-X) is true.
    First, a set, e.g., a choice function, cannot be true or false, only propositions like A = B can be. Second, g({y,z}) by definition returns y or z (since g returns an element of its argument). So f({x}) = g(A - {x}) also equals y or z. We have y ∈ A U {A} and z ∈ A U {A}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2012
    Posts
    7

    Thumbs up Re: Question regarding a Lemma on axiom of choice

    Thanks a million!

    It solved various basic questions, especially about set builder notation.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Axiom of Choice Question (Basic)
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: August 31st 2011, 08:50 AM
  2. a question about the Axiom of choice
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 9th 2011, 08:36 AM
  3. Axiom of choice.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 11th 2010, 08:50 AM
  4. With or without Choice-axiom?
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: December 19th 2009, 07:08 PM
  5. axiom of choice
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 13th 2009, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum