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

Axiom of choice and natural numbers.

  1. Jun 14, 2006 #1
    i have a few question, that i hope they will answered.
    1) let w={0,1...,n,..}={0}UN, and let f:wxw->w such that the next requirements apply:
    a) f(0,n)=n+1
    b) f(m+1,0)=f(m,1)
    c) f(m+1,n+1)=f(m,f(m+1,n).

    i need to prove that for every n,m in w, the next statement applies:
    f(m,n)<f(m,n+1).
    (i tried with induction, but this was too much complicated for me to do).

    2)let there be 2 sets, X and Y, prove with the help of AC that there exist a function from X onto Y iff |X|>=|Y|.

    well for the second question, here what i did:
    suppose, there exists f:X->Y which is onto Y, if we utilize AC then lets define P(Y)\{empty set} as a subset of X, then by AC f|P(Y)\{empty set} P{Y}\{EMPTY SET}->Y such that f|P(X)\{ES}(A) is in A for every A in P(Y)\{ES} which means Y is onto P(Y)\{ES} and therefore there is bijection between Y and a subset of X, therefore |X|>=|Y|, the second conditional here im not sure hoe to prove, i will appreciate your help.
     
  2. jcsd
  3. Jun 14, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    in 2) what is P(Y)? Not the power set, surely.

    The only if part (that you have tried to prove) is simply: pick a preimage of every point in Y to create a bijection with a subset of X.

    the if part is easy then, assuming that your definition of => for cardinals is Y is in bijection with a subset of X: use that bijection to define a map for all x in X
     
  4. Jun 14, 2006 #3
    it is the power set of Y, why 'not the power set, surely'.

    what's wrong with my approach?
     
  5. Jun 14, 2006 #4
    so about the first if, i should pick f^-1(y)={x in A|f(x)=y} such that for every f^-1(y) is in A where A is in X so there's a bijection between Y and a subset of X, is this correct?

    what about the second if?
     
  6. Jun 14, 2006 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    No, that won't work: y may have many preimages: you need to pick one for each y, that is what the axiom of choice allows you to do.

    I told you how to do the 'if' part (which I think you call 'the second if'; it is not a first and second if, it as an if and on only if): you know there is a bijection between Y and a subset of X, ie there is a surjective map from a subset of X to Y, so just extend that to a map on all of X (that is trivially surjective.
     
  7. Jun 14, 2006 #6
    the definition of AC that i know from my book is: let X be a family of non empty sets, then there exists a function f:P(X)\{empty set}->X such that f(A) is in A for every A in P(X)\{empty set}.

    now if there exists a function from X onto Y f:X->Y then for every y in Y there exists x in X such that f(x)=y, now in order to show that there's a bijection between a subset of X and Y i need to show there's a one to one mapping between them, if ill define A as a subset of X then by AC g:P(A)\{empty set}->A if we let P(A)\{empty set}=Y then there's a one to one cause if x!=x' when x' and x are in P{A}\{empty set} then also f(x)!=f(x') cause f(x) and f(x') are in A which is a subset of P(A)\{empty set}, right?

    i think the second part of the proof i can manage.
     
  8. Jun 14, 2006 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Again, I repeat my request for you to define P(X), I presume it is power set. There is no way in general to define P(Y) as a subset of X if P(Y) genuinely does mean the power set, which is what you wanted to do in your first post, hence my confusion here. (There is a trivial surjection from X to X but no way to make P(X) a subset of X). Since you are talking about the axiom of choice (and families of sets) then I think it might mean product, but that would be a very non-standard use of the letter P). Try to avoid using X to mean different things in the same post, by the way.
     
    Last edited: Jun 14, 2006
  9. Jun 14, 2006 #8
    matt, where in my post did i say the P(X) is a subset of X?
    all that i said in my post is that A is a subset of X and A is subset of P(A)\{empty set}, not vice versa.

    P(X) is the power set of X.
     
    Last edited: Jun 14, 2006
  10. Jun 14, 2006 #9
    another question in set theory:
    find a choice function without the help of AC (if you can) for the next sets:
    1) P(Z)\{empty sets}
    2) P(Q)\{empty set}
    for the first option perhaps it should be f(x)=-x for x in P(Z)\{es}, cause it gets every number from P(Z)\{empty set} to itself but so does f(x)=x, as far as i can tell i need to find a function f(A) which is in A such that A is in P(Z)\{empty set}, right? if so than both of these functions will do as choice functions.
     
  11. Jun 14, 2006 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Look at post 1: your method is to, and I quote,

    "if we utilize AC then lets define P(Y)\{empty set} as a subset of X"

    this is, in general, impossible: you cannot define P(Y) as a subset of X given some surjection from X to Y, since if you could then you can define P(X) as a subset of X which is impossible.
     
  12. Jun 14, 2006 #11
    but now ive refraind from that, havent i?

    im really confused here as to how to create a bijection between Y and a subset of X, if we have f:X->Y onto Y then by definition for every y in Y there exists x in X such that f(x)=y, now i need to use AC to see that there's a function one to one from Y->A where A is a subset of X, now if we take a choice function g:Y->A (A is non empty) g(B) is in B and B is in Y, now i need to show that if y!=y' then g(y)!=g(y') how do i show it with what im given?
     
  13. Jun 14, 2006 #12

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Take the union of the sets f^{-1}(y) for y in Y. It is therefore a family of sets and by the axiom of choice it is possible to choose a representative of each one. That is all the axiom of choice says. This is where you use the choice function.
     
  14. Jun 14, 2006 #13
    so g:Uf^-1(y)->A (A a subset of X) such that g(B) is in B for every B in Uf^-1(y), but now i need to show that if g(x)=g(x') then x=x', how o i do this? (this ofcourse in order to show that they are one to one).
     
  15. Jun 14, 2006 #14

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I am still puzzled as to what you're doing, but that is my fault not yours. B is what? an element of something? a subset of something?

    The g you ought to be constructing which is from Y to X is trivially an injection (otherwise f would map one element of X to two elements of Y, and that is not allowed as f is a function).
     
  16. Jun 14, 2006 #15
    im following the defintion from here http://planetmath.org/encyclopedia/AxiomOfChoice.html
    in my notation B is the same as x in there.
    shouldnt it be from Y to a subset of X?
     
  17. Jun 14, 2006 #16

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    A map from Y to a subset of X is a map from Y to X.

    I am not going to, nor should I be expected to, follow a link (that I am supposed to guess...?) to planet math in order to figure out what you mean when you write a letter. Tell me, and everyone else.
     
  18. Jun 15, 2006 #17
    no one asked you to guess here, you asked what B stands for and i gave a link to planet math which explains it, any other problems from your behalf to read it are your problems, not mine.

    btw, does my construction of g ok, or does it lack something you didnt mention already in your posts?
     
    Last edited: Jun 15, 2006
  19. Jun 15, 2006 #18

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You used B without explaining its meaning before I asked. If you want help, the onus is on you to explain yourself clearly. I will not bother helping anymore, bye.
     
  20. Jun 15, 2006 #19
    I agree with Matt that your use of [tex] P(X) [/tex] was confusing. As such I didn't get too far into the proof in the direction you opted and didn't read the back and forth too much but I think Matt gave a hint on how to do it.

    Here's an idea for how to prove it in the other direction

    [tex] |X| >= |Y| [/tex] implies that there is an injection [tex] g:Y -> X [/tex]

    Define [tex] f:X \rightarrow Y [/tex] so that

    For all [tex] x \in X [/tex]

    [tex] f(x) = [/tex] [Fill in the blank] if [tex] x \in ran(g) [/tex]

    [tex] f(x) = [/tex] [Something about choice] if [tex] x \notin ran(g) [/tex]

    To show the other direction you can use a similar idea.
     
    Last edited: Jun 15, 2006
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Axiom of choice and natural numbers.
  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...