My Math Forum An error on functions and powersets, in a Dover book?
 User Name Remember Me? Password

 Abstract Algebra Abstract Algebra Math Forum

 February 13th, 2008, 06:55 PM #1 Newbie   Joined: Feb 2008 Posts: 4 Thanks: 0 An error on functions and powersets, in a Dover book? Hey all, Taking discrete mathematics this semester and I'm really enjoying the course material. I'm digging a bit farther into it because I have an interest in these topics, and, of course, I want to get an A in the class. So I'm working on a proof provided in the Dover book "Elements of Abstract Algebra" by Allan Clark. In it, there is a theorem which states: There is no one-to-one-correspondence f: X -> 2^X for any set X. (Note that 2^X in this context refers to the powerset of X) For the vast majority of sets, this is true.. But what about the empty set ({}) ? If I'm not mistaken 2^{} = {{}} and a mapping: {} -> {{}} Is both one-to-one and onto. So, is this an error in the book? Or am I doing something wrong? Although the book provided a proof by contradiction, I gave it a try without. I'm still learning proofs, so I'd like advice if it's wrong, or could be improved: Theorem: There is no one-to-one correspondence f: X -> 2^X for any set X Let n(X) := the number of elements in a set X In order for f to have one-to-one correspondence, the Domain(f) and Codomain(f) must have equal number of elements. However, for any set X, the 2^X has 2^n(X) elements, therefore f: X-> 2^X cannot be a one-to-one correspondence. That was my first try. If the theorem was changed to not include the empty set, it would be correct.. if I'm not already mistaken. - Rob Update: Correction, thanks to CRGreathouse
 February 13th, 2008, 07:00 PM #2 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 937 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Ah, but you did make a mistake early on. You wrote that 2^{} = {}, but in fact the power set of {} is not {} but {{}}, a set which has one element instead of the zero elements in {}. Your proof works, though, and does tell you that the power set of a 0-element set will have 1 element. You almost figured it out... just like Saccheri nearly discovered non-Euclidean geometry. :P
 February 15th, 2008, 05:22 PM #3 Member   Joined: Feb 2008 Posts: 89 Thanks: 0 Greetings: In order that a 1-1 correspondence may exist between two sets, they must both share the same cardinality. But for any set, S, n(P(S)) = 2^n(S), where P(S)==pwr set of S, and n(Si) refers to the cardinality of set Si. That is, the cardinality of P(S) is equal to 2 raised to the cardinality of S. Because 2^x > x for all non-negative integers, x, it is not possible for S and P(S) to have like cardinality. Hence no such 1-1 correspondence exists and the proof is therefore complete. Regards, Rich B.

 Tags book, dover, error, functions, powersets

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Relmiw Advanced Statistics 2 February 13th, 2012 02:57 PM finalight Applied Math 4 December 1st, 2011 09:29 AM Solarmew Applied Math 3 November 19th, 2011 05:38 PM hateqq Calculus 0 October 28th, 2010 11:28 PM bigli Real Analysis 5 July 26th, 2007 10:44 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top