Trying to find a flaw in my proof that there are more rearrangements of an infinite series than real numbers

Consider the function $F\colon\Bbb{N\to N}$ defined by: $$F(n)=\begin{cases} 0 & n=0\\ n-1 & n>0\end{cases}$$ by your argument, since this function is not a bijection (clearly $F(0)=F(1)$ so it is not injective), $\Bbb N$ is not the same size as $\Bbb N$.


What just happened? You've proved, as I did above, there is a surjective function which is not injective. But that doesn't prevents a different function to be a bijection.

Cantor's diagonal works by showing that any function is not surjective, and therefore there are no bijections. But you've only showed that one function is not injective, and concluded that there are no bijections.

You have to remember: Infinite sets are very different from finite sets. Just because one function is a surjection which is not a bijection doesn't mean there a different one is not.

Here's an injective function from the rearrangements into the reals:

Let $f\colon\Bbb{N\to N}$ be the permutation describing the rearrangement. Namely, $f(n)=k$ if and only if the $k$th summand is $\frac1n$ (up to a sign, if you prefer). Map the rearrangement given by $f$ to the real number given by: $$\sum_{n\in\Bbb N}\frac2{3^{2^n\cdot 3^{f(n)}}}$$

This sum converges, and you can quite easily show that if $f\neq g$, then there is some $n$ such that $f(n)\neq g(n)$ and therefore one of the digits in the trenary expansion of the two reals is different, and since those are only $0$ or $2$ this means that the real numbers are different. Therefore the map from rearrangements into the real numbers given above is injective.

On the other hand, you can easily show that there are at least $2^{\aleph_0}$ rearrangements, but I will leave this to you as an exercise.


As explained in the comments, what you've done is whip up a non-injective surjection from $\mathbb{S}$ to $\mathbb{R}$. This alone doesn't prove the statement in question, however - just because one surjection isn't injective doesn't mean that there isn't some other surjection which is injective.

This is a fundamental difference between the infinite and finite cases. If $A$ and $B$ are finite sets and $f:A\rightarrow B$ is a non-injective surjection, then $A$ does in fact have greater cardinality than $B$. But this fails for infinite sets: consider for example the map from naturals to naturals given by $$x\mapsto \left\lfloor{x\over 2}\right\rfloor$$ (where "$\lfloor\cdot\rfloor$" is the floor function). This is a non-injective surjection; should we conclude that $\lvert\mathbb{N}\rvert>\lvert\mathbb{N}\rvert$? You can easily whip up other examples to drive the point home.

Indeed, $\mathbb{R}$ and $\mathbb{S}$ have the same cardinality. Matt Samuel's comment has suggested an explanation: that the set $\mathbb{N}^\mathbb{N}$ of maps from naturals to naturals - or equivalently, infinite sequences of natural numbers - has cardinality at least that of $\mathbb{S}$, and so we'll be done if we can find an injection from $\mathbb{N}^\mathbb{N}$ to $\mathbb{R}$. We can do this by "coding into the binary expansion" - think about how the real number $$0.\color{red}{00}1\color{red}{0000}1\color{red}{000}1\color{red}{0}1...$$ corresponds to the sequence $$2,4,3,1,....$$ Do you see how to turn this into an honest-to-goodness injection?


Incidentally, while it doesn't make a difference in the context of the axiom of choice (which tells us that given a surjection $A\rightarrow B$ we can find an injection $B\rightarrow A$), it will ultimately be better to think of cardinality in terms of injections rather than surjections: $\lvert A\rvert\ge\lvert B\rvert$ iff there is an injection $B\rightarrow A$, not iff there is a surjection $A\rightarrow B$. It's not immediately obvious that this is a better notion when choice fails, but it really does turn out to be the right one.


While you showed $|\mathbb{R}| \leq |\mathbb{S}|$ properly by constructing a surjection, the problem with your proof of $|\mathbb{R}| \neq |\mathbb{S}|$ is that it merely shows that the particular kind of map you are trying to construct cannot be a bijection. For the proof to be valid, it would need to show that any map from $\mathbb{S}$ to $\mathbb{R}$ is not a bijection.