Transfinite Series Rearrangement

If a series $\sum_{n=0}^\infty a_n$ is absolutely convergent — that is, if $\sum_{n=0}^\infty |a_n|$ converges — then you can rearrange its terms however you want, and its value will not change. I will call this the “absolute rearrangement theorem”.

This may seem like the most obvious fact ever. After all, addition is commutative, so of course the value doesn’t change when you rearrange the terms! If that’s what you’re thinking, then this video by Morphocular will blow your mind. It explains that, if the series is conditionally convergent — that is, if $\sum_{n=0}^\infty a_n$ converges but $\sum_{n=0}^\infty |a_n|$ diverges — then you really can change the value by rearranging the terms. In fact, you can rearrange the series to make it converge to any value you want!

With that in mind, the absolute rearrangement theorem seems a little less obvious. But obvious or not, it’s true, and you can find proofs on the internet. So you can rest assured that you can rearrange absolutely convergent series however you want.

… or so I thought. I recently came across a situation where the usual definition of rearranging a series “however you want” did not, in fact, allow me to rearrange the series however I wanted. In this post, I’ll share how this conundrum finally provided me with a concrete use for one of the most fascinating topics ever: transfinite ordinals.

What is a rearrangement?

In order to understand the problem, we first need to see the usual definition of a rearrangement.

Definition: A rearrangement of a series $\sum_{n=0}^\infty a_n$ is a series of the form $\sum_{n=0}^\infty a_{f(n)}$, where $f$ is a bijection from $\mathbb{N}$ to $\mathbb{N}$.

Basically, the bijection $f$ rearranges the natural numbers, and then we apply that rearrangement to our series by summing $a_{f(n)}$ instead of $a_n$. Hopefully this is pretty intuitive. It definitely seems like a reasonable way to formalize the concept of rearranging a series.

We can use this definition to prove the absolute rearrangement theorem. Feel free to expand “The Proof” below to see my proof if you’re curious, but it’s not needed to understand the rest of the post. (The video I linked earlier is probably a more intuitive proof, especially if you aren’t familiar with analysis. But I wrote this before seeing the video, and I barely survived programming the expandable/collapsible element, so the sunken cost fallacy tells me to keep my proof here!)

So we have a seemingly perfect definition of a rearrangement, and we’ve proven that the absolute rearrangement theorem holds for it. Let’s see a quick example of a rearrangement to make sure we understand it.

An example of a rearrangement

We might rearrange $\sum_{n=0}^\infty a_n$ by adding one odd term, then two even terms, then one odd term, then two even terms, and so on. That would look like

$${\color{red} a_1} + {\color{blue} a_0} + {\color{blue} a_2} + {\color{red} a_3} + {\color{blue} a_4} + {\color{blue} a_6} + {\color{red} a_5} + {\color{blue} a_8} + {\color{blue} a_{10}} + \cdots.$$

I’ve colored the odd terms red and the even terms blue to make the pattern more clear. We can start thinking about what the bijection $f$ is. (Note that I’ll be counting starting from $0$, rather than $1$.)

• Since $a_1$ moved to position $0$, we have $f(0) = 1$.
• Since $a_0$ moved to position $1$, we have $f(1) = 0$.
• Since $a_2$ stayed in position $2$, we have $f(2) = 2$.
• Since $a_{10}$ moved to position $8$, we have $f(8) = 10$.

We can actually find a formula for the entire function function:

$$f(n) = \begin{cases} \frac{2n}3 + 1, & \text{$n$ is divisible by $3$},\\ 2\left(\left\lfloor \frac n3 \right\rfloor + \left\lfloor \frac{n+1}3 \right\rfloor\right), & \text{$n$ is not divisible by $3$}. \end{cases}$$

Okay, maybe not the most intuitive formula ever, but don’t worry about it. The point is, there is a function $f$, and it is a bijection, so this is a rearrangement. Therefore, the absolute rearrangement theorem tells us that it is safe to do this rearrangement as long as the series is absolutely convergent. That’s useful, because this is the exact kind of rearrangement that could alter the value of a conditionally convergent series.

Rearrangements that aren’t rearrangements

Now let’s rearrange $\sum_{n=0}^\infty a_n$ in a different way: Let’s sum all of the even terms first, and then sum all of the odd terms.

