Mfcttrf

So I had this thought that I was trying to prove as an exercise

Let $mathbbR$ be the set of real numbers and let $mathbbS$ be the set of all possible rearrangements of the alternating harmonic series. Prove that $|mathbbR| < |mathbbS|$

I thought I had a proof of this, but I then posted it to Reddit /r/math only to be downvoted and told the proof was wrong. The only comment I received was to "look at it from the other direction", but that confused me.

Here is my proof:

Two sets have the same cardinality iff there exists a bijection between them.

From the rearrangement theorem we can show that a the alternating harmonic series can converge to any real number via the following algorithm:

Start with $1$, if this is larger than the target number add the next negative term, otherwise add the next positive term. We create a mapping from the created rearrangement to the limit of this rearrangement. Notice that this maps to all real numbers.

Now take one of the series that we had, and switch the first two terms. This is a new rearrangement since it does not begin with $1$, so it should be mapped to a new real number. However all real numbers have already had a rearrangement mapped to them. As such we have two rearrangements pointing to a single real number, which means that our mapping is not a bijection.

As such there must be more rearrangements than real numbers.

Now I am not sure where my proof went wrong, so any help would be appreciated!

While you showed $|mathbbR| leq |mathbbS|$ properly by constructing a surjection, the problem with your proof of $|mathbbR| neq |mathbbS|$ 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 $mathbbS$ to $mathbbR$ is not a bijection.

As explained in the comments, what you've done is whip up a non-injective surjection from $mathbbS$ to $mathbbR$. 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:Arightarrow 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 $$xmapsto [xover 2]$$ (where "$[cdot]$" is the floor function). This is a non-injective surjection; should we conclude that $vertmathbbNvert>vertmathbbNvert$? You can easily whip up other examples to drive the point home.

Indeed, $mathbbR$ and $mathbbS$ have the same cardinality. Matt Samuel's comment has suggested an explanation: that the set $mathbbN^mathbbN$ of maps from naturals to naturals - or equivalently, infinite sequences of natural numbers - has cardinality at least that of $mathbbS$, and so we'll be done if we can find an injection from $mathbbN^mathbbN$ to $mathbbR$. We can do this by "coding into the binary expansion" - think about how the real number $$0.colorred001colorred00001colorred0001colorred01...$$ 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 $Arightarrow B$ we can find an injection $Brightarrow A$), it will ultimately be better to think of cardinality in terms of injections rather than surjections: $vert Avertgevert Bvert$ iff there is an injection $Brightarrow A$, not iff there is a surjection $Arightarrow 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.

Consider the function $FcolonBbbNto N$ defined by: $$F(n)=begincases 0 & n=0\ n-1 & n>0endcases$$
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 $fcolonBbbNto 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_ninBbb Nfrac23^2^ncdot 3^f(n)$$

This sum converges, and you can quite easily show that if $fneq 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.

You have shown the cardinality of the real numbers is a lower bound by constructing a surjective map. You can't conclude from the fact that it is not injective that there are more rearrangements, because in order to do that you'd need to be able to show that every map is not injective.

In fact, the cardinality of the set of functions from $mathbb N$ to $mathbb N$ is an upper bound, and that is the same as that of the real numbers. So in fact there are equally many arrangements as real numbers.

In Cantor's diagonal argument, we are given an arbitrary function from the naturals to the real numbers, and the argument provides an algorithm for finding a number that the function doesn't hit. This works because it's not just one function this works for, it is every function. Therefore no function from the naturals to the real numbers is surjective.