# Is the sum of all natural numbers countable?

I do not even know if the question makes sense.

The point is rather simply. If I have the sum of all natural numbers,

$$\sum_{n\in \mathbb{N}}n$$

this is clearly "equal to infinity".

But since almost a century ago, we know that there are (a lot of) different "infinities".

So, is this sum equal to something countable or something bigger?

I tried to look for references, but couldn't find anything and, since I am not an expert in Logic, Set Theory or Foundations of Mathematics, I thought that it would be good to ask here.

PS: This question is about sum of cardinals.

-
It doesn't make sense. Sets are countable, numbers are not. –  Thomas Andrews Jun 23 '14 at 16:13
Watch out dadexix! You have posted a divergent series. It's impossible to get everyone on stackexchange to come to any sort of agreement about these objects. Half of your answers will be "It doesn't make sense since it diverges!" –  Joel Jun 23 '14 at 16:14
In general, it is a good idea to (1) include vital information when you write the question; (2) not accept the first answer as soon as possible. (Hurkyl's answer is very good, and I have no qualms against it being accepted, but it's often a good thing to let a question sit for more than fifteen minutes before accepting an answer.) –  Asaf Karagila Jun 23 '14 at 16:48
Also, it's not "almost a century ago", it's almost a century and a half ago. We know about different types of infinities since the 1880s (and slightly before that, if you want to be strict). Almost a century ago would put you roughly in the 1930s, when set theory has been well-developed and its modern version has established roots. –  Asaf Karagila Jun 23 '14 at 17:00
Luckily "almost" is not well-defined, and in terms of mathematical progress, I would say that 80 years is almost a century. Also, we didn't learn these things the day that Cantor died, or just a couple of years before he did. We learned these things about infinity when he was much much younger. –  Asaf Karagila Jun 23 '14 at 17:29

The $\infty$ from calculus has nothing to do with cardinality.

Now, it is possible to define a sum of cardinal numbers and use that instead of the infinite sum from calculus. If you do that, you do indeed have

$$\sum_{n \in \mathbf{N}} n = \aleph_0$$

A quick proof of this is that we know the sum is:

$$\aleph_0 \leq \sum_{n \in \mathbf{N}} n \leq \sum_{n \in \mathbf{N}} \aleph_0 = |\mathbf{N}| \cdot \aleph_0 = \aleph_0 \cdot \aleph_0 = \aleph_0$$

(the first inequality is because we know the sum is not finite, and $\aleph_0$ is the smallest infinite cardinal)

For reference, the definition of the sum

$$\sum_{i \in I} \alpha_i$$

where the $\alpha_i$ are cardinal numbers is to choose disjoint sets $S_i$ with $|S_i| = \alpha_i$, and then we define

$$\sum_{i \in I} \alpha_i = \left| \bigcup_{i \in I} S_i \right|$$

A formulaic way to choose the $S_i$ is as the Cartesian product $S_i = \{ i \} \times \alpha_i$ (where I'm assuming we've defined things so that $\alpha_i$ denotes a specific set). That is, $S_i$ is the set of ordered pairs $(i,a)$ with $a \in \alpha_i$.

-
If I remember correctly the sum on cardinals coincides, on the natural numbers, with the sum from Calculus, is it right? –  dadexix86 Jun 23 '14 at 16:12
@dadexix: For a finite sum, yes. More precisely, if I let $\widehat{n}$ denote the cardinal number corresponding to the natural number $n$, then $$S = \sum_{i=0}^{n-1} a_i \Longleftrightarrow \widehat{S} = \sum_{i \in \widehat{n}} \widehat{a}_i$$ –  Hurkyl Jun 23 '14 at 16:15
Ok thanks. Can you please provide me references for the fact that cardinal sum as above converges to $\aleph_0$? –  dadexix86 Jun 23 '14 at 16:18
@dadexix: I've added a calculation –  Hurkyl Jun 23 '14 at 16:20
A sum of cardinal numbers is not defined in terms of limits or "convergence" (you used that word above), @dadexix86 Indeed, with sums of cardinal numbers, there is no inherent ordering on the summands necessary, and so no partial sums or epsilon-deltas. –  blue Jun 24 '14 at 18:13

