Is the sum of all natural numbers countable?

Question

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.

Thanks in advance, Davide

PS: This question is about sum of cardinals.
It is not about Calculus.

Answer 1

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$.

Answer 2

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

Answer 3

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.

Answer 4

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$$

Answer 5

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|$.)

Answer 6

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.)

Answer 7

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.

Answer 8

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:

My personal policy for not explaining a downvote is when (i) another has already explained well why an answer is misleading or unhelpful, or else (ii) a poster is being obtuse and belligerent, making further discussion pointless (which is certainly not the case here). I understand that sometimes users post answers out of a noble but erroneous attempt to help or answer, and a resulting discussion ends up being enlightening for both them and surely other readers too, which is what transpired here.owever, if users fail to edit or update their answer to reflect new insight or correction, then their answer still stands to mislead readers while the enlightening discussion gets lost in the comment threads (which, especially when long, are not read nearly as much as posts themselves, which is why it is important the original post reflect the current understanding). I use downvoting as a routine way to spur users into updating their posts if they are otherwise unhelpful or misleading (downvotes are removable after edits are made), since sometimes they forget or don't feel the need to edit.

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

Answer 9

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.