1
$\begingroup$

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?

$\endgroup$
5
  • 5
    $\begingroup$ Even if $A$ is finite? empty? But if $A$ is infinite it already contains a subset equivalent to $\mathbb N$. $\endgroup$
    – lulu
    Apr 14, 2019 at 13:00
  • $\begingroup$ 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)$... $\endgroup$
    – davideleo
    Apr 14, 2019 at 13:14
  • $\begingroup$ What's unclear about consider the cardinalities of finite sets? $\endgroup$
    – Asaf Karagila ♦
    Apr 14, 2019 at 13:15
  • 2
    $\begingroup$ 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. $\endgroup$
    – Andrés E. Caicedo
    Apr 14, 2019 at 13:18
  • $\begingroup$ Each element of that countably infinite subset is an element of $\mathscr P(A)$. $\endgroup$
    – lulu
    Apr 14, 2019 at 13:22

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ 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.. $\endgroup$
    – davideleo
    Apr 14, 2019 at 15:34
  • 2
    $\begingroup$ @Davide: The axiom of choice is not needed to prove this. A set is infinite if and only if it has arbitrarily large finite sets. $\endgroup$
    – Asaf Karagila ♦
    Apr 14, 2019 at 15:40
  • $\begingroup$ If you want, you can prove that more rigorously by induction. $\endgroup$
    – Mark Kamsma
    Apr 14, 2019 at 16:08
  • $\begingroup$ 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. $\endgroup$
    – davideleo
    Apr 14, 2019 at 16:08
  • 2
    $\begingroup$ @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$. $\endgroup$
    – Asaf Karagila ♦
    Apr 14, 2019 at 16:30

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.