My Math Forum  

Go Back   My Math Forum > College Math Forum > Abstract Algebra

Abstract Algebra Abstract Algebra Math Forum

LinkBack Thread Tools Display Modes
February 13th, 2008, 06:55 PM   #1
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
farleyknight is offline  
February 13th, 2008, 07:00 PM   #2
Global Moderator
CRGreathouse's Avatar
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
CRGreathouse is offline  
February 15th, 2008, 05:22 PM   #3
Joined: Feb 2008

Posts: 89
Thanks: 0


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(S
i) 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.


Rich B.
nikkor180 is offline  

  My Math Forum > College Math Forum > Abstract Algebra

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

Copyright © 2018 My Math Forum. All rights reserved.