Re: [math-fun] Re: favorite theorem
Michael Kleber wrote: <<
A set is finite if there exists no bijection of it onto one of its proper subsets.
Unfortunately, that's not true. Or rather, there are models of set theory in which this definition ("Dedekind-finite") is equivalent to the usual notion of "finite", but there are others in which it is not. The Axiom of Choice is more than enough to imply they are equivalent, but that seems like much more than you want to get into if you're looking for beautiful stand-alone theorems.
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
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
participants (2)
-
dasimov＠earthlink.net -
franktaw＠netscape.net