2
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ "big. You just won't believe how vastly, hugely, mind-bogglingly big it is." $\endgroup$ – Gerry Myerson Mar 11 '14 at 5:55
  • $\begingroup$ @GerryMyerson I know it's big, now can you look at my attempt to answer? Thanks $\endgroup$ – grayQuant Mar 12 '14 at 19:10
  • $\begingroup$ 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...) $\endgroup$ – Steven Stadnicki Mar 16 '14 at 17:47
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How do I find if this injection exists? $\endgroup$ – grayQuant Mar 12 '14 at 15:00
  • 1
    $\begingroup$ Are you familiar with continued fractions, grayQuant? $\endgroup$ – Gerry Myerson Mar 12 '14 at 22:12
  • $\begingroup$ @ 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. $\endgroup$ – Tom Collinge Mar 13 '14 at 14:03
  • $\begingroup$ @Tom, the cardinality of the reals does equal the cardinality of ${\bf N}^{\bf N}$. $\endgroup$ – Gerry Myerson Mar 13 '14 at 23:57
  • $\begingroup$ @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| $\endgroup$ – Tom Collinge Mar 14 '14 at 7:59
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is it ok to not show to injections but arrive at the conclusion of a bijection by showing one injection and on e surjection? $\endgroup$ – grayQuant Mar 12 '14 at 19:09
  • 1
    $\begingroup$ 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? $\endgroup$ – Christoph Mar 12 '14 at 19:13
  • 1
    $\begingroup$ How? What exactly is $F(1)$ or $F(42)$? $\endgroup$ – Christoph Mar 12 '14 at 20:23
  • 1
    $\begingroup$ I have fixed a typo/error in your (otherwise correct) chain of inequalities. $\endgroup$ – Hurkyl Mar 14 '14 at 20:26
  • 1
    $\begingroup$ @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/… $\endgroup$ – Slade Mar 14 '14 at 20:54
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.