Proving "No Surjection X \rightarrow P(X)": A Closer Look

[kidsmoker]

Hi,

there's a proposition in my lecture notes which states "If X is a set, there can be no surjection [tex]X \rightarrow P(X)[/tex]", where P(x) is the power set of X (does anyone know how I get the squiggly P?).

The proof given there seems unnecessarily complicated to me. Would the following be okay?

We need to show that if X is a set, there can be no surjection [tex]X \rightarrow P(X)[/tex].

Suppose that [tex]p:X \rightarrow P(X)[/tex] is a map. Now P(X) is the set of all the subsets of X. Define p(x) = {x}.

This maps each [tex]x \in X[/tex] to the most obvious subset {x}. Then clearly there is the subset [tex]\emptyset \in P(X)[/tex] such that [tex]p(x) \neq \emptyset[/tex] for any [tex]x \in X[/tex]. Hence no surjection can exist.

This seems to break down when X is the empty set (in which case there is a surjection surely?) but other than that it seems okay to me.

Any help appreciated!

 

[mathwonk]

this is a basic fallacy. you are starting by assuming your map is arbitrarily given, then immediately you are forgetting it was already given and you are defining it over again to suit your argument.start over: let f:S-->P(S) be ANY map, but fixed. NOW try to find an element not in the image.

the usual trick is as follows: define a subset of S to contain exactly those elements x that are NOT contained in the subset f(x). then this subset cannot be f of anything.this weird looking proof is an abstraction of cantor's 2nd diagonal agument which is much simplker to understand.

it is based on the fact that if S = the positive integers, then there is a 1-1 correspondence between subsets of S and infinites equences of 0's and 1's.

I.e. the subset {1,4,5,8,...} corresponds to the sequence (1,0,0,1,1,0,0,1,...)

i.e. you put a "1" in each positioin corresponding to an integer in your subset, and put a "0" in entries corresponding to integers not ni your subset. see the resemblance to the earlier proof?

anyway. now consider a map f:N-->P(N) from positive integers to such sequences.

then just list the values of this map in a list, with f(1) in the first rwo, f(2) in the second row,etc...
]
]thus you have an infinite list of infinites equences and you want to produce an infinite sequence that is not in that list.

just form your sequence as follows: start with the interger, either "0" or "1", different from whatever appear first in the first row. then next put whatever i NOT the second element of the second row,...i.e. write down the "diagonal" sequence foprmed by yopur list, and then change every entry to the other choice. If the diagonal sequence is (0,0,1,1,0,1,0,...)

th change it to (1,1,0,0,1,0,1,...).then this sequence differs from everys equence in your list, namely it differs from the nth sequence at least in the nth place.

this proof shows there are more infinite decimals, i.e. real numbers, than there are positive integers.

the weird proof above about subsets is an abstraction of this nice simple argument, as mathematicians are won't to do.

 

[kidsmoker]

Okay yeah, I can see why my proof above is wrong. I still think my train of thought is correct though.

No matter how you define the map, the power set of [tex]X = \left\{x_{1}, x_{2},..., x_{n} \right\}[/tex] will always contain subsets [tex]\left\{x_{1} \right\}[/tex] , [tex]\left\{x_{2} \right\}[/tex] , ... , [tex]\left\{x_{n} \right\}[/tex] and also the empty set [tex]\emptyset[/tex]. So there's always going to be at least one more element in P(X) than in X, hence no map [tex]X \rightarrow P(X)[/tex] can be surjective. That was more what I was trying to say. Is that still wrong though?

Thanks.

 

[HallsofIvy]

But the same argument would show that there cannot be a surjection from N to Z (positive integers to all integers): but there is: let f(n)= n if n is an even number, f(n)= -(n+1)/2 if n is odd.

Saying that there cannot be a surjection from A to B if B "has more members" than A only works for finite sets.

 

[kidsmoker]

Ah yeah, I hadn't thought about it like that.

I've re-read the proof in my notes and understand it better now. Thanks!

 

[mathwonk]

it is tricky. just because there does exist ONE injective map that is not surjective, does NOT imply that NO injective map can be surjective (for infinite sets).

I apologize for shouting.

this stuff takes a while to master, i believe cantor was actually burned at the stake for publishing this stuff, or maybe drowned publicly.

or was that the first woman to cure a sick child in new england?

to this day if you try to order wine from out of state in massachusetts i believe you are publicly whipped.

 

[HallsofIvy]

And rightly so!

(I am told that you cannot buy Jack Daniels whiskey at the distillery because it is in a dry county!)