Existence of a sequence that has every element of $\mathbb N$ infinite number of times

Question

I was wondering if a sequence that has every element of $\mathbb N$ infinite number of times exists ($\mathbb N$ includes $0$). It feels like it should, but I just have a few doubts.

Like, assume that $(a_n)$ is such a sequence. Find the first $a_i \not = 1$ and the next $a_j, \ \ j > i, \ \ a_j = 1$. Swap $a_j$ and $a_i$. This can be done infinitely many times and the resulting sequence has $1$ at position $M \in \mathbb N$, no matter how large $M$ is. Thus $(a_n) = (1_n)$.

Also, consider powerset of $\mathbb N, \ \ 2^{\mathbb N}$. Then form any permutation of these sets, $(b_{n_{\{N\}}})$. Now simply flatten this, take first element $b_1$ and make it first element of $a$ and continue till you come to end of the first set and then the next element in $a$ is the first element of $b_2$... But again, if you start with set $\{1 | k \in \mathbb N\}$ (infinite sequence of ones), you will get the same as in the first case...

You would not be able to form a bijection between this sequence and a sequence that lists every natural number once, for if you started $(a_n)$ with listing every natural number once, you would be able to map only the first $\aleph_0$ elements of $(a_n)$ to $\mathbb N$.

But consider decimal expansion of $\pi$. Does it contain every natural number infinitely many times?

What am I not getting here?

What would the cardinality of such a sequence, if interpreted as a set, be?

score 23 · Accepted Answer · answered Mar 12 '13 at 21:16

23

$$\langle \underbrace{0}_{1\text{ term}},\underbrace{0,1}_{2\text{ terms}},\underbrace{0,1,2}_{3\text{ terms}},\underbrace{0,1,2,3}_{4\text{ terms}},\underbrace{0,1,2,3,4}_{5\text{ terms}},\dots\rangle$$

Each $n\in\Bbb N$ appears in all but the first $n$ blocks, hence infinitely often.

answered Mar 12 '13 at 21:16

Brian M. Scott

616,228

Oh dear, I was over thinking (or under thinking) again... – Valtteri Mar 12 '13 at 21:21
My powerset example is wrong, because every subset has every number just once and the first example was dubious to begin with. – Valtteri Mar 12 '13 at 21:26

score 9 · Answer 2 · answered Mar 12 '13 at 21:15

9

Let $a_n$ be the largest natural number, $k$ such that $2^k$ divides $n+1$

answered Mar 12 '13 at 21:15

Thomas Andrews

177,126

This is my favorite example, partly because of the short but complete description. It has an alternative (longer) description as: Put 0 in every second position; put 1 in every second of the positions that are still vacant; put 2 in every second of the positions that are still vacant; etc. – Andreas Blass Nov 21 '18 at 15:57

score 9 · Answer 3 · answered Mar 12 '13 at 21:20

9

Let $f\colon\Bbb{N\to N\times N}$ be a bijection, and let $a_n$ be the right coordinate of $f(n)$, then $\langle a_n\mid n\in\Bbb N\rangle$ is a sequence covering all the elements of $\Bbb N$, and each appearing infinitely many times.

answered Mar 12 '13 at 21:20

Asaf Karagila

393,674

1

Indeed, the existence of such a bijection is equivalent to this statement. – Thomas Andrews Mar 12 '13 at 21:22

Existence of a sequence that has every element of $\mathbb N$ infinite number of times

3 Answers3

Linked