# Prove a function existence

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.

## 1 Answer

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.

• Well, one lucky singleton can get to be the image of $\varnothing$ ... – Henning Makholm Nov 26 '17 at 21:40
• @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. – Stefan Mesken Nov 26 '17 at 21:41
• Nice proof, thank you ! – Yariv Levy Nov 26 '17 at 22:05
• @YarivLevy You're welcome. – Stefan Mesken Nov 26 '17 at 22:10