$$(a_0 + a_2 + a_4 + a_6 + \cdots) + (a_1 + a_3 + a_5 + a_7 + \cdots).$$

This certainly seems like it should count as a rearrangement. After all, we’re adding each term exactly once. But things start to go wrong when we try to think about what the bijection $f$ is.

• $a_0$ stayed in position $0$, so $f(0) = 0$.
• $a_2$ moved to position $1$, so $f(1) = 2$.
• $a_4$ moved to position $2$, so $f(2) = 4$.
• $a_1$ moved to position… infinity?

Since $a_1$ comes after infinitely many terms, there is no natural number that could represent its position! We used up all the natural numbers on the even terms; $f(n) = 2n$ for all $n \in \mathbb{N}$. Therefore there is no bijection $f : \mathbb{N} \to \mathbb{N}$ that represents this rearrangement.

So this is not a rearrangement, as per our definition. And that means that the absolute rearrangement theorem doesn’t apply to it. To be fair, this ordering isn’t really a single series. You need two series to express it:

$$\sum_{n=0}^\infty a_{2n} + \sum_{n=0}^\infty a_{2n + 1}.$$

But still, this feels like it should be a rearrangement, right? We just happen to be arranging all the even terms before all the odd terms.

It gets worse.

Alright, I’m sure it’s not too hard to extend the absolute rearrangement theorem so that it applies to orderings that partition the series into two series, like the one we just saw. But we still wouldn’t be covering every conceivable reordering. For example, what if our reordering partitioned the series into three series?

$$\sum_{n=0}^\infty a_{3n} + \sum_{n=0}^\infty a_{3n+1} + \sum_{n=0}^\infty a_{3n+2},$$

This is a situation that we still haven’t covered. Well, no big deal. We could just use our hypothetical two-partition theorem twice. And if we wanted to prove the absolute rearrangement theorem for some higher number of partitions, we could use induction on the number of partitions.

But we still wouldn’t have proved it for every conceivable reordering. What if we reordered the series in such a way that it split into infinitely many series? Such an ordering is possible! For example, we could arrange the terms in a two-dimensional array like this:

$$\def\arraystretch{1.5} \begin{array}{llllll} \quad a_{0 } & +\ a_{2 } & +\ a_{5 } & +\ a_{9 } & +\ a_{14} & +\ \cdots \\ +\ a_{1 } & +\ a_{4 } & +\ a_{8 } & +\ a_{13} & +\ a_{19} & +\ \cdots \\ +\ a_{3 } & +\ a_{7 } & +\ a_{12} & +\ a_{18} & +\ a_{25} & +\ \cdots \\ +\ a_{6 } & +\ a_{11} & +\ a_{17} & +\ a_{24} & +\ a_{32} & +\ \cdots \\ +\ a_{10} & +\ a_{16} & +\ a_{23} & +\ a_{31} & +\ a_{40} & +\ \cdots \\ \quad\vdots & \quad\vdots & \quad\vdots & \quad\vdots & \quad\vdots & \quad\ddots \end{array}$$

Then each row is an infinite sum, and there are infinitely many rows. The formula for adding up all the rows is

$$\sum_{n=0}^\infty \sum_{m=0}^\infty a_{m + \frac12(n+m)(n+m+1)}.$$

If we wanted the absolute rearrangement theorem to hold for a nested sum like this, we would need yet another proof. This would be a generalization of Fubini’s theorem, which states that you can swap the order of summation if the double sum is absolutely convergent.

If we could prove the absolute rearrangement theorem for double sums, then we could use induction to prove it for triple sums, quadruple sums, and so on. Then would we have covered every possible reordering?

No! We could reorder the series into an infinitely nested series!

$$\cdots \sum_{n_2=0}^\infty \sum_{n_1=0}^\infty \sum_{n_0=0}^\infty a_{g(n_0, n_1, n_2, \dots)}.$$

This is getting crazy. It takes a bit of care to even define what this means. We can consider this to be the limit as the number of nestings increases, so at every step only finitely many indexes $n_k$ are nonzero. The function $g$ is a bijection between the set of sequences of natural numbers with finitely many nonzero terms, and the natural numbers. (Such a bijection exists since both sets are countable.)

