Is the set of all rational additive partitions of a rational number countable?

78 Views Asked by At

We usually call additive partitions the set, we call it $P$, of all the ways to write a positive integer $n$ as a sum of positive integers. Formally:

\begin{equation} P_n = \left\{ (a_1 ,...,a_n)\in\mathbb{N}^n:\sum_{0<k\leq n} a_k =n\right\} \quad \forall n\in\mathbb{N} \end{equation}

I was thinking about writing any rational number as a sum of rational numbers, and define the set of rational additive partitions as:

\begin{equation} P_q = \left\{ (p_n)_{n\in\mathbb{N}} :p_n\in\mathbb{Q},\quad\sum_{k>0} p_k =q\right\} \quad \forall q\in\mathbb{Q} \end{equation}

For example, if $q=1$ then the sequences $(\frac{1}{2},\frac{1}{2},0,0,\ldots),(\frac{1}{3},\frac{1}{2},\frac{1}{6},0,0,\ldots),\ldots$ belong to $P_1$, because $\frac{1}{2}+\frac{1}{2}=1, \quad\frac{1}{3}+\frac{1}{2}+\frac{1}{6}=1$ etc...

This set is certainly infinite, but I was wondering if it was countable. My guess is that it is countable $\forall q$, because $\mathbb{Q}$ is countable, but I don't know how to prove it. Any suggestions?

Thanks.

1

There are 1 best solutions below

11
On BEST ANSWER

This set is uncountable. To see this, consider

$$ q=\sum_{\ell=1}^\infty2^{-\ell}q\;. $$

The (infinitely many) terms are rational numbers. Now take the uncountable set of infinite binary sequences (i.e. binary sequences that are not eventually zero). This is uncountable since it essentially corresponds to binary representations of real numbers in $[0,1]$; the restriction to infinite sequences merely excludes the countably many finite sequences. For each such binary sequence $b_k$, traverse the sequence and let $p_k$ be the next term in the above series if $b_k=1$, and $0$ if $b_k=0$. This yields uncountably many different sequences $p_k$ of rational numbers, all of which sum to $q$.