1. Jan 10, 2007

MathematicalPhysicist

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. Jan 10, 2007

matt grime

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
3. Jan 10, 2007

MathematicalPhysicist

so what i wrote in the third paragraph is correct?

4. Jan 10, 2007

MathematicalPhysicist

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? (-:

5. Jan 10, 2007

EnumaElish

You could invoke "every 1-1 is invertible"?

6. Jan 11, 2007

matt grime

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
7. Jan 11, 2007

fopc

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.

8. Jan 11, 2007

EnumaElish

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
9. Jan 11, 2007

EnumaElish

And I guess that's how this question relates to the AOC.

10. Jan 11, 2007

matt grime

11. Jan 11, 2007

EnumaElish

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.

12. Jan 11, 2007

matt grime

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.

13. Jan 11, 2007

MathematicalPhysicist

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.

14. Jan 11, 2007

EnumaElish

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.

15. Jan 11, 2007

matt grime

16. Jan 12, 2007

MathematicalPhysicist

the only thing i can see is, that g(y)=x such that f(g(y))=y.

17. Jan 12, 2007

EnumaElish

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.)

18. Jan 12, 2007

MathematicalPhysicist

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.

19. Jan 12, 2007

EnumaElish

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.

20. Jan 12, 2007

MathematicalPhysicist

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.