Inquiry about axiom of choice.

MathematicalPhysicist
Gold Member
4,139
149

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?
 

Answers and Replies

matt grime
Science Advisor
Homework Helper
9,394
3
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:
MathematicalPhysicist
Gold Member
4,139
149
so what i wrote in the third paragraph is correct?
 
MathematicalPhysicist
Gold Member
4,139
149
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
Science Advisor
Homework Helper
2,285
123
You could invoke "every 1-1 is invertible"?
 
matt grime
Science Advisor
Homework Helper
9,394
3
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:
90
0
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
Science Advisor
Homework Helper
2,285
123
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
Science Advisor
Homework Helper
2,285
123
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
Science Advisor
Homework Helper
9,394
3
Read post 2, lines 1-2.
 
EnumaElish
Science Advisor
Homework Helper
2,285
123
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
Science Advisor
Homework Helper
9,394
3
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
Gold Member
4,139
149
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
Science Advisor
Homework Helper
2,285
123
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
Science Advisor
Homework Helper
9,394
3
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
Gold Member
4,139
149
the only thing i can see is, that g(y)=x such that f(g(y))=y.
 
EnumaElish
Science Advisor
Homework Helper
2,285
123
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
Gold Member
4,139
149
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
Science Advisor
Homework Helper
2,285
123
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
Gold Member
4,139
149
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
Science Advisor
Homework Helper
9,394
3
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
Science Advisor
Homework Helper
2,285
123
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.
 

Related Threads for: Inquiry about axiom of choice.

Replies
21
Views
10K
Replies
2
Views
440
  • Last Post
Replies
17
Views
5K
  • Last Post
Replies
3
Views
2K
  • Last Post
2
Replies
49
Views
3K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
11
Views
4K
  • Last Post
Replies
8
Views
2K
Top