Inquiry about axiom of choice.

[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 don't think i used here the axiom of choice, is there another way to prove this statement with the axiom of choice?

and also I am 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?

 

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

 

[MathematicalPhysicist]

so what i wrote in the third paragraph is correct?

 

[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 I am 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? (-:

 

[EnumaElish]

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

 

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

 

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

 

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

 

[EnumaElish]

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.

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

 

[matt grime]

Read post 2, lines 1-2.

 

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

 

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

 

[MathematicalPhysicist]

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.

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.

 

[EnumaElish]

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.

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.

 

[matt grime]

so you mean if f:X->Y is onto Y, then f(X)=Y

Yes.

let x be in X,

this won't do anything since we are never going to assume that g will be surjective (this can only happen if f is a bijection). Thus there is no point trying to construct something for any x 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})

g is *not* a function from Y to f^{-1}(y).

Given y in Y define g by making some choice of an x in f^{-1}(y) for each y in Y.

 

[MathematicalPhysicist]

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

 

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

 

[MathematicalPhysicist]

enumaelish, my second question is unrelated to my first question to which i already got an naswer to.
this questiom I am asking now is to prove that if f:X->Y is onto Y then there exists g:Y->X which is injective.

 

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

 

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

 

[matt grime]

Just because you did not cite the AoC does not mean you did not use it. It is equivalent to many other statements. And make sure you cite all assumptions on X, Y, and f.

 

[EnumaElish]

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.

Yes, checking your notes will be a good idea at this point.

 

[Kirk Hilliard]

but in class we proved this statement without the use of AOC.

The statement that "every surjective function has a right inverse" is equivalent to the axiom of choice.