Surjective Maps
in [Math]
|
Prev: Is Pascal's Triangle related to the Normal Bell Curve?
Next: Dodeca Developer || Must have all the skills || Immediate Need In OH
From: Maury Barbato on 17 Feb 2010 03:23 Hello, let X, Y and I be three (non empty) sets and {f_i:X->Y} a family of distinct surjective maps indexed by I. Can you find distinct injective maps {g_i:Y->X} such that (f_i)°(g_i) is the identity map of Y for every i in I? Thank you very much for your attention. My Best Regards, Mury Barbato PS Note that the g_i's are required to be distinct.
From: Arturo Magidin on 17 Feb 2010 14:54 On Feb 17, 12:23 pm, Maury Barbato <mauriziobarb...(a)aruba.it> wrote: > Hello, > let X, Y and I be three (non empty) sets and > {f_i:X->Y} a family of distinct surjective maps > indexed by I. > Can you find distinct injective maps {g_i:Y->X} > such that (f_i)°(g_i) is the identity map of Y > for every i in I? Note: if you can find such g_i, then the g_i are necessarily injective, because hk injective implies k injective for any two functions h and k that can be composed. As to your question, only if you assume the axiom of choice. In fact: THEOREM. The following are equivalent: 1. The Axiom of Choice: if {X_i}_{i in I} is a nonempty family of nonempty sets, then there exists f:I --> \/X_i such that f(i) in X_i for each i in I. 2. If A and B are nonempty sets, and g:A-->B is surjective, then there exists h:B-->A such that gh = id_B. Proof. (1) --> (2). For each b in B, let X_b = {a in A : f(a) = b}. Since g is surjctive, and B is nonempty, {X_b}_{b in B} is a nonempty family of nonempty sets. Let h:B-->\/X_b = A be a function such that h(b) is in X_b for all b in B. Then for all b in B we have g(h(b)) = b, since g(a)=b for all a in X_b. (2) --> (1). Let Y_i = X_i x {i}. Let Y = \/_{i in I} Y_i. Define g:Y --> I by letting g((x,j)) = j. This map is surjective, since I is nonempty and each X_i is nonempty (hence each Y_i is nonempty). By (2), there exists h:I-->Y such that h(i) is in Y_i for each i. Define f:I--->\/X_i by letting f(i) be the first component of h(i). Since h(i) is in Y_i, it follows that h(i) = (x,i) for some x in X_i, so f(i) is in X_i for each i. QED If you have the axiom of choice, then for each i the set of right inverses of f_i is nonempty (by the Theorem), so now you have a nonempty family of nonempty sets, so another application of the Axiom of Choice lets you pick one right inverse g_i for each g_i. -- Arturo Magidin
From: Ask me about System Design on 17 Feb 2010 14:54 On Feb 17, 10:23 am, Maury Barbato <mauriziobarb...(a)aruba.it> wrote: > Hello, > let X, Y and I be three (non empty) sets and > {f_i:X->Y} a family of distinct surjective maps > indexed by I. > Can you find distinct injective maps {g_i:Y->X} > such that (f_i)°(g_i) is the identity map of Y > for every i in I? > > Thank you very much for your attention. > My Best Regards, > Mury Barbato > > PS Note that the g_i's are required to be distinct. If it is required that i <> j implies g_i <> g_j, then not always. The index set I may be too large to accomplish this. For example, let X have 8 elements, Y have 2 elements. Then there are at most 64 distinct possibilities for g_i. So if I is greater than 64 (e.g. divide X into two 4 element sets and map one set to one member of Y and the rest to the other, there being at least 65 ways to do this), then the task of finding enough maps from Y to X is doomed, regardless of any other conditions that you might impose on the g_i's. If I is small enough, then there may still be some obstacles as the f_i may behave identically on a subset of X - 8 elements mapping bijectively to a subset of Y - 2 elements, and behave like the above example on an 8 element subset of X onto a two element subset of Y. So you can't tell without knowing a lot about the f_i. Gerhard "Ask Me About System Design" Paseman, 2010.02.17
From: Arturo Magidin on 17 Feb 2010 15:05 On Feb 17, 1:54 pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > If you have the axiom of choice, then for each i the set of right > inverses of f_i is nonempty (by the Theorem), so now you have a > nonempty family of nonempty sets, so another application of the Axiom > of Choice lets you pick one right inverse g_i for each g_i. Oops; I didn't see your requirement that the g_i be distinct. As Gerhard has pointed out, you may not have "enough" functions from Y to X to accomplish this in general, even if all the f_i are distinct, or even if your sets are infinite.
From: Maury Barbato on 17 Feb 2010 23:02
grpadmin(a)gmail.com wrote: > On Feb 17, 10:23 am, Maury Barbato > <mauriziobarb...(a)aruba.it> wrote: > > Hello, > > let X, Y and I be three (non empty) sets and > > {f_i:X->Y} a family of distinct surjective maps > > indexed by I. > > Can you find distinct injective maps {g_i:Y->X} > > such that (f_i)°(g_i) is the identity map of Y > > for every i in I? > > > > Thank you very much for your attention. > > My Best Regards, > > Mury Barbato > > > > PS Note that the g_i's are required to be distinct. > > If it is required that i <> j implies g_i <> g_j, > then > not always. The index set I may be too large to > accomplish this. > > For example, let X have 8 elements, Y have 2 > elements. > Then there are at most 64 distinct possibilities for > g_i. So if I is greater than 64 (e.g. divide X into > two 4 element sets and map one set to one member of Y > and the rest to the other, there being at least 65 > ways > to do this), then the task of finding enough maps > from > Y to X is doomed, regardless of any other conditions > that you might impose on the g_i's. > > If I is small enough, then there may still be some > obstacles as the f_i may behave identically on a > subset > of X - 8 elements mapping bijectively to a subset of > Y - 2 elements, and behave like the above example on > an > 8 element subset of X onto a two element subset of Y. > So you can't tell without knowing a lot about the > f_i. > > Gerhard "Ask Me About System Design" Paseman, > 2010.02.17 Thank you so much for your enlightening example, Gerhard! Best Regards, Maury Barbato |