1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Find a one-to-one function

  1. Mar 1, 2008 #1
    [SOLVED] Find a one-to-one function

    Let A1, A2, A3... be infinite pairwise disjoint sets. Find an injective function

    f : A1 U A2 U A3 U... -> A1 x A2 x A3 x...

    For all i, I choose fixed elements a_i in each A_i. If x is in A_n, I tried

    f(x) = (a1, a2,...,a_n-1, x, a_n+1,...).

    But this doesn't work because, e.g., f(a1)=f(a2). So I added the extra rule

    f(a_n) = (a1, a2,...,a_n-1, b_n, a_n+1,...),

    where a_n not= b_n. But this still doesn't work because f(a_n)=f(b_n). Can someone help me find an injective function that works?

    Or at least prove that such an injective function exists using the axiom of choice (without simply stating that the cardinality of the domain is smaller than the cardinality of the range, because using this fact is not allowed in my question, unless I prove it using the axiom of choice).
     
    Last edited: Mar 1, 2008
  2. jcsd
  3. Mar 1, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    If the cardinality of domain is generally smaller than the cardinality of the range, which is true, there generally is no one-to-one function. Do you just mean an injective function?
     
  4. Mar 1, 2008 #3
    Yes, injective function.
     
  5. Mar 1, 2008 #4

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    You're almost there. You just need to know where to map the a_i's. That the sets A_i are infinite will be useful here.
     
  6. Mar 2, 2008 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Use the axiom of choice to pick an element in each A_i. Call that 'a' in the cartesian product. If x is in the union then it belongs to exactly one A_i since they are pairwise disjoint. Define f(x) to be 'a' but only change the ith element.
     
  7. Mar 2, 2008 #6
    Isn't that what I did in the first post? But it runs into problems, e.g. f(a1)=f(a2).
     
  8. Mar 2, 2008 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    How? 'a'=(a1,a2,a3,a4...). f(a1)=(b1,a2,a3,a4,...). f(a2)=(a1,b2,a3,a4...). ... ... ..., I don't know how many ...'s I need here. I'm leaning on the pairwise disjoint condition.
     
  9. Mar 2, 2008 #8
    Ok, so for each i, using the axiom of choice, we use a choice function c: P(A_i) -> A_i and define (let's say x is in A_n),

    f(x) = (a1, a2,...,a_n-1, c(A_n-{x}), a_n+1,...).

    So the nth component has changed. Now suppose x and y are distinct points in A_n (the same A_n). How do we guarantee that f(x) not= f(y)? Perhaps change the domain of the choice function c to subsets of the form A_n-{x} and make the choice function injective somehow?
     
    Last edited: Mar 2, 2008
  10. Mar 2, 2008 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Right. Now you just just need an injective map from A_i->A_i-{a_i}. A_i is infinite. How do you define infinite? If your definition is that A_i can be placed into 1-1 correspondence with a proper subset, that should be pretty easy.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Find a one-to-one function
Loading...