# Find a one-to-one function

1. Mar 1, 2008

### mathboy

[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. Mar 1, 2008

### Dick

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?

3. Mar 1, 2008

### mathboy

Yes, injective function.

4. Mar 1, 2008

### morphism

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.

5. Mar 2, 2008

### Dick

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.

6. Mar 2, 2008

### mathboy

Isn't that what I did in the first post? But it runs into problems, e.g. f(a1)=f(a2).

7. Mar 2, 2008

### Dick

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.

8. Mar 2, 2008

### mathboy

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
9. Mar 2, 2008

### Dick

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.