Alright, don’t worry if you didn’t follow that. The point is just to show how convoluted our rearrangements could be. But if we had proved the absolute rearrangement theorem for a crazy arrangement like this, then surely we would have covered every conceivable rearrangement, right? Still no. We can go much further. However the expression wouldn’t fit on your screen, and it hurts my head to think about it, so we’ll leave it here.

No matter how far we go, it would always be possible to go further. So now that we see how incomplete our first definition of a rearrangement was, how can we really prove the absolute rearrangement theorem for every rearrangement? How can we even define what a rearrangement is?

Transfinite ordinals!

A long time ago, I watched a Vsauce video called How To Count Past Infinity. If you haven’t seen it already, you should definitely watch it, it’s fantastic. He explains all things infinity: countable and uncountable sets, Cantor’s diagonal argument, cardinals vs. ordinals, etc…

I had no idea what he was talking about.

Since then, though I haven’t had any formal education on this stuff, I’ve spent quite a bit of time thinking and reading about it, and my understanding has improved quite a bit. I now only mostly don’t understand it. One of the most fascinating but perplexing concepts is the transfinite ordinals. These things are so cosmically enormous that I just can’t fit them into my understanding. So naturally, I’ll try to explain them in a few paragraphs.

To $\omega$ and beyond!

Ordinals are numbers which represent the order of things. First, second, third, and so on. (I’ll include “$0$th” too.) So far there’s nothing special. These are just the natural numbers you know and love:

$$0, 1, 2, 3, 4, 5, 6, \dots$$

Now, transfinite ordinals are what we get when we think of things that happen after an infinite list of things. So we axiomatically decree that there is a new number, $\omega$, which represents the first thing that happens after the infinite sequence. So now our list of ordinals looks like this:

$$0, 1, 2, 3, 4, 5, \dots, \omega.$$

But another property of ordinals is that every ordinal has a successor; a number which directly follows it. So after $\omega$ we have $\omega+1$, then $\omega+2$, and so on.

$$0, 1, 2, 3, 4, 5, \dots, \omega, \omega+1, \omega+2, \omega+3, \dots$$

Now we have an infinite sequence that happens after an infinite sequence. But wait, there’s more! What if something else happens after all the ordinals listed here? This would be the $\omega\!\cdot\!2$th event. Then the next ordinal would be $\omega\!\cdot\!2 + 1$, followed by $\omega\!\cdot\!2 + 2$, and so on. Then after that infinite sequence would be $\omega\!\cdot\!3$. Then after another infinite sequence would be $\omega\!\cdot\!4$, and so on.

But what if something happens after all the ordinals $\omega, \omega\!\cdot\!2, \omega\!\cdot\!3, \dots$? That would be the $\omega^2$th event. Then eventually would come $\omega^3$, and then we would eventually get to $\omega^4$, and so on, all the way up to $\omega^\omega$. And it doesn’t stop there. There’s $\omega^{\omega^\omega}$, and $\omega^{\omega^{\omega^\omega}}$, and so on, forever. Even after an infinitely nested power tower of $\omega$s, there are more ordinals, though mathematicians had to invent new notation to represent them.

It’s really mind-boggling stuff, for me at least. No matter how high up the ordinal mountain I try to climb, there are more ordinals that fly above my conceptualization. I think that part of my difficulty has been because these numbers don’t seem to describe anything tangible. Sure, you can use them to kill make-believe hydras, and if you sprinkle in a bit of black magic you can proof that every Goodstein sequence terminates. But I never felt like there was any concrete process which the ordinals really represented. Until now!

The ordinals describe our rearrangements!

Let’s look back at our first example of a reordering that was not a valid rearrangement:

$$(a_0 + a_2 + a_4 + a_6 + \cdots) + (a_1 + a_3 + a_5 + a_7 + \cdots).$$

Remember, the killer question was, “which position is $a_1$ in?” Since it comes after an infinite sequence, its position is not described by any natural number. But now we have ordinals! $a_1$ is the first item after an infinite sequence. That’s exactly what it means to be the $\omega$th item! Then $a_3$ is in position $\omega + 1$, and $a_5$ is in position $\omega + 2$, and so on. In general, $a_{2n+1}$ is in position $\omega + n$. We can now write down the position of every single term. Thus, we can describe this rearrangement with all the ordinals less than $\omega\!\cdot\!2$.

