I was just working on some intro problems from an algebra textbook, and one of the proofs I had seemed to make sense to me, but when I compared it to a solution given online, it was seemingly very different and mine seemed to be somewhat of a weak argument. So I am looking for any insight on this, and maybe it will also serve to give me a better understanding of constructing proofs in general.
The question was,
- If $S$ any set, prove that it is impossible to find a mapping of $S$ onto $S^{*}$. (where S* represents the set of all subsets of $S$, i.e. the power set).
Well, what I had wrote was,
From previous proofs we know that if $|S|=n$ then $|S^{*}|=2^{n}$
and in order for some mapping $\sigma:S \to S^{*}$ to be onto, we would require that for any $s^{*} \in S$, we can find some $s \in S$ such that $s \sigma= s^{*}$.
Consider the case that $n=0$, then clearly we cannot choose some $s \in S$ to map to any $s^{*} \in S^{*}$ regardless so it is non issue.
And for any $n \gt 0$, we have that $|S^{*}| \gt |S|$ so it cannot be that we can maintain a valid mapping while satisfying the onto property as it would require some elements in S to be mapped to more then one element in S*.
Does this make sense? And if not, what parts are not good about it?
The answer given, was via contradiction, and basically said let f be any mapping, and showing that f is not onto by constructing an element in S* that is not in the image of any s in S. Which of course seems very nice and valid, but I am trying to understand if one is much more correct/valid etc.
Thanks all for any help/input
The second proof, known as the technique of diagonalization, also works when $S$ is infinite.