Since we want to talk about the sum of cardinals, we first need to make sure that we know what is an infinite sum of cardinals.

## And before that we need to make it perfectly clear. These are not natural numbers anymore. These are finite cardinals.

Suppose that $I$ is an index set, and for each $i\in I$, we have a cardinal $a_i$, then $\sum\limits_{i\in I} a_i$ is the cardinality of $\bigcup\limits_{i\in I}A_i$, where $\{A_i\mid i\in I\}$ is a set of pairwise disjoint sets, and $|A_i|=a_i$.

But why is this well-defined? Meaning, given two cardinals, $a,b$ we know that $a+b$ is well defined. If $A,A'$ have cardinality $a$ and $B,B'$ have cardinality $b$, and $A\cap B=A'\cap B'=\varnothing$, then $|A\cup B|=|A'\cup B'|$. How do we prove that? We pick some bijection from $A$ to $A'$ and from $B$ to $B'$ and we show that the union of these bijections is a bijection between the union of the sets.

Well that's fine and dandy. But what happens when we have an infinite sum? Well, if we have an infinite sum then we need to make infinitely many choices. And here we have to appeal to the axiom of choice. But let us, for a moment, assume the axiom of choice holds. In this case the same idea can be applied to the infinite case, we choose bijections as before and show that every two unions of these cardinalities will have the same size.

So in order to calculate what is $\sum\limits_{n\in\Bbb N} n$ we need to find a set which can be partitioned into infinitely many parts, each part having the cardinality of a different finite set. We can do that explicitly with $\Bbb N$ (as another answer shows), or we can use theorems to show that indeed $\Bbb N$ itself is such set. In either case, we have that $\sum\limits_{n\in\Bbb N}n=\aleph_0$.

We can also use other theorems about cardinal arithmetic to bound this sum from above and below by $\aleph_0$. For example, $$\aleph_0=\sum_{n\in\Bbb N}1\leq\sum_{n\in\Bbb N}n\leq\sum_{n\in\Bbb N}\aleph_0=\aleph_0.$$ The first equality holds because $\Bbb N$ is the union of $\aleph_0$ singletons; the second and third are obvious; and the final equality is true because in the presence of the axiom of choice repeated sums can be turn into a multiplication, so this is just $(\aleph_0)^2=\aleph_0$.

But what would happen if we decide not to accept the axiom of choice? Well, then we can't necessarily guarantee that we can choose bijections when considering infinite sums of cardinals. Could that affect the result? Yes, yes it can.

Consider if you will the case where there exists a Russell set, namely an infinite set which can be written as a countable union of pairwise disjoint pairs, but there is no function which chooses one element from each pair. Let $S$ be such set, and $\{S_n\mid n\in\Bbb N\}$ be such partition. We immediately observe that $S$ is not countable, despite being a countable union of pairs. Why? If it were countable, then we could have enumerated its elements and choose from each $S_n$ the one whose index is smaller.

Now the sum $\sum\limits_{n\in\Bbb N}2$ may depend whether or not we choose the $n$-th pair as $S_n$ or as $\{2n,2n+1\}$. In the former case we have a countable union of sets of size $2$, whose size is not countable; in the latter case we have a countable union of sets of size $2$, whose size is countable. So the infinite sum is not well-defined.

Of course, from this we can easily create an example where there are sets of size $n$ whose union is not countable. Simply inflate the $S_n$'s by adding natural numbers. The union of these inflated sets will have $S$ as a subset, so it couldn't possibly be countable (since subsets of a countable set are countable themselves); and on the other hand, well... $\Bbb N$ is the union of $\aleph_0$ finite sets of increasing size as before.

