# Surjection from a powerset onto $\Bbb{N}$ is always possible

I found this answer that I can't quite understand: https://math.stackexchange.com/a/1296795/431135

It says that, for any infinite set $$A$$, there is always a surjection from $$\cal{P}(A)$$ onto $$\Bbb{N}$$. In particular, without using the Axiom of Choice.

Any sub-hint on how to see this hint?

• Even if $A$ is finite? empty? But if $A$ is infinite it already contains a subset equivalent to $\mathbb N$.
– lulu
Apr 14, 2019 at 13:00
• Right @lulu, I had to specify $A$ infinite. And ok, $A$ has at least a subset in bijection with $\Bbb N$, but then that's just an element of $\cal{P}$$(A)$... Apr 14, 2019 at 13:14
• What's unclear about consider the cardinalities of finite sets? Apr 14, 2019 at 13:15
• The point of Asaf's comment is that, provably in ZF, if $A$ is infinite, then for any finite $n$, $A$ has a subset of size $n$. Perhaps you may want to prove this first. Apr 14, 2019 at 13:18
• Each element of that countably infinite subset is an element of $\mathscr P(A)$.
– lulu
Apr 14, 2019 at 13:22

To avoid using the axiom of choice, define a map $$f\colon P(A) \to \mathbb{N}$$ by $$f(S) = n \iff |S| = n.$$ Since $$A$$ is infinite, it has subsets of all finite cardinalities. Thus $$f$$ is surjective.
• I like this explicit function, but are you entirely sure you're not using the axiom of choice? Since $A$ is infinite, then it is not in bijection with any $n\in \Bbb{N}$. Does this mean that for each $n$ there's a subset of $A$ of size $n$? It feels like there is an hidden choice function there.. Apr 14, 2019 at 15:34
• My definition of infinite set is "a set not in bijection with any $n\in\Bbb{N}$". Which I guess I can interpret as "for any $n$ I can inject $n$ into my infinite set". Thanks, I think now I convinced myself, I just never thought of a way to show an intuitively obvious fact like this. Apr 14, 2019 at 16:08
• @Davide: Induction. If $A$ is infinite and $B$ is a subset of $A$ of size $n$, then because $A$ is infinite $A\neq B$. Choose $a\in A\setminus B$, then $B\cup\{a\}$ has $n+1$ subsets. We didn't use AC because we were given $A$ and only made one choice, $a$. Apr 14, 2019 at 16:30