# Inquiry about axiom of choice.

Gold Member

## Main Question or Discussion Point

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?

Related Set Theory, Logic, Probability, Statistics News on Phys.org
matt grime
Homework Helper
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:
Gold Member
so what i wrote in the third paragraph is correct?

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

EnumaElish
Homework Helper
You could invoke "every 1-1 is invertible"?

matt grime
Homework Helper
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:
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
Homework Helper
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:
EnumaElish
Homework Helper
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
Homework Helper

EnumaElish
Homework Helper
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
Homework Helper
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.

Gold Member
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
Homework Helper
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
Homework Helper
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.

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

EnumaElish
Homework Helper
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.)

Gold Member
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.

EnumaElish
Homework Helper
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.

Gold Member
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
Homework Helper
Just becuase 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