Prove or disprove the existence of $f \in P(\Bbb N)\setminus \{\Bbb N\} \rightarrow P(\Bbb N)\setminus \{{\emptyset}\}$ which is surjective (onto) and ${\forall} A \in P(\Bbb N) \setminus \Bbb \{\Bbb N\}.A \subsetneq f(A)$

How can i disprove an existence of a function ?

Intuitively i couldn't think of any function such as, but that's not a mathematical prove.


Such a function cannot exist. In fact, at most singleton can be in the range of such a function.

For suppose that such an $f$ exists. Fix distinct $m, n \in \mathbb N$. Then there are $A,B \subseteq N$ such that $f(A) = \{m\}$ and $f(B) = \{n\}$. Since $$ A \subsetneq \{m\}, $$ it follows that $A = \emptyset$ and by the same reasoning we get that $B = \emptyset$. However $f(A) \neq f(B)$, which is our desired contradiction.

  • $\begingroup$ Well, one lucky singleton can get to be the image of $\varnothing$ ... $\endgroup$ – Henning Makholm Nov 26 '17 at 21:40
  • $\begingroup$ @HenningMakholm Oh, I misread the question and thought that $\emptyset \not \in \mathrm{dom}(f)$ was one of the requirements. I'll edit my answer. $\endgroup$ – Stefan Mesken Nov 26 '17 at 21:41
  • $\begingroup$ Nice proof, thank you ! $\endgroup$ – Yariv Levy Nov 26 '17 at 22:05
  • $\begingroup$ @YarivLevy You're welcome. $\endgroup$ – Stefan Mesken Nov 26 '17 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.