# What is the cardinality of the set of all infinite sequences?

The set is defined as {$(n_1, n_2,...n_k ..) | n_k \in \mathbb{N}$}. What are some approaches to finding and proving the cardinality of this set?

• "big. You just won't believe how vastly, hugely, mind-bogglingly big it is." – Gerry Myerson Mar 11 '14 at 5:55
• @GerryMyerson I know it's big, now can you look at my attempt to answer? Thanks – grayQuant Mar 12 '14 at 19:10
• To clarify: you also want $k\in\mathbb{N}$ here, I presume? (There's not much that keeps someone from talking about 'sequences' indexed by arbitrary ordinals, and since we are talking about infinite cardinalities then it's important to be sure...) – Steven Stadnicki Mar 16 '14 at 17:47

You have $|\mathbb{N}|$ options for as many slots, so $|\mathbb{N}|^{|\mathbb{N}|}$ different sequences.

There are several ways to prove that this is $|\mathbb{R}|$. I'll give one, but try to come up with another (hint, power sets).

Continued Fractions. Given a sequence $a_i$ we can map it to a continued fraction by $f(\{a_i\})=[0;a_1,a_2,\ldots]$. When the sequences are taken over the naturals, this is a bijection with the $(\mathbb{R}-\mathbb{Q})\cap[0,1]$. Since there are only countably many rationals, the irrationals in $[0,1]$ and $[0,1]$ itself have the same cardinality by the properties of cardinal arithmetic. It's well-known that $|[0,1]|=|\mathbb{R}|$, and several proofs are given here.

• How do I find if this injection exists? – grayQuant Mar 12 '14 at 15:00
• Are you familiar with continued fractions, grayQuant? – Gerry Myerson Mar 12 '14 at 22:12
• @ Stella Biderman I don't think we can both be right unless |R| = |N| ^ |N|. I'd be pleased if you would look at my answer and comment. – Tom Collinge Mar 13 '14 at 14:03
• @Tom, the cardinality of the reals does equal the cardinality of ${\bf N}^{\bf N}$. – Gerry Myerson Mar 13 '14 at 23:57
• @Gerry, thanks for the clarification. I subsequently found references that $|\mathbb{N}|^{|\mathbb{N}|}$ is uncountable but I'd appreciate a reference to a proof that $|\mathbb{N}|^{|\mathbb{N}|}$ = |R| – Tom Collinge Mar 14 '14 at 7:59

We call the set of all infinite sequences of natural numbers $E$. Notice that for each infinite sequence in $E$, each term ($n_k$) in the sequence can be mapped to $k\in\mathbb{N}$, hence the cardinality of each infinite sequence is $\aleph_0$. Because $E$ is an infinite set of infinite sequences, the cardinality must be bigger than $\aleph_0$. In fact, $\#E$ can be expressed as $$\#E = \aleph_0^{\aleph_0}.$$ Because $\aleph_0 > 2$, we follow the law of exponents and get

$2^{\aleph_0} \leq \aleph_0^{\aleph_0} \leq \left(2^{\aleph_0}\right)^{\aleph_0} = 2^{\aleph_0 *\aleph_0} = 2^{\aleph_0}.$

Therefore the cardinality of E is: $$\#E = \aleph_0^{\aleph_0} = 2^{\aleph_0}.$$ QED

Note: The above assertion that the exponents $\aleph_0 \times \aleph_0=\aleph_0$ is to recognize the Cartesian product of two countably infinite sets are still countably infinite. The sketch of the proof is as follows: Suppose $A$ and $B$ are both countably infinite, so we can write $A$ and $B$ in list form as $$A = \{a_1, a_2, a_3, \dots \},$$ $$B = \{b_1, b_2, b_3, \dots \},$$ and form a rectangular table with elements $(a_1, b_1), (a_1, b_2), (a_1, b_3),\dots$ in the table. We can process each element in the table diagonally and see each element of $A\times B$ will be listed, therefore $A\times B$ can be expressed in list form, so $A\times B$ is also countably infinite. In other words, we have proved that $$\aleph_0 \times \aleph_0=\aleph_0.$$

• Is it ok to not show to injections but arrive at the conclusion of a bijection by showing one injection and on e surjection? – grayQuant Mar 12 '14 at 19:09
• The set of positive integer sequences is at least as big as $\mathbb R$, since we can represent real numbers as sequences of digits. Thus $|E|=|\mathbb N|$ can't be true. Your function $F$ is not well defined, what does $F(k)=\{n_k\}$ mean? – Christoph Mar 12 '14 at 19:13
• How? What exactly is $F(1)$ or $F(42)$? – Christoph Mar 12 '14 at 20:23
• I have fixed a typo/error in your (otherwise correct) chain of inequalities. – Hurkyl Mar 14 '14 at 20:26
• @grayQuant In response to your first question, here is the theorem that allows one to demonstrate that $\# A \leq \# B \leq \# A \implies \# A = \# B$: en.wikipedia.org/wiki/… – Slade Mar 14 '14 at 20:54

An infinite sequence in N can be veiwed (is defined as) a function from N -> N (with domain all of N, i.e. a: N -> N and notate a1 = a(1), a2 = a(2), etc.).

How many different functions are there ?

Each function is a subset of N x N, i.e. an element of P(N x N), so S the set of all functions (sequences) is a subset of P(N x N) and so |S| <= |P(N x N)|.

As there is a bijection between N and N x N then there is a bijection between P(N) and P(N x N) so that |S| <= |P(N x N)| = |P(N)|.

Permutations of N are a subset of possible functions denoted as sym(N), so that |sym(N)| <= |S|. How many permutations are there ? There is a proof (below) that shows an injection from P(N) into sym(N) so that |P(N)| <= |sym(N)| <= |S| <= |P(N)|

So the answer is that |S| = |P(N)|.

Proof P(N) injects into sym(N).

Split N into two infinite subsets N1 and N2 (say even and odd). There is a bijection between them , say f: N1 -> N2.

We can define a mapping g: P(N1) -> sym(N) as follows:

For A ∈ P(N1), p ∈ sym(X) is the permutation p: N -> N as n exchanges with f(n) if n ∈ A, else n is unchanged.

Then g is an injection from P(N1) into sym(N), so that | P(N1)| ≤ |sym(X)|.

But then |N1| = |N|, so that | P(N1)| = | P(N)| and thus |P(N)| ≤ |sym(X)|.

• And since |P(N)| = |R|, the final answer is that the numbr of sequences = |R| – Tom Collinge Mar 13 '14 at 13:38
• This was helpful, I ended up taking a different approach, take a look? – grayQuant Mar 14 '14 at 14:51
• I'm glad it helped. Where am I looking for the different approach ? – Tom Collinge Mar 14 '14 at 18:56
• I edited my answer... – grayQuant Mar 14 '14 at 20:16
• @grayQuant. Thanks: it's probably OK, but I'm not very comfortable yet myself with cardinal arithmetic. – Tom Collinge Mar 14 '14 at 20:59