3

I'm trying to prove this function is injective:

$$f:P(\mathbb N)\to \mathbb R, f(M)=\sum_{n\in M}3^{-n}$$

I've already proved that this function is well-defined but I couldn't prove this function is injective. Even to the case $|M|=2$, I found difficult, I think I didn't catch the essense of what means this function be injective.

I need help

Thanks in advance

user42912
  • 23,582
  • I'm not sure what you mean by "proving that the function is well-defined". The function is given by a concrete recipe on each $M$, so there is nothing to check regarding its definition. – Martin Argerami May 17 '14 at 00:38
  • It's injective because the base-$3$ expansion of a real number is unique (unique enough for our purposes, anyway). I would have made this an answer, but now I think of it I've never seen a proof of that... – Jack M May 17 '14 at 00:43
  • 1
    @MartinArgerami That's not true, strictly speaking. The sum could diverge, or the sum's value could depend on the summation order. – fgp May 17 '14 at 00:43
  • @MartinArgerami I agree with you – user42912 May 17 '14 at 00:43
  • @fgp: good point. – Martin Argerami May 17 '14 at 00:47
  • @JackM: you could start proving it for base 10 instead of base 3 :D – Martin Argerami May 17 '14 at 00:48
  • @fgp Why the sum's value doesn't depend on the summation order when $M$ is infinity? – user42912 May 17 '14 at 12:32
  • @user42912 Because all the summands are positive, and thus if the sum converges at all (which it does), it converges absolutely. That suffices to guarantee that the order is irrelevant. – fgp May 17 '14 at 21:01

2 Answers2

3

Let $M_1$ and $M_2$ be distinct subsets of $\mathbb{N}$. We need to show that $f(M_1)\ne f(M_2)$.

Let $m$ be the smallest integer which is in one of $M_1$ or $M_2$, but not in the other. We may assume that $m\in M_1$.

Note that $$f(M_1)-f(M_2)\ge \frac{1}{3^m} -\sum_{m+1}^\infty \frac{1}{3^i}.$$ By the formula for the sum of a geometric series, $\sum_{m+1}^\infty \frac{1}{3^{i}}=\frac{1}{2\cdot 3^m}$, so $f(M_1)-f(M_2)$ is positive.

Remark: There is less to this than meets the eye. Our sums are the base $3$ expansions of certain reals, and base $3$ expansions that avoid the "trit" $2$ are unique.

André Nicolas
  • 507,029
0

Injective means that different choice of $M$ will always produce different numbers. Suppose that $$ \sum_{n\in M}3^{-n}=\sum_{n\in N}3^{-n}. $$ Let $k=\min\{n:\ n\in M\setminus N\ \text{ or }n\in N\setminus M\}$. This means that $\{1,\ldots,k-1\}\subset M\cap N$. Thus the all the terms with $n<k$ of the sums are equal. So $$ \sum_{n\in M,\ n\geq k}3^{-n}=\sum_{n\in N,\ n\geq k}3^{-n}. $$

Assume that $k\in M$ and $k\not\in N$ (otherwise we exchange roles). Then $$ 3^{-k}+\sum_{n\in M,\ n\geq k+1}3^{-n}=\sum_{n\in N,\ n\geq k+1}3^{-n}. $$ That is $$ 3^{-k}=\sum_{n\in N,\ n\geq k+1}3^{-n}-\sum_{n\in M,\ n\geq k+1}3^{-n} \leq\sum_{n=k+1}^\infty3^{-n}=\frac{3^{-k-1}}{1-1/3}=\frac{3^{-k}}2. $$ We got to a contradiction, that shows that our $k$ cannot exist. So $M=N$.

Martin Argerami
  • 205,756