0

$\mathcal{P}(\mathbb{Z}_+)$ is the power set of the positive integers. I know the general way to prove a set is denumerable is to find a bijective function between that set and the positive integers, but I'm not sure how to write something that does that without assuming $P$ is already denumerable. Can anyone offer a solution?

JKEG
  • 2,517
IgnorantCuriosity
  • 1,423
  • It's enough to make an injective function from $P$ into a set that you know is denumerable, for instance into ${\mathbb N}$. – Magdiragdag Nov 29 '16 at 23:15
  • 1
    A standard trick is writing a set as a countable union of countable sets. – JonathanZ Nov 29 '16 at 23:28
  • @user275313 I think that leads me into the same problem I'm unable to get past now. Each element of P is a countable set because it is finite. But I'm not sure how to show that the "number" of sets in P is countable. – IgnorantCuriosity Nov 30 '16 at 00:20
  • @Magdiragdag Why would an injective function alone prove that P is denumerable? – IgnorantCuriosity Nov 30 '16 at 00:21

1 Answers1

0

For each set $X$ in $P$, define the "height" of $X$ to be the number of elements in $X$ plus the sum of all elements in $X$. The height is a positive integer (or $0$ for the empty set) because $X$ is finite. Moreover, it is not too hard to check that for every positive integer $h$, there are only finitely many sets with height $h$. Therefore we can list all sets of height $0$, followed by all sets of height $1$ (actually, there aren't any), followed by all sets of height $2$ and so on, thus giving a list of all sets in $P$. Therefore $P$ is denumerable.

The list might begin $$\eqalign{ &\varnothing\,,\ \{1\}\,,\ \{2\}\,,\ \{3\}\,,\ \{1,2\}\,,\ \{4\}\,,\ \{1,3\}\,,\ \{5\}\,,\ \{1,4\}\,,\ \{2,3\}\,,\ \{6\}\cr &\color{red}{\,0\ \ \ \ \ \,2\ \ \ \ \ \ \ 3\ \ \ \ \ \ \ 4\ \ \ \ \ \ \ \ \ 5\ \ \ \ \ \ \ \ \,5\ \ \ \ \ \ \ \ \ 6\ \ \ \ \ \ \ \ 6\ \ \ \ \ \ \ \ \ 7\ \ \ \ \ \ \ \ \ \ 7\ \ \ \ \ \ \ \ \ 7}\cr}$$ where for each set I have also given the height in red.

David
  • 82,662