So let’s pretend that we can sum over sequences indexed by the ordinals. Then we can write this rearrangement as a single summation:

$$\sum_{n=0}^\infty a_{2n} + \sum_{n=0}^\infty a_{2n+1} = \sum_{n < \omega\cdot2} a_{f(n)},$$

$$\text{where} \ f(n) = \begin{cases} 2n, & n < \omega,\\ 2m + 1, & n = \omega + m. \end{cases}$$

This time, unlike in the original definition of rearrangements, this function $f$ is not a bijection from $\mathbb{N}$ to $\mathbb{N}$. Rather, it’s a bijection from the set of ordinals less than $\omega\!\cdot\!2$ to $\mathbb{N}$. (In set theory, each ordinal is defined as the set of all ordinals less than it. This means that $\mathbb{N} = \omega$, so we can actually say that $f$ is a bijection from $\omega\!\cdot\!2$ to $\omega$.)

---

This would also work with the triple sum:

$$\sum_{n=0}^\infty a_{3n} + \sum_{n=0}^\infty a_{3n+1} + \sum_{n=0}^\infty a_{3n+2} = \sum_{n < \omega\cdot3} a_{f(n)},$$

$$\text{where } f(n) = \begin{cases} 3n, & n < \omega,\\ 3m + 1, & n = \omega + m,\ m < \omega,\\ 3m + 2, & n = \omega\!\cdot\!2 + m. \end{cases}$$

This time, $f$ is a bijection from $\omega\!\cdot\!3$ to $\omega$.

---

It even works with the nested sums:

$$\sum_{n=0}^\infty \sum_{m=0}^\infty a_{m + \frac12(n+m)(n+m+1)} = \sum_{n < \omega^2} a_{f(n)},$$

$$\quad \text{where } f(\omega\!\cdot\!j + i) = i + \frac12(j+i)(j+i+1).$$

Here $f$ is a bijection from $\omega^2$ to $\omega$.

---

And yes, even that ridiculous infinitely-nested sum can be expressed as a single sum:

$$\cdots \sum_{n_2=0}^\infty \sum_{n_1=0}^\infty \sum_{n_0=0}^\infty a_{g(n_0, n_1, n_2, \dots)} = \sum_{n < \omega^\omega} a_{f(n)},$$

$$\text{where } f(\cdots + \omega^2\!\cdot\!n_2 + \omega\!\cdot\!n_1 + n_0) = g(n_0, n_1, n_2, \dots).$$

For this one, $f$ is a bijection fom $\omega^\omega$ to $\omega$.

---

I always struggled to understand what ordinals actually represent. But by stumbling into this rearrangement problem, I ran into exactly the type of thing that they represent! Ordinals let us cleanly express every conceivable reordering with a single sum. So let’s redefine rearrangements using ordinals:

Definition: A (new and improved) rearrangement of a series $\sum_{n=0}^\infty a_n$ is a series of the form $\sum_{n<\mu} a_{f(n)}$, where $\mu$ is an ordinal and $f$ is a bijection from $\mu$ to $\omega$.

Now if we could prove the absolute rearrangement theorem for this definition of a rearrangement, we really would be covering every rearrangement that I could possibly think of!

Does this actually work?

Wait a second. I just started writing things like

$$\sum_{n < \omega^\omega} a_{f(n)}$$

as if it’s just something you’re allowed to do. But does this actually make sense?

Yes! This is a well-defined concept. The Wikipedia page for Series defines these well-ordered sums using transfinite recursion, which is an extension of recursive formulas into the transfinite ordinals. This definition does indeed coincide to all the nested sum expressions above.

Finally, let’s not forget the question we started with: Does the absolute rearrangement theorem hold for transfinite series? The answer is again yes! Before I realized there was any connection with transfinite ordinals, I posted this question on Math Stack Exchange. A helpful user informed me that there is actually a way to define sums that has nothing to do with the order of the terms. With that knowledge, I was able to answer my question using transfinite induction. So, if I didn’t make any mistakes, you really can rearrange absolutely convergent series however you want.

---

Alright, that’s it! This post ended up being a lot longer than I thought it would be. I guess it just goes to show the lengths I will go to to procrastinate from making videos! Hopefully this is as interesting to you as it is to me.