(And all that is left is that you believe me that it is consistent that a Russell set exists, and that is consistent with the failure of the axiom of choice.)

-
+1, I really enjoyed reading your answer and learnt a lot from it! (I have no knowledge of set theory, so this was a very interesting read for me) –  Shaktal Jun 23 '14 at 18:17
Shaktal, My pleasure! –  Asaf Karagila Jun 23 '14 at 18:22
What's exactly the difference between a natural number and a finite cardinal? I am sure that in my courses someone defined the firsts as the seconds. –  dadexix86 Jun 23 '14 at 18:40
@dadexix86: The context. In the context of the natural numbers there is no such thing as an infinite sum. In the context of the cardinal numbers, there is such thing. This is the same as dividing by $2$. You can't divide $1$ by $2$ in the context of the natural numbers, but you can in the context of the rational numbers. –  Asaf Karagila Jun 23 '14 at 19:13
@Sasho: For this specific case? The axiom of countable choice from families of finite sets would suffice. In general for having infinite sums of cardinals you need more and more choice. –  Asaf Karagila Jun 25 '14 at 14:48

Issues of notation and subtleties of different notions of infinity aside, your intuition is correct. We could "set-ify" this sum as follows:

$$\mathbb{N} = \{1\} \cup \{2,3\}\cup \{4,5,6\} \cup \{7,8,9,10\} \cup\cdots$$

-

You need to define precisely what is meant by that sum, or the question is simply unanswerable (it has no meaning).

In the context of cardinalities, $\sum_{i\in I} |A_i|$ is understood as the cardinality of the disjoint union of the $A_i$. In that sense, your sum is indeed countable (equals $\aleph_0$).

In the context of ordinals, the sum is understood as the ordinal corresponding to the well-ordering of the set resulting from ordering the finite ordinals (lexicographically), one after the other. This is the ordinal $\omega$.

In the sense of analysis, the sum diverges. Within the extended reals, the sum is $+\infty$. It makes no sense to equate $+\infty$ and $\omega$, and the fact that the ordinal $\omega$ coincides with the cardinal $\aleph_0$ is pretty much an accident in this case, not the indication of some deep underlying principle. All three contexts are different. (That said, if $I$ is an ordinal, and the $\alpha_i$ are all ordinals, the ordinal sum $\sum_{i\in I}\alpha_i$ has cardinality the cardinal sum $\sum_{i\in I}|\alpha_i|$.)

-

The series diverges, so we can't assign a number to it. Notice "countability" refers to sets, not numbers.

-
That is not true in general. It depends on your notion of sumability. The series the OP has posted is commonly assigned the value $-1/12$ where this is viewed as the residue of $\zeta(z)$ at $z=-1$. On the other hand, I agree that sums are often assigned real or complex numbers, and so countability does not make sense in that context. –  Joel Jun 23 '14 at 16:12
There may be contexts in which it makes sense to assign a real or complex value to a series that diverges, but in any case there isn't 1) A definitive value we can assign to that series and 2) A definitive way to assign a cardinality to that series. –  dREaM Jun 23 '14 at 16:15
@Bananarama: What do you mean by "there isn't a definitive value we can assign to that series"? -1/12 is a pretty definitive value. –  Mehrdad Jun 24 '14 at 21:28
@Mehrdad What do you mean there isn't a definitive card to choose out of a deck? The ace of spades is a pretty definitive card. But there is more than one card that can be drawn. There is more than one kind of summability method, and they can give different values. In certain contexts, zeta regularization is the method (physics), but not absolutely without context. –  blue Jun 24 '14 at 22:04
@blue: I mean, do you think you can come up with any sensible definition of summation that will assign a different value than -1/12 to this series? I'd like to see what other value you can assign to it... –  Mehrdad Jun 24 '14 at 22:13

