Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Inquiry about axiom of choice.

  1. Jan 10, 2007 #1
    i have this question:
    if: X=U X_i for every i in I, where X_i's are non empty and are disjoint, then |X|>=|I|.
    obvously there's the one to one function from I to X, which is g(i)=X_i, but my question is according to my text i need to use here the axiom of choice, i dont think i used here the axiom of choice, is there another way to prove this statement with the axiom of choice?

    and also im not sure my approach is correct cause X_i is a subset of X and not an element in X.
    perhaps g is a one to one from I to P(X)\{empty set}, and from the axiom of choice we are assurd that there exists a function f:P(X)\{empty set}->X so if we take fog we have a function from I to X which is one to one cause g is one to one:
    fog(i)=fog(j)=> f(X_i)=f(X_j) and f(X_i) is in X_i and f(X_j) is in X_j for every X_i in P(X)\{empty set}, so X_i and X_j arent disjoint which means that i=j.
    am i correct here?
     
  2. jcsd
  3. Jan 10, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Your notional function g above is defintely not a function from I to X. It is a function from I to the power set of X. To get a function from I to X you must pick an element of each X_i. This is where you're invoking the axiom of choice.

    Your composition with some function f from P(X) to X is what is needed.
     
    Last edited: Jan 10, 2007
  4. Jan 10, 2007 #3
    so what i wrote in the third paragraph is correct?
     
  5. Jan 10, 2007 #4
    i have another question, unrelated to AOC.
    i need to show that if f:X->Y is onto, then there exists a 1-1 function g:Y->X such that f(g(y))=y for every y inY. (we did it in class but im trying to prove it again)
    obviously, f(X)=Y but i forgot how lecturer proved, and it's mess to even search it in my clipboard, any help trying to invoke my memory? (-:
     
  6. Jan 10, 2007 #5

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    You could invoke "every 1-1 is invertible"?
     
  7. Jan 11, 2007 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    But every 1-1 is not invertible. Every surjection has a RIGHT (duh, edited correction) inverse. You just pick an inverse image for every point.
     
    Last edited: Jan 11, 2007
  8. Jan 11, 2007 #7
    I think the word invertible is typically used in the context of two-sided inverses.
    Functions with two-sided inverses are bijective.
    Every injective function has a left inverse.
    Every surjection has a right inverse.

    Clearly, every surjection does not have a left inverse.

    There is a closely related theorem to the one stated in post #4.
    If your f is (instead) injective, then there exists a left inverse (your g) that is surjective.
     
  9. Jan 11, 2007 #8

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    I was interpreting and using "1-1" for "1-1 correspondence" (a bijection); I admit it is confusing because I now understand that 1-1 stands for an injection.
     
    Last edited: Jan 11, 2007
  10. Jan 11, 2007 #9

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    And I guess that's how this question relates to the AOC.
     
  11. Jan 11, 2007 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Read post 2, lines 1-2.
     
  12. Jan 11, 2007 #11

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    I have. The reason for #9 is that in #4 the OP said the question about inverses is unrelated to the AOC. But I think it is related.
     
  13. Jan 11, 2007 #12

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    It is clear how to use the result in post 1 to prove this result. I is just the image, and X_i is the preimage of i in I.
     
  14. Jan 11, 2007 #13
    so you mean if f:X->Y is onto Y, then f(X)=Y let x be in X, such that there exists y=f(x) then f^-1({y})={x in X| f(x)=y}, we pick g:Y->f^-1({y}) so g(y)=x, and f(g(y))=y, so g(y) is injective, and thus g:Y->X is 1-1.
    i feel something is missing, cause for example if two elements from X are mapped onto one element in Y, then f^-1 of this elelment in y has two elements.
     
  15. Jan 11, 2007 #14

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    g needs to be a function, so g cannot point to two elements in X. IMHO I think that's where the AOC could be useful.
     
  16. Jan 11, 2007 #15

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

     
  17. Jan 12, 2007 #16
    the only thing i can see is, that g(y)=x such that f(g(y))=y.
     
  18. Jan 12, 2007 #17

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    In your OP you proposed "g(i)=X_i" which led others to think that the way you defined it, g was not a function, or, in any case, g was not the answer that the problem was seeking. I think you need to invoke the AOC to redefine g:Y--->X such that g(y) = x for some element y of Y and some element x of X. You really need to think carefully about the domain and the range of g and its stated properties (it is a function, and it is 1-1, and it satisfies f(g(y))=y). Then think about why you need the AOC to get there -- what is the obstacle that you need to remove by invoking the AOC spell, as J. K. Rowling would put it? (Remember, these spells are very specific.)
     
  19. Jan 12, 2007 #18
    enumaelish, my second question is unrelated to my first question to which i already got an naswer to.
    this questiom im asking now is to prove that if f:X->Y is onto Y then there exists g:Y->X which is injective.
     
  20. Jan 12, 2007 #19

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    Sorry, but the point also applies to the later question. It is tempting to write g = f^-1, which was my first instinct, too (but wrong). Since f is onto, it is possible that the inverse of f for each y will be multiple x's (a set). Since g is required to be a function, g = f^-1 will not do. (The value of g can only be a single _element_ in X.) It is this obstacle that you can remove by the AOC.
     
  21. Jan 12, 2007 #20
    but in class we proved this statement without the use of AOC.
    i see i need to recheck my notes, cause you appraently can't help me.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Inquiry about axiom of choice.
  1. Axiom of choice (Replies: 3)

  2. Axiom of Choice (Replies: 17)

  3. The Axiom of Choice? (Replies: 11)

  4. The Axiom of Choice (Replies: 8)

Loading...