
Abstract Algebra Abstract Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
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 onetoonecorrespondence 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 onetoone 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 onetoone 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 onetoone 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 onetoone 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: 933 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 0element set will have 1 element. You almost figured it out... just like Saccheri nearly discovered nonEuclidean geometry. :P 
February 15th, 2008, 05:22 PM  #3 
Member Joined: Feb 2008 Posts: 89 Thanks: 0  Greetings: In order that a 11 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 nonnegative integers, x, it is not possible for S and P(S) to have like cardinality. Hence no such 11 correspondence exists and the proof is therefore complete. Regards, Rich B. 

Tags 
book, dover, error, functions, powersets 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Error with Moment Generating Functions  Relmiw  Advanced Statistics  2  February 13th, 2012 02:57 PM 
proving powersets in relation to a set  finalight  Applied Math  4  December 1st, 2011 09:29 AM 
how to prove powersets  Solarmew  Applied Math  3  November 19th, 2011 05:38 PM 
Integrating product of exponential and error functions  hateqq  Calculus  0  October 28th, 2010 11:28 PM 
continuous functions on Munkres's book  bigli  Real Analysis  5  July 26th, 2007 10:44 PM 