Your first instinct is correct: your question as stated doesn't make sense. However, here is one possible interpretation which gives your question real meaning. Take a collection $\{A_n\}$ of disjoint finite sets where $A_n$ has $n$ elements. Then your sum in some sense "is" the cardinality of the union $$\bigcup_{n=1}^\infty A_n.$$ A countable union of finite sets is countable, so in that sense your sum "is" countable.

Edit: This is essentially the same as Hurkyl's answer.

-
Thank you for the answer! :) –  dadexix86 Jun 23 '14 at 16:21

WARNING: the mathematical manipulations below are wrong. I have copied Asaf Karagila's explanation as to why. I believe this post has now an educational value not as an answer but as something one should not do -and why.

ORIGINAL POST
Since learning is a good thing, can somebody please point to me all (or at least some) of the ...cardinal sins I am committing by writing

$$\sum_{n\in \mathbb{N}}n = \lim_{k\rightarrow \infty}\sum_{i=1}^ki = \lim_{k\rightarrow \infty} \frac 12 k(k+1) = \frac 12 \lim_{k\rightarrow \infty} (k^2 + k)$$

$$=\frac 12\cdot [(\aleph_0)^2+\aleph_0] = \frac 12\cdot [\aleph_0+\aleph_0] = \aleph_0$$

... to which Asaf Karagila commented

It is a horrible horrible thing to use limits to talk about infinite sums of cardinals. Because then you create this illusion that cardinal operations are continuous. But lo and behold, $\lim2^n=\aleph_0$ where as $2^{\lim n}=2^{\aleph_0}$. I have written a couple of answers on this matter before...Finding a limit using arithmetic over cardinals

Later User @blue downvoted the post explaining his approach to the matter as follows:

As I see it, that's a serious and respected approach, and a thoughtful use of the downvoting tool.

-
It is a horrible horrible thing to use limits to talk about infinite sums of cardinals. Because then you create this illusion that cardinal operations are continuous. But lo and behold, $\lim 2^n=\aleph_0$ where as $2^{\lim n}=2^{\aleph_0}$. I have written a couple of answers on this matter before. –  Asaf Karagila Jun 23 '14 at 20:12
@AsafKaragila Thanks, I do appreciate. I will look up these past answers of yours. –  Alecos Papadopoulos Jun 23 '14 at 20:20
math.stackexchange.com/q/532803/622 Might be the suitable discussion here. –  Asaf Karagila Jun 23 '14 at 20:22
@AsafKaragila I am going. –  Alecos Papadopoulos Jun 23 '14 at 20:22
(And possibly the links there too!) –  Asaf Karagila Jun 23 '14 at 20:24

This answer may be mathematically bush league, but here it goes . . .

In finance, I can tell you the price of a security that gives off an infinite number of dividends. I'd do it this way . . .

P = Div1/Discount Rate

Where Div1 is the dividend next period (usually a year) divided by a discount rate. The British once issued these securities -- they were called consoles. The price represented the sum of all future dividends, which were usually natural natural numbers, but could be anything that was positive.

Prices were widely quoted, so if you had a price and Div1, which is/was usually available, you could figure out the discount rate. So, the quoted price represented the sum of all dividends from next period until eternity. If if all dividend are natural numbers you can easily find their sum by applying the discount rate you found to new issues coming to market. So, the short answer is, yes, they are absolutely summable. From the other fascinating answers that are way out of my league, they are likely countable individually too.

-

The mathematical definition of countable is that there exists a 1 to 1 relationship between all items in the set with the natural number system. Since the example of adding the numbers in the natural number set will yield a natural number, then the summation operation is valid for natural numbers. So since the set of one number (the summation) maps to a number in the natural number set, it is considered "countably infinite." (proofs left as an exercise to the reader)

For those still scratching their heads, an example of a set that is not countably infinite is the real number system that contains an infinite number of fractions between any 2 whole numbers.

-
This is not really a proof. How do you justify then that $\prod n$ is not countable, where the product is over all positive integers? –  Andres Caicedo Jun 24 '14 at 20:42

## protected by Asaf KaragilaJun 25 '14 at 16:54

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.