Skip to main content
2 of 4
corrected a typo
Will Brian
  • 18.5k
  • 3
  • 79
  • 106

This answer is an extended comment on the answers of Joel David Hamkins and Paul Larson. Let's say that the rearrangment number $\kappa$ is the smallest cardinality of a family of bijections that can change the value of any conditionally convergent sum. Our goal is to find the value of the rearrangement number in terms of other small cardinals.

Using a nice argument involving "padding with zeroes", Joel shows that $\kappa \geq \mathfrak{p}$. (At least, this is one way of summarizing his answer. The inequality $\kappa \geq \mathfrak{p}$ implies $\kappa$ is uncountable and also that MA proves $\kappa = \mathfrak{c}$, which are the two assertions in Joel's answer; see also Andreas Blass's comment on Joel's answer).

In this answer, I want to show how to take the "padding with zeroes" argument a bit further to show that

  • $\kappa \geq \mathfrak{b}$
  • by itself, Joel's "padding with zeroes" argument cannot prove anything stronger than $\kappa \geq \mathfrak{b}$.

(if you've forgotten what $\mathfrak{b}$ is, I'll define it below; for now just know that $\mathfrak{p} \leq \mathfrak{b}$ is always true and $\mathfrak{p} < \mathfrak{b}$ is consistent, so this inequality improves the former one).

First a few definitions:

  • $A \subseteq \mathbb N$ is preserved by $f: \mathbb N \rightarrow \mathbb N$ if $f$ does not change the order of $A$, except possibly on a finite set. More precisely, $A$ is preserved by $f$ iff there is some cofinite subset $A'$ of $A$ such that $$x < y \qquad \Leftrightarrow \qquad f(x) < f(y)$$ for all $x,y \in A'$.

  • If $A$ is not preserved by $f$, we say that $A$ is jumbled by $f$.

  • A family $\mathcal B$ of bijections is jumbling if every infinite set is jumbled by some member of $\mathcal B$.

  • The "jumbling number" $\mathfrak{j}$ is the smallest cardinality of a jumbling family.

This last definition is just a placeholder -- we'll show in a bit that $\mathfrak{j}$ is equal to another well-known cardinal, namely $\mathfrak{b}$. So what's the point of defining $\mathfrak{j}$ at all? Consider the following proposition and its proof:

Proposition: $\kappa \geq \mathfrak{j}$.

Proof: Suppose $\mathcal B$ is a family of bijections $\mathbb N \rightarrow \mathbb N$ and $|\mathcal B| < \mathfrak{j}$. By definition, there is an infinite set $A \subseteq \mathbb N$ that is preserved by every member of $\mathcal B$. Fix any conditionally convergent sequence $\langle b_n \rangle$. Define a new sequence $\langle a_n \rangle$ so that $a_n = 0$ if $n \notin A$, and otherwise $a_n = b_k$, where $n$ is the $k^{th}$ element of $A$. (In other words, pad the sequence $b_n$ with extra zeroes, putting the new zeroes precisely on the complement of $A$.)

Let $f \in \mathcal B$. Since no member of $\mathcal B$ jumbles $A$, the nonzero terms of $\langle b_n \rangle$, $\langle a_n \rangle$, and $\langle f(a_n) \rangle$ are all in the same order, except perhaps for finitely many terms. Thus $$\sum_{n \in \mathbb N}b_n = \sum_{n \in \mathbb N}a_n = \sum_{n \in \mathbb N}a_{f(n)}.$$ Therefore no $f \in \mathcal B$ can rearrange $\langle a_n \rangle$ sufficiently to change the value of its sum (even though such a rearrangement is clear possible, because $\langle b_n \rangle$ is only conditionally convergent). Since $\mathcal B$ was an arbitrary family of bijections with $|\mathcal B| < \mathfrak{j}$, this finishes the proof. QED

The proof of this proposition is nothing new: it is simply Joel's "padding with zeroes" argument in a slightly more abstract setting. The thing to notice is that $\mathfrak{j}$ is the largest cardinal number for which this argument succeeds: if $\lambda \geq \mathfrak{j}$, we cannot claim that $\lambda$ bijections will leave the nonzero terms of some sequence in the same order (modulo a finite set). Indeed, I defined the number $\mathfrak{j}$ simply to be the cardinal number at which the "padding with zeroes" argument stops working.

Now, as promised, we'll show that $\mathfrak{j}$ is just a more familiar number in disguise. Recall that $\mathfrak{b}$ is the smallest cardinality of an "unbounded" family $\mathcal F$ of functions $\mathbb N \rightarrow \mathbb N$. A "bound" for $\mathcal F$ means a function $h: \mathbb N \rightarrow \mathbb N$ such that, for every $f \in \mathcal F$, $h(n) > f(n)$ for all but finitely many $n$.

Theorem: $\mathfrak{j} = \mathfrak{b}$.

Proof:

Part I: $\mathfrak{b} \leq \mathfrak{j}$. Suppose $\lambda < \mathfrak{b}$; we will show that $\lambda < \mathfrak{j}$ as well. To this end, let $\mathcal B$ be a family of bijections $\mathbb N \rightarrow \mathbb N$ with $|\mathcal B| = \lambda$. We must show that $\mathcal B$ is not a jumbling family.

To each $b \in \mathcal B$, we associate a (recursively defined) function $f_b: \mathbb N \rightarrow \mathbb N$ as follows: $$f_b(n) = \max\{b(0),\dots,b(n),b^{-1}(0),\dots,b^{-1}(n)\}+1.$$ Because $|\mathcal B| = \lambda < \mathfrak{b}$, there is some $h: \mathbb N \rightarrow \mathbb N$ such that, for every $b \in \mathcal B$, $h(n) > f_b(n)$ for all but finitely many $n$.

Let $a_0 = 0$, let $$a_{n+1} = h(a_n)+n,$$ and let $A = \{a_n : n \in \mathbb N\}$. $A$ is clearly infinite, and I claim that $A$ is preserved by every element of $\mathcal B$ (which means that $\mathcal B$ is not a jumbling family).

Fix $b \in \mathcal B$ and fix $N$ such that $h(n) > f_b(n)$ for all $n \geq N$. We will show that for all $n \geq N$ we have $b(a_n) < b(a_{n+1})$, from which it follows that $A$ is preserved by $b$. If $n \geq N$, we have $a_n \geq n$ and $$a_{n+1} = h(a_n) + n > h(a_n) > f_b(a_n).$$ From the definition of $f_b$, it is clear that $a_{n+1} > f_b(a_n)$ implies $b(a_{n+1}) > b(a_n)$. Thus $b$ does not jumble $A$.

Part II: $\mathfrak{j} \leq \mathfrak{b}$. Fix an unbounded family $\mathcal F$ of functions $\mathbb N \rightarrow \mathbb N$. We will find a jumbling family $\mathcal B$ with $|\mathcal B| = |\mathcal F|$.

We may assume that every member of $\mathcal F$ is strictly increasing and strictly positive (if not, replace each $f \in \mathcal F$ with the function $g$ defined by $g(n) = \max\{f(0),\dots,f(n)\} + n + 1$). Thus each member of $\mathcal F$ naturally partitions $\mathbb N$ into nonempty intervals, namely $[0,f(0))$, $[f(0),f(1))$, $[f(1),f(2))$, etc. Let $b_f$ be the function that flips each of these intervals upside-down. That is, (setting $f(-1) = 0$ for convenience), if $f(m-1) \leq n < f(m)$, then $b_f(n) = f(m-1) + (f(m)-1) - n$.

Clearly $b_f$ is a bijection for every $f \in \mathcal F$. Let $\mathcal B = \{b_f : f \in \mathcal F\}$. We want to show that every infinite set is jumbled by some $b_f$.

Let $A$ be an infinite subset of $\mathbb N$. Let $h$ be the unique increasing enumeration of $A$. Since $\mathcal F$ is unbounded, there is some $f \in \mathcal F$ such that, for infinitely many values of $n$, we have $f(n) > h(n)+n$. By the pigeonhole principle, if $f(n) > h(n) + n$, then there are intervals of the form $[f(m-1),f(m))$ containing more than one member of $A$; in fact, the number of members of $A$ that do not have an interval to themselves is at least $n$. Since $f(n) > h(n)+n$ infinitely often, it follows that there are infinitely many intervals of the form $[f(m-1),f(m))$ containing multiple elements of $A$. Because each of these intervals is flipped upside-down by $b_f$, we see that $b_f$ jumbles $A$.

QED

Putting this together with Paul Larson's observation, we have what seems to me a decent range for $\kappa$:

Theorem: $\mathfrak{b} \leq \kappa \leq non(M)$.

For the record, I can see no real reason to think that $\mathfrak{j} = \kappa$. In fact, I'll leave it as an exercise to show that the family $\mathcal B$ defined in Part II of my proof has the following property: for every $f \in \mathcal B$, if $\sum_{n \in \mathbb N}a_n$ converges, then $\sum_{n \in \mathbb N}a_{f(n)}$ converges also, and to the same value. In other words, we have a jumbling family that doesn't change the value of any sums!

Will Brian
  • 18.5k
  • 3
  • 79
  • 106