4
$\begingroup$

I am fighting with an exercise of set theory. There is given a hint to it, but i can't totally understand it, because i am stuck in the first part of it... May i ask you a for little help, please?

Given is $P_{f}(\mathbb{N})\subset P(\mathbb{N})$, where $P_{f}(\mathbb{N})=\left \{ I\subset \mathbb{N}\mid I\, is\, finite \right \}$, defines the power set of $\mathbb{N}$, consisting only of all finite subsets. The idea of the exercise is to show that there exists a bijection between $P_{f}(\mathbb{N})$ and $\mathbb{N}$.

For this exercise i have the following hint. I have to consider the set of the prime numbers $\mathbb{P}$ and $\mathbb{P\, '}\subset \mathbb{P}$, the set of all non zero powers of prime numbers.

a) Consider a set $A\subset \mathbb{N}$, which is infinite. Show that there is a bijective map $g_{A}:A\rightarrow \mathbb{N}$ with $g_{A} (a)=card(A\cap [0,a])$.

So, i know that $A$ as a subset of countable set should be also countable. Then from this follows that the map $g_{A}$ must be injective. It is also surjective, because $A$ is a subset of $\mathbb{N}$. Is this correct? I said nothing about the cardinality of the both subsets...the problem is, that they are both infinite. Intuitively, i think that $\left | A \right |\leq \left | \mathbb{N} \right |$, because both are infinite and contain only natural numbers.

b) Use (a) to show that there is a bijection $\tau :P_{f}(\mathbb{P}\, ')\rightarrow P_{f}(\mathbb{N})$.

Ok, here is clear that it's true, because $P_{f}(\mathbb{P}\, ')\subset P_{f}(\mathbb{N})$ and $\mathbb{P}\, '\subset \mathbb{N}$, both infite sets, because we know by Euclid that the prime numbers are infinitely many.

c) Show that the map $P_{f}(\mathbb{P}\, ')\rightarrow \mathbb{N}$, sending a finite subset $I\subset \mathbb{P}\, '$ to the number $\prod_{q\in I}q$ is a bijection.

Here i intuitively understand what do they mean. I have to use the prime factorization of the numbers, but how to formulate it i am not sure.

Clearly from (c) should follow that there is a bijection between $P_{f}(\mathbb{N})$ and $\mathbb{N}$.

Can anybody help me with this proof? I would be glad to read your remarks, if you have some. Thanks in advance!

$\endgroup$

2 Answers 2

3
$\begingroup$

Here's how I would do it:

There is an obvious injective map from $\mathbb N$ to $\mathcal P_f(\mathbb N)$.

There is a slightly less obvious injective map the other way: $\{n_1, n_2, n_3, \dotsc, n_k\} \mapsto 2^{n_1}3^{n_2}\dotsb p_k^{n_k}$ where $n_1 < n_2 < \dotsb < n_k$ and $p_i$ denotes the $i$th prime. Injectivity follows from the fundamental theorem of arithmetic.

Now apply Cantor–Bernstein–Schroeder.

$\endgroup$
1
$\begingroup$

I did this counting as part of my bachelor's thesis a few years back. My proof goes in a different direction, but maybe it'll give you some insight.

First of all, define $P_n(\Bbb N) = \{I\subset \Bbb N|\: |I| = n\}$. Every such set is countable, since it's no larger than $\Bbb N^n$ (there is an injection $\iota:P_n(\Bbb N)\to \Bbb N^n$ given by taking an element $I$, sorting its elements and see it as a vector).

Note that we have $P_f(\Bbb N) = \bigcup_n P_n(\Bbb N)$.

Since every $P_n(\Bbb N)$ is countable, index each of them. Now, to index the elements $I_i \in P_f(\Bbb N)$, let $I_1$ be the first element of $P_1(\Bbb N)$, $I_2$ the first element of $P_2(\Bbb N)$, and $I_3$ the second element of $P_1(\Bbb N)$. Now for $I_4$, take the first element from $P_3(\Bbb N)$ and so on, going in a triangular manner. Every element of any $P_n(\Bbb N)$ will eventually be reached by this procedure, and thus we have indexed all elements of $P_f(\Bbb N)$.

PS. I realized toward the end that I had forgotten the empty set, but you know the story of Hilbert's hotel, right?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .