Yes, you need at least a weak form of the Axiom of Choice. It is sufficient to use the Countable Axiom of Choice: if S is a countable set of disjoint, non-empty sets, there is a set T containing exactly one element from each element of S. Given a surjection s: X -> X U {X}, define u(0) = {{X}}, and u(j+1) = {x : s(x) in u(j)}. It is easy to show that u(j) is non-empty for each j, and that they are pairwise disjoint. Let S be {u(j) : j in omega}. Apply the Countable Axiom of Choice to get a set T containing one element from each u(j); call this t(j). We must have t(0) = {X}, since this is the only element of u(0). Now define i: X U {X} -> X by i(t(j)) = t(j+1), i(x) = x for any x not in T. Clearly this is an injection. ------------ While the Countable Axiom of Choice is non-constructive, it is sort of "almost-constructive" - it encodes a sequence of operations that one could carry out, given infinite time. (That is, each of the choices will eventually be made.) It has far fewer non-intuitive consequences than the Axiom of Choice. Franklin T. Adams-Watters -----Original Message----- From: dasimov@earthlink.net Actually, in suggesting the exercise [that boils down to] There is an injection i: X u {X} -> X <=> There is a surjection s: X -> X u {X}, it struck me that the => direction is simple enough, but the <= direction seems to require the Axiom of Choice. I.e., =>: ----------- Define a surjection S_i: X -> X u {X} via S_i(x) = i^(-1)(x), if x is in Im(i); else S_i(x) = X. But for <=: ------------- Define an injection I_s: X u {X} -> X via I_s(x) = some member of s^(-1)(x), if x is in s^(-1)(X); else I_s(x) = some member of s^(-1)(X). (I'm not sure how to get around the use of AC in <=.) --Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun ___________________________________________________ Try the New Netscape Mail Today! Virtually Spam-Free | More Storage | Import Your Contact List http://mail